In social choice theory, the Gibbard–Satterthwaite theorem is a result published independently by philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a single winner. It states that for every voting rule, one of the following three 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 susceptible to tactical voting: in certain conditions, a voter's sincere ballot may not best defend their opinion.
While the scope of this theorem is limited to ordinal voting, Gibbard's theorem is more general, in that it deals with processes of collective decision that may not be ordinal: for example, voting systems where voters assign grades to candidates. Gibbard's 1978 theorem and Hylland's theorem are even more general and extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the voters' actions but may also involve a part of chance.
Informal description
Consider three voters named Alice, Bob and Carol, who wish to select a winner among four candidates named , , and . Assume that they use the Borda count: each voter communicates his or her preference order over the candidates. For each ballot, 3 points are assigned to the top candidate, 2 points to the second candidate, 1 point to the third one and 0 points to the last one. Once all ballots have been counted, the candidate with the most points is declared the winner.
Assume that their preferences are as follows.
If the voters cast sincere ballots, then the scores are: . Hence, candidate will be elected, with 7 points.
But Alice can vote strategically and change the result. Assume that she modifies her ballot, in order to produce the following situation.
Alice has strategically upgraded candidate and downgraded candidate . Now, the scores are: . Hence, is elected. Alice is satisfied by her ballot modification, because she prefers the outcome to , which is the outcome she would obtain if she voted sincerely.
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 voting rule 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.
Formal statement
Let 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. We denote by the set of voters. Let be the set of strict weak orders over : an element of this set can represent the preferences of a voter, where a voter may be indifferent regarding the ordering of some alternatives. A voting rule is a function . Its input is a profile of preferences and it yields the identity of the winning candidate.
We say that is manipulable if and only if there exists a profile where some voter , by replacing her ballot with another ballot , can get an outcome that she prefers (in the sense of ).
We denote by the image of , i.e. the set of possible outcomes for the election. For example, we say that has at least three possible outcomes if and only if the cardinality of is 3 or more.
We say that is dictatorial if and only if there exists a voter 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. If the dictator has several equally most-liked alternatives among the possible outcomes, then the winning alternative is simply one of them.
Examples
Serial dictatorship
The serial dictatorship is defined as follows. If voter 1 has a unique most-liked candidate, then this candidate is elected. Otherwise, possible outcomes are restricted to the most-liked candidates, whereas the other candidates are eliminated. Then voter 2's ballot is examined: if there is a unique best-liked candidate among the non-eliminated ones, then this candidate is elected. Otherwise, the list of possible outcomes is reduced again, etc. If there are still several non-eliminated candidates after all ballots have been examined, then an arbitrary tie-breaking rule is used.