기술 요약: 순위 집계에서의 비례적 대표성

문제 정의

본 논문은 가중치가 부여된 입력 순위들의 프로필을 하나의 출력 순위로 결합하는 것을 목표로 하는 순위 집계(rank aggregation) 문제를 다룬다. 이 설정에서 프로필 $R$은 후보자 집합 $C$와 모든 가능한 순위 $\succ$를 해당 가중치 $R(\succ) \in [0, 1]$에 매핑하는 함수로 구성되며, 모든 가중치의 합은 1이다. 이 가중치는 서로 다른 기준(예: 호텔 예약 시 가격 대비 평점)의 중요도나 특정 순위를 지지하는 투표자의 비율을 나타낸다.

식별된 핵심 과제는 Kemeny rule, Borda count, Condorcet형 규칙과 같은 고전적인 사회 후생 함수(Social Welfare Functions, SWFs)가 본질적으로 **다수결 중심적(majoritarian)**이라는 점이다. 이러한 규칙들은 가장 높은 가중치를 가진 입력 순위와의 거리를 최소화하는 출력 순위를 선택하는 경향이 있어, 소수의 선호도를 무시하게 된다. 예를 들어, 두 개의 역순위가 각각 51%와 49%의 가중치를 가질 때, 표준 SWF들은 종종 단순히 51%의 순위를 반환하며, 이는 49% 그룹을 대변하지 못한다. 본 논문은 모든 입력 순위가 그 가중치에 비례하여 출력에 영향을 미칠 수 있도록 보장하는 **비례적 대표성(proportional representation)**을 갖춘 SWF를 설계하고자 한다.

방법론 및 프레임워크

저자들은 입력 순위 $\succ$에 대한 출력 순위 $\triangleright$의 **효용(utility)**을 두 순위 사이의 쌍별 일치(pairwise agreements) 수로 정의함으로써 비례성을 공식화한다:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ and } x \triangleright y\}|$$
$m$명의 후보자에 대해 총 $\binom{m}{2}$개의 쌍별 비교가 존재하므로, 가중치 $\alpha$를 가진 입력 순위는 이상적으로 적어도 $\lfloor \alpha \binom{m}{2} \rfloor$의 효용을 얻어야 한다.

본 논문은 **승인 기반 위원회 투표(approval-based committee voting)**와 **참여 예산제(participatory budgeting)**에서 영감을 얻은 비례성 공리 계층을 도입한다:

1. 만장일치 정당한 대표성 (uJR): 가장 약한 조건으로, 가중치가 $1/\binom{m}{2}$ 이상인 모든 입력 순위가 적어도 하나의 쌍별 일치를 얻어야 함을 요구한다.
2. 만장일치 비례 정당한 대표성 (uPJR): 핵심 공리로, 가중치 $\alpha$를 가진 입력 순위가 적어도 $\lfloor \alpha \binom{m}{2} \rfloor$의 효용을 얻어야 함을 요구한다.
3. 강한 비례 정당한 대표성 (sPJR): 보장 범위를 그룹으로 확장한 강화된 조건이다. 만약 하위 프로필 $S$의 총 가중치가 $\alpha$라면, 출력은 $S$에 속한 순위들의 합집합으로부터 적어도 $\lfloor \alpha \binom{m}{2} \rfloor$개의 쌍별 일치를 얻어야 한다.

이러한 공리들을 달성하기 위해, 저자들은 참여 예산제의 가격 책정 가능성(priceability) 개념을 응용한다. 이들은 출력 순위의 구성을 입력 순위들의 예산을 사용하여 후보자(또는 후보자 쌍)를 "구매"하는 순차적 구매 과정으로 모델링한다.

주요 기여 및 결과

1. 기존 방법의 한별점

본 논문은 먼저 Squared Kemeny rule(Lederer et al. [2024]가 비례적 순위를 위해 제안함)을 분석한다. 저자들은 $m \ge 5$인 경우, Squared Kemeny rule이 가장 약한 공리인 uJR조차 만족하지 못함을 증명한다. 구체적으로, 상당한 가중치를 가진 입력 순위가 Squared Kemeny 출력으로부터 효용을 전혀 얻지 못하는 프로필을 구성하여 새로운 메커니즘의 필요성을 입증한다.

2. 비례적 순차 보다 규칙 (Proportional Sequential Borda Rule, PSB)

