Skip to content

The Gibbard–Satterthwaite theorem — why no method is strategy-proof

The formal reason "just vote honestly" can never be guaranteed. Proved independently by Allan Gibbard (1973) and Mark Satterthwaite (1975), it is — with Arrow's theorem — one of the two impossibility results that anchor voting theory. This page states it plainly, lists the escape hatches, and explains why it reframes the whole strategy debate (including STAR's).

Level: 301 · deep dive Companion: Strategic voting across the Equal Vote methods · What makes a voting method good?.

The statement, in plain terms

For a single-winner election with three or more candidates, any voting rule that is deterministic, non-dictatorial, and can elect any of the candidates is manipulable: there is at least one situation in which some voter can get a result they prefer by voting insincerely.

In one line: no reasonable ranked voting method is strategy-proof. There is no method where honesty is always, provably, the best move for every voter in every situation. Manipulation is always possible — the theorem says nothing about whether it's easy, common, or safe, which is the part that actually matters (below).

What "manipulable" does and doesn't mean

  • It means: somewhere in the space of all possible elections, there's a profile where one voter, by misrepresenting their preferences, flips the winner to someone they like better. One counterexample is enough to make a method "manipulable."
  • It does not mean: that manipulation is easy to pull off, that it happens often in real elections, that the manipulator can know when to do it, or that it doesn't backfire. Those are empirical questions about a specific method — and they're where methods differ enormously.

The escape hatches (what the theorem quietly assumes)

A method can dodge Gibbard–Satterthwaite only by giving up one of its premises:

  • Two candidates. With only two options there's nothing to manipulate — honest majority rule is strategy-proof. (It's the ≥3 case that bites.)
  • Dictatorship. If one voter's ballot always decides, no one else can manipulate — strategy-proof, and useless.
  • A restricted outcome set (not "onto"). A rule that can only ever elect one fixed candidate is trivially unmanipulable.
  • Randomization. Gibbard's 1977 follow-up shows the only strategy-proof processes are random mixtures of dictatorships and pairwise votes — e.g. random ballot (pick one voter's ballot at random). Strategy-proof, but nobody wants elections decided by lottery.

Every usable method fails at least one escape condition — so every usable method is manipulable. That's the whole point.

The fifth hatch: change what you're asking for

The four above all give up something about the rule. There is one more, and it gives up something about the requirement: stop demanding a dominant strategy. Strategy-proofness asks that honesty be best no matter what anyone else does. Bayesian incentive compatibility asks only that honesty be best when everyone else is honest, in expectation over a shared prior — a Bayes–Nash equilibrium rather than a dominant strategy.

That is strictly weaker, so G–S no longer applies, and useful things become possible: Kim (2017) gets both an incentive-compatible ordinal rule that is Pareto efficient and an incentive-compatible cardinal rule that beats every ordinal rule. Whether the weakening is too generous is a fair fight — a common prior is exactly what a published poll destroys — but it is the hatch the mechanism-design literature actually uses, and it belongs on this list.

Does it apply to STAR, Approval, and Score?

Strictly, Gibbard–Satterthwaite is about ranked (ordinal) rules, so it doesn't literally cover cardinal ballots. But that's a technicality, not a loophole:

  • Voters ultimately care about who wins — an ordinal preference over outcomes — so the incentive to misreport survives the switch to scores. Gibbard's more general 1973/1978 game-form theorem covers cardinal mechanisms too.
  • And concretely, cardinal methods have their own well-known strategy: exaggeration (score your side 5, everyone else 0), which pushes Score toward Approval, and bullet voting. STAR's automatic runoff is specifically designed to blunt that incentive — but it does not eliminate it, because no method can. See strategic voting.

So the honest statement covers all four of this library's methods: Approval, STAR, Ranked Robin, and RCV-IRV are all manipulable. None is strategy-proof. (It's one row you won't find passed in Criteria at a glance, because no method passes it.)

Why this reframes the entire strategy debate

This is the theoretical backbone of the repo's honesty stance — "resistant, not proof." Because no method is strategy-proof, "which voting method can't be gamed?" is the wrong question (the answer is always "none"). The right questions are empirical and comparative:

  • When does honesty pay? For which method, and under what electorate, is a sincere ballot the best practical strategy most of the time?
  • How hard and how risky is manipulation? Does it require coordination and knowing the result in advance? Does it backfire?

Those are exactly what Voter Satisfaction Efficiency simulations and the strategic-voting analysis measure. Gibbard–Satterthwaite doesn't end the debate — it starts it correctly, by ruling out the fantasy of an unmanipulable method and forcing the argument onto degrees of strategy-resistance. STAR's own advocates concede the point openly; the honest case for any method has to. See STAR's honest limits.

Allowing ties does not escape it (Duggan and Schwartz)

G-S assumes every election has a unique winner. That looks like a loophole: could a rule that sometimes returns a set of tied winners be strategyproof? It's a fair question, since real methods do produce ties and need tiebreakers.

Duggan–Schwartz (2000) closes it. For rules that may return a tied set: if the rule can elect at least three candidates and is strategyproof, then some single voter is a nominator — their top choice is always in the winning set. Not literally a dictator, but the same shape of failure, and no real method would accept it. Allowing ties buys indecisiveness, not honesty.

(One genuine subtlety worth stating: "strategyproof" needs more care here, because a voter comparing two sets of tied winners has to be assumed to compare them somehow — optimistically, pessimistically, or by expected utility. The result holds across those readings, which is what makes it a closed door rather than a technicality.)

The practical reading is the same one this repo takes everywhere: you cannot tiebreak your way out of manipulability. Consistent with the Ranked Robin tiebreak analysis, where Brandt, Saile & Stricker prove no anonymous, Pareto-optimal tiebreaking rule — fixed order or coin flip — escapes manipulability once voters may express ties.

Relation to Arrow's theorem

Arrow (1951) and Gibbard–Satterthwaite are close cousins — G-S can even be derived from Arrow. Roughly:

  • Arrow is about aggregation: no rule can combine individual rankings into a group ranking while satisfying a short list of fairness conditions.
  • Gibbard–Satterthwaite is about incentives: no rule can make honest voting a dominant strategy.

Two faces of the same fact — there is no perfect voting method — which is why every method in this library has an honest-limits page, and why "it fails criterion X" is a trade-off to weigh, never a disqualification. Deeper math: the math behind Condorcet (Arrow & Gibbard–Satterthwaite in context).

Sources

  • A. Gibbard, "Manipulation of Voting Schemes: A General Result," Econometrica 41 (1973).
  • M. Satterthwaite, "Strategy-proofness and Arrow's Conditions," Journal of Economic Theory 10 (1975).
  • A. Gibbard, "Manipulation of Schemes That Mix Voting with Chance," Econometrica 45 (1977).
  • J. Duggan & T. Schwartz, "Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized," Social Choice and Welfare 17 (2000), pp. 85–93 — the tied-set generalization above.
  • Gibbard–Satterthwaite theorem (Wikipedia) · Gibbard's theorem (Wikipedia)