Gibbard–Satterthwaite theorem
It has been suggested that Gibbard's theorem be merged into this article. (Discuss) Proposed since November 2023. |
The Gibbard–Satterthwaite theorem is a theorem in
- 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 some situations, a voter's sincere ballot may not best defend their opinion.
The scope of this theorem is limited to ordinal voting. It does not apply to
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.
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.
Gibbard–Satterthwaite theorem — If an ordinal voting rule has at least 3 possible outcomes and is non-dictatorial, then it is manipulable.
Counterexamples and loopholes
A variety of "counterexamples" to the Gibbard-Satterthwaite theorem exist when the conditions of the theorem do not apply.
Cardinal voting
Consider a three-candidate election conducted by score voting. It is always optimal for a voter to give the best candidate the highest possible score, and the worst candidate the lowest possible score. Then, no matter which score the voter assigns to the middle candidate, it will always fall (non-strictly) between the first and last scores; this implies the voter's score ballot will be weakly consistent with that voter's honest ranking. However, the actual optimal score may depend on the other ballots cast, as indicated by Gibbard's theorem.
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.
This voting rule is not manipulable: a voter is always better off communicating his or her sincere preferences. It is also dictatorial, and its dictator is voter 1: the winning alternative is always that specific voter's most-liked one or, if there are several most-liked alternatives, it is chosen among them.
Simple majority vote
If there are only 2 possible outcomes, a voting rule may be non-manipulable without being dictatorial. For example, it is the case of the simple majority vote: each voter assigns 1 point to her top alternative and 0 to the other, and the alternative with most points is declared the winner. (If both alternatives reach the same number of points, the tie is broken in an arbitrary but deterministic manner, e.g. outcome wins.) This voting rule is not manipulable because a voter is always better off communicating her sincere preferences; and it is clearly not dictatorial. Many other rules are neither manipulable nor dictatorial: for example, assume that the alternative wins if it gets two thirds of the votes, and wins otherwise.
Corollary
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.
Theorem — If a strict voting rule has at least 3 possible outcomes, it is non-manipulable if and only if it is dictatorial.
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:[4] 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.[5] 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.[6][7]
Sketch of proof
The Gibbard–Satterthwaite theorem can be proved using
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.[clarification needed] 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.[8]: 214–215
Later authors have developed other variants of the proof.[5][6][7][9][10][11][12][13][14][excessive citations]
History
The strategic aspect of voting is already noticed in 1876 by Charles Dodgson, also known as
Related results
The Duggan–Schwartz theorem extend this result in another direction, by dealing with deterministic voting rules that choose multiple winners.[19]
Importance
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.
See also
- Ranked voting
- Strategic voting
- Gibbard's theorem
- Arrow's impossibility theorem
- Duggan–Schwartz theorem
Notes and references
- ^ Gibbard's theorem does not imply that cardinal methods necessarily incentivize reversing one's relative rank of two candidates.
- S2CID 46164353.
- ^ JSTOR 1914083.
- ^ .
- ^ Weber, Tjark (2009). "Alternatives vs. Outcomes: A Note on the Gibbard-Satterthwaite Theorem". Technical Report (University Library of Munich).
- ^ .
- ^ ISSN 0165-1765.
- ^ ISSN 0165-1765.
- ^ ISBN 0-521-87282-0.
- S2CID 153421058.
- JSTOR 2648754.
- ISBN 978-0198761884.
- S2CID 46164353.
- ISBN 9780521424585. Retrieved 10 January 2016.
- JSTOR 2695497.
- ^ Black, Duncan (1958). The theory of committees and elections. Cambridge: University Press.
- JSTOR 2662065.
- JSTOR 1907685.
- S2CID 27639067.
- S2CID 271833.