Instant Runoff Voting and the Reinforcement Paradox

논문 제목: 즉각적 결선투표 (IRV) 와 강화 역설 (Reinforcement Paradox)
저자: David McCune, Jennifer Wilson

이 논문은 즉각적 결선투표 (Instant Runoff Voting, IRV, 일명 순위 선택 투표) 가 가지는 고전적인 역설들 중 상대적으로 덜 연구된 **'강화 역설 (Reinforcement Paradox)'**의 취약성을 분석한 연구입니다. 강화 역설은 두 개의 서로 다른 선거에서 후보 X 가 IRV 에 의해 승리했음에도, 두 선거의 투표지를 합친 전체 선거에서는 X 가 패배하는 현상을 말합니다.

아래는 이 논문의 문제 제기, 방법론, 주요 기여, 결과 및 의의에 대한 상세한 기술적 요약입니다.

---

1. 문제 제기 (Problem Statement)

• 강화 역설의 정의: 투표 방법 $f$에 대해, 두 개의 유권자 집합 $B_1$과 $B_2$가 있을 때, $f(B_1) = f(B_2) = X$ (X 가 승리) 인데도 불구하고, 합집합 $B_1 \cup B_2$에 대해 $f(B_1 \cup B_2) \neq X$가 되는 경우를 말합니다. 이는 통계학의 심슨의 역설 (Simpson's Paradox) 과 유사한 사회적 선택 이론의 역설입니다.
• 실무적 중요성: IRV 는 각 선거구 (precinct) 가 단순히 1 위 득표 수만 보고하는 것이 아니라, 모든 순위별 투표지 수를 중앙 집계소에 전송하여 전체적인 순위를 매겨야 합니다. 만약 강화 역설이 발생한다면, 지역별 승리를 합산했을 때 전체 승자가 달라질 수 있어 행정적 복잡성과 정당성 논란을 초래합니다.
• 기존 연구의 한계: 기존 연구 (Plassmann & Tideman, Courtin et al.) 는 주로 두 개의 독립적인 가상의 선거를 생성하여 합쳤을 때 역설이 발생하는 빈도를 측정했습니다. 반면, 본 논문은 단 하나의 실제 (또는 가상의) 선거 데이터에서 유권자 집합을 어떻게 분할하든 역설이 발생할 수 있는지를 분석하는 새로운 접근법을 취합니다.

2. 방법론 (Methodology)

본 논문은 3 후보 선거를 중심으로 다음과 같은 방법론을 적용했습니다.

A. 필요충분조건 도출 (Necessary and Sufficient Conditions)

• 3 후보 (A, B, C) IRV 선거에서, 패배한 후보 (1 위 득표자가 아닌 '준우승자' 또는 1 위 득표자가 가장 적은 '다수결 패배자') 가 두 개의 하위 선거 ($B_1, B_2$) 에서 모두 승리할 수 있는 대수적 필요충분조건을 수학적으로 유도했습니다.
• Proposition 1 (완전 투표지): 모든 유권자가 후보를 완전히 순위 매긴 경우의 조건.
• Proposition 2 (부분 투표지): 일부 유권자가 순위 매김을 생략한 경우 (실제 선거 데이터에 더 부합) 의 조건.
• 이 조건들은 특정 후보가 하위 선거에서 승리하기 위해 필요한 득표 비율과 순위 배분 구조를 명확히 합니다.

B. 시뮬레이션 및 모델링 (Monte Carlo Simulations)

• 이론적 모델: 다양한 유권자 행동 모델을 사용하여 수백만 개의 가상의 선거를 생성하고 역설 발생 빈도를 추정했습니다.
  • Dirichlet 분포 (IAC, IC 모델): 무작위 문화 (Impartial Culture) 및 무관한 무작위 문화 (Impartial Anonymous Culture) 모델.
  • 1 차원 공간 모델 (1D Spatial): 유권자와 후보를 직선 위에 배치하여 거리를 기반으로 선호도를 결정하는 모델.
  • 양극화 모델 (Bimodal): 정치적 양극화를 반영하기 위해 두 개의 정상 분포를 결합한 모델.
• 실증 데이터 분석: 미국 (FairVote 데이터, APA 선거), 스코틀랜드 지방선거 등 416 개의 실제 IRV 선거 데이터를 수집하여 분석했습니다.
  • 3 후보 이상인 선거는 IRV 알고리즘을 적용하여 3 후보로 축소 (Reduce) 한 후 분석했습니다.
  • 부트스트래핑 (Bootstrapping): 실제 선거 데이터에서 표본을 재추출하여 역설의 민감도 (Robustness) 를 분석했습니다.

C. 지리적 분할 분석

• 실제 선거 데이터 중 유권자의 지역 (Precinct, District) 정보가 있는 경우, 무작위 분할이 아닌 지리적 경계에 따른 분할이 역설을 일으키는지 확인하기 위해 이진 정수 선형 계획법 (Binary Integer Linear Programming, ILP) 을 활용하여 최적의 분할을 탐색했습니다.

3. 주요 기여 (Key Contributions)

1. 수학적 조건 제시: 3 후보 IRV 선거에서 강화 역설이 발생할 수 있는 필요충분조건을 최초로 명확히 제시했습니다. 이는 특정 선거가 역설에 취약한지 여부를 분할을 직접 생성하지 않고도 판단할 수 있게 합니다.
2. 접근법의 전환: 기존 연구가 "두 선거를 합쳐서 역설이 발생하는가"를 보는 것과 달리, **"하나의 선거를 분할하여 역설이 발생하는가"**를 분석함으로써, 실제 선거 데이터의 취약성을 더 정확하게 평가할 수 있는 프레임워크를 제공했습니다.
3. 부분 투표지 (Partial Ballots) 분석: 실제 IRV 선거에서 흔히 발생하는 순위 생략 (Truncation) 이 포함된 경우의 역설 조건을 분석했습니다.
4. 대규모 실증 데이터 분석: 이론적 모델뿐만 아니라 미국과 스코틀랜드의 실제 선거 데이터를 기반으로 한 최초의 대규모 실증 분석을 수행했습니다.

4. 주요 결과 (Results)

A. 발생 빈도 (Frequency)

• 이론적 모델: 무작위 문화 (IAC) 모델이나 경쟁이 치열한 모델 (높은 $\alpha$ 값) 에서 강화 역설 발생 확률은 매우 높게 나타났습니다.
  • IAC 모델 (완전 투표지): 역설 발생 확률 약 24.9% (다수결 후보가 없는 경우 조건부 확률 56.8%).
  • 공간 모델 (1D Spatial): 약 16.6% (조건부 40.1%).
• 실증 데이터: 416 개의 실제 선거 (3 후보로 축소된 경우 포함) 분석 결과, 약 **24.8%**의 선거에서 강화 역설이 발생할 수 있는 분할이 존재하는 것으로 나타났습니다.
  • 다수결 후보가 없는 선거로 한정할 경우 이 비율은 **37.6%**까지 상승합니다.
  • 이는 기존 연구들이 보고했던 극히 낮은 확률 (0.02% 등) 과는 대조적으로, IRV 가 강화 역설에 매우 취약함을 보여줍니다.

B. 역설의 유형

• 준우승자 역설 (Runner-up Paradox): 2 위 후보가 하위 선거에서 모두 승리하는 경우.
• 다수결 패배자 역설 (Plurality Loser Paradox): 1 위 득표자가 가장 적은 후보가 하위 선거에서 모두 승리하는 경우.
• 실제 데이터 특징: 실제 선거에서는 다수결 패배자 역설이 발생할 경우, 거의 항상 준우승자 역설도 동시에 발생하는 경향이 있었습니다 (준우승자가 다수결 패배자보다 훨씬 강력한 후보인 경우가 많기 때문).

C. 지리적 분할의 의미

• 무작위 분할을 허용할 때 역설 발생 빈도는 높았으나, 지리적 경계 (Precinct/District) 를 고려한 분할로 제한하면 역설 발생 빈도는 크게 감소했습니다 (약 3.0%).
• 이는 역설이 이론적으로는 흔하지만, "북부 vs 남부"와 같이 의미 있는 자연스러운 분할로 나타나는 경우는 상대적으로 드물 수 있음을 시사합니다.
• 사례: 2022 년 알래스카 특별 하원의원 선거 (Peltola vs. Palin vs. Begich) 에서, Begich(다수결 패배자) 가 특정 지리적 분할 (해외 투표지 + 특정 지역) 에서 두 하위 선거 모두 승리하는 역설이 발견되었습니다.

D. 부트스트래핑 결과

• 실제 역설을 보이는 선거의 경우, 유권자 표본을 재추출했을 때 역설이 유지될 확률이 매우 높았습니다 (대부분 90% 이상). 이는 역설이 데이터의 작은 변동에 민감하지 않고 구조적으로 존재함을 의미합니다.

5. 의의 및 결론 (Significance and Conclusion)

• IRV 의 취약성 재확인: IRV 는 일관성 (Consistency) 을 만족하지 않으며, 3 후보 선거에서 강화 역설에 매우 취약하다는 것을 이론적, 실증적으로 입증했습니다.
• 행정적 함의: IRV 를 사용할 때, 단순히 지역별 승자를 합산하는 방식으로는 전체 승자를 결정할 수 없으며, 모든 투표지를 중앙에서 집계해야 한다는 필요성이 더욱 강조됩니다.
• 이론과 현실의 괴리: 기존 이론적 연구들은 역설 발생을 드물게 예측했으나, 본 연구의 새로운 접근법 (단일 선거 분할 분석) 은 역설이 훨씬 더 빈번하게 발생할 수 있음을 보여주었습니다.
• 향후 연구 방향:
  • 지리적, 인구통계학적 변수에 따른 '자연스러운 분할'에서의 역설 빈도 추가 연구 필요.
  • Condorcet 일관성 투표 방법 (Condorcet consistent methods) 에 대한 강화 역설 분석 확대.
  • 역설을 일으키는 분할 집단의 구조적 특성 (유사성 등) 에 대한 연구.

결론적으로, 이 논문은 IRV 가 이론적으로뿐만 아니라 실제 선거 환경에서도 강화 역설에 상당히 취약함을 보여주며, 투표 시스템의 설계와 해석에 있어 일관성 (Consistency) 의 중요성을 다시 한번 환기시킵니다.