🤖 AI

Proportional Committee Elections with Positive and Negative Votes

이 논문은 유권자가 양의 투표와 음의 투표를 모두 던질 수 있는 환경에서의 비례적 위원회 선거를 조사하며, 음의 투표에 대한 두 가지 뚜렷한 해석을 제안하여 새로운 비례성 공리를 정의하고 프라그멘(Phragmén) 규칙, PAV, 그리고 MES의 변형들에 의한 공리 충족 여부를 평가한다.

원저자: Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

게시일 2026-08-13

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

개인이 내는 의견이라는 무질서한 군중의 목소리를 하나의 공정한 집단 결정으로 바꾸기 위해 수학과 컴퓨터 알고리즘을 사용하는 과학의 한 분야, 즉 **계산 사회 선택(computational social choice)**의 영역을 상상해 보십시오. 여기서는 단순히 "예!"라고 외치는 것뿐만 아니라, 들릴 만큼 크게 "아니오!"라고 외치는 것도 중요한 세계입니다. 여러분은 아마 학급에서 현장 학습지를 투표하거나 팀이 영화 관람을 결정할 때 이런 모습을 본 적이 있을 것입니다. 보통은 자신이 좋아하는 것에 손을 들어 올립니다. 하지만 만약 여러분이 "절대로 저건 안 돼"라고 말하기 위해 손을 들 수도 있다면 어떨까요? 이것이 바로 이 논문이 탐구하는 반전입니다. 사람들이 후보를 승인할 수도 있고, 거부(veto)할 수도 있는 선거 말입니다.

핵심 문제는 **비례성(proportionality)**입니다. 이것은 피자를 자르는 것과 같습니다. 만약 파티 참석자 중 친구들이 40%를 차지한다면, 그들은 다른 사람들이 원하지 않아 남겨진 조각이 아니라 대략 40%의 피자 조각을 가져가야 합니다. 고전적인 투표 방식에서는 모두가 "예"라고만 할 때 피자를 공정하게 자르는 방법을 알고 있습니다. 하지만 사람들이 "아니오"라고 말하기 시작하면 수학은 복잡해집니다. 어떤 집단이 특정 후보를 싫어한다면, 그것이 그들이 그 후보를 피하기 위해 피자 한 조각을 얻는다는 뜻일까요, 아니면 단지 "좋은 것"의 조각을 먹을 수 있다는 뜻일까요? 이 논문은 다음과 같은 질문을 던집니다. 사람들이 엄지 척(좋아요) 버튼과 엄지 척 반대(싫어요) 버튼을 모두 사용할 때, 어떻게 하면 공정한 투표 시스템을 설계할 수 있을까요?

"Proportional Committee Elections with Positive and Negative Votes(양성과 음성 투표가 있는 비례적 위원회 선거)"라는 제목의 이 논문은 바로 이 퍼즐을 깊이 파고듭니다. 옥스퍼드 대학교와 바르샤바 대학교의 연구진인 저자들은 "아니오"라는 투표를 해석하는 방법이 단 하나가 아니라고 주장합니다. 그들은 두 가지 다른 안경을 쓰는 것처럼, 부정적인 투표를 두 가지 다른 관점으로 바라봐야 한다고 주장합니다.

첫 번째 안경: 대칭적 관점 (The "Equal Weight" Lens - "동등한 무게" 렌즈)
첫 번째 모델에서 저자들은 투표자에게 나쁜 후보를 차단하는 것은 좋은 후보를 선출하는 것만큼이나 중요하다고 가정합니다. 이것은 왼쪽으로 줄을 당기는 것(거부)이 오른쪽으로 당기는 것(승인)만큼이나 강한 줄다리기 게임과 같습니다. 수학적으로 이를 처리하기 위해, 저자들은 "아니오" 투표를 실제 후보와 정반대인 유령 후보를 위한 "예" 투표로 취급합니다. 만약 당신이 후보 A에 대해 "아니오"라고 투표한다면, 그것은 수학적으로 "안티-A"에 대해 "예"라고 투표하는 것과 같습니다.

