기술적 요약: 부분 순서를 통한 투표 – 다수결 및 반다수결 계급

1. 문제 제기

본 논문은 고전적 사회선택 이론에서 사용되는 표준적인 선형 순서(완전한 순위) 대신 엄격한 부분 순서로 표현된 개인적 선호를 다룰 때의 집단 의사결정 문제를 다루고 있다. 많은 실제 시나리오에서 유권자에게 대안의 큰 집합을 완전히 순위 매기도록 요구하는 것은 지나치게 부담스럽다. 부분 순서는 유권자가 일부 쌍에 대해서는 엄격한 선호를 표현하면서도 다른 쌍에 대해서는 무관심하거나 비교할 수 없음을 허용한다.

핵심적인 과제는 잘 알려진 다수결 규칙(가장 빈번하게 최상위 순위로 지정된 대안을 선택) 과 반다수결 규칙(가장 빈번하게 최하위 순위로 지정된 대안을 선택하며, 거부권 (Veto) 으로도 알려짐) 을 이 영역으로 확장하는 것이다. 주요 어려움은 부분 순서에서 유권자가 여러 개의 "최상위" 대안(그것들보다 선호되지 않는 대안) 이나 여러 개의 "최하위" 대안(그것들보다 선호되지 않는 대안) 을 가질 수 있으며, 이러한 집단의 구조는 유권자 간에 현저히 다를 수 있다는 점이다. 본 논문은 이러한 표준 규칙들을 부분 순서로 일반화하는 자연스러운 투표 규칙의 계급들을 식별하고 공리적으로 특징짓는 것을 목표로 한다.

2. 방법론

저자들은 무한한 유권자 우주에서 임의의 유한 부분집합이 참여할 수 있는 가변 유권자 집단 모델 내에서 공리적 접근법을 채택한다.

모델

• 대안: $|A| = m \geq 3$인 유한 집합 $A$.
• 선호: 엄격한 부분 순서 $\succ$(비반사적, 반대칭적, 추이적).
• 주요 집합:
  • $T(\succ)$: 최상위 대안의 집합 (극대 원소).
  • $B(\succ)$: 최하위 대안의 집합 (극소 원소).
  • $NT(\succ)$ 및 $NB(\succ)$: 각각 최상위가 아닌 집합과 최하위가 아닌 집합.
• 투표 규칙: 부분 순서 프로필을 비어 있지 않은 승리 대안 집합으로 매핑하는 함수.

점수 규칙

본 논문은 대안의 점수가 선호도 그래프 내에서의 위치에만 의존하는 위치 기반 점수 규칙에 초점을 맞춘다. 저자들은 최상위 및 최하위 집합에 점수가 할당되는 방식에 따라 몇 가지 규칙 계급을 정의한다:

1. 다수결 계급: 최상위가 아닌 대안은 상수 점수 $k'$를 받고, 최상위 대안은 $\geq k'$의 점수를 받으며, 적어도 하나의 최상위 대안은 엄격하게 더 많은 점수를 받는다.
2. 간단한 다수결 계급: 모든 최상위 대안은 동일한 점수 $k$를 받는다.
3. 단조로운 간단한 다수결 계급: 최상위 집합의 크기가 감소함에 따라 최상위와 최상위가 아닌 대안 간의 점수 차이가 증가한다(더 "결단력 있는" 최상위 순위를 보상).
4. 균일 다수결 규칙: 모든 최상위 대안은 1 점, 모든 최상위가 아닌 대안은 0 점을 받는 특정 규칙.
5. 반다수결 계급: 최하위 집합에 초점을 맞춰 대칭적으로 정의됨 (최하위가 아닌 대안은 점수 $k$를 받고, 최하위 대안은 $\leq k$의 점수를 받음).

공리

특징짓는 작업은 부분 순서에 맞게 조정된 표준 공리들과 승인 투표에서 영감을 받은 새로운 공리들의 집합에 의존한다:

• 표준: 무명성 (Anonymity), 중립성 (Neutrality), 강화 (Reinforcement, 일관성), 연속성 (Continuity).
• 반응성: 부분 충실성 (단일 유권자가 최상위를 선택), 충실성 (단일 유권자가 정확히 최상위를 선택), 부분 회피성 (단일 유권자가 모든 최하위를 선택하지 않음), 회피성 (단일 유권자가 최하위를 선택하지 않음).
• 합동성: T-합동성 ($x$를 최상위로 순위 매기지 않는 유권자를 추가하는 것이 $x$의 승리를 초래해서는 안 됨) 과 B-합동성 ($x$를 최하위로 순위 매기지 않는 유권자를 추가하는 것이 $x$의 패배를 초래해서는 안 됨).
• 축소/확장: 유권자가 최상위 집합을 축소하거나 최하위 집합을 확장할 때 결과가 어떻게 변하는지에 대한 제약.
• 기술적 속성: 최상위-의존성 (Tops-Only) 과 최하위-의존성 (Bottoms-Only)(결과가 최상위/최하위 집합에만 의존함).

3. 주요 기여 및 결과

점수 규칙의 특징짓기

정리 1은 무명성, 중립성, 강화, 연속성을 만족하는 투표 규칙이 위치 기반 점수 규칙인 것과 동치임을 확립한다. 이는 Young(1975) 의 고전적 결과를 부분 순서 영역에 맞게 조정한 것이다.

