The Gibbard–Satterthwaite theorem is a theorem in
social choice theory
Social choice theory is a branch of welfare economics that extends the Decision theory, theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures (social welfare function, soc ...
. It was first conjectured by the philosopher
Michael Dummett
Sir Michael Anthony Eardley Dummett (; 27 June 1925 – 27 December 2011) was an English academic described as "among the most significant British philosophers of the last century and a leading campaigner for racial tolerance and equality." H ...
and the mathematician
Robin Farquharson in 1961 and then proved independently by the philosopher
Allan Gibbard
Allan Fletcher Gibbard (born 1942) is an American philosopher who is the Richard B. Brandt Distinguished University Professor of Philosophy Emeritus at the University of Michigan, Ann Arbor. Gibbard has made major contributions to contemporary e ...
in 1973
and economist
Mark Satterthwaite in 1975.
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:
# 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 not straightforward, i.e. there is no single
always-best strategy (one that does not depend on other voters' preferences or behavior).
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.
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
The Borda method or order of merit is a positional voting rule that gives each candidate a number of points equal to the number of candidates ranked below them: the lowest-ranked candidate gets 0 points, the second-lowest gets 1 point, and so on ...
: 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
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.
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
Score voting, sometimes called range voting, is an electoral system for single-seat elections. Voters give each candidate a numerical score, and the candidate with the highest average score is elected. Score voting includes the well-known approva ...
. 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
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properti ...
.
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 his or 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.
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.
Sketch of proof
The Gibbard–Satterthwaite theorem can be proved using
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
A dictatorship is an autocratic form of government which is characterized by a leader, or a group of leaders, who hold governmental powers with few to no Limited government, limitations. Politics in a dictatorship are controlled by a dictator, ...
. Hence, such a voting rule
must also be a dictatorship.
Later authors have developed other variants of the proof.
History
The strategic aspect of voting is already noticed in 1876 by Charles Dodgson, also known as
Lewis Carroll
Charles Lutwidge Dodgson (27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet, mathematician, photographer and reluctant Anglicanism, Anglican deacon. His most notable works are ''Alice ...
, a pioneer in social choice theory. His quote (about a particular voting system) was made famous by
Duncan Black:
This principle of voting makes an election more of a game of skill than a real test of the wishes of the electors.
During the 1950s,
Robin Farquharson published influential articles on voting theory. In an article with
Michael Dummett
Sir Michael Anthony Eardley Dummett (; 27 June 1925 – 27 December 2011) was an English academic described as "among the most significant British philosophers of the last century and a leading campaigner for racial tolerance and equality." H ...
, he conjectures that deterministic voting rules with at least three outcomes are never straightforward
tactical voting
Strategic or tactical voting is voting in consideration of possible ballots cast by other voters in order to maximize one's satisfaction with the election's results.
Gibbard's theorem shows that no voting system has a single "always-best" stra ...
. This conjecture was later proven independently by
Allan Gibbard
Allan Fletcher Gibbard (born 1942) is an American philosopher who is the Richard B. Brandt Distinguished University Professor of Philosophy Emeritus at the University of Michigan, Ann Arbor. Gibbard has made major contributions to contemporary e ...
and
Mark Satterthwaite. In a 1973 article, Gibbard exploits
Arrow's impossibility theorem from 1951 to prove the result we now know as
Gibbard's theorem
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properti ...
.
Independently, Satterthwaite proved the same result in his PhD dissertation in 1973, then published it in a 1975 article.
This proof is also based on Arrow's impossibility theorem, but does not involve the more general version given by Gibbard's theorem.
Related results
Gibbard's theorem
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properti ...
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.
Gibbard's 1978 theorem and
Hylland's theorem extend these results to non-deterministic mechanisms, i.e. where the outcome may not only depend on the ballots but may also involve a part of chance.
The
Duggan–Schwartz theorem extend this result in another direction, by dealing with deterministic voting rules that choose multiple winners.
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
Mechanism design (sometimes implementation theory or institution design) is a branch of economics and game theory. It studies how to construct rules—called Game form, mechanisms or institutions—that produce good outcomes according to Social ...
, which deals with a broader class of decision rules.
Noam Nisan describes this relation:
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
*
Arrow's impossibility theorem
*
Condorcet cycle
*
Duggan–Schwartz theorem
*
Gibbard's theorem
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properti ...
*
Ranked voting
Ranked voting is any voting system that uses voters' Ordinal utility, rankings of candidates to choose a single winner or multiple winners. More formally, a ranked vote system depends only on voters' total order, order of preference of the cand ...
*
Strategic voting
Strategic or tactical voting is voting in consideration of possible ballots cast by other voters in order to maximize one's satisfaction with the election's results.
Gibbard's theorem shows that no voting system has a single "always-best" strat ...
Notes and references
{{DEFAULTSORT:Gibbard-Satterthwaite theorem
Voting theory
Economics theorems
Theorems in discrete mathematics