연구진은 세 가지 유명한 투표 규칙을 이 모델에 대해 테스트했습니다:

프라그멘(Phragmén) 규칙: 이것은 투표자들이 후보를 사기 위해 시간이 지남에 따라 돈을 버는 느린 속도의 경매와 같습니다. 저자들은 이 규칙을 투표자가 후보를 차단하는 데에도 돈을 쓸 수 있도록 변형했을 때, 놀라울 정도로 잘 작동한다는 것을 발견했습니다. 이는 큰 집단이 "좋은 것"과 "반대되는 것" 모두에서 공정한 몫을 얻도록 보장합니다.
PAV (Proportional Approval Voting - 비례적 승인 투표): 이 규칙은 총 행복을 극대화하려고 노력합니다. 저자들은 부정적인 투표가 있더라도 PAV가 여전히 집단에게 매우 높은 수준의 만족감을 준다는 것을 증명했습니다. 비록 완벽하지는 않지만 말입니다. 그들은 수학적으로 완벽함에서의 아주 작은, 피할 수 없는 격차(만족도에서 약 1.5점의 "손실")가 존재함을 보여주었지만, 여전히 매우 강력한 규칙임을 입증했습니다.
"낭비된 노력" 문제: 저자들은 이러한 규칙들에서 재미있는 결함을 발견했습니다. 때때로 어떤 집단은 애초에 당선될 가능성이 없는 후보를 거부하는 데 모든 "투표 에너지"를 써버릴 수도 있습니다. 이는 마치 군중이 단지 힘을 느끼기 위해 지지자가 전혀 없는 후보를 향해 "안 돼!"라고 소리치는 것과 같습니다. 그렇게 함으로써, 그들은 실제로 좋아하는 후보를 지지할 에너지를 실수로 다 써버리게 됩니다. 논문은 해결책으로, 투в표자들이 실제로 경쟁 중인 후보만을 거부할 수 있도록 허용할 것을 제안합니다.

두 번째 안경: 비대칭적 관점 (The "Representation First" Lens - "대표성 우선" 렌즈)
두 번째 모델은 관점을 완전히 뒤집습니다. 여기서 저자들은 "아니오"가 "예"와는 다르다고 주장합니다. 이 세계에서 당신의 주된 목표는 '당신의 사람들'을 당선시키는 것입니다. 나쁜 후보를 막는 것은 보너스일 뿐, 그것이 "대표성"으로 계산되지는 않습니다. 이것은 "내 친구를 팀에 넣고 싶고, 동시에 불량배가 들어오는 것도 막고 싶지만, 내 친구의 자리가 진짜 중요한 상품이다"라고 말하는 것과 같습니다.

이를 처리하기 위해 저자들은 **"반대세(Opposition Tax)"**라는 새로운 개념을 발명했습니다. 모든 후보가 많은 사람으로부터 "아니오" 투표를 받을 때마다, 그 후보의 가격표가 올라간다고 상상해 보십시오. 만약 어떤 후보가 10명에게 사랑받지만 9명에게 미움을 받는다면, 그 후보를 선출하는 비용은 매우 비싸집니다. 이는 투표 시스템이 신중하도록 강제합니다.

저자들은 이 세금을 적용하여 **MES (Method of Equal Shares - 균등 분배법)**와 프라그멘 규칙을 변형했습니다.
결과는 어떠했을까요? 이 "세금이 부과된" 규칙들은 큰 집단이 자신들의 몫에 해당하는 대표를 얻는 것과 동시에, 강력한 반대에 부딪힌 집단이 자신들이 싫어하는 후보를 성공적으로 차단할 수 있도록 보장하는 데 성공했습니다.
그러나 저자들은 PAV(행복 극대화 모델)가 이 모델에서는 완전히 무너진다는 것을 발견했습니다. 수학적으로, 대표성과 차단의 필요성을 모두 만족시키기 위해 PAV를 조정하는 것은 불가능하다는 것이 증명되었습니다. 이는 이 특정한 사고방식에 있어서는 막다른 길입니다.

