Gibbard–Satterthwaite theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 09:58, 11 November 2016

The Gibbard–Satterthwaite theorem, named after Allan Gibbard^[1] and Mark Satterthwaite,^[2] is a result about the deterministic voting systems that choose a single winner using only ballots from voters (with a finite number of possible ballot types). The Gibbard–Satterthwaite theorem states that, for three or more candidates, one of the following three things must hold for every voting rule:

The rule is dictatorial (i.e., there is a single individual who can choose the winner), or
There is some candidate who can never win, under the rule, or
The rule is susceptible to tactical voting, in the sense that there are conditions under which a voter with full knowledge of how the other voters are to vote and of the rule being used would have an incentive to vote in a manner that does not reflect his or her preferences.

Rules that forbid particular eligible candidates from winning or are dictatorial are defective. Hence, every deterministic voting system that selects a single winner either is manipulable or does not meet the preconditions of the theorem.

The theorem does not apply to randomized voting systems, such as the system that chooses a voter randomly and selects the first choice of that voter.

Definitions

A social-choice-function is a function that maps a set of individual preferences to a social outcome. An example function is the plurality function, which says "choose the outcome that is the preferred outcome of the largest number of voters". We denote a social choice function by $\operatorname {Soc}$ and its recommended outcome given a set of preferences by $\operatorname {Soc} (P)$ .

