Constituency Optimisation Through Hamiltonian Representation Of Mandates (COTHROM): Algorithmic Redistricting of Irish Election Boundaries

기술 요약: 해밀토니안 표현을 통한 선거구 최적화 (COTHROM)

문제 정의
본 논문은 아일랜드의 단기 이양식 비례대표제(PR-STV) 체제 하에서 선거구 경계를 재획정하는 계산적 과제를 다룬다. 이 과정은 아일랜드 헌법과 2022년 선거 개혁법에 의해 규율되며, 특정 "하드(hard)" 제약 조건(예: 총 171181석, 35석 규모의 선거구, 연속성)과 "소프트(soft)" 목표(예: 비례성, 카운티 경계 침범 방지, 조밀성, 지리적 고려 사항)를 준수해야 한다.

핵심적인 어려움은 가능한 경계 구성의 조합 폭발(combinatorial explosion)과 소프트 목표들 사이의 내재된 긴장에 있다. 예를 들어, 카운티 경계를 엄격히 준수하는 구성은 비례성에서 상당한 편차를 초래할 수 있는 반면, 수학적으로 최적인 비례 지도는 수많은 카운티 경계 침범을 요구할 수 있다. 현재 선거 위원회(EC)는 수동으로 경계를 그리는데, 이는 체계적인 비교 근거가 부족하며 방대한 허용 가능 대안 공간 내에서 제안된 계획이 최적에 가까운지를 입증할 수 없는 방식이다.

방법론
저자들은 통계 물리학, 특히 포츠 모델(Potts model)을 사용하여 선거구 재획정 문제를 모델링하는 계산 프레임워크인 COTHROM을 제안한다.

1. 해밀토니안 정식화 (Hamiltonian Formulation):
   법적 및 헌법적 요구 사항은 해밀토니안(에너지 함수) $H(\sigma)$의 항으로 인코딩된다. 여기서 $\sigma$는 선거구로 할당된 개별 선거 구역(ED)들의 특정 구성을 나타낸다. 총 에너지는 다음과 같은 특정 목적 함수의 가중 합으로 구성된다:

• $H_P$ (비례성): 선거구 인구가 의석당 국가 평균에서 벗어나는 정도에 대해 페널티를 부여한다.
• $H_C$ (연속성): 선거구가 여러 개의 분리된 구성 요소로 나뉘는 것에 대해 페널티를 부여한다.
• $H_D$ (조밀성): 비구형(non-globular) 형태를 페널티로 주는 이산 컷-엣지(cut-edge) 메트릭을 사용하여, 조밀한 형태를 장려하고 '살라만더링(salamanderinging, 선거구 쪼개기)'을 방지한다.
• $H_B$ (카운티 경계): 선거구의 주요 카운티 범위를 벗어난 ED 할당 수를 계산한다.

목적 함수는 $H = \sum J_\alpha (H_\alpha / Z_\alpha)$이며, 여기서 $J_\alpha$는 각 목표의 상대적 가중치를 나타내는 결합 상수이고, $Z_\alpha$는 정규화 계수이다.

2. 시뮬레이티드 어닐링(Simulated Annealing)을 통한 최적화:
   $H$를 최소화하는 구성을 찾기 위해 저자들은 마르코프 연쇄 몬테카를로(MCMC) 방법과 시뮬레이티드 어닐링 스케줄을 사용한다.

• 알고리즘: Gibbs 샘플러를 사용하여 개별 ED의 선거구 할당을 업데이트한다. 무작위 이동을 제안하는 메트로폴리스(Metropolis) 알고리즘과 달리, Gibbs 샘플러는 주어진 ED에 대한 가능한 모든 할당의 조건부 분포로부터 표본을 추출하여 고에너지 지형에서의 효율성을 높인다.
• 어닐링 (Annealing): 시스템은 높은 "온도"(광범위한 구성 공간 탐색 허용)에서 시작하여 기하학적 스케줄($T_k = \alpha^k T_0$)에 따라 서서히 냉각된다. 이를 통해 시스템은 국소 최솟값(local minima)에서 탈출하여 주어진 가중치에 대한 최적의 상태인 바닥 상태(ground state)로 수렴할 수 있다.

