Strategy-Proof Probabilistic Social Choice Correspondences under Conditional Expected Utility

기술적 요약: 조건부 기대 효용 하에서의 전략적 무결성을 갖는 확률적 사회 선택 대응관계

문제 정의
본 논문은 단일 대안이 아닌 대안의 비공집합 부분집합에 대한 로터리(lottery)를 할당하는 **확률적 사회 선택 대응관계(Probabilistic Social Choice Correspondences, PSCCs)**의 구조를 조사한다. 본 연구는 두 가지 바람직한 속성인 만장일치성(unanimity)(모든 행위자가 특정 집합을 가장 높게 평가하면, 그 집형이 확률 1로 선택됨)과 전략적 무결성(strategy-proofness)(진실한 보고가 지배 전략임)에 초점을 맞춘다.

분석은 행위자들이 후속적인 타이 브레이킹(tie-breaking) 또는 최종 선택 단계에 대한 자신의 믿음에 기초하여 선택된 집합을 평가하는 조건부 기대 효용(Conditional Expected Utility, CEU) 프레임워크 하에서 수행된다. 본 논문은 Barbera et al. (2001)이 도입한 두 가지 선호 영역을 검토한다:

1. CEUC (조건부 기대 효용 일관적): 행위자들은 선택될 대안들의 가능성에 대한 주관적 평가(믿음)를 가진다.
2. CEUCEP (동등한 확률을 가진 조건부 기대 효용 일관적): 행위자들은 선택된 집합 내의 모든 대안이 최종 결과로서 동일한 확률을 가진다고 간주한다.

중심 연구 질문은 대안의 집합에 대해 무작위화를 허용하는 것(PSCCs)이 결정론적 전략적 무결 대응관계(DSCCs)의 볼록 외포(convex hull)를 넘어 전략적 무결한 규칙의 클래스를 확장하는지, 아니면 확률적 규칙이 단순히 결정론적 규칙들에 대한 로터리로 환원되는지 여부이다.

방법론 및 프레임워크
저자들은 $n$ 명의 행위자와 $m$ 개의 대안($m \ge 3$)을 가진 사회 선택 환경을 정식화한다.

• 선호: 행위자들은 효용 함수 $v$와 평가 $\lambda$로부터 유도된 대안의 비공집합 부분집합에 대한 선호를 가진다. CEUC 영역에서 $\lambda$는 주관적이며, CEUCEP 영역에서 $\lambda$는 균등하다.
• 전략적 무결성: **제1차 확률 우위(First-Order Stochastic Dominance, FOSD)**를 통해 정의된다. 행위자는 진실하게 보고했을 때의 로터리와 잘못 보고했을 때의 로터리를 비교한다. 이 정의는 행위자의 집합에 대한 서수적 선호에 의존하며, 이는 표현 독립적(즉, 보고된 선호를 생성하는 모든 효용/평가 쌍에 대해 성립함)임을 보장한다.
• 분석적 접근: 저자들은 행위자 수에 대한 귀납법을 사용하고, 확률 분포의 지지 집합(support)을 제한하기 위해 특정 구조적 보조정리를 활용한다. 주요 도구는 다음과 같다:
  • 만장일치적이고 전략적 무결한 PSCC는 반드시 tops-only(결과가 행위자들의 최상위 순위 집합에만 의존함)여야 함을 확립한다.
  • 로터리의 지지 집합이 행위자들의 최상위 집합들의 합집합 내의 **단원 집합(singletons) 및 이원 집합(doubletons)**으로 제한됨을 증명한다.
  • 확률 값들 사이의 모순이나 등식을 도출하여 허용 가능한 규칙을 규명하기 위해 특정 선호 프로필을 구성한다.

주요 결과 및 특징

본 논문은 두 영역에 걸쳐 만장일치적이고 전략적 무결한 PSCC에 대한 완전한 특성화를 제공하며, 무작위화의 영향이 영역에 따라 다름을 밝힌다.

1. CEUC 영역 (주관적 평가)

• 결과: CEUC 영역에서의 모든 만장일치적이고 전략적 무결한 PSCC는 **무작위 독재 규칙(Random Dictatorial Rule)**이다.
• 시사점: 규칙이 임의의 대안 집합에 대해 무작위화를 허용하더라도, 전략적 무결성과 만장일치성은 확률 질량이 행위자들이 최상위로 평가하는 단원 집합에만 배정되도록 강제한다. 집합에 대한 무작위화는 추가적인 유연성을 제공하지 못하며, 규칙의 클래스는 표준적인 무작위 독재(Gibbard, 1977)로 축소된다.

