It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961[1] and then proved independently by the philosopher Allan Gibbard in 1973[2] and economist Mark Satterthwaite in 1975.
[3] It deals with deterministic ordinal electoral systems that choose a single winner, and shows that for every voting rule of this form, at least one of the following three things must hold: Gibbard's proof of the theorem is more general and covers processes of collective decision that may not be ordinal, such as cardinal voting.
Assume that they use the Borda count: each voter communicates his or her preference order over the candidates.
Once all ballots have been counted, the candidate with the most points is declared the winner.
Assume that she modifies her ballot, in order to produce the following situation.
Alice is satisfied by her ballot modification, because she prefers the outcome
We say that the Borda count is manipulable: there exists situations where a sincere ballot does not defend a voter's preferences best.
The Gibbard–Satterthwaite theorem states that every ranked-choice voting is manipulable, except possibly in two cases: if there is a distinguished voter who has a dictatorial power, or if the rule limits the possible outcomes to two options only.
be the set of alternatives (which is assumed finite), also called candidates, even if they are not necessarily persons: they can also be several possible decisions about a given issue.
who is a dictator, in the sense that the winning alternative is always her most-liked one among the possible outcomes regardless of the preferences of other voters.
Gibbard–Satterthwaite theorem — If an ordinal voting rule has at least 3 possible outcomes and is non-dictatorial, then it is manipulable.
However, the actual optimal score may depend on the other ballots cast, as indicated by Gibbard's theorem.
If there are still several non-eliminated candidates after all ballots have been examined, then an arbitrary tie-breaking rule is used.
This voting rule is not manipulable: a voter is always better off communicating his or her sincere preferences.
If there are only 2 possible outcomes, a voting rule may be non-manipulable without being dictatorial.
(If both alternatives reach the same number of points, the tie is broken in an arbitrary but deterministic manner, e.g. outcome
This voting rule is not manipulable because a voter is always better off communicating his or her sincere preferences; and it is clearly not dictatorial.
The definitions of possible outcomes, manipulable, dictatorial have natural adaptations to this framework.
Indeed, a strict voting rule is dictatorial if and only if it always selects the most-liked candidate of the dictator among the possible outcomes; in particular, it does not depend on the other voters' ballots.
Theorem — If a strict voting rule has at least 3 possible outcomes, it is non-manipulable if and only if it is dictatorial.
It is possible that some other alternatives can be elected in no circumstances: the theorem and the corollary still apply.
We give a sketch of proof in the simplified case where some voting rule
The strategic aspect of voting is already noticed in 1876 by Charles Dodgson, also known as Lewis Carroll, a pioneer in social choice theory.
[18] This conjecture was later proven independently by Allan Gibbard and Mark Satterthwaite.
[2] Independently, Satterthwaite proved the same result in his PhD dissertation in 1973, then published it in a 1975 article.
Gibbard's theorem deals with processes of collective choice that may not be ordinal, i.e. where a voter's action may not consist in communicating a preference order over the candidates.
The Duggan–Schwartz theorem extend this result in another direction, by dealing with deterministic voting rules that choose multiple winners.
The Gibbard–Satterthwaite theorem is generally presented as a result about voting systems, but it can also be seen as an important result of mechanism design, which deals with a broader class of decision rules.
Noam Nisan describes this relation:[8]: 215 The GS theorem seems to quash any hope of designing incentive-compatible social-choice functions.
The whole field of Mechanism Design attempts escaping from this impossibility result using various modifications in the model.The main idea of these "escape routes" is that they allow for a broader class of mechanisms than ranked voting, similarly to the escape routes from Arrow's impossibility theorem.