Gibbard-Satterthwaite theorem

From Wikipedia, the free encyclopedia

The Gibbard–Satterthwaite theorem is a result about voting systems designed to choose a single winner from the preferences of certain individuals, where each individual ranks all candidates in order of preference. It states that, for three or more candidates, one of the following three things must hold for every voting rule:

The rule is dictatorial, or
There is some candidate who cannot win, under the rule, in any circumstances, or
The rule is manipulable (i.e. 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 preferences.

Since rules which forbid certain candidates from winning or which are dictatorial are not suitable for real-life voting systems, all democratic systems either are manipulable or do not meet the preconditions of the theorem. Taylor shows that the result holds even if ties are allowed in the ballots: the winner is then chosen from the candidates tied at the top of the dictator's ballot.

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 only choosing a winner. Similarly, the Duggan-Schwartz theorem deals with voting systems that choose a (nonempty) set of winners rather than a single winner.

[edit] External links

[edit] References

Allan Gibbard, "Manipulation of voting schemes: a general result", Econometrica, Vol. 41, No. 4 (1973), pp. 587–601.
Mark A. Satterthwaite, "Strategy-proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions", Journal of Economic Theory 10 (April 1975), 187-217.
Alan D. Taylor, "The manipulability of voting systems", The American Mathematical Monthly, April 2002.