$p$-orderings: From Slater to Kemeny-Young to Ranked Pairs

기술 요약: p-ORDERINGS: SLATER에서 KEMENY-YOUNG을 거쳐 RANKED PAIRS까지

문제 정의
선호 투표(preferential elections)에서 투표 용지는 후보자들 사이의 쌍체적 다수 우위(pairwise majority margins)를 유도한다. 많은 사회적 후생 규칙(social welfare rules)이 전체 프로필보다는 이러한 가중치가 부여된 쌍체적 정보를 활용하지만, 서로 다른 순위 규칙들을 연결하는 통일된 프레임워크는 부족한 실정이었다. 구체적으로, 본 논문은 세 가지 저명한 마진 기반 규칙인 슬레이터 순위(Slater orderings; 쌍체적 불일치의 수를 최소화), 케메니-영 규칙(Kemeny-Young rule; 불일치 크기의 합을 최소화), 그리고 랭크드 페어즈(Ranked Pairs; 큰 마진을 사전식으로 우선순위화) 사이의 관계를 다룬다. 핵심 문제는 이 규칙들이 마진-오브-빅토리(margin-of-victory, m.o.v.) 행렬에 기반한 특정 최적화 원리에 의해 도출된 하나의 정형적인(canonical) 순위 규칙 가족의 구성원으로 간데 볼 수 있는지 여부이다.

방법론
저자들은 주어진 순위와 불일치하는 쌍체적 다수 마진의 $p$-노름(p-norm)을 최소화함으로써 정의되는, p-ordering이라 명명된 순위 규칙 가족을 도입한다.

1. m.o.v. 행렬에 대한 p-노름의 정의: 주어진 후보자 순위에 대해, 저자들은 m.o.v. 행렬의 상삼각 부분(upper-triangular part) 중 음수인 항목들을 추출한다. 이들은 순위 $\pi$의 $p$-노름을 다음과 같이 정의한다:
   $$\|\pi\|_p = \left( \sum_{i<j, m_{ij}<0} |m_{ij}|^p \right)^{1/p}$$
   p-ordering은 이 양을 최소화하는 후보자들의 순열이다.

2. 정형적 정당성 (정리 1): 저자들은 함수 $f(x) = |x|^p$의 선택이 임의적인 것이 아니라고 주장한다. 세 가지 자연스러운 가정—척도 불변성(scale invariance), 마진 크기에 따른 의존성, 그리고 마진 크기에 대한 단조성—하에서, 저자들은 이 구조와 호환되는 유일한 연속 점수 함수가 $c|x|^p$ 형태임을 증여한다. 이는 p-가족이 마진 기반 구축물들 사이에서 정형적임을 입증한다.

3. Q-sum을 통한 최적화: 분석을 용이하게 하기 위해, 저자들은 부호가 있는 크기들의 합인 "Q-sum"(따름정리 2) $\sum \mu_{ij} |m_{ij}|^p$을 정의한다. 이 합을 최대화하는 것은 음수 항목들의 $p$-노름을 최소화하는 것과 동등하다.

주요 결과
본 논문은 $p > 0$의 스펙트럼에 따른 p-ordering의 거동을 확립한다:

• $p \to 0^+$로의 극한 (명제 1): $p$-노름을 최소화하는 것은 쌍체적 불일치의 개수를 최소화하는 것과 동등해진다. 따라서 p-ordering은 **슬레이터 순위(Slater ordering)**로 수렴한다.
• $p = 1$인 경우 (명제 2): 1-노름 순위는 절대적 불일치 마진의 합을 최소화하는 케메니-영(Kemeny-Young) 규칙과 수학적으로 동등하다.
• $p \to \infty$로의 극한 (정리 2): 모든 차이가 있고 0이 아닌 쌍체적 마진을 가진 선거에 대하여, $p \geq p^*$인 모든 $p$에 대해 p-ordering이 정확히 랭크드 페어즈(Ranked Pairs) 순위와 일치하는 임계값 $p^*$가 존재한다.
  • 메커니즘: 이 증명은 "누적 지배 성질(Cumulative Dominance Property)"(보조정리 3)에 의존한다. $p$가 증가함에 따라, 가장 큰 마진의 항이 모든 작은 항들의 합을 지배하게 된다. 결과적으로, 최적화 절차는 사전식(lexicographic)이 된다: 즉, 가장 큰 마진을 먼저 만족시키는 것을 우선시한 다음, 그다음으로 큰 마진을 처리하며, 이는 랭크드 페어즈 알고리즘을 정확히 모방한다.
• 안정화: p-ordering의 집합은 양의 $p$축 상의 유한한 구간들에 대해 일정하다 (명제 9). 충분히 큰 $p$에 대해서, 해는 고유한 랭크드 페어즈 순위로 안정화된다 (차이가 있는 마진을 가정할 경우).

p-Ordering의 속성
본 논문은 p-ordering 가족의 공리적 속성을 분석한다:

• 스미스-일관성(Smith-consistency): 모든 $p > 0$에 대하여, p-ordering은 스미스 집합(Smith set) 외부의 후보자들보다 집합 내부의 후보자들을 상위에 배치한다 (명제 5).
• 콘도르셋 호환성(Condorcet Compatibility): 콘도르셋 승자가 존재하면 그가 1위가 되며, 콘도르셋 패자가 존재하면 그가 꼴찌가 된다.
• 단조성(Monotonicity): p-ordering이 유일하다면, 이는 단조성 속성을 만족한다 (명제 7).
• 최하위 탈락 독립성(Last Place Loser Independence): 역순 투표(reversed-ballot election)에서 마지막 순위인 후보자를 제거하는 것은 원래 선거의 승자를 변경하지 않는다 (명제 6).
• 클론 불변성(Clone Invariance): 이 가족은 일반적으로 클론 불변적이지 않은데, 이는 케메니-영 규칙($p=1$)이 이 기준을 충족하지 못하기 때문이다 (명제 3).

의의
본 논문은 슬레이터, 케메니-영, 랭크드 페어즈라는 세 가지 별개의 투표 규칙을 쌍체적 다수 마진에 기반한 단일 매개변수 가족으로 통합한다고 주장한다. 랭크드 페어즈가 이 정형적 가족의 최종적인 큰-$p$ 구성원으로서 나타남을 입증함으로써, 본 연구는 사회적 선택 이론의 계산 기반, 합계 기반, 그리고 사전식 접근법 사이의 이론적 가교를 제공한다. 저자들은 랭크드 페어즈가 고립된 휴리스틱이 아니라, 마진 크기에 의해 구동되는 연속적인 최적화 과정의 자연스러운 극한임을 강조한다. 결과는 tie-breaking(동점 처리)의 복잡성을 피하기 위해 차이가 있고 0이 아닌 마진을 가정하에 증명되었으며, 충분히 큰 $p$에 대한 랭크드 페어즈로의 수렴은 성립한다.