결론
이 논문은 단순히 "새로운 규칙이 여기 있다"라고 말하는 것이 아닙니다. "아니오"라는 투표를 어떻게 해석하느냐에 따라 모든 것이 달라진다는 것을 증명합니다. 만약 당신이 "좋은 것"과 "나쁜 것"의 균형을 맞추는 데 관심이 있다면, 조정된 프라그멘 또는 PAV를 사용하는 대칭 모델을 사용하십시오. 만약 당신이 자신의 집단이 테이블에 앉을 자리를 확보하는 데 더 관심이 있다면, "반대세"를 사용하는 비대칭 모델을 사용하십시오.

저자들은 또한 우리가 이러한 시나리오를 위한 훌륭한 규칙들을 가지고 있지만, 여전히 열려 있는 질문들이 있다고 지적합니다. 예를 들어, 첫 번째 모델에서 PAV 규칙을 완벽하게 효율적으로 만들 수 있을까요? 그들은 완벽함에서의 작은 격차가 실재한다고 생각하지만, 그것이 메울 수 없다는 것을 증명하지는 못했습니다. 그리고 두 번째 모델에서, 그들의 규칙이 때때로 작동을 위해 조기에 멈춰야 해서 일부 자리를 빈 상태로 남겨둔다는 점을 인정하며, 이는 그들이 미래의 연구자들이 해결하기를 바라는 문제입니다.

궁극적으로 이 연구는 하나의 로드맵입니다. 민주주의에 "아니오" 투표라는 복잡성을 추가할 때, 우리는 기존의 지도를 그대로 사용할 수 없음을 보여줍니다. 모두가 피자를 공정하게 나누어 먹든, 혹은 단지 그 피자 테두리가 다가오지 못하게 막으려 하든, 우리는 새로운 도구, 새로운 세금, 그리고 새로운 사고방식이 필요합니다.

=== 기술 요약: 양성 및 음성 투표를 포함한 비례 위원회 선거 ===

1. 문제 정의

본 논문은 유권자가 양성 투표(찬성), 음성 투표(반대/거부권), 또는 기권할 수 있는 환경에서의 비례 위원회 선거(proportional committee elections) 문제를 다룹니다. 비례 대표성은 고전적인 승인 투표(유권자가 후보자를 찬성하기만 하는 경우)에서 잘 연구된 주제이지만, 음성 투표의 도입은 개념적 및 기술적으로 상당한 어려움을 야기합니다.

핵심적인 난점은 유권자가 후보자를 차단할 수 있는 권한을 가질 때 **비례성(proportionality)**을 어떻게 정의하느냐에 있습니다. 순 찬성 점수(찬성 수에서 반대 수를 뺀 값)를 기준으로 후보자를 선정하는 단순한 방식은 공정한 대표성을 제공하지 못합니다. 논문의 동기 부여 사례에서 보여주듯, 단순 순점수 규칙은 다수의 강력한 반대를 받는 후보자를 당선시키거나, 반대로 소수의 지지가 다수의 반대에 의해 상쇄되어 소수가 지지하는 후보를 선출하지 못하는 결과를 초래할 수 있습니다. 본 논문은 이러한 삼항 투표(ternary voting) 환경에서 비례성을 공식화하고, 표준 투표 규칙(Phragmén의 규칙, Proportional Approval Voting (PAV), 그리고 Method of Equal Shares (MES))을 이 새로운 조건 하에서 평가하고자 합니다.

2. 방법론 및 프레임워크

저자들은 음성 투표의 의미를 해석하기 위해 두 가지 구별되는 **효용 모델(utility models)**을 제안하며, 이는 서로 다른 공리적 비례성 정의와 규칙 적응으로 이어집니다.

2.1 대칭적 효용 모델 (The Symmetric Utility Model)

