Gibbard–Satterthwaite theorem

Formal statement

Let ${\displaystyle \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 ${\displaystyle \mathcal{N}=\{1,\dots ,n\}}$ the set of voters. Let ${\displaystyle \mathcal{P}}$ be the set of strict weak orders over ${\displaystyle \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 ${\displaystyle f:{\mathcal{P}}^n\to \mathcal{A}}$. Its input is a profile of preferences ${\displaystyle (P_1,\dots ,P_n)\in {\mathcal{P}}^n}$ and it yields the identity of the winning candidate.

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

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

We say that ${\displaystyle f}$ is dictatorial if and only if there exists a voter ${\displaystyle 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.

Corollary for strict preferences

We now consider the case where by assumption, a voter cannot be indifferent between two candidates. We denote by ${\displaystyle \mathcal{L}}$ the set of strict total orders over ${\displaystyle \mathcal{A}}$ and we define a strict voting rule as a function ${\displaystyle 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 ${\displaystyle \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.

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 ${\displaystyle f}$ is assumed to be Pareto-efficient.

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

It is possible to prove that, if ${\displaystyle f}$ is non-manipulable and non-dictatorial, ${\displaystyle \mathrm{Rank}}$ satisfies independence of irrelevant alternatives. Arrow's impossibility theorem says that, when there are three or more alternatives, such a ${\displaystyle \mathrm{Rank}}$ function must be a dictatorship. Hence, such a voting rule ${\displaystyle f}$ 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 P₁ for agent 1, define Menu₂(P₁) as the option set of 2 - the set of all candidates that could potentially be elected when agent 1 votes P₁ (ranging over all possible votes of agent 2).

The following lemmas are proved for a strategyproof rule f:

1. f(P₁,P₂) = Best(P₂, Menu₂(P₁)), as otherwise agent 2 could manipulate. Similarly, f(P₁,P₂) = Best(P₁, Menu₁(P₂)), as otherwise agent 1 could manipulate.
2. For any preference reported by agent 1, the best candidate by that preference is on the menu for agent 2. Formally, Best(P₁,Range(f)) in Menu₂(P₁). Proof: Let OPT₁ := Best(P₁,Range(f)). Since OPT₁ is in range f, it equals R(P₁^*,P₂^*) for some profile (P₁^*,P₂^*). Hence, it is in Menu₁(P₂*). By Lemma 1, f(P₁,P₂^*) = Best(P₁, Menu₁(P₂*)) = OPT₁ = Best(P₂*, Menu₂(P₁)). In particular, OPT₁ is in Menu₂(P₁).
3. Unanimity holds: If Best(P₁,Range(f)) = Best(P₂,Range(f)) = x, then f(P₁,P₂)=x. Proof: follows from Lemmas 2 and 1. In particular, for every preference P, f(P,P) = Best(P, Range(f)).
4. The menu depends only on the best element; formally, if Best(P₁,Range(f)) = Best(P₁*,Range(f)) = x, then Menu₂(P₁)=Menu₂(P₁*). Proof: By Lemma 2, x is in both Menu₂(P₁) and Menu₂(P₁*). If the menus are not equal, then (wlog) some candidate z is in Menu₂(P₁) and not in Menu₂(P₁*). Let P₂* be a preference that ranks z first, x second, and then all other candidates. Then, by Lemma 1, f(P₁,P₂*) = z and f(P₁*,P₂*) = x. But this means that x is in Menu₁(P₂), so by Lemma 1 again, f(P₁,P₂*) = Best(P₁, Menu₁(P₂*))=x --- a contradiction [agent 1 could manipulate from P₁ to P₁*].
   • Hence, we can write from now on Menu₂(x), meaning, Menu₂(P₁) for all P₁ with best element x; by Lemma 2, x in Menu₂(x) for all x.
5. For every x and z in Range(f), and for every P_x with best candidate x and P_z with best candidate z, P_x prefers Best(P_z,Menu₂(x)) to z. Proof: Take x,z,P_x,P_z as in the lemma statement, and let y=Best(P_z,Menu₂(x)). Assume by contradiction that P_x prefers z to y. By Lemma 1, f(P_x,P_z)=Best(P_z, Menu₂(x)) = y. By Lemma 3, f(P_z,P_z)=Best(P_z,Range(f)) = z. But this means that z is in Menu₁(P_z), so y cannot be Best(P_x, Menu₁(P_z)). But by Lemma 1, f(P_x,P_z) = Best(P_x, Menu₁(P_z)) --- a contradiction [agent 1 can profitably manipulate from P_x to P_z].
6. For every x in Range(f), Menu₂(x) is either a singleton or the entire Range(f). Proof: By contradiction, let x be some candidate that violates that statement. So Menu₂(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 P_x with best candidate x, that prefers z to y; and a preference P_z with best candidate z, that ranks y second. Then Best(P_z, Menu₂(x)) = y but P_x prefers z to y, contradicting Lemma 5.
7. Menu₂(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 Menu₂(x) is a singleton (and must be equal to {x}), and y some other candidate for which Menu₂(y) = Range(f). Let P_y 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 Menu₂(P_y) = Range(f), there is some P₂ for which f(P_y,P₂)=z. But then agent 1 could manipulate from P_y to some preference P_x with best element x, as this would force the outcome to be x.

Based on Lemma 7, there are two options:

• If Menu₂(P₁) is a singleton for all P₁, then by Lemma 2 this singleton must be Best(P₁,Range(f)). Then f(P₁,P₂) = Best(P₁,Range(f)), so 1 is a dictator.
• If Menu₂(P₁) = Range(f) for all P₁, then by Lemma 1 f(P₁,P₂) = Best(P₂, 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

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.

Multi-winner voting rules

The Duggan–Schwartz theorem extend this result in another direction, by dealing with deterministic voting rules that choose multiple winners.

Restricted preference domains

The GS theorem crucially relies on the fact that all preference rankings over the sets of candidates are possible. The theorem might not hold under domain restrictions, that is, when the agents are allowed to express preferences from a restricted set. There are various works studying possibility and impossibility results for restricted preference domains.

Single-peaked preferences

When the agents are restricted to have single-peaked preferences, the GS theorem does not hold, as the median voting rule is strategyproof and non-dictatorial.

Quadratic preferences in a Euclidean space

Border and Jordan consider voting on continuous domains, when the set of candidates is a Euclidean space R^d, or at least a cartesian product of intervals (an axes-parallel box) in it. They study the restriction that all agents have quadratic utilities --- utility functions of the form: ${\displaystyle u(x)=-(x-p{)}^T\cdot H\cdot (x-p)}$, where p is a candidate point and H is a positive definite matrix.

They prove that any strategyproof rule that respects unanimity (if all agents have the same peak, then this peak is the outcome) is dictatorial. Equivalently, any strategyproof rule that is onto the set of candidates is dictatorial.

Their proof uses quadratic utilities in which the matrix H has off-diagonal elements. In the special case that H is a diagonal matrix, the utility functions become separable (the utility is a simple sum of utilities from the m issues). In that case, mechanisms based on multi-dimensional extension of the median voting rule are strategyproof and respect unanimity. However, if H is allowed to have even infinitesimally small off-diagonal elements, the dictatorship theorem prevails.

Continuous preferences in any metric space

Barbera and Peleg consider a more general setting, in the set of candidates can be any metric space M (e.g. the set of all possible facility locations). If agents can have arbitrary utility functions over M, then GS holds as-is. Barbera and Peleg make the natural assumption that agents can only have continuous utility functions over M. They prove that any strategyproof rule whose range contains at least three candidates is dictatorial, even in this restricted domain.

Their proof is an adaptation of their Proof by Menus (above) to a proof using only continuous utilities. As a preliminary result, they prove that it is sufficient to consider preferences with a single best candidate. They prove that, if a voting rule f is dictatorial when restricted to preferences with a single best candidate, then it remains dictatorial without that restriction. They also prove that this restriction does not change the range of f. They also prove that:

• Range(f) is a closed set.
• For every utility continuous function u₁, Menu₂(u₁) is a closed set.

Lemmas 1--3 from above do not make any domain assumptions, so they still hold.

Lemma 4 (menu depends only on best element; if Best(u₁,Range(f)) = Best(u₁*,Range(f)) = x, then Menu₂(u₁)=Menu₂(u₁*)) requires a different proof, as the preference P₂* assumed in that proof is not necessarily continuous. Proof: By Lemma 2, x is in both Menu₂(u₁) and Menu₂(u₁*). If the menus are not equal, then (wlog) some candidate z is in Menu₂(u₁) and not in Menu₂(u₁*). Let r be a positive real number such that Ball(z,2r) --- the ball of radius 2r around z --- does not intersect Menu₂(u₁*).

Let u_2z be the following continuous utility function: u_2z(y) = ${\displaystyle \frac{d(y,M\setminus Ball(z,r))}{d(y,z)+d(y,M\setminus Ball(z,r))}}$, where M is the set of all candidates, and d is its metric. This function looks like a dome with a peak at z; it has u_2z(t)=0 for all t in Menu₂(u₁*), and z = Best(u_2z).

Similarly, let u_2x be the following continuous utility function: u_2x(y) = ${\displaystyle \frac{d(y,M\setminus Ball(x,r))}{2[d(y,x)+d(y,M\setminus Ball(x,r))]}}$; it is a dome with a peak at x. Note that Ball(z,r) and Ball(x,r) do not intersect.

Finally, let u₂* := u_2z+u_2x; it has a high dome with a peak at z, and a distinct lower dome with a peak at x.

We have f(u₁,u₂*) = Best(u₂*,Menu₂(u₁)) = z, as z is in Menu₂(u₁). Simultaneously, f(u₁*,u₂*) = Best(u₂*,Menu₂(u₁*)) = x, as the entire dome with peak at z is not in Menu₂(u₁*). Hence, when 2 reports u₂*, agent 1 can gain by manipulating from u₁ to u₁^*.

Hence, we can still write the menu as a function of the best element: Menu₂(x) = Menu₂(u₁) for all u₁ with best element x.

Lemma 5 does not make any domain assumptions, so it still holds given Lemma 4.

Lemma 6 (For every x in Range(f), Menu₂(x) is either a singleton or the entire Range(f)) requires a similar proof. Proof: By contradiction, let x be some candidate that violates that statement. So Menu₂(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 continuous function u_x with global maximum x and u_x(z) > u_x(y), and a continuous function u_z with global maximum z, whose maximum on Menu₂(x) is y. Then Best(u_z, Menu₂(x)) = y. Then u_x(z) > u_x(Best(u_z, Menu₂(x))), contradicting Lemma 5.

The rest of the proof is similar to the finite case: Lemma 6 implies Lemma 7, which implies that either agent 1 or agent 2 is a dictator.

The same proof holds for any utility domain that satisfies the following:

• If some candidate x is in both Menu₂(u₁) and Menu₂(u₁*), and some other candidate z is in Menu₂(u₁) and not in Menu₂(u₁*), then the domain contains a utility function u₂ with Best(u₂, Menu₂(u₁)) = z and Best(u₂, Menu₂(u₁*)) = x.
• For every three candidates x y and z, such that Menu₂(x) contains y but does not contain z, there is a function u₁ with global maximum at x and with u₁(z) > u₁(y), and a function u₂ with a global maximum at z and whose maximum on Menu₂(x) is y.
• For every candidate y with Menu₂(y) = Range(f), there is a utility function with maximum element y, that prefers x to some third candidate z.

Quadratic preferences in any convex set

Zhou extends the results of Border and Jordan by allowing the set of candidates M to be any convex subset of R^d. An example scenario is voting on the amount of public goods to produce, as in budget-proposal aggregation (in which M is a simplex - the set of all possible ways to allocate a fixed budget among several public goods). Like Barbera and Peleg, he also restricts the agents' utilities to continuous functions; like Border and Jordan, he assumes that agents have quadratic utility functions. He proves that, if f is strategyproof, and the dimension of Range(f) is at least 2, then f is dictatorial.

• [If the dimension of Range(f) is 1, then convexity of preferences implies single-peakedness, so the median voting rule is strategyproof.]

The proof uses the same lemmas 1--3 above (which are domain-independent), as well as the closedness of Range(f) and Menu₂(u₁). In addition, he proves that Menu₂(u₁) is star-shaped relative to Range(f) with center x = Best(u₁,Range(f)). This means that for every point y in Menu₂(u₁), the segment [x,y] is contained in Menu₂(u₁). Based on star-shapedness, he proves Lemma 4 (the menu depends only on the best element). This leads to Lemma 6 (the menu is either a singleton or Range(f)), from which dictatorship follows.

He later studies a further restriction, in which the agents' utilities should be both quasiconcave and monotonically increasing.

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.

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.