User:Closed Limelike Curves/Gibbard's theorem

In the fields of mechanism design, game theory, and social choice, Gibbard's theorem—sometimes called the Gibbard–Satterthwaite theorem—is a result showing that almost every kind of game involves at least some minimal amount of strategic thinking. In other words, it is impossible to design a game such that there will always be a universally-best (dominant) strategy that a player can use. As a result, playing the game requires

Gibbard's theorem is based on the idea of a game form, which can be thought of as the "outline" of a game

Gibbard's theorem is often (mistakenly) misunderstood as involving being a disproof of the revelation principle, a different proof that shows any can be converted into a . However, it shows only that

game can be —strategic voting, , or .

While the theorem states that any , it does not imply that can be manipulated

only two kinds of straightforward game forms, that is, with an always-best strategy.

1. The game is a dictatorship, i.e. one player decides on the outcome and the others have no .
2. A rule limits the possible outcomes to two alternatives only.

History

Gibbard's theorem was first conjectured by philosopher Michael Dummett and mathematician Robin Farquharson in 1961. It was first proved by the philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. Gibbard generalized the to include randomized voting (lotteries) in 1978.

Informal description

Consider three voters named Alice, Bob and Carol, who wish to select a winner among four candidates named $a$, $b$, $c$ and $d$. 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	$a$	$b$	$c$	$d$
Bob	$c$	$b$	$d$	$a$
Carol	$c$	$b$	$d$	$a$

If the voters cast sincere ballots, then the scores are: $(a:3,b:6,c:7,d:2)$. Hence, candidate $c$ 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	$b$	$a$	$d$	$c$
Bob	$c$	$b$	$d$	$a$
Carol	$c$	$b$	$d$	$a$

Alice has strategically upgraded candidate $b$ and downgraded candidate $c$. Now, the scores are: $(a:2,b:7,c:6,d:3)$. Hence, $b$ is elected. Alice is satisfied by her ballot modification, because she prefers the outcome $b$ to $c$, 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 ${\mathcal {A}}$ 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 ${\mathcal {N}}=\{1,\ldots ,n\}$ the set of voters. Let ${\mathcal {P}}$ be the set of strict weak orders over ${\mathcal {A}}$: 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 $f:{\mathcal {P}}^{n}\to {\mathcal {A}}$. Its input is a profile of preferences $(P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}$ and it yields the identity of the winning candidate.

We say that $f$ is manipulable if and only if there exists a profile $(P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}$ where some voter $i$, by replacing her ballot $P_{i}$ with another ballot $P_{i}'$, can get an outcome that she prefers (in the sense of $P_{i}$).

We denote by $f({\mathcal {P}}^{n})$ the image of $f$, i.e. the set of possible outcomes for the election. For example, we say that $f$ has at least three possible outcomes if and only if the cardinality of $f({\mathcal {P}}^{n})$ is 3 or more.

We say that $f$ is dictatorial if and only if there exists a voter $i$ 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 $a$ 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 $a$ wins if it gets two thirds of the votes, and $b$ wins otherwise.

Corollary

We now consider the case where by assumption, a voter cannot be indifferent between two candidates. We denote by ${\mathcal {L}}$ the set of strict total orders over ${\mathcal {A}}$ and we define a strict voting rule as a function $f:{\mathcal {L}}^{n}\to {\mathcal {A}}$. 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: instead of assuming that the rule has at least three possible outcomes, it is sometimes assumed that ${\mathcal {A}}$ 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 $f$ is assumed to be Pareto-efficient.

It is possible to build a social ranking function $\operatorname {Rank}$, as follows: in order to decide whether $a\prec b$, the $\operatorname {Rank}$ function creates new preferences in which $a$ and $b$ are moved to the top of all voters' preferences. Then, $\operatorname {Rank}$ examines whether $f$ chooses $a$ or $b$.

It is possible to prove that, if $f$ is non-manipulable and non-dictatorial, $\operatorname {Rank}$ satisfies independence of irrelevant alternatives. Arrow's impossibility theorem says that, when there are three or more alternatives, such a $\operatorname {Rank}$ function must be a dictatorship. Hence, such a voting rule $f$ 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, 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, he conjectures that deterministic voting rules with at least three outcomes are never straightforward tactical voting. This conjecture was later proven independently by Allan Gibbard 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. 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 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, 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.

Notes and references

It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

1. The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome.
2. The process limits the possible outcomes to two options only.
3. The process is not straightforward; the optimal ballot for a voter depends on their beliefs about other voters' ballots.

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.

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 and Hylland's theorem, 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.

Overview

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.

• 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.

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.

Formal statement

Let ${\mathcal {A}}$ be the set of alternatives, which can also be called candidates in a context of voting. Let ${\mathcal {N}}=\{1,\ldots ,n\}$ be the set of agents, which can also be called players or voters, depending on the context of application. For each agent $i$, let ${\mathcal {S}}_{i}$ be a set that represents the available strategies for agent $i$; assume that ${\mathcal {S}}_{i}$ is finite. Let $g$ be a function that, to each $n$-tuple of strategies $(s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}$, maps an alternative. The function $g$ is called a game form. In other words, a game form is essentially defined like an n-player game, but with no utilities associated to the possible outcomes: it describes the procedure only, without specifying a priori the gain that each agent would get from each outcome.

We say that $g$ is strategyproof (originally called: straightforward) if for any agent $i$ and for any strict weak order $P_{i}$ over the alternatives, there exists a strategy $s_{i}^{*}(P_{i})$ that is dominant for agent $i$ when she has preferences $P_{i}$: there is no profile of strategies for the other agents such that another strategy $s_{i}$, different from $s_{i}^{*}(P_{i})$, would lead to a strictly better outcome (in the sense of $P_{i}$). This property is desirable for a democratic decision process: it means that once the agent $i$ has identified her own preferences $P_{i}$, she can choose a strategy $s_{i}^{*}(P_{i})$ that best defends her preferences, with no need to know or guess the strategies chosen by the other agents.

We let ${\mathcal {S}}={\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}$ and denote by $g({\mathcal {S}})$ the range of $g$, i.e. the set of the possible outcomes of the game form. For example, we say that $g$ has at least 3 possible outcomes if and only if the cardinality of $g({\mathcal {S}})$ is 3 or more. Since the strategy sets are finite, $g({\mathcal {S}})$ is finite also; thus, even if the set of alternatives ${\mathcal {A}}$ is not assumed to be finite, the subset of possible outcomes $g({\mathcal {S}})$ is necessarily so.

We say that $g$ is dictatorial if there exists an agent $i$ who is a dictator, in the sense that for any possible outcome $a\in g({\mathcal {S}})$, agent $i$ has a strategy at her disposal that ensures that the result is $a$, whatever the strategies chosen by the other agents.

Gibbard's theorem—If a game form is not dictatorial and has at least 3 possible outcomes, then it is not strategyproof.

Examples

Serial dictatorship

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

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

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.

See also

• Ranked voting
• Strategic voting
• Arrow's impossibility theorem
• Duggan–Schwartz theorem