Counting Votes with Multisets

기술 요약: 멀티셋(Multisets)을 이용한 투표 집계

문제 정의
본 논문은 복잡한 선거 시스템, 특히 선호 투표(preferendums) 및 다중 가중치 옵션이 포함된 선호 투표 방식에서 투표 집계 알고리즘을 기술, 설명 및 구현하는 데 따르는 과제를 다룹니다. 단순한 선거(예: 두 명의 후보, 단일 투표)는 리스트나 단순 집계로 기술할 수 있지만, 즉결 결선 투표제(IRV), 드 보라(De Borda) 계산법, 단기 이양식 투표제(STV)와 같은 메커니즘은 잉여 표의 이전, 후보자 탈락, 선호도 재가중화 등을 포함합니다. 저자들은 리스트와 같은 표준 데이터 타입이 이러한 작업에 최적화되지 않았다고 주장합니다. 리스트는 순서(결과에는 무관함)를 유지하며, 투표 순서에 관한 정보를 유출하여 기밀성을 해칠 가능성이 있기 때문입니다. 또한, 이러한 알고리즘을 리스트로 구현하면 검증과 투명성 확보가 어려운 복잡하고 임시방편적인(ad-hoc) 코드로 이어지기 쉽습니다.

방법론
본 논문은 투표 결과와 투표 집계 과정을 리스트 대신 멀티셋(요소가 중복될 수 있는 집합)을 사용하여 모델링할 것을 제안합니다. 저자들은 멀티셋에 대한 연산을 정형화하기 위해 **범주론(category theory)**의 기초적인 기법을 채택합니다. 핵심 방법론은 다음과 같습니다:

1. 데이터 타입 선택: 투표의 집합을 후보자와 그 다중도(투표수)를 요소로 하는 멀ets $N(X)$ (또는 분수 투표의 경우 $M(X)$)로 표현합니다. 이는 투표의 순서를 추상화합니다.
2. 범주적 구조: 저자들은 멀티셋의 세 가지 특정 범주적 성질을 활용하여 투표 알고리즘을 도출하고 표현합니다:
   • 가환 모노이드(Commutative Monoid): 멀티셋은 자유 가환 모노이드를 형성하여, 순서에 상관없이 투표수의 합산(투표함의 합집합)을 가능하게 합니다.
   • 함자성(Functoriality): 멀티셋 구성 $N$은 함자(functor)로 작용합니다. 이를 통해 후보자에 대해 정의된 함수(예: "리스트의 헤드" 또는 "후보자 삭제")를 리스트의 멀티셋으로 들어 올릴(lift) 수 있습니다. 이 성질은 1순위 선호도를 집계하고 탈락한 후보자의 표를 재배분하는 데 사용됩니다.
   • 모나드 구조(Monad Structure): 멀티셋은 unit(단일 원소 멀티셋 생성)과 flatten(멀티셋의 멀티셋을 하나로 합침)을 갖는 모나드를 형성합니다. 이 구조는 단일 투표(선호도 리스트)가 여러 후보에게 가중치 기여를 하는 방식으로 분해되는 가중치 계산을 처리하는 데 사용됩니다.

주요 기여 및 결과
논문은 세 가지 구체적인 투표 메커니즘을 통해 이러한 범주적 구조의 적용을 입증하며, 추상화를 보여주기 위해 작은 규모의 예시(EfProb 라이브러리의 Python 스크립트로 검증됨)를 사용합니다:

1. 즉결 결선 투표제 (IRV):

   • 메커니즘: 1순위 득표수가 가장 적은 후보자를 반복적으로 탈락시키고, 그들의 표를 다음 순위로 이전합니다.
   • 적용: 저자들은 멀티셋의 함자성을 사용합니다. head 함수(첫 번째 선호도 선택)와 delete 함수(탈락한 후보자 제거)를 선호도 리스트의 멀티셋에 적용하도록 들어 올립니다. 이를 통해 1순위 선호도의 집계와 이후의 표 재배분을 복잡한 반복적 리스트 처리 없이 단순한 함수 합성($N(\text{hd})$ 및 $N(\text{del } c)$)으로 표현할 수 있습니다.

2. 드 보라 계산법 (De Borda Count):

   • 메커니즘: 유권자는 후보자 순위를 매기며, 순위에 따라 점수가 부여됩니다 (예: 1위는 $n$점, 2위는 $n-1$점 등).
   • 적용: 모나드 구조가 활용됩니다. 각 선호도 리스트는 unit과 점수 부여를 통해 가중치가 부여된 후보들의 멀티셋으로 매핑됩니다. 이러한 가중치 멀티셋들의 집합은 멀티셋의 멀티셋을 형성합니다. flatten 연산은 이 구조를 하나의 총점 멀티셋으로 압축하여, 가중치 기여도를 효율적으로 합산합니다.

3. 단기 이양식 투표제 (STV):

   • 메커니즘: 다인 선거구에서 사용됩니다. 쿼터(Droop 쿼터)를 초과한 후보자가 당선되며, 그들의 잉여 표는 다음 선호도로 이전됩니다.
   • 적용: 저자들은 "이전 가치"(투표의 분수 값)를 처리하기 위해 데이터 타입을 분수 멀티셋($M(X)$)으로 확장합니다. 모노이드 구조를 사용하여 뺄셈(당선된 후보자에게 사용된 표의 가치 감소)을 수행하고, 함자성을 사용하여 재배분을 수행합니다. 이 과정은 전체 멀티셋에서 당선된 후보자의 쿼터 가중치만큼을 빼는 반복적인 뺄셈과, 당선된 후보자 제거 및 남은 분수 가중치를 다음 선호도로 전달하는 과정으로 모델링됩니다.

의의 및 주장
본 논문은 자신의 주요 기여가 심오한 범주론 자체에 있는 것이 아니라, 투표 시스템 영역 내에서 기존의 범주적 구조(함자, 모나드, 모노이드)를 인식하고 활용하는 데 있다고 겸손하게 주장합니다. 저자들의 주장은 다음과 같습니다:

• 추상화: 알고리즘을 멀티셋 관점에서 기술함으로써, 복잡한 메커니즘을 몇 줄의 수학적 표기법으로 기술할 수 있게 합니다.
• 정확성 및 투명성: 멀티셋 접근 방식은 투표의 순열에 대한 안정성(순서 독립성)을 본질적으로 보장하며, 이는 공정한 집계의 필수 요건입니다. 이는 계산 로직을 투표 용지의 물리적 또는 순차적 표현으로부터 분리합니다.
• 구현: 이러한 추상화는 멀티셋을 지원하는 함수형 프로그래밍 언어(예: Haskell)에서 증명 가능한 정확한 구현을 용이하게 합니다.
• 접근성: 본 논문은 이러한 범주적 기법을 비전문가들에게도 접근 가능하게 만드는 것을 목표로 하며, 이들이 단순히 이론적인 구성물이 아니라 선거 결과의 투명성과 정확성을 보장하기 위한 실질적인 도구임을 입증합니다.

결론적으로, 본 논문은 몇 가지 단순화된 가정(예: 균일한 리스트 길이)을 사용했으나, 멀티셋 접근 방식이 물리적 투표 용지를 분류하는 역사적 의존도를 넘어, 향후 참조 구현 및 선거 알고리즘 분석을 위한 견고한 프레임워크를 제공한다고 밝히고 있습니다.