uPJR을 만족시키기 위해 저자들은 **비례적 순차 보다 규칙 (PSB)**을 제안한다.

• 메커니즘: PSB는 순차적으로 작동한다. 각 라운드에서 현재 예산을 기준으로 가중 보다 점수(weighted Borda score)를 최대화하는 후보자를 선택한다. 그 후, 선택된 후보자의 순위 기여도에 비례하여 입력 순위들의 예산을 업데이트함으로써, 해당 후보자의 배치를 위해 "비용을 지불"한다.
• 이론적 보장: 저자들은 rank-priceability라는 구조화된 공리를 도입하며, 이는 참여 예산제의 priceability와 유사하다. 이들은 rank-priceability가 uPJR을 함을 증명한다.
• 결과: 정리 4.5는 PSB가 rank-priceability를 만족하며, 결과적으로 uPJR을 만족함을 확립한다.
• 정량적 보장: 공리적 만족을 넘어, 정리 4.6은 PSB가 모든 하위 프로필 $S$에 대해 최소 $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$의 평균 효용을 보장함을 증명한다. 이는 그룹의 가중치에 대한 선형 하한선을 제공한다.

3. 흐름 조정 보다 규칙 (Flow-adjusting Borda Rule, FB)

저자들은 PSB의 지불 방식이 협력적으로 행동하는 순위 그룹을 충분히 보호하지 못하기 때문에 sPJR을 만족하지 못한다는 점을 지적한다. 이를 해결하기 위해, 단순한 순위가 아닌 특정 후보자 쌍에 대해 비용을 지불하는 정교한 공리인 pair-priceability를 도입하고 **흐름 조정 보다 규칙 (FB)**을 제안한다.

• 메커니즘: FB는 PSB의 개선된 형태이다. PSB와 마찬가지로 순차적으로 보다 승자를 선택하지만, 단순한 비례적 지불 대신, 구축된 네트워크에서 **최대 유량 문제(maximum flow problem)**를 해결하여 지불액을 결정한다. 이 네트워크는 예산 제약과 쌍별 제약을 준수하면서 비용 대비 효용 비율을 최소화하도록 보장한다.
• 결과: 정리 5.5는 FB가 pair-priceability를 만족하며, 이는 sPJR(정리 5.3)을 함을 증명한다.
• 정량적 보장: 정리 5.6은 FB가 PSB와 동일한 선형 평균 효용 보장($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$)을 제공하여, 개인과 그룹 모두에 대한 강력한 공정성을 보장함을 보여준다.

4. 추가 변형 모델

부록에서 저자들은 참여 예산제의 MES(Method of Equal Shares)에서 영감을 받은 **Ranked Method of Equal Shares (RMES)**를 논의한다. 이들은 RMES가 rank-priceability를 만족하며(따라서 uPJR 만족), 초기 보다 점수에만 기초하여 상위 $\lfloor m/4 \rfloor$명의 후보자를 선택하는 약간 다른 공리적 프로필을 제공함을 보여준다.

의의 및 주장

본 논문은 순위 집계를 위한 최초의 진정한 비례적 사회 후복 함수를 제시한다고 주장한다. 주요 의의는 다음과 같다:

• 분야 간 가교 역할: 승인 기반 위원회 투표와 참여 예산제(특히 PJR 및 priceability)의 심도 있는 결과들을 순위 집계 영역으로 성공적으로 전이시켰다.
• 미해결 문제 해결: 이전의 시도들(Squared Kemeny 등)이 달성하지 못한 uPJR 및 sPJR을 만족하는 SWF 설계 문제를 해결하였다.
• 공리적 및 정량적 강점: 제안된 규칙들(PSB 및 FB)은 강력한 공리적 공정성 조건을 만족할 뿐만 아니라, 어떤 투표자 그룹에 대해서도 평균 효용에 대한 견고한 정량적 보장을 제공하여 소수의 선호도가 체계적으로 무시되지 않도록 보장한다.

저자들은 본 연구가 효용 지표로서 쌍별 일치(pairwise agreement)에 초점을 맞추고 있으나, 이는 문헌의 표준적인 접근 방식임을 언급한다. 또한 향-후 연구로서 더 강력한 공정성 개념(EJR 또는 코어 안정성 등)과 다양한 순위 위치의 가치를 고려하는 더 일반적인 효용 함수를 탐구할 수 있음을 시사한다.