A House Monotone, Coherent, and Droop Proportional Ranked Candidate Voting Method

이 논문은 단일이양식투표 (STV) 의 드룹 비례성, 의석 단조성, 일관성을 충족하며 최상위 당선자를 즉시결선투표 (IRV) 승자로 선정하는 프라그멘 (Phragmén) 절차 기반의 새로운 순위형 투표 방법을 제안합니다.

핵심

🏛️ 1. 문제 상황: "왜 의석 수가 늘었는데, 내 지역구는 줄어들었지?"

미국이나 유럽 같은 나라에서는 인구에 비례하여 국회의원 (또는 대표) 수를 정합니다. 하지만 과거에는 이상한 일이 자주 벌어졌습니다.

• 앨라배마 역설 (Alabama Paradox): 전체 의석 수가 늘어났는데, 오히려 특정 주의 의석 수가 줄어든다는 기이한 현상.
• 새 주 역설 (New State Paradox): 새로운 주가 생기고 의석 수가 조정되는데, 기존 주의 의석 수가 바뀌어 버리는 일.

이건 마치 피자를 자를 때입니다. 피자가 10 조각에서 11 조각으로 늘어났는데, 왜 내 조각은 더 작아진 걸까요? 기존의 방식 (하밀턴 방식 등) 은 이런 '수학적 착시'를 일으켰습니다.

현재 많은 나라는 **나눗셈 방식 (Divisor Method)**을 써서 이 문제를 해결했습니다. 하지만 이 방식은 '정당'만 뽑을 때 잘 작동합니다. 유권자가 **후보 개인을 1 등, 2 등, 3 등...으로 순위 매겨 투표하는 방식 (STV 등)**에서는 여전히 불공정한 결과가 나올 수 있습니다.

🎯 2. 이 논문이 해결하려는 세 가지 목표

이 논문은 순위 매기식 투표에서 다음 세 가지 '황금 규칙'을 모두 지키는 방법을 찾았습니다.

1. 드루프 비례성 (Droop Proportionality): "우리 팀이 30% 이상 지지받으면, 적어도 1 명은 뽑혀야 해!"라는 원칙입니다. (예: 100 명 중 34 명 이상이 A 후보를 좋아하면, A 후보는 무조건 당선되어야 함).
2. 하우스 단조성 (House Monotonicity): "의석 수가 늘어나면, 기존에 뽑혔던 사람들은 계속 뽑혀야 해." (의석 5 명에서 6 명으로 늘면, 기존 5 명은 모두 6 명 명단에 포함되어야 함).
3. 일관성 (Coherence): "A 지역과 B 지역을 따로 뽑아도, 합쳐서 뽑아도 결과는 같아야 해." (지역을 합치면 결과가 뒤바뀌지 않아야 함).

🚀 3. 새로운 방법: "탑다운 (Top-Down) 프라그멘 방식"

저자는 **'프라그멘 (Phragmén)'**이라는 100 년 전 수학자의 아이디어를 현대화했습니다. 이 방식을 **'최고의 팀 빌딩'**에 비유해 볼까요?

💡 기존 방식의 문제점 (바닥부터 쌓기)

기존 방식은 "누가 꼴등인지"부터 찾아서 제외시키는 방식이었습니다.

• 비유: 피아노 반주자가 "가장 못 치는 사람부터 제외하자"라고 해서, 결국 좋은 실력의 사람도 실수 하나에 탈락하는 경우입니다.
• 결과: 의석 수가 바뀌면, 아까 뽑혔던 사람이 갑자기 떨어지는 기이한 일이 일어납니다.

✨ 새로운 방식 (탑다운 프라그멘)

이 논문이 제안하는 방식은 **"이미 뽑힌 사람은 절대 떨어뜨리지 않고, 그 위에 새로운 사람을 추가한다"**는 방식입니다.

