독재 체제

Dictatorship mechanism

사회적 선택 이론에서 독재 메커니즘은 가능한 모든 대안 중에서 투표의 결과가 다른 유권자들을 고려하지 않고 미리 결정된 한 사람의 선호도를 반영하는 규칙이다.독재 자체는 실제로 좋은 메커니즘으로 여겨지지 않지만 이론적으로는 중요하다. 애로우의 불가능성 정리에 따르면 적어도 세 가지 대안이 있을 때 독재는 제한 없는 영역, 파레토 효율성, 그리고 무관한 대안들의 독립성을 만족시키는 유일한 순위 투표 제도이다.마찬가지로, 지바드의 정리에 따르면, 적어도 세 가지 대안이 있을 때, 독재정권은 전략을 입증할 수 있는 유일한 규칙이다.

비독재권은 보다 일반적인 투표 규칙의 속성으로, 결과는 모든 개인의 선호도에 의해 영향을 받는다.개인 선호도 P를 가진 단일 유권자 i가 없는 경우 이 속성은 충족되며, 따라서 P는 항상 사회적("당선") 선호도 순서가 됩니다.다시 말해, 개인의 선호도가 항상 우세해서는 안 된다.익명의 투표 시스템(유권자 2명 이상)은 자동으로 비독재적 속성을 충족합니다.

독재정권에는 실제로 유용한 변형이 있다. 즉, 연쇄독재, 무작위독재, 무작위 연쇄독재(아래 참조)다.

형식적 정의

비독재권은 애로우의 불가능성 [1]정리에서 필요한 조건 중 하나이다.사회적 선택과 개인의 가치에서 Kenneth Arrow는 비독재권을 다음과 같이 정의합니다.

헌법 영역의 모든 순서 집합, 그리고 모든 사회 상태 x와 y 쌍에 x P_}) y가 x P y를 의미하도록 {1, ..., n}에는 유권자 i가 없다.

당연히 독재는 비독재권을 만족시키지 못하는 규칙이다.

연쇄 독재

독재체제는 독재자가 가장 선호하는 단일 선택지를 가질 때만 잘 정의된다.독재자가 둘 이상의 최선의 선택지 중에서 무관심할 때, 그 중 하나를 임의로 임의로 선택할 수 있지만, 이것은 파레토 효율적이지 않을 것이다.보다 효율적인 해결책은 첫 번째 독재자의 모든 최선의 선택권 중에서 그들이 가장 선호하는 것을 선택할 수 있는 두 번째 독재자를 임명하는 것이다.만약 두 번째 독재자 역시 둘 이상의 선택지 사이에서 무관심하다면, 세 번째 독재자는 그 중 하나를 선택하는 식이다.이 규칙을 연쇄 [2]: 6 독재라고 합니다.또 다른 이름은 priority mechanism입니다.

우선 순위 메커니즘은 종종 주택 할당 문제에 사용된다.예를 들어, 기숙사 방을 학생들에게 할당할 때, 학생들에게 미리 지정된 우선순위(예: 나이, 성적, 거리 등)에 따라 순서를 정하고, 각 학생들이 사용 가능한 방 중에서 가장 선호하는 방을 선택하게 하는 것이 일반적입니다.

무작위 독재와 무작위 연쇄 독재

독재정권은 명백히 불공평하지만, 그것은 예상대로 공평한 변형을 가지고 있다.랜덤독재(RD) 룰에서는 투표자 중 1명을 랜덤으로 균일하게 선택하고 그 투표자가 가장 선호하는 대안을 선택한다.이것은 무작위 사회적 선택을 위한 일반적인 규칙 중 하나이다.복수 정합성이 있는 단체에서 사용되는 경우, 랜덤 투표라고 불리기도 합니다.

독재와 마찬가지로, 무작위 독재도 무관심의 가능성을 다루어야 한다; 일반적인 해결책은 무작위 우선 순위라고도 불리는 무작위 [2]: 6 연속 독재로 확장하는 것이다.이 메커니즘에서는 유권자의 무작위 배열을 선택하고, 각 유권자는 기존의 대안을 자신이 가장 선호하는 것으로 좁혀 여전히 이용 가능한 것으로 한다.에이전트 간에 분할할 수 없는 개체를 할당하는 일반적인 메커니즘입니다. 임의 우선 순위 항목 할당을 참조하십시오.

특성.

앨런 지바드는 무작위 독재정리를 [3]증명했다.기본 설정이 엄격한 경우 RD가 다음 세 가지 속성을 충족하는 유일한 규칙이라고 합니다.

  • 익명성: 복권은 다른 유권자들 사이에서 미리 차별을 두지 않는다.
  • 강력한 SD 전략성: 에이전트에 의한 잘못된 보고는 확률적으로 약하게 지배되는 결과를 낳습니다.
  • 이전 Pareto 효율성: 최종 결과는 Pareto 효율성입니다.
    • 실제로 엄격한 선호로 인해 RD는 SD 효율성이라는 더 강력한 효율성 특성을 충족합니다. 즉, 결과적인 복권은 확률적으로 우세하지 않습니다.선호도가 약한 RSD는 사후 효율성을 충족하지만 SD 효율에는 위배됩니다.
    • 엄격한 선호에도 불구하고 RD는 PC 효율성이라는 강력한 속성을 위반합니다. 즉, 결과적으로 발생하는 복권은 쌍 비교라는 의미에서 지배될 수 있습니다(각 에이전트에 대해 RD 복권보다 다른 복권이 더 나은 대체 복권을 제공할 가능성이 더 높습니다).

RD는 의제 일관성이라는 특성도 충족시킵니다.다음 [4]속성을 충족하는 유일한 규칙입니다.

  • 강력한 수축 일관성('규칙성'): 임의의 대안을 제거할 경우 확률이 감소할 수 없습니다.
  • 사후 효율화.
  • 무관한 대안의 독립성의 확률론적 버전.

후속 연구는 다양한 [2]: 15 확장뿐만 아니라 대안적인 증거를 제공했다.하나의 불가능한 결과는 정리를 약한 선호로 확장하는 것과 관련이 있다.선호도가 약하기 때문에 적어도 4명의 에이전트와 4개의 대안이 있을 경우 익명성, SD 효율성 및 SD 전략성이 양립할 수 없다는 것이다.증명은 SMT 솔버를 사용하여 도출되었으며 인터랙티브 정리 프로버 Isabelle/HOL에 [5]의해 검증되었다.

RD는 모집단 일관성이라는 공리와 복제 일관성이라는 공리를 충족하지만 구성 일관성을 위반합니다.

계산

RD와 RSD 메커니즘의 실장은 간단합니다.즉, 임의의 투표자 또는 임의의 순열을 선택해, 각 독재자가 최선의 옵션을 선택하도록 하는 것입니다.그러나 때로는 특정 대안이 선택될 확률을 미리 계산하려고 합니다.RD(선호도가 엄격한 경우)에서는 이것도 간단합니다.대안 x가 선택될 확률은 x를 1순위로 하는 유권자 수를 총 유권자 수로 나눈 것과 같습니다.그러나 RSD는 상황이 다릅니다(관심이 없는 경우).

  • 확률 계산은 #P-hard입니다.[6]
  • 지원을 계산하기 위한 효율적인 알고리즘(양수 확률로 선택된 대안)[6]이 있다.
  • 매개 변수화된 복잡성이 다루기 쉬운 알고리즘이 있습니다. 매개 변수는 객체 수, 대안 수 및 유권자 [7]유형 수입니다.
  • 부분 승인 [8]: Appendix 투표의 맥락에서 확률을 계산하는 지수 시간 알고리즘이 있습니다.

레퍼런스

  1. ^ 게임 이론 제2판 길레르모 오웬 Ch 6pp124-5 Axiom 5 학술 프레스, 1982 ISBN0-12-531150-8
  2. ^ a b c Felix Brandt (2017-10-26). "Probabilistic Social Choice". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN 978-1-326-91209-3.
  3. ^ Gibbard, Allan (1977). "Manipulation of Schemes that Mix Voting with Chance". Econometrica. 45 (3): 665–681. doi:10.2307/1911681. ISSN 0012-9682. JSTOR 1911681.
  4. ^ Pattanaik, Prasanta K.; Peleg, Bezalel (1986). "Distribution of Power under Stochastic Social Choice Rules". Econometrica. 54 (4): 909–921. doi:10.2307/1912843. ISSN 0012-9682. JSTOR 1912843.
  5. ^ Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian (2018-01-31). "Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving". Journal of the ACM. 65 (2): 6:1–6:28. arXiv:1604.05692. doi:10.1145/3125642. ISSN 0004-5411. S2CID 1135734.
  6. ^ a b Aziz, Haris; Brandt, Felix; Brill, Markus (2013-12-01). "The computational complexity of random serial dictatorship". Economics Letters. 121 (3): 341–345. arXiv:1304.3169. doi:10.1016/j.econlet.2013.09.006. ISSN 0165-1765. S2CID 14384249.
  7. ^ Aziz, Haris; Mestre, Julián (2014-11-01). "Parametrized algorithms for random serial dictatorship". Mathematical Social Sciences. 72: 1–6. arXiv:1403.0974. doi:10.1016/j.mathsocsci.2014.07.002. ISSN 0165-4896. S2CID 6719832.
  8. ^ Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). "Collective choice under dichotomous preferences". Journal of Economic Theory. 122 (2): 165–184. doi:10.1016/j.jet.2004.05.005. ISSN 0022-0531.