MathLabs
TheoremProved

The Gibbard–Satterthwaite Theorem

Statement

Let a social choice function pick a single winner from at least 33 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 33 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 aa wins at some profile, and the profile changes only by some voters moving aa higher in their own ranking (without otherwise reordering the other alternatives), aa must still win. Otherwise a voter whose sincere ranking is the "before" profile could misreport as the "after" profile to push aa 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 aa above bb in the derived ranking exactly when aa would still win after every alternative other than aa and bb 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 33 alternatives, this derived social ranking must be dictatorial: some voter ii's ranking always equals the derived social ranking.

Finally, check that this same voter ii's top choice is always the winner of the original social choice function: since the derived ranking puts ii's favorite alternative above every other alternative, and the derived ranking tracks who wins pairwise comparisons, ii's favorite must be the overall winner at every profile. So the original strategy-proof, onto social choice function is dictated by voter ii.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Kenneth J. Arrow (1950). A Difficulty in the Concept of Social Welfare · DOI:10.1086/256963
  2. Allan Gibbard (1973). Manipulation of Voting Schemes: A General Result · DOI:10.2307/1914083
  3. Amartya Sen (1970). Collective Choice and Social Welfare