The Gibbard–Satterthwaite Theorem
Statement
Let a social choice function pick a single winner from at least alternatives, for every possible profile of voter rankings, in such a way that every alternative can actually win for some profile (onto). If the function is strategy-proof — no voter can ever get a better outcome (according to their true ranking) by reporting a false ranking — then it must be a dictatorship: some voter's top choice is always the winner.
Why is it true?
Ranked-choice systems are often sold as resistant to strategic voting. Gibbard–Satterthwaite says the opposite is essentially unavoidable: as soon as a rule picks a single winner from or more alternatives, is defined for every profile, lets every alternative win sometimes, and is not a dictatorship, there is guaranteed to be some situation where some voter benefits from lying about their preferences.
Proof sketch
Sketch (reduction to Arrow's theorem). First, a monotonicity lemma: if alternative wins at some profile, and the profile changes only by some voters moving higher in their own ranking (without otherwise reordering the other alternatives), must still win. Otherwise a voter whose sincere ranking is the "before" profile could misreport as the "after" profile to push from losing to winning, or vice versa — either way, contradicting strategy-proofness for someone.
Next, use the choice function to build a derived social ranking for each profile: declare above in the derived ranking exactly when would still win after every alternative other than and is deleted from every voter's ballot, leaving a straight two-way race. Ontoness and strategy-proofness of the original choice function, together with the monotonicity lemma, can be used to check that this derived ranking satisfies Unrestricted Domain, Weak Pareto, and Independence of Irrelevant Alternatives as a social welfare function.
By Arrow's Impossibility Theorem, since there are at least alternatives, this derived social ranking must be dictatorial: some voter 's ranking always equals the derived social ranking.
Finally, check that this same voter 's top choice is always the winner of the original social choice function: since the derived ranking puts 's favorite alternative above every other alternative, and the derived ranking tracks who wins pairwise comparisons, 's favorite must be the overall winner at every profile. So the original strategy-proof, onto social choice function is dictated by voter .
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Kenneth J. Arrow (1950). A Difficulty in the Concept of Social Welfare · DOI:10.1086/256963
- Allan Gibbard (1973). Manipulation of Voting Schemes: A General Result · DOI:10.2307/1914083
- Amartya Sen (1970). Collective Choice and Social Welfare