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.^[1] It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

A corollary of this theorem is the Gibbard–Satterthwaite theorem about voting rules. The key difference between the two theorems is that Gibbard–Satterthwaite applies only to ranked voting. Because of its broader scope, Gibbard's theorem makes no claim about whether voters need to reverse their ranking of candidates, only that their optimal ballots depend on the other voters' ballots.^{[note 1]}

Gibbard's theorem is more general, and considers processes of collective decision that may not be ordinal: for example, voting systems where voters assign grades to or otherwise rate candidates (cardinal voting). Gibbard's theorem can be proven using Arrow's impossibility theorem.

Gibbard's theorem is itself generalized by Gibbard's 1978 theorem^[3] and Hylland's theorem,^[4] which extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the agents' actions but may also involve an element of chance.

Gibbard's theorem assumes the collective decision results in exactly one winner and does not apply to multi-winner voting. A similar result for multi-winner voting is the Duggan–Schwartz theorem.

If the two other voters respectively cast ballots $(0,1,1)$ and $(1,1,1)$ , then voter $1$ has only one ballot that leads to the election of her favorite alternative $a$ : $(1,0,0)$ .

However, if we assume instead that the two other voters respectively cast ballots $(0,0,1)$ and $(0,1,1)$ , then voter $1$ should not vote $(1,0,0)$ because it makes $c$ win; she should rather vote $(1,1,0)$ , which makes $b$ win.

Consider some voters $1$ , $2$ and $3$ who wish to select an option among three alternatives: $a$ , $b$ and $c$ . Assume they use approval voting: each voter assigns to each candidate the grade 1 (approval) or 0 (withhold approval). For example, $(1,1,0)$ is an authorized ballot: it means that the voter approves of candidates $a$ and $b$ but does not approve of candidate $c$ . Once the ballots are collected, the candidate with highest total grade is declared the winner. Ties between candidates are broken by alphabetical order: for example, if there is a tie between candidates $a$ and $b$ , then $a$ wins.

Assume that voter $1$ prefers alternative $a$ , then $b$ and then $c$ . Which ballot will best defend her opinions? For example, consider the two following situations.

To sum up, voter $1$ faces a strategic voting dilemma: depending on the ballots that the other voters will cast, $(1,0,0)$ or $(1,1,0)$ can be a ballot that best defends her opinions. We then say that approval voting is not strategyproof: once the voter has identified her own preferences, she does not have a ballot at her disposal that best defends her opinions in all situations; she needs to act strategically, possibly by spying over the other voters to determine how they intend to vote.

Gibbard's theorem states that a deterministic process of collective decision cannot be strategyproof, except possibly in two cases: if there is a distinguished agent who has a dictatorial power, or if the process limits the outcome to two possible options only.

Examples[edit]

Serial dictatorship[edit]

We assume that each voter communicates a strict weak order over the candidates. 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 his ex-aequo most-liked candidates and the other candidates are eliminated. Then voter 2's ballot is examined: if he has 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 is still several non-eliminated candidates after all ballots have been examined, then an arbitrary tie-breaking rule is used.

This game form is strategyproof: whatever the preferences of a voter, he has a dominant strategy that consists in declaring his sincere preference order. It is also dictatorial, and its dictator is voter 1: if he wishes to see candidate $a$ elected, then he just has to communicate a preference order where $a$ is the unique most-liked candidate.

Simple majority vote[edit]

If there are only 2 possible outcomes, a game form may be strategyproof and not dictatorial. For example, it is the case of the simple majority vote: each voter casts a ballot for her most-liked alternative (among the two possible outcomes), and the alternative with most votes is declared the winner. This game form is strategyproof because it is always optimal to vote for one's most-liked alternative (unless one is indifferent between them). However, it is clearly not dictatorial. Many other game forms are strategyproof and not dictatorial: for example, assume that the alternative $a$ wins if it gets two thirds of the votes, and $b$ wins otherwise.

A game form showing that the converse does not hold[edit]

Consider the following game form. Voter 1 can vote for a candidate of her choice, or she can abstain. In the first case, the specified candidate is automatically elected. Otherwise, the other voters use a classic voting rule, for example the Borda count. This game form is clearly dictatorial, because voter 1 can impose the result. However, it is not strategyproof: the other voters face the same issue of strategic voting as in the usual Borda count. Thus, Gibbard's theorem is an implication and not an equivalence.