이 모델에서 유권자는 승인된 후보자를 선출하는 것과 반대하는 후보자를 배제하는 것으로부터 동일한 효용을 얻습니다.

공식화: 저자들은 모든 실제 후보자 $c$ 에 대해 "가상 음성 후보자"( $\neg c$ )를 도입합니다. 실행 가능한 결과는 각 후보자에 대해 $\{c, \neg c\}$ 중 정확히 하나를 선택해야 하며, 이때 최대 $k$ 개의 양성 후보자만을 선택한다는 제약을 따릅니다.
비례성 공리: 논문은 유권자 집단 $S$ $S$ 에 대한 ** $\ell$ $ℓ$ -응집성( $\ell$ $ℓ$ -cohesiveness)**을 정의합니다. 집단은 그 크기가 전체 유권자 대비 정당한 수준이라면, 공통적으로 승인된 후보들( $A_S$ $A_{S}$ )과 공통적으로 반대하는 후보들( $D_S$ $D_{S}$ )로부터 얻는 "공통 만족"에 대해 비례적인 몫을 가질 자격이 있습니다.
- 비례적 정당 대표성 (PJR): 집단 전체가 비례적인 대표 몫을 얻도록 보장합니다.
- 비례성 정도 (Proportionality Degree): 집단의 평균 만족도를 높게 보장합니다.
규칙 적응:
- Phragmén의 규칙: 유권자가 축적된 예산을 후보자를 선출하거나, 혹은 거부(후보의 음성 대응물을 구매)하는 데 사용할 수 있도록 적응되었습니다.
- Proportional Approval Voting (PAV): 총 "만족된" 후보자(선출된 양성 또는 배제된 음성)의 수를 기반으로 조화 점수(harmonic scores)의 합을 최대화하도록 적응되었습니다.

2.2 비대칭적 효용 모델 (The Asymmetric Utility Model)

이 모델에서 유컷자는 주로 대표되는 것에 관심을 둡니다. 반대 투표는 원치 않는 후보자의 당선을 방해하는 역할만 할 뿐, 선호하는 후보자를 선출하는 것과 동등한 직접적인 효용을 생성하지 않습니다.

공식화: 양성 투표와 음성 투표는 별개로 취급됩니다. 대표권을 갖는 권리는 차단할 권리와 구별됩니다.
비례성 공리:
- 확장된 정당 양성 대표성 (EJPR) / PJPR: 표준 EJR/PJR과 유사하지만, 반대하는 유권자의 존재를 고려하여 조정되었습니다. 집단 $S$ 는 반대하는 유권자의 거부권을 극복하고 $\ell$ 명의 대표를 요구할 만큼 충분히 큰 경우 ** $\ell$ -양성-응집적( $\ell$ -positively-cohesive)**이라고 합니다.
- 집단 거부권 (Group Veto): 충분히 큰 집단이 특정 후보 세트 $T$ 에 대해 반대할 경우, $T$ 에서 선출되는 후보의 수를 제한하는 새로운 공리입니다.
규칙 적응:
- Tax-MES 및 Tax-Phragmén: 이 규칙들은 **"반대세(opposition tax)"**를 도입합니다. 후보자 $c$ 를 선출하는 비용은 그 지지자와 반대자의 비율( $p(c) = |A_c| / (|A_c| - |D_c|)$ )에 따라 증가합니다. 이는 지지자들이 강한 반대에 직면한 후보를 선출하는 것을 더 어렵게 만들어, 음성 투표의 영향력을 효과적으로 균형 잡도록 합니다.

3. 주요 기여 및 결과

3.1 대칭적 효용 모델에서의 결과

