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.
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 their 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. Voter Choice 1 Choice 2 Choice 3 Choice 4 Alice Bob Carol
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. Voter Choice 1 Choice 2 Choice 3 Choice 4 Alice Bob Carol 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 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.
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.
Corollary for strict preferences We now consider the case where by assumption, a voter cannot be indifferent between two candidates. We denote by the set of strict total orders over and we define a strict voting rule as a function . The definitions of possible outcomes, manipulable, dictatorial have natural adaptations to this framework.
For a strict voting rule, the converse of the Gibbard–Satterthwaite theorem is true. 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. As a consequence, it is not manipulable: the dictator is perfectly defended by her sincere ballot, and the other voters have no impact on the outcome, hence they have no incentive to deviate from sincere voting. Thus, we obtain the following equivalence.
In the theorem, as well as in the corollary, it is not needed to assume that any alternative can be elected. It is only assumed that at least three of them can win, i.e. are possible outcomes of the voting rule. It is possible that some other alternatives can be elected in no circumstances: the theorem and the corollary still apply. However, the corollary is sometimes presented under a less general form: instead of assuming that the rule has at least three possible outcomes, it is sometimes assumed that contains at least three elements and that the voting rule is onto, i.e. every alternative is a possible outcome. The assumption of being onto is sometimes even replaced with the assumption that the rule is unanimous, in the sense that if all voters prefer the same candidate, then she must be elected.
Proofs
Proof using Arrow's impossibility theorem The original proofs by Gibbard and Satterthwaite used the Arrow's impossibility theorem for social ranking functions. We give a sketch of proof in the simplified case where some voting rule is assumed to be Pareto-efficient.
It is possible to build a social ranking function , as follows: in order to decide whether , the function creates new preferences in which and are moved to the top of all voters' preferences. Then, examines whether chooses or .
It is possible to prove that, if is non-manipulable and non-dictatorial, satisfies independence of irrelevant alternatives. Arrow's impossibility theorem says that, when there are three or more alternatives, such a function must be a dictatorship. Hence, such a voting rule must also be a dictatorship.
Later authors have developed other variants of the proof.
Proof using Menus Barbera and Peleg presented a different proof, using the notion of menus (also called: option sets). For simplicity, we present the proof for n=2 voters, and for preferences without ties (The extension to any number of voters can be done by straightforward induction; the extension to preferences with ties is straightforward as long as the domain contains all profiles without ties).
Definitions:
Given a preference-ordering P and a set of candidates B, define Best(P,B) as the best candidate in B, given preference ordering P. Given a preference-ordering P1 for agent 1, define Menu2(P1) as the option set of 2 - the set of all candidates that could potentially be elected when agent 1 votes P1 (ranging over all possible votes of agent 2).
The following lemmas are proved for a strategyproof rule f:
f(P1,P2) = Best(P2, Menu2(P1)), as otherwise agent 2 could manipulate. Similarly, f(P1,P2) = Best(P1, Menu1(P2)), as otherwise agent 1 could manipulate. For any preference reported by agent 1, the best candidate by that preference is on the menu for agent 2. Formally, Best(P1,Range(f)) in Menu2(P1). Proof: Let OPT1 := Best(P1,Range(f)). Since OPT1 is in range f, it equals R(P1*,P2*) for some profile (P1*,P2*). Hence, it is in Menu1(P2*). By Lemma 1, f(P1,P2*) = Best(P1, Menu1(P2*)) = OPT1 = Best(P2*, Menu2(P1)). In particular, OPT1 is in Menu2(P1). Unanimity holds: If Best(P1,Range(f)) = Best(P2,Range(f)) = x, then f(P1,P2)=x. Proof: follows from Lemmas 2 and 1. In particular, for every preference P, f(P,P) = Best(P, Range(f)). The menu depends only on the best element; formally, if Best(P1,Range(f)) = Best(P1*,Range(f)) = x, then Menu2(P1)=Menu2(P1*). Proof: By Lemma 2, x is in both Menu2(P1) and Menu2(P1*). If the menus are not equal, then (wlog) some candidate z is in Menu2(P1) and not in Menu2(P1*). Let P2* be a preference that ranks z first, x second, and then all other candidates. Then, by Lemma 1, f(P1,P2*) = z and f(P1*,P2*) = x. But this means that x is in Menu1(P2), so by Lemma 1 again, f(P1,P2*) = Best(P1, Menu1(P2*))=x --- a contradiction [agent 1 could manipulate from P1 to P1*]. Hence, we can write from now on Menu2(x), meaning, Menu2(P1) for all P1 with best element x; by Lemma 2, x in Menu2(x) for all x. For every x and z in Range(f), and for every Px with best candidate x and Pz with best candidate z, Px prefers Best(Pz,Menu2(x)) to z. Proof: Take x,z,Px,Pz as in the lemma statement, and let y=Best(Pz,Menu2(x)). Assume by contradiction that Px prefers z to y. By Lemma 1, f(Px,Pz)=Best(Pz, Menu2(x)) = y. By Lemma 3, f(Pz,Pz)=Best(Pz,Range(f)) = z. But this means that z is in Menu1(Pz), so y cannot be Best(Px, Menu1(Pz)). But by Lemma 1, f(Px,Pz) = Best(Px, Menu1(Pz)) --- a contradiction [agent 1 can profitably manipulate from Px to Pz]. For every x in Range(f), Menu2(x) is either a singleton or the entire Range(f). Proof: By contradiction, let x be some candidate that violates that statement. So Menu2(x) contains x (by Lemma 2), and some other element y (as it is not a singleton), but not some third element z (as it is not the entire range). Then there is a preference Px with best candidate x, that prefers z to y; and a preference Pz with best candidate z, that ranks y second. Then Best(Pz, Menu2(x)) = y but Px prefers z to y, contradicting Lemma 5. Menu2(x) is either a singleton for all x, or the entire Range(f) for all x. Proof: By contradiction, let x be some candidate for which Menu2(x) is a singleton (and must be equal to {x}), and y some other candidate for which Menu2(y) = Range(f). Let Py be a preference with best element y, that prefers x to some third candidate z (here we assume that Range(f) contains at least three candidates). Since Menu2(Py) = Range(f), there is some P2 for which f(Py,P2)=z. But then agent 1 could manipulate from Py to some preference Px with best element x, as this would force the outcome to be x. Based on Lemma 7, there are two options:
If Menu2(P1) is a singleton for all P1, then by Lemma 2 this singleton must be Best(P1,Range(f)). Then f(P1,P2) = Best(P1,Range(f)), so 1 is a dictator. If Menu2(P1) = Range(f) for all P1, then by Lemma 1 f(P1,P2) = Best(P2, Range(f)), so 2 is a dictator.
Variants
Non-ordinal ballots 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.
Non-deterministic voting rules