다수결 계급

본 논문은 다수결 계급에 대한 공리적 특징짓기를 제공한다:

• 정리 2: 규칙이 다수결 계급에 속할 필요충분조건은 무명성, 중립성, 강화, 연속성, 부분 충실성, 그리고 T-합동성을 만족하는 것이다.
• 계 3: 간단한 다수결 계급은 부분 충실성을 충실성으로 대체함으로써 특징지어진다.
• 정리 4: 단조로운 간단한 다수결 계급은 간단한 다수결 계급의 공리에 축소 공리를 추가함으로써 특징지어진다.
• 정리 6: 균일 다수결 규칙은 무명성, 중립성, 강화, 부분 충실성, 그리고 강한 축소에 의해 특징지어진다. 이 증명은 강한 축소가 최상위-의존성을 함의하여 문제를 선형 순서 사례로 축소시키고, 여기서 Sekiguchi(2012) 의 특징짓기가 적용됨을 보여준다.

반다수결 계급

반다수결 계급에 대해 대칭적인 결과가 제공된다:

• 정리 9: 규칙이 반다수결 계급에 속할 필요충분조건은 무명성, 중립성, 강화, 연속성, 부분 회피성, 그리고 B-합동성을 만족하는 것이다.
• 계 10: 간단한 반다수결 계급은 부분 회피성을 회피성으로 대체함으로써 특징지어진다.
• 정리 11: 단조로운 간단한 반다수결 계급은 확장 공리를 추가함으로써 특징지어진다.
• 정리 13: 균일 반다수결 규칙은 무명성, 중립성, 강화, 부분 회피성, 그리고 강한 확장에 의해 특징지어진다.

공리의 독립성

저자들은 이러한 특징짓기에 사용된 공리들의 논리적 독립성을 증명한다(명제 7, 8, 14, 15). 이는 모든 공리를 만족하지만 하나만 제외하는 반례 규칙들을 구성함으로써 이루어진다. 특히, 연속성이 부분 순서 설정에서 다수결 및 반다수결 계급의 특징짓기에 필수적임을 강조한다. 이는 종종 표준 선형 순서 다수결 규칙 (예: Ching, 1996) 에서는 불필요한 것으로 간주된다. 이러한 필요성은 부분 순서에서 최상위/최하위 집합의 다양한 구조가 연속성 없이는 T-합동성 및 축소와 같은 공리들을 덜 제한적으로 만들기 때문에 발생한다.

승인 투표에의 적용

본 논문은 그 결과들이 승인 투표에 적용됨을 보여준다. 여기서 투표지는 모든 대안을 포괄하는 서로소인 최상위 및 최하위 집합을 가진 부분 순서이다 ($T(\succ) \cap B(\succ) = \emptyset$ 그리고 $T(\succ) \cup B(\succ) = A$).

• 계 16: 승인 집합의 크기에 따라 점수가 결정되는 크기 기반 승인 투표 규칙은 단조로운 간단한 다수결 계급의 공리 (부분 충실성 포함) 로 특징지어진다.
• 계 17 및 18: 표준 승인 투표 규칙은 각각 균일 다수결 규칙과 균일 반다수결 규칙의 공리에 의해 특징지어진다.
• 계 19: "반-크기" 승인 규칙 (더 큰 승인 집합을 선호) 은 단조로운 간단한 반다수결 공리에 의해 특징지어진다.

4. 중요성 및 주장

본 논문은 부분 순서 영역에 대한 다수결 유사 및 반다수결 유사 규칙에 대한 최초의 공리적 특징짓기를 제공한다고 주장한다. 그 중요성은 다음과 같다:

1. 일반화: "최상위"와 "최하위"가 단일 원소가 아닌 집합인 설정으로 다수결 및 반다수결의 직관적 논리 (최상위 및 최하위 위치에 초점) 를 성공적으로 확장하여, 부분 순서의 구조적 풍부함을 존중한다.
2. 통합: 선형 순서, 부분 순서, 승인 투표에 걸친 이러한 규칙들에 대한 이해를 통합한다. 저자들은 선형 순서에 대한 그들의 특징짓기가 확립된 문헌 결과와 수렴하여 일반화를 검증한다고 지적한다.
3. 승인 투표에 대한 새로운 통찰: 부분 순서 프레임워크에서 이러한 결과를 유도함으로써, 본 논문은 승인 투표 문헌에서 종종 암묵적으로 가정되는 "최상위-의존성" 가정에 직접 의존하지 않고, 표준 및 크기 기반 승인 투표 규칙에 대한 새로운 독립적인 공리적 특징짓기를 제공한다.
4. 영역의 미묘함: 결과는 부분 순서를 통한 투표의 특정 미묘함, 특히 선형 순서 사례와 구별되는 더 넓은 맥락에서 연속성 공리의 필요성을 보여준다.

저자들은 다수결 및 반다수결에 초점을 맞췄지만, 그들의 프레임워크가 보르다 (Borda), 누적 (Cumulative), 단계별 (Stepwise) 등 다른 점수 규칙들의 부분 순서 영역으로의 유사한 일반화를 위한 문을 연다고 결론지었다.