A social-choice function is called manipulable by player $i$ if there is a scenario in which player $i$ can gain by reporting untrue preferences (i.e., if the player reports the true preferences then $\operatorname {Soc} (P)=a$ , if the player reports untrue preferences then $\operatorname {Soc} (P')=a'$ , and player $i$ prefers $a'$ to $a$ ). A social-choice function is called incentive-compatible if it is not manipulable by any player.

A social-choice function is called monotone if, whenever the following is true:

When $i$ has some preferences $P$ , $\operatorname {Soc} (P)=a$ ;
When $i$ has other preferences $P'$ , $\operatorname {Soc} (P')=a'$ ;

Then, under the preferences $P$ , player $i$ prefers outcome $a$ , and under the preferences $P'$ , player $i$ prefers outcome $a'$ . It can be demonstrated that incentive-compatibility and monotonicity are equivalent.^[3]

For example, when there are only two possible outcomes, the majority rule is incentive-compatible and monotone: when a player switches his preference from one option to the other, this can only be better for the other option.

A player $i$ is called a dictator in a social-choice function $\operatorname {Soc}$ if $\operatorname {Soc}$ always selects the outcome that player $i$ prefers over all other outcomes. $\operatorname {Soc}$ is called a dictatorship if there is a player $i$ who is a dictator in it.

Formal statement

If $\operatorname {Soc}$ is incentive-compatible and returns at least three different outcomes, then $\operatorname {Soc}$ is a dictatorship.

Proof

The GS theorem can be proved based on Arrow's impossibility theorem. Arrow's impossibility theorem is a similar theorem that deals with social ranking functions - voting systems designed to yield a complete preference order of the candidates, rather than simply choosing a winner.

Given a social choice function $\operatorname {Soc}$ , it is possible to build a social ranking function $\operatorname {Rank}$ , as follows: in order to decide whether $a\prec b$ , the $\operatorname {Rank}$ function creates new preferences in which $a$ and $b$ are moved to the top of all voters' preferences. Then, $\operatorname {Rank}$ examines whether $\operatorname {Soc}$ chooses $a$ or $b$ .

It is possible to prove that, if $\operatorname {Soc}$ is incentive-compatible and not a dictatorship, then $\operatorname {Rank}$ satisfies the properties: unanimity and independence-of-irrelevant-alternatives, and it is not a dictatorship. Arrow's impossibility theorem says that, when there are three or more alternatives, such a $\operatorname {Rank}$ function cannot exist. Hence, such a $\operatorname {Soc}$ function also cannot exist.^[4]^{: 214–215}

Related results

Taylor (2002, Theorem 5.1)^[5] shows that the result holds even if ties are allowed in the ballots (but a single winner must nevertheless be chosen): for such elections, a dictatorial rule is one in which the winner is always chosen from the candidates tied at the top of the dictator's ballot, and with this modification the same theorem is true.

The Duggan–Schwartz theorem deals with voting systems that choose a (nonempty) set of winners rather than a single winner.

Noam Nisan describes the relation between the GS theorem and mechanism design:^[4]^: 215

"The GS theorem seems to quash any hope of designing incentive-compatible social-choice functions. The whole field of Mechanism Design attempts escaping from this impossibility result using various modifications in the model."

The main idea of these "escape routes" is that they deal only with restricted classes of preferences (in contrast to GS, which deals with arbitrary preferences). For example, suppose that all agents have quasi-linear preferences. This means that their utility function depends linearly on money. This means that monetary transfers can be used to induce them to act truthfully. This is the idea behind the successful Vickrey–Clarke–Groves auction.

History

Robin Farquharson published influential articles on the theory of voting;^[6] in an article with Michael Dummett,^[7] he conjectured that deterministic voting rules with at least three issues faced endemic tactical voting.^[8]

After the establishment of the Farquarson-Dummett conjecture by Gibbard and Sattherthwaite, Michael Dummett contributed three proofs of the Gibbard–Satterthwaite theorem in his monograph on voting.^[9]^[10]

The theorem is also covered by Hervé Moulin.^[11]

References

^ Gibbard, Allan (1973). "Manipulation of voting schemes: A general result". Econometrica. 41 (4): 587–601. doi:10.2307/1914083. JSTOR 1914083.
^ Satterthwaite, Mark Allen (April 1975). "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions". Journal of Economic Theory. 10 (2): 187–217. doi:10.1016/0022-0531(75)90050-2.
^ Muller, Eitan; Satterthwaite, Mark A. (April 1977). "The equivalence of strong positive association and strategy-proofness". Journal of Economic Theory. 14 (2): 412–418. doi:10.1016/0022-0531(77)90140-5.
^ ^a ^b Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
^ Taylor, Alan D. (April 2002). "The manipulability of voting systems". The American Mathematical Monthly. 109: 321–337. doi:10.2307/2695497. JSTOR 2695497.
^ Farquharson, Robin (Feb 1956). "Straightforwardness in voting procedures". Oxford Economic Papers, New Series. 8 (1): 80–89. JSTOR 2662065.
^ Dummett, Michael; Farquharson, Robin (January 1961). "Stability in voting". Econometrica. 29 (1): 33–43. doi:10.2307/1907685. JSTOR 1907685.
^ Dummett, Michael (2005). "The work and life of Robin Farquharson". Social Choice and Welfare. 25 (2): 475–483. doi:10.1007/s00355-005-0014-x. JSTOR 41106711.
^ Dummett, Michael (1984). Voting Procedures. Oxford University Press. ISBN 978-0198761884.
^ Fara, Rudolf; Salles, Maurice (October 2006). "An interview with Michael Dummett: From analytical philosophy to voting analysis and beyond". Social Choice and Welfare. 27 (2): 347–364. doi:10.1007/s00355-006-0128-9. JSTOR 41106783.
^ Moulin, Hervé (1991). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 9780521424585. Retrieved 2016-01-10.

External links

[1] Gibbard, Allan (1973). "Manipulation of voting schemes: A general result". Econometrica. 41 (4): 587–601. doi:10.2307/1914083. JSTOR 1914083.

[2] Satterthwaite, Mark Allen (April 1975). "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions". Journal of Economic Theory. 10 (2): 187–217. doi:10.1016/0022-0531(75)90050-2.

[3] Muller, Eitan; Satterthwaite, Mark A. (April 1977). "The equivalence of strong positive association and strategy-proofness". Journal of Economic Theory. 14 (2): 412–418. doi:10.1016/0022-0531(77)90140-5.

[agt-4] Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[5] Taylor, Alan D. (April 2002). "The manipulability of voting systems". The American Mathematical Monthly. 109: 321–337. doi:10.2307/2695497. JSTOR 2695497.

[6] Farquharson, Robin (Feb 1956). "Straightforwardness in voting procedures". Oxford Economic Papers, New Series. 8 (1): 80–89. JSTOR 2662065.

[7] Dummett, Michael; Farquharson, Robin (January 1961). "Stability in voting". Econometrica. 29 (1): 33–43. doi:10.2307/1907685. JSTOR 1907685.

[8] Dummett, Michael (2005). "The work and life of Robin Farquharson". Social Choice and Welfare. 25 (2): 475–483. doi:10.1007/s00355-005-0014-x. JSTOR 41106711.

[9] Dummett, Michael (1984). Voting Procedures. Oxford University Press. ISBN 978-0198761884.

[10] Fara, Rudolf; Salles, Maurice (October 2006). "An interview with Michael Dummett: From analytical philosophy to voting analysis and beyond". Social Choice and Welfare. 27 (2): 347–364. doi:10.1007/s00355-006-0128-9. JSTOR 41106783.

[11] Moulin, Hervé (1991). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 9780521424585. Retrieved 2016-01-10.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 64: / Line 64: @@
 The GS theorem can be proved based on [[Arrow's impossibility theorem]]. Arrow's impossibility theorem is a similar theorem that deals with '''social ranking functions''' - voting systems designed to yield a complete preference order of the candidates, rather than simply choosing a winner.
-Given a social choice function <math>Soc</math>, it is possible to build a social ranking function <math>Rank</math>, as follows: in order to decide whether <math>a\prec b</math>, the <math>Rank</math> function creates new preferences in which <math>a</math> and <math>b</math> are moved to the top of all voters' preferences. Then, <math>Rank</math> examines whether <math>Soc</math> chooses <math>a</math> or <math>b</math>.
+Given a social choice function <math>\operatorname{Soc}</math>, it is possible to build a social ranking function <math>\operatorname{Rank}</math>, as follows: in order to decide whether <math>a\prec b</math>, the <math>\operatorname{Rank}</math> function creates new preferences in which <math>a</math> and <math>b</math> are moved to the top of all voters' preferences. Then, <math>\operatorname{Rank}</math> examines whether <math>\operatorname{Soc}</math> chooses <math>a</math> or <math>b</math>.
-It is possible to prove that, if <math>Soc</math> is incentive-compatible and not a dictatorship, then <math>Rank</math> satisfies the properties: unanimity and independence-of-irrelevant-alternatives, and it is not a dictatorship. [[Arrow's impossibility theorem]] says that, when there are three or more alternatives, such a <math>Rank</math> function cannot exist. Hence, such a <math>Soc</math> function also cannot exist.<ref name=agt>{{Cite Algorithmic Game Theory 2007}}</ref>{{rp|214–215}}
+It is possible to prove that, if <math>\operatorname{Soc}</math> is incentive-compatible and not a dictatorship, then <math>\operatorname{Rank}</math> satisfies the properties: unanimity and independence-of-irrelevant-alternatives, and it is not a dictatorship. [[Arrow's impossibility theorem]] says that, when there are three or more alternatives, such a <math>\operatorname{Rank}</math> function cannot exist. Hence, such a <math>\operatorname{Soc}</math> function also cannot exist.<ref name=agt>{{Cite Algorithmic Game Theory 2007}}</ref>{{rp|214–215}}
 == Related results ==