1. 1 등 뽑기 (Instant Runoff): 먼저 1 명을 뽑습니다. (이는 기존 방식과 같아서 가장 인기 있는 사람, 즉 '즉시 결승전' 승자가 됩니다.)
2. 2 등 뽑기: 이미 뽑힌 1 명을 '보호'합니다. 이제 2 번째 사람을 뽑을 때, 1 명이 이미 자리를 잡았다고 가정하고 나머지 후보들 중에서 가장 공평하게 2 번째 사람을 찾습니다.
3. 3 등 뽑기: 1 등, 2 등 모두를 '보호'하고 3 번째 사람을 찾습니다.

핵심 메커니즘: "의석 부담 (Seat Load)"
이 방식은 유권자의 표를 '부담'으로 봅니다.

• 한 후보가 당선되면, 그를 지지한 유권자들은 '의석 1 개'를 떠안게 됩니다.
• 다음 후보를 뽑을 때는, 이미 의석을 많이 떠안은 유권자들의 표는 덜 중요하게 계산하고, 아직 의석을 안 떠안은 유권자들의 표를 더 중요하게 봅니다.
• 이렇게 하면, 특정 집단이 너무 많은 표를 독차지하지 못하게 막아주며, 소수 의견도 공정하게 반영됩니다.

📝 4. 구체적인 예시 (간단히)

논문 속 예시 (200 명의 유권자) 를 보면:

• 기존 방식: 1 명 뽑을 때는 C 가, 3 명 뽑을 때는 A, B, D 가 뽑혔습니다. (C 가 3 명 명단에 없으면 안 되는데, 없어졌습니다. 이것이 '하우스 단조성' 위반입니다.)
• 새로운 방식:
  • 1 명 뽑을 때: C가 뽑힙니다.
  • 2 명 뽑을 때: C 는 유지되고, A가 추가됩니다. (명단: C, A)
  • 3 명 뽑을 때: C, A 는 유지되고, B가 추가됩니다. (명단: C, A, B)
  • 결과: 의석 수가 늘어나도, 기존에 뽑힌 사람들은 계속 명단에 남아있습니다. 그리고 소수 의견 (B 를 지지하는 그룹) 도 적절히 반영됩니다.

🌟 5. 왜 이 방식이 중요한가요?

이 방식은 **정치적 정당 (Party List)**을 만들 때 아주 유용합니다.

• 정당들이 "우리 당의 후보 순위를 어떻게 매길까?" 고민할 때, 이 방식을 쓰면 1 등부터 N 등까지의 순서가 논리적이고 공평하게 나옵니다.
• 유권자가 "A 후보는 1 등, B 후보는 2 등"으로 투표하면, 그 결과가 의석 수 변화에 따라 뒤바뀌지 않습니다.
• 결론: "누가 1 등인지"부터 확실히 하고, 그 다음에 2 등, 3 등을 찾아나가는 이 방식은 수학적으로 완벽하고, 정치적으로 공정한 선거를 가능하게 합니다.

📌 요약

이 논문은 "의석 수가 늘어나도 기존 당선자는 떨어지지 않고, 소수 의견도 공정하게 반영되며, 지역을 합쳐도 결과가 일관된" 새로운 투표 방식을 소개합니다.

마치 팀을 구성할 때처럼, 이미 뽑힌 팀원 (당선자) 을 해고하지 않고, 새로운 팀원을 가장 공평하게 추가해 나가는 방식입니다. 이는 복잡한 수학 공식 없이도, 유권자의 의사를 가장 잘 반영하는 '완벽한 투표 시스템'의 한 걸음입니다.

기술 요약

논문 요약: 하우스 단조성, 일관성, 그리고 Droop 비례성을 만족하는 순위형 후보 투표 방법 (House Monotone, Coherent, and Droop Proportional Ranked Candidate Voting Method)

저자: Ross Hyman (시카고 대학교 연구컴퓨팅센터)

1. 연구 배경 및 문제 제기 (Problem)

본 논문은 비례대표 선거에서 사용되는 순위형 투표 (Ranked Candidate Voting) 방법론의 한계를 해결하기 위한 새로운 방법을 제안합니다.

