Gibbard–Satterthwaite theorem

The Gibbard–Satterthwaite theorem, named after Allan Gibbard and Mark Satterthwaite, is a result about the deterministic voting systems that choose a single winner using only the preferences of the voters, where each voter ranks all candidates in order of preference. The Gibbard–Satterthwaite theorem states that, for three or more candidates, one of the following three things must hold for every voting rule:

1. The rule is dictatorial (i.e., there is a single individual who can choose the winner), or
2. There is some candidate who can never win, under the rule, or
3. 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 voting system that selects a single winner either is manipulable or does not meet the preconditions of the theorem. Taylor (2002, Theorem 5.1) 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. Arrow's impossibility theorem is a similar theorem that deals with voting systems designed to yield a complete preference order of the candidates, rather than simply choosing a winner. Similarly, the Duggan–Schwartz theorem deals with voting systems that choose a (nonempty) set of winners rather than a single winner.

Conjecture by Dummett and Farquharson

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

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.^[2]

Notes

1. ↑ 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. 
2. ↑ Michael Dummett Voting Procedures (Oxford, 1984)

References

• Michael Dummett (1984). Voting Procedures. Oxford. ISBN 978-0198761884. 
• 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. 
• Rudolf Farra and Maurice Salles (October 2006). "An Interview with Michael Dummett: From analytical philosophy to voting analysis and beyond". Social Choice and Welfare 27 (2). 
• Farquharson, Robin (Feb 1956). "Straightforwardness in voting procedures". Oxford Economic Papers, New Series 8 (1): 80–89. JSTOR 2662065. 

• Michael Dummett and Robin Farquharson (Jan 1961). "Stability in Voting". Econometrica 29 (1): 33–43. doi:10.2307/1907685. JSTOR 1907685. 

• Allan Gibbard (1973). "Manipulation of voting schemes: a general result". Econometrica 41 (4): 587–601. JSTOR 1914083. 
• Mark A. Satterthwaite (April 1975). "Strategy-proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions". Journal of Economic Theory 10: 187–217. doi:10.1016/0022-0531(75)90050-2. 
• Alan D. Taylor (April 2002). "The manipulability of voting systems". The American Mathematical Monthly. JSTOR 2695497. 

External links

• The Proof of the Gibbard–Satterthwaite Theorem Revisited
• Arrow’s Theorem and the Gibbard–Satterthwaite Theorem: A Unified Approach
• The Gibbard-Satterthwaite theorem about honest & strategic voting - in the RangeVoting website.
• An example of an election situation in which, by all common voting methods, it pays to vote strategically.