2. CEUCEP 영역 (동등한 확률)
이곳의 특성화는 행위자 수($n$)와 대안 수($m$)에 따라 더 미묘하게 달라진다.

• 경우 A: $n \le 3$ (모든 $m \ge 3$)

  • 결과: 규칙의 클래스는 정확히 **무작위 이중 독재 규칙(Random Bi-dictatorial Rules)**의 집합이다.
  • 정의: 이들은 두 행위자의 최상위 집합의 합집합을 선택하는 결정론적 이중 독재 규칙들의 볼록 결합이다.
  • 시사점: 소규모 사회에서 확률적 규칙은 새로운 구조를 생성하지 않으며, 단지 결정론적 이중 독재에 대한 로터리일 뿐이다.

• 경우 B: $n \ge 4$ 이고 $m = 3$ 인 경우

  • 결과: 규칙의 클래스는 **연합 가중 규칙(Coalition-Weighted Rules)**으로 확장된다.
  • 정의: 이 규칙들은 대안을 지지하는 연합의 크기와 구성에 따라 확률을 할당하는 연합 가중 함수 $v: 2^N \to [0, 1]$에 의해 생성된다. 단원 집합 $\{x\}$의 확률은 $v(N_x)$이고, 이원 집합 $\{x, y\}$의 확률은 $v(N_x \cup N_y) - v(N_x) - v(N_y)$이다.
  • 의의: 이 클래스는 엄격히 더 큰 무작위 이중 독재 규칙의 집합이다. 논문은 결정론적 전략적 무결 대응관계의 볼록 결합으로 쓰일 수 없는 만장일치적이고 전략적 무결한 PSCC의 구체적인 예(예시 3)를 제공한다. 이는 무작위화가 특정 구성에서 진정으로 새로운 규칙의 집합을 넓힐 수 있음을 보여준다.

• 경우 C: $n \ge 4$ 이고 $m \ge 4$ 인 경우

  • 결과: 클래스는 다시 무작위 이중 독재 규칙으로 축소된다.
  • 시사점: 세 개의 대안을 가진 경우에서 관찰된 "추가적인 자유"는 네 개 이상의 대안이 있을 때 사라진다. 논문은 $m \ge 4$인 경우 모든 연합 가중 규칙이 무작위 이중 독재 규칙과 동일함을 증명한다.

의의 및 주장

본 논문은 집합 가치 사회 선택에서 무작위화의 구체적이고 영역 의존적인 역할을 식별했다고 주장한다:

1. 영역 민감성: 무작위화가 일반적인 경우나 CEUC 영역에서는 전략적 무결한 규칙의 클래스를 일반적으로 확장시키지 못하지만, CEUCEP 영역에서는 대안의 수가 정확히 3개이고 행위자의 수가 4명 이상일 때 이를 확장시킨다.
2. 확률적 규칙의 참신성: 저자들은 $m=3, n \ge 4$인 경우, 허용되는 확률적 규칙들이 결정론적 규칙들의 볼록 결합이 아니라는 점을 강조한다. 이는 확률적 메커니즘이 단순히 결정론적 규칙들에 대한 로터리라는 직관에 도전한다.
3. 결정론적 기준과의 연결: 본 논문은 $m=3, n \ge 4$인 경우 확장된 클래스의 결정론적 구성원들이 Barbera et al. (2001)이 특성화한 이중 독재 규칙과 정확히 일치함을 확립한다. 따라서 이 확장은 순수하게 확률적인 현상이다.
4. 구조적 통찰: 본 연구는 $m \ge 4$일 때의 "축소"가 대안의 수에 의해 부과된 구조적 제약임을 명확히 하여, 세 개의 대안을 가진 경우가 연합 가중 규칙이 더 풍부한 구조를 제공하는 예외적인 사례임을 구분한다.

요약하자면, 본 논문은 결정론적 규칙과 확률적 규칙 사이의 관계가 균일하지 않음을 보여준다. 즉, 무작위화는 진정으로 새로운 전략적 무결 대응관계를 생성할 수 있지만, 이 현상은 사회 선택 환경의 특정 매개변수(특히 대안과 행위자의 수) 및 행위자의 선택 과정에 대한 믿음의 성격에 매우 민감하게 반응한다.