• 현황: 현재 미국 의회 의석 배분이나 많은 국가의 정당명부식 비례대표 선거는 '알라바마 역설 (Alabama Paradox)'과 '새 주 역설 (New State Paradox)'을 피할 수 있는 **분배자 방법 (Divisor Methods)**을 사용합니다.
• STV 의 한계: 호주, 아일랜드 등에서 사용되는 **단일이양식 투표 (STV, Single Transferable Vote)**는 유권자의 선호 순위를 반영하고 Droop 비례성 (Droop Proportionality) 을 만족한다는 장점이 있지만, **하우스 단조성 (House Monotonicity)**과 **일관성 (Coherence)**을 만족하지 못합니다.
  • 하우스 단조성 위반: N 명의 당선자가 결정된 후, 의석 수를 N+1 로 늘렸을 때 기존 N 명의 당선자가 모두 다시 당선되어야 하는데, STV 는 이를 보장하지 못합니다. 이는 비례적 후보 명단 (Candidate List) 을 생성할 수 없음을 의미합니다.
  • 일관성 위반: 서로 다른 후보군이 포함된 두 투표 집합을 합쳐서 계산했을 때, 개별 집합으로 계산한 결과와 모순이 발생할 수 있습니다.
• 기존 대안의 부족: 기존에 제안된 하향식 (Bottom-up) 또는 상향식 (Top-down) STV 변형 방법들은 Droop 비례성을 만족하지 못하거나, 모든 '단단한 연합 (Solid Coalition)'을 명시적으로 찾아야 하는 등 계산상 비효율적이거나 복잡한 문제가 있었습니다.

2. 방법론 (Methodology)

저자는 **Phragmén 의 절차 (Phragmén's procedure)**를 기반으로 한 새로운 상향식 (Top-down) 순위형 투표 방법을 제안합니다. 이 방법은 Droop 비례성, 하우스 단조성, 일관성을 동시에 만족합니다.

핵심 개념: Phragmén 우선순위 (Priority)

Phragmén 방법은 각 후보가 당선될 때 유권자들이 부담하는 '의석 부하 (Seat-load)'를 계산하여 우선순위를 매깁니다.

• 기존 Phragmén (승인 투표용): 후보 C 의 우선순위 $P_C = V_C / (1 + S_C)$ (여기서 $V_C$는 C 를 지지하는 표, $S_C$는 C 당선 전까지 C 를 지지하는 표들의 누적 의석 부하).
• 본 논문의 적용 (순위 투표용): 기존의 Quota(할당량) 기반 방식은 하우스 단조성을 위반하므로, 본 방법은 할당량 (Quota) 에 의존하지 않고 순수한 Phragmén 우선순위 계산을 기반으로 합니다.

제안된 알고리즘: 상향식 Phragmén (Top-down Phragmén)

이 방법은 1 위부터 N 위까지 순서대로 당선자를 결정합니다.

1. 초기 설정: $M$명의 당선자를 결정할 때, 이미 당선된 $M-1$명의 후보를 '이전 당선자 (Previously Elected)'로, 나머지를 '희망 후보 (Hopeful)'로 분류합니다.
2. 불완전 단단한 연합 (Imperfect Solid Coalitions) 처리:
   • 기존 Phragmén 방식은 이전 당선자들이 포함된 표의 부하를 정확히 반영하지 못해 Droop 비례성을 위반할 수 있습니다.
   • 본 방법은 불완전 단단한 연합을 고려합니다. 즉, 어떤 표에서는 이전 당선자 A 가 1 위이고 B 가 2 위일 때, 다른 표에서는 B 가 1 위이고 A 가 2 위일 수 있지만, 두 표 모두 A 와 B 를 선호한다는 점을 인정합니다.
   • 이를 위해 각 희망 후보에 대해 $M$개의 '불완전 연합' 시나리오를 가정하고, 각 시나리오에서 Phragmén 우선순위를 계산한 후 최대값을 해당 후보의 최종 우선순위로 채택합니다.
3. 선택 및 배제 과정:
   • 현재 라운드에서 가장 높은 우선순위를 가진 희망 후보를 당선시키고, 나머지 후보들의 우선순위를 재계산합니다.
   • 배제 (Exclusion): 우선순위가 가장 낮은 희망 후보를 배제합니다. 이때 배제된 후보가 다시 등장하지 않도록 처리하며, 이전 당선자들의 부하가 재조정됩니다.
   • 재귀적 반복: 이 과정을 모든 희망 후보가 배제되거나 당선될 때까지 반복하여 1 위부터 N 위까지의 명단을 생성합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

1) 세 가지 핵심 속성 만족 증명 (Section VI)