3. 다기준 의사결정 분석 (MCDA):
   목표의 상대적 가중치($J_\alpha$)를 결정하는 것은 법으로 규정된 것이 아닌 규범적 선택임을 인식하여, 프레임워크는 단일한 가중치를 강요하지 않는다. 대신, MCDA를 활용하여 **파레토 프런트(Pareto front)**를 매핑한다. 어떤 구성이 다른 하나를 악화시키지 않고 하나의 목표를 개선할 수 있다면 그 구성은 파레토 최적이다. 이 접근 방식은 경쟁하는 헌법적 목표들 사이의 트레이드오프를 명시적이고 정량적으로 만든다.

주요 결과
프레임워크는 20개의 의석과 5개의 선거구로 구성된 코크 카운티(County Cork) 데이터를 사용하여 검증되었다.

• 수렴: 시스템은 무작위 초기 구성이 온도가 낮아짐에 따라 구조적이고 연속적인 선거구로 "결정화(crystallize)"되는 명확한 상전이를 보여주었다.
• 최적성: 2023년 EC 경계를 COTHROM이 생성한 파레토 프런트와 비교했을 때, 기존의 법적 경계는 지배(dominated)되는 것으로 나타났다. COTHROM은 동일한 수준의 조밀도에 대해 더 낮은 비례성 편차를 보이거나, 동일한 비례성에 대해 더 나은 조밀도를 보이는 구성을 일관되게 생성했다.
• 카운티 경계: 미들랜드(midland) 카운티들을 대상으로 한 테스트 케이스에서, 프레임워크는 비례성을 위해 카운티 경계 준수를 희생하거나 그 반대의 트레이드오프를 수행하는 능력을 입증했다. 카운티 경계에 대한 결합 상수($J_B$)를 높임으로써, 알고리즘은 더 높은 인구 편차를 감수하면서도 2023년 경계를 거의 정확하게 재현하는 지도를 만들어냈다.
• 파레토 분석: 본 연구는 현재의 EC 경계가 파레토 프런트 위에 있지 않음을 밝혀냈으며, 이는 특정 트레이드오프를 수용한다면 비례성이나 조밀성을 개선할 수 있음을 시사한다. 즉, 다른 목표를 희생하지 않고도 개선이 가능하다는 것이다.

의의 및 주장
본 논문은 아일랜드의 선거구 재획정을 위해 특별히 설계되어 여러 헌법적 요구 사항을 체계적으로 최적화하는 최초의 계산 프레임워크라고 주장한다. 주요 기여는 다음과 같다:

• 투명성 및 감사 가능성: 법적 명령을 명시적인 수학적 모델로 인코딩함으로써, 프레임워크는 결과의 재현을 가능하게 하고 특정 가중치가 결과에 어떻게 영향을 미치는지 검사할 수 있게 한다. 이는 현재의 수동 프로세스와 대조되는 점으로, 제안된 계획의 최적성을 엄밀하게 증명할 수 없다는 한계를 극복한다.
• 명시적 트레이드오프 정량화: 파레토 프런트 분석을 통한 접근은 논쟁을 암묵적 숙의에서 명시적 정량화로 전환한다. 이를 통해 의사 결정자는 조밀성이나 카운티 경계의 무결성을 얻기 위해 비례성을 얼마나 희생해야 하는지를 정확히 파악할 수 있다.
• 알고리즘 거버넌스: 이 연구는 선거 위원회가 공청회를 위한 수학적으로 최적화된 시작점을 생성할 수 있는 "알고리즘 거버넌스"의 경로를 제시하며, 이를 통해 최종 경계가 단순히 법을 준수하는 것을 넘어 정의된 법적 지형 내에서 최적에 가깝도록 보장한다.
• 한계 및 범위: 저자들은 현재 모델이 복잡한 지형적 특징(산, 강)이나 공동체 유대감에 관한 공청회의 미묘한 통찰을 아직 통합하지 못했음을 겸허히 언급하며, 이를 향후 확장 과제로 제시한다. 또한, "카운티 경계 침범"의 정의가 현재 면적 비율에 기반한 단순화된 휴리스틱임을 인정하며, EC의 구체적인 법적 해석에 맞춘 추가 정교화가 필요함을 밝힌다.

요약하자면, COTHROM은 아일랜드의 선거구 재획정이라는 복잡한 다목적 최적화 지형을 탐색하기 위한 엄격하고 물리학에 기반한 도구를 제공하며, 지리적 제약을 존중하면서도 비례성이라는 헌법적 명령을 더 잘 충족할 수 있는 선거 경계를 생성, 비교 및 정당화하는 방법을 제시한다.