[기술 요약] 순위 기반 투표를 위한 메트릭 기하학: 선거 구조 학습을 위한 도구

1. 문제 정의 (Problem)

전통적인 계산 사회 선택(Computational Social Choice) 이론은 후보자와 유권자가 공통의 메트릭 공간에 임베딩되어 있다는 '메트릭 선호(Metric Preferences)' 모델을 연구해 왔습니다. 그러나 기존 연구들은 주로 다음과 같은 한계를 가집니다:

• 불완전한 투표(Partial Ballots): 실제 선거에서는 모든 후보자를 순위 매기지 않고 일부만 기입하는 경우가 많으나, 기존의 순위 거리(Ranking Distance) 지표들은 완전한 순열(Full Permutation)을 가정하는 경우가 많습니다.
• 기술적 도구의 부족: 선거의 양극화(Polarization), 비례성(Proportionality), 선호 다양성 등을 측정하기 위한 기하학적 프레임워크가 불완전한 투표 데이터에 적용되기 어려웠습니다.
• 유권자 블록 및 후보자 슬레이트 식별: 유권자 집단(Blocs)과 그들이 선호하는 후보자 묶음(Slates)을 객관적이고 통계적으로 분류하는 방법론이 필요했습니다.

2. 방법론 (Methodology)

본 논문은 두 가지 주요 순위 통계 지표인 **Kendall tau($d_H$)**와 **Spearman footrule($d_B$)**을 불완전한 순위(Partial Rankings)로 확장하는 메트릭 기하학적 프레임워크를 제안합니다.

A. 좌표 임베딩 (Coordinate Embeddings)

불완전한 투표를 다차원 공간의 점으로 변환하기 위해 두 가지 임베딩 방식을 정의합니다:

1. Borda Embedding ($b$): 각 후보자의 순위를 점수로 변환하여 $R^m$ 공간에 매핑합니다. 불완전한 투표의 경우, 언급되지 않은 후보자에게는 0점을 부여하는 '비관적 관례(Pessimistic Convention)'를 사용하여 거리 $d_B$를 정의합니다.
2. Head-to-head Embedding ($h$): 모든 후보자 쌍(Pairwise)의 비교 결과를 $\{-1, 0, 1\}$로 기록하여 $R^{\binom{m}{2}}$ 공간에 매핑합니다. 이를 통해 거리 $d_H$를 정의합니다.

B. 투표 그래프 (Ballot Graphs)

좌표 임베딩 외에도, 투표를 그래프의 노드로 간주하는 방식을 제안합니다:

• Ballot Graph ($G_m$): 인접한 순위 교체(Neighbor swaps)와 투표의 절단/확장(Truncation/Extension)을 에지로 연결하여 $d_H$를 구현합니다.
• Shortcut Ballot Graph ($G^+_m$): 일반적인 교체(General swaps) 에지를 추가하여 $d_B$를 구현합니다.
• Generalized Ballot Graph ($\mathcal{e}G_m$): 동점(Ties)이 허용되는 일반화된 투표를 처리하기 위한 그래프 구조입니다.

C. 클러스터링 알고리즘 (Clustering)

1. 유권자 블록 식별: 임베딩된 좌표 공간에서 $k$-medoids(PAM 알고리즘) 또는 $k$-means를 사용하여 유사한 선호도를 가진 유권자 그룹을 분류합니다.
2. 후보자 슬레이트 식별: 후보자 간의 불일치 정도($D_B$)를 기반으로 후보자들을 그룹화(Agglomeration 또는 Center 기반)하여 유권자들이 선호하는 후보자 묶음을 찾아냅니다.

3. 주요 기여 (Key Contributions)

• 메트릭의 확장: Kendall tau와 Spearman footrule이 불완전한 투표 및 동점 상황에서도 자연스럽게 확장됨을 수학적으로 증명했습니다.
• 그래프 실현(Graph Realization): 순위 거리 지표를 그래프 상의 최단 경로 거리(Path metric)로 구현하여, 투표 데이터를 네트워크 구조로 분석할 수 있는 토대를 마련했습니다.
• 분류 안정성 증명: 양극화된 선거($R > 10r$ 조건)에서는 서로 다른 메트릭($d_H$와 $d_B$)을 사용하더라도 동일한 유권자 클러스터링 결과가 도출됨을 이론적으로 보였습니다.

4. 연구 결과 (Results)

A. 합성 데이터 검증 (Synthetic Validation)

Mallows 모델을 이용한 합성 선거 데이터를 통해, 제안된 클러스터링 방법이 실제 생성된 중심점(Centers)과 클러스터 크기를 매우 정확하게 복원함을 확인했습니다.

B. 스코틀랜드 실제 선거 데이터 적용 (Scottish Elections)

2012~2022년 스코틀랜드 지방 선거 데이터(1,000건 이상)를 분석한 결과:

• 유권자 블록: 정당 라벨을 사용하지 않고도 유권자의 선호 구조를 효과적으로 파악했습니다. (예: Pentland Hills 지역의 SNP-Lab-Con 삼각 구도 식별)
• 후보자 슬레이트: 정당 기반 분석보다 더 정교한 후보자 간 유사성을 발견했습니다. 특히, 정당 라벨을 사용하지 않았음에도 불구하고 정당별 후보자들을 매우 일관되게 하나의 슬레이트로 묶어냈습니다.
• 방법론적 강건성: $d_H$와 $d_B$를 혼용하거나 다양한 클러스터링 기법을 사용해도 결과가 매우 유사하게 나타나는 높은 안정성을 보였습니다.

5. 의의 (Significance)

본 논문은 순위 기반 투표 데이터를 기하학적 객체로 취급할 수 있는 강력한 수학적 도구를 제공합니다. 이는 단순히 투표 결과를 집계하는 것을 넘어, 선거의 양극화 정도, 비례성, 선호의 다양성을 정량적으로 측정하고 시각화할 수 있는 프레임워크를 구축했다는 점에서 학술적/실무적 가치가 매우 높습니다. 특히 실제 선거의 불완전한 투표 데이터를 처리할 수 있다는 점에서 실용성이 뛰어납니다.