저자는 제안된 방법이 다음 세 가지 속성을 수학적으로 증명했습니다.

• 하우스 단조성 (House Monotonicity): $N$명의 당선자가 결정된 후 $N+1$명의 당선자를 결정할 때, 기존 $N$명의 당선자는 반드시 포함됩니다. 이는 **후보 명단 (Candidate List)**을 생성하는 데 필수적입니다.
• 일관성 (Coherence): 서로 다른 후보군이 포함된 두 투표 집합을 합쳐서 계산하더라도, 각 집합을 개별적으로 계산한 결과와 모순이 발생하지 않습니다.
• Droop 비례성 (Droop Proportionality): 특정 후보군을 지지하는 유권자 수가 Droop 할당량 ($V_{total}/(N+1)$) 을 초과하면, 그 수에 비례하여 해당 후보군이 당선됩니다. 특히, Instant Runoff Voting (IRV) 의 1 위 당선자는 모든 $N$에 대해 적어도 하나의 Droop 준수 집합에 포함됨이 증명되었습니다.

2) 기존 방법론과의 비교

• 기존 Quota 기반 Phragmén: 할당량을 사용하여 당선/배제를 결정하므로 하우스 단조성과 일관성을 위반합니다.
• Aziz et al. (2025) 의 하향식 (Bottom-up) 방법: 하우스 단조성과 Droop 비례성을 만족하지만, 1 위 당선자가 IRV 승자와 다를 수 있으며, 모든 단단한 연합을 찾아야 하는 계산 복잡도가 높을 수 있습니다.
• 본 논문의 상향식 (Top-down) 방법: IRV 승자를 1 위로 보장하며, Droop 비례성을 만족하면서도 불완전 연합을 효율적으로 처리합니다.

3) 예시 적용 (Example 1)

제공된 예시 (200 표, 4 후보) 에 대해 본 방법을 적용했을 때 생성된 명단은 C > A > B > D였습니다.

• 1 위: C (IRV 승자)
• 2 위: A
• 3 위: B
• 4 위: D
  이 명단의 상위 $N$명은 항상 $N$명의 당선자 집합에 대한 Droop 준수 집합을 형성했습니다.

4. 의의 및 결론 (Significance & Conclusion)

• 이론적 의의: 순위형 투표에서 하우스 단조성, 일관성, Droop 비례성이라는 세 가지 이상적인 속성을 동시에 만족하는 최초의 실용적인 상향식 (Top-down) 방법을 제시했습니다.
• 실용적 가치: 정당명부식 비례대표 선거에서 필요한 '후보 명단'을 생성하는 데 직접적으로 적용할 수 있습니다. 기존 STV 는 명단 생성에 부적합했으나, 이 방법은 이를 해결합니다.
• 한계 및 향후 연구: 알고리즘이 다소 복잡하고 "미학적으로 아름답지 않다 (ascetically ugly)"고 저자 스스로 평가하며, 더 단순하고 우아한 방법이 발견되기를 기대합니다. 또한, '불완전한 단단한 연합'의 정의와 처리 방식에 대한 추가 연구가 필요함을 언급했습니다.

결론적으로, Ross Hyman 의 연구는 Phragmén 의 고전적 아이디어를 현대적 순위 투표 환경에 적응시켜, 비례대표 선거의 공정성 (Droop 비례성) 과 안정성 (하우스 단조성, 일관성) 을 모두 확보할 수 있는 강력한 대안을 제시했습니다.