Phragmén의 규칙: 저자들은 적응된 Phragmén의 규칙이 PJR을 만족하며, 강력하게 $\ell$ -응집적인 집단에 대해 높은 비례성 정도(평균 만족도)를 제공함을 증명합니다. 이 규칙은 다항 시간 내에 실행됩니다.
Proportional Approval Voting (PAV): 논문은 PAV가 최적에 가까운 비례성 보장을 제공한다는 기술적 증명을 제공합니다. 구체적으로, 임의의 $\ell$ $ℓ$ -응집적 집단에 대해 평균 만족도는 최소 $(1 - \epsilon)\ell - 3/2$ $(1 - ϵ) ℓ - 3/2$ 입니다 (여기서 $\epsilon$ $ϵ$ 은 $k$ $k$ 에 의존하는 작은 항).
- 타이트함 (Tightness): 저자들은 반례를 통해 상수 $3/2$ 가 필요함을 입증합니다. 즉, 이 환경에서 PAV는 평균 만족도를 $\ell - 1$ 로 보장할 수 없습니다.
결과 관련 거부 (Outcome-Relevant Vetoes): 저자들은 유권자가 어차피 당선될 가능성이 없는 후보를 차단하기 위해 영향력을 "소비"함으로써, 오히려 선호하는 후보를 선출할 능력을 감소시키는 현상을 식별했습니다. 이를 해결하기 위해 역사실적 거부 삭제 (Counterfactual Veto Deletion, CVD) 및 **최대 거부 삭제 (Maximal Veto Deletion, MVD)**를 제안합니다. 저자들은 표준 PAV와 Phragmén이 이러한 삭제 속성을 자연스럽게 만족하지 못하는 "역사실적 안정성(counterfactually stable)"이 부족함을 보여주고, 낭비되는 거부 영향력을 완화하기 위한 순차적 정교화(예: Sequential Counterfactual Phragmén)를 제안합니다.

3.2 비대칭적 효용 모델에서의 결과

Tax-MES 및 Tax-Phragmén: 저자들은 MES와 Phragmén을 반대세와 함께 적응함으로써, EJPR(Tax-MES의 경우) 또는 PJPR(Tax-Phragmén의 경우)을 집단 거부권 공리와 동시에 만족시킬 수 있음을 보여줍니다.
Thiele 규칙의 불가능성: 일반화된 Thiele 규칙(PAV를 포함하는 클래스)에 관한 중요한 부정적 결과가 제시됩니다. 저자들은 어떠한 일반화된 Thiele 규칙도 EJPR을 만족하면서 동시에 음성 투표를 존중(즉, 집단 거부권과 같은 부정적 보장을 제공)할 수 없음을 증명합니다. 이는 PAV가 양성 및 음성 공정성 기준을 동시에 만족시키기 위해 비대칭 환경으로 자연스럽게 확장될 수 없음을 시사합니다.

4. 의의 및 주장

본 논문은 양성 및 음성 투표가 모두 존재하는 위원회 선거에서 비례적 대표성을 위한 이론적 보장을 제공하는 첫 번째 연구라고 주장합니다. 이 분야의 이전 연구들(예: Talmon 및 Page)은 시뮬레이션에 의존했을 뿐, 표준 규칙들의 공리적 만족을 확립하지 못했습니다.

저자들은 이 연구가 음성 투표를 어떻게 해석해야 하는지에 대한 근본적인 구분을 강조합니다:

대칭적: 차단이 선출만큼 가치 있는 경우. 이는 의견을 집계하는 데 적합합니다 (예: 성명서 또는 정책 선택).
비대칭적: 차단이 방어 기제이지만, 대표성이 주된 목표인 경우. 이는 대표를 선출하는 데 적합합니다 (예: 참여 예산제 또는 입법 기구).

논문은 이진 승인 투표를 넘어선 것이 진정으로 새로운 비례성 문제들을 야기하며, 이를 위해 서로 다른 공리적 프레임워크와 규칙 설계가 필요함을 결론짓습니다. 또한, PAV의 비례성 보장에서 발생하는 간극을 메우고, 매트로이드(matroid)의 교차 관계로 분석을 확장하며, 역사실적으로 안정적인 효율적 계산 가능 규칙을 설계하는 등의 향후 과제를 제시합니다.