기바르-사테르스와이트 정리

사회적 선택 이론에서 기브바드-사터스와이트 정리는 1973년^[1] 철학자 앨런 기브바드와 1975년 경제학자 마크 새터스와이트가 독자적으로 발표한 결과다.^[2] 단일 당선자를 선택하는 결정론적 서열적 선거제도를 다룬다. 그것은 모든 투표 규칙에 대해 다음 세 가지 중 하나를 보유해야 한다고 명시하고 있다.

1. 이 규칙은 독재적이다. 즉, 승자를 선택할 수 있는 저명한 유권자가 존재한다.
2. 이 규칙은 가능한 결과를 두 가지 대안에만 국한한다.
3. 이 규칙은 전술적 투표에 취약하다. 특정 상황에서 유권자의 성실한 투표는 자신의 의견을 가장 잘 방어하지 못할 수 있다.

이 정리의 범위는 서수 투표에 한정되어 있지만, 기브바드의 정리는 서수가 아닐 수도 있는 집단 결정 과정, 예를 들어 유권자가 후보자에게 등급을 부여하는 투표 시스템을 다룬다는 점에서 더 일반적이다. 기바드의 1978년 정리나 힐랜드의 정리는 더욱 일반적이며 이러한 결과를 비결정론적 과정, 즉 그 결과가 유권자의 행동에 달려 있을 뿐만 아니라 운명의 일부도 수반할 수 있는 과정으로 확장한다.

비공식 설명

$앨리스$, 밥$,$ $캐롤$이라는 세 명의 유권자를 생각해 보십시오$.$ $그들$은 $4명$의 $후보$ 중 $당선자$를 선택하기를 원하는데, $그들$은 보르다 카운트를 사용한다고 가정해보라: 각 유권자들은 후보자들보다 자신의 선호 질서를 전달한다. 각 투표의 경우 1위 후보에게 3점, 2위 후보에게 2점, 3위 후보에게 1점, 마지막 후보에게 0점이 배정된다. 일단 모든 투표용지가 집계되면 가장 많은 점수를 받은 후보가 당선자로 선언된다.

그들의 선호도는 다음과 같다고 가정해 보자.

만약 유권자들이 성실한 투표를 한다면, 점수는 다음과 같다$:{\displaystyle }$ (${\displaystyle 3,}$ $b$: ${\displaystyle 6,}$ ${\displaystyle c}$: ${\displaystyle 7,}$ d${\displaystyle }$: ${\displaystyle 2}$) ${\displaystyle (a:3,b:6,c:7,d:2)}.$ 따라서, $c{\displaystyle }$ ${\displaysty$ c$}$ 후보가 $7점$으로 선출될 것이다$.$

그러나 앨리스는 전략적으로 투표할 수 있고 결과를 바꿀 수 있다. 다음과 같은 상황을 연출하기 위해 그녀가 투표용지를 수정한다고 가정해보자.

앨리스는 전략적으로 $후보{\displaystyle }$b를 $업그레이드$하고 후보$$ $c$를 $다운그레이드했다$ 이제 점수는 다음과 같다:${\displaystyle }$(${\displaystyle \mathrm{a}}$: 2${\displaystyle }$,$$: 7${\displaystyle }$, ${\displaystyle \mathrm{c}}$: 6${\displaystyle }$, ${\displaystyle d}$: ${\displaystyle 3}$) ${\displaystyle (a:2,b:7,c:6,d:3$) . $따라서{\displaystyle }$ b ${\displaysty$ b$}$이 선출된다$.$ 앨리스는 투표 결과 $b$를$c$보다 $선호$하기 때문에 자신의 투표 수정에 만족하고 $있는데$ 이것은 그녀가 성실하게 투표할 경우 얻을 수 있는 $결과물이다.$

우리는 보르다 카운트가 조작할 수 있다고 말한다: 성실한 투표권이 유권자의 선호를 가장 잘 방어하지 못하는 상황이 있다.

기바드-새터트웨이트의 정리는 모든 투표 규칙은 조작할 수 있다고 명시하고 있는데, 두 가지 경우를 제외하고, 독재적인 권력을 가진 저명한 유권자가 있는 경우 또는 그 규칙이 가능한 결과를 두 가지 선택사항으로만 제한하는 경우일 수 있다.

형식명세서

반드시 사람이 아니더라도 A ${\$을(를) 대안 집합(한정으로 가정)으로$$ 하고 후보라고도 함: 주어진 문제에 대해 몇 가지 가능한 결정이 될 수도 있다. $N{\displaystyle \mathcal{}}$=${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle }$… , ${\displaystyle n}$}$${\$displaystyle${\$mathcal{N}=\{1,\ldots,n\}}}$을(를) 투표자 집합으로$$ 나타낸다. $P{\displaystyle \mathcal{}}$ ${\$을(를) $A{\displaystyle \mathcal{}}$ ${\$에 대한 엄격한 미약 주문 집합으로$$ 두십시오$.$ 이 집합의 요소는 유권자의 선호를 나타낼 수 있으며, 유권자는 일부 대안들의 순서에 대해 무관심할 수 있다. A voting rule is a function ${\displaystyle f:{\mathcal {P}}^{n}\to {\mathcal {A}}}$. Its input is a profile of preferences ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$ and it yields the identity of the winning candidate.

We say that ${\displaystyle f}$ is manipulable if and only if there exists a profile ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$ where some voter ${\displaystyle i}$, by replacing her ballot ${\displaystyle P_{i}}$ with another ballot ${\dis$$Playstyle P_{i}'}$는 그녀가 선호하는 결과를 얻을 수 있다($$${\displaystyle P_{}}$ i ${\$

$f$(${\displaystyle P^{}}$n${\displaystyle {}^{}}$) ${\$$displaystyle$ $f({\mathcal{P}^{n$$}})$의 이미지$$$,$ 즉 선거에 사용할 수 있는 결과의 집합을 가리킨다. 예를 들어, $f{\displaystyle ({\mathcal{}}^{}}$ ${\displaystyle n^{}}$) ${\displaystyle f({\mathcal{P}^{n}})$의 카디널리티가 3 이상일$$ 경우에만 $f{\displaystyle }$ ${\displaystyle f}$이(가) 최소한 세 가지 가능한 결과를 가지고$$ 있다고 말한다.

우리는 승리하는 대안이 다른 유권자들의 선호와 상관없이 가능한 결과들 중에서 항상 그녀의 가장 인기 있는 대안이라는 점에서 독재자 $i$가 $존재$하는 경우에만 $f{\displaystyle }$ ${\displaystyle$ $f$$}$가 독재적이라고 말한다. 만약 독재자가 가능한 결과들 중에서 가장 인기 있는 몇 가지 대안들을 가지고 있다면, 승리하는 대안들은 단지 그것들 중 하나일 뿐이다.

예

연쇄독재

연쇄독재는 다음과 같이 정의된다. 만약 유권자 1이 독특한 가장 인기 있는 후보를 가지고 있다면, 이 후보가 선출된다. 그렇지 않으면, 가능한 결과는 가장 인기 있는 후보들로 제한되는 반면, 다른 후보자들은 탈락한다. 그런 다음 유권자 2의 투표 용지를 조사한다. 투표에서 제외되지 않은 후보 중에서 가장 잘 알려진 후보가 있다면, 이 후보가 선출된다. 그렇지 않으면 가능한 결과의 목록이 다시 감소한다. 모든 투표 용지를 검토한 후에도 몇 명의 비탈당 후보가 남아 있는 경우, 임의의 동점 처리 규칙을 사용한다.

이 투표 규칙은 조작할 수 없다: 유권자는 항상 자신의 성실한 선호를 전달하는 것이 더 낫다. 그것은 또한 독재적이며, 그것의 독재자는 유권자 1이다: 승리하는 대안은 항상 특정 유권자의 가장 많은 관심을 받는 대안이거나, 만약 가장 많은 관심을 받는 대안이 있다면, 그들 중에서 선택되는 것이다.

단순다수투표

만약 두 가지 결과만 있을 경우, 투표 규칙은 독재적이지 않고 통제할 수 없을 수도 있다. 예를 들어, 단순 다수결의 경우, 각 투표자는 자신의 상위 대안에 1점, 다른 대안에 0점을 할당하고, 대부분의 대안이 승자로 선언된다.(두 대안이 동일한 수치에 도달하면, 임의적이지만 결정론적인 방식으로 동점이 깨진다$$(예: 결과: ${\displaysty a}).$.) 유권자는 항상 자신의 성실한 선호를 전달하는 것이 더 낫고, 독재적이지 않기 때문에 이 투표 규칙은 조작할 수 없다. 예를 들어, 많은 다른 규칙들은 조작할 수도 없고 독재적이지도 않다$.$ 예를 $들어$$,$ 대안 a가 2/3의 표를$$ 얻으면$승리$하고 b가 그렇지 $않으면$ 승리한다고$$ 가정한다.

컨버터가 보관되지 않는 게임 양식

다음 규칙을 고려하십시오. 유권자 1의 투표에서 1위를 차지한 후보나 후보를 제외한 모든 후보가 탈락한다. 그러면 탈락하지 않은 후보 중에서 보르다 카운트를 이용해서 한 명이 당선된다. 이 모든 과정은 정의상 독재적이다. 그러나, 일반적인 보르다 카운트와 같은 이유로 조작이 가능하다. 따라서 기바르-사테르스와이트의 정리는 함축성이며 등가성이 아니다.

코롤라리

이제 우리는 두 후보 사이에 유권자가 무관심할 수 없는 경우를 가정해 본다. We denote by ${\displaystyle {\mathcal {L}}}$ the set of strict total orders over ${\displaystyle {\mathcal {A}}}$ and we define a strict voting rule as a function ${\displaystyle f:{\mathcal {L}}^{n}\to {\mathcal {A}}}$. The definitions of possible outcomes, manipulable, dictatorial have natur이 틀에 대한 적응

엄격한 투표 규칙을 위해, 기바드-사터스와이트 정리의 역행은 사실이다. 사실, 엄격한 투표 규칙은 만약 그것이 가능한 결과들 중에서 항상 가장 인기 있는 독재자 후보를 선택하는 경우에만 독재적이다; 특히, 그것은 다른 유권자들의 투표에 의존하지 않는다. 결과적으로, 그것은 조작할 수 없다: 독재자는 그녀의 성실한 투표에 의해 완벽하게 방어되고, 다른 유권자들은 결과에 영향을 주지 않기 때문에 그들은 성실한 투표에서 벗어날 동기가 없다. 따라서 우리는 다음과 같은 동등성을 얻는다.

정리에서는 물론 각론에서도 어떤 대안도 선출할 수 있다고 가정할 필요는 없다. 이들 중 적어도 3명이 승리할 수 있다고 가정할 뿐이다. 즉, 투표 규칙의 가능한 결과들이다. 어떤 상황에서도 다른 대안이 선출될 수 있는 것은 가능하다: 정리나 관록은 여전히 적용된다. 그러나 때로는 덜 일반적인 형태로도 제시된다.^[3] 규칙에는 최소한 세 가지 가능한 결과가 있다고 가정하는 대신, $A{\displaystyle \mathcal{}}$ ${\${\$mathcal{A}}$에 최소한 세 가지 요소가$$ 포함되어 있고 투표 규칙이 적용되어 있다고 가정하는 경우도 있다. 즉, 모든 대안이 가능한 결과라고 할 수 있다.^[4] 잘 알고 있다는 가정은, 모든 유권자들이 같은 후보를 선호한다면, 그녀가 선출되어야 한다는 점에서, 때로는 그 규칙이 만장일치라는 가정으로 대체되기도 한다.^[5][6]

증거 스케치

기바드-사터스와이트 정리는 단순히 당선자를 선택하는 것이 아니라 사회순위 기능, 즉 후보자의 완전한 선호 질서를 산출하도록 고안된 투표 시스템을 다루는 화살의 불가능성 정리에 근거해 증명할 수 있다. 우리는 투표 규칙 $f{\displaystyle }$ ${\displaystyle f}$이(가) 만장일치로 가정된$$ 단순화된 사례에서 증거의 스케치를 제공한다. 다음과 같은 소셜 순위 ${\displaystyle \mathrm{함수}}$ Lank$${\$displaystyle \operatorname {Lank$을(를) 구축할 수 있다.${\displaystyle \mathrm{bb}}${\$displaystyle$ a$\prec$b$\},$ ${\displaystyle \mathrm{Lank}}$ ${\displaysty \operatorname {Lank},$} 함수가 ${\displaysty$ $a}$ 및$$ $}$을(을) 이동시키는 새로운 기본 설정을 생성한다.o 모든 유권자의 선호도 중 으뜸 ${\displaystyle \mathrm{그런}}$ 다음 랭크$${\$displaystyle \operatorname {Lank}$에서 f {\$displaystyle$ f}이$(가)$ ${\displaystyle a}$ 또는$$ $b{\displaystyle }$ ${\displaysty b}$을(를) 선택하는지 검사하십시오$.$ $만약{\displaystyle }$ f ${\displaystyle$ f$}$이(가) 비조작적이고 비독재적인 것이라면$$ ${\displaystyle \mathrm{랭크}}$ ${\displaystyle \operatorname {Lank}}$은(는) 만장일치, 관련 없는 대안의 독립성, 그리고$$ 독재가 아니라는 것을 증명할 수 있다. Arrow의 불가능성 정리는 대안이 3개 이상일 때 ${\displaystyle \mathrm{Lank}}$ ${\displaystyle \operatorname {Lank} }$함수와$$ 같은 함수는 존재할 수 없다고 말한다. 따라서 그러한 투표 규칙 $f{\displaystyle }$ ${\displaystyle f}$도 존재할 수 없다.^{[7]: 214–215}

역사

투표의 전략적 측면은 이미 1876년 사회 선택 이론의 선구자인 루이스 캐롤로도 알려진 찰스 도그슨에 의해 주목을 받고 있다. 그의 인용(특정 투표 시스템에 관한 것)은 던컨 블랙에 의해 유명해졌다.^[8]

투표의 이 원칙은 선거를 실제 선거자들의 희망에 대한 시험이라기 보다는 실력 놀이로 만든다.

1950년대에 로빈 파콰르손은 투표 이론에 관한 영향력 있는 기사를 발표하였다.^[9] 마이클 더밋과의 기사에서, 그는 적어도 3개의 이슈를 가진 결정론적 투표 규칙이 고질적인 전술적 투표에 직면해 있다고 추측한다.^[10][11] 이 파르콰르손-덤메트 추측은 앨런 기바드와 마크 새터스와이트에 의해 독립적으로 증명되었다. 1973년 기사에서 기바드는 우리가 지금 기바드의 정리라고 알고 있는 결과를 증명하기 위해 1951년부터 화살의 불가능한 정리를 악용하고, 그 후 그는 현재의 결과를 추론하고, 이것이 바로 그 결과인 것이다.^[1] 사터스와이트는 독립적으로 1973년 박사학위 논문에서도 같은 결과를 입증한 뒤 1975년 기사로 발표한다.^[2] 그의 증명도 화살의 불가능 정리에 바탕을 두고 있지만, 기바드의 정리가 부여한 보다 일반적인 버전은 노출시키지 않는다. 나중에, 몇몇 저자들은 우리가 위에서 언급한 정리 그 자체나 골격과 약화된 버전을 위해 일반적으로 더 짧은 증명의 변형들을 개발한다.^{[4][5][6][12][13][14][15][16][17]}

관련결과

기바드의 정리는 순서형이 아닐 수 있는 집단 선택의 과정, 즉 유권자의 행동이 후보들에 대한 선호 질서를 전달하는 데 있지 않을 수 있는 과정을 다룬다. 기바드의 1978년 정리 및 힐랜드의 정리는 이러한 결과를 비결정론적 메커니즘, 즉 투표에 따라 결과가 좌우될 뿐만 아니라 운명의 일부도 수반할 수 있는 것으로 확장한다.

듀건-슈워츠 정리는^[18] 단일 승자가 아닌 후보 중 비어 있지 않은 부분 집합을 선택하는 결정론적 투표 규칙을 다루면서 이 결과를 다른 방향으로 확장시킨다.

후세

기바드-새터트웨이트 정리는 일반적으로 사회 선택 이론의 분야에 속하는 결과로서, 투표 시스템에 적용되는 결과로 제시되지만, 그것은 또한 집합적인 의사결정을 하기 위한 규칙을 구상하는 것을 다루는 메커니즘 설계의 정석적인 결과로서도 볼 수 있다, 아마도 금전적 이전을 수반하는 과정에서는 말이다. 노암 니산(^{[7]: 215} Noam Nisan)은 이러한 관계를 다음과 같이 설명한다.

GS의 정리는 인센티브와 호환되는 사회적 선택 기능을 설계할 수 있는 어떤 희망도 잠재우는 것처럼 보인다. 메커니즘 설계의 전체 분야는 모델의 다양한 수정을 사용하여 이 불가능한 결과로부터 탈출하려고 시도한다.

이러한 '탈출 경로'의 주요 개념은 임의의 선호를 다루는 기브바드-사터스와이트 정리와는 대조적으로, 제한된 계급의 선호만을 다룬다는 것이다. 예를 들어, 이 분야에서는 흔히 대리인이 준선형 선호를 가지고 있다고 가정하는데, 이는 그 효용함수가 돈에 선형적으로 의존한다는 것을 의미한다. 그럴 경우 금전적 이전을 통해 진실된 행동을 유도할 수 있다. 이것이 비크리-클라크-그로브스 경매의 성공 배경이다.

참고 항목

• 기바드의 정리
• 화살의 불가능 정리
• 듀간-슈워츠 정리

참조