Gibbard–Satterthwaite theorem
The Gibbard–Satterthwaite theorem is a theorem in social choice theory. It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961 and then proved independently by the philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems, and shows that for every voting rule of this form, at least one of the following things must hold:
- The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
- The rule limits the possible outcomes to two alternatives only; or
- The rule is manipulable, i.e. not strategyproof, i.e., there is no single always-best strategy (one that does not depend on other voters' preferences or behavior).
- The rule does not yield a single winner
Gibbard's proof of the theorem is more general and covers processes of collective decision that may not be ordinal, such as cardinal voting. Gibbard's 1978 theorem and Hylland's theorem are even more general and extend these results to non-deterministic processes, where the outcome may depend partly on chance; the Duggan–Schwartz theorem extends these results to multiwinner electoral systems.
The theorem has two interpretations. The old interpretation views it as a proof that "democracy is impossible", stating that if we require a voting rule to yield a single winner, there are distributions of voter preferences where the rule is dictatorial or "allows manipulation".
The modern interpretation views it as a proof that there is no point to look for an agreement using a voting rule when there is no agreement. In this interpretation the theorem is an argument to use "none of above" as a choice in every vote (as the Debian General Resolution Procedure does), and to accept that a vote can yield no result, signaling that more deliberation is needed about the topic.