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:

1. The process is dictatorial, i.e. there exists a distinguished agent who can impose the outcome;
2. The process limits the possible outcomes to two options only;
3. The process is open to strategic voting: once an agent has identified their preferences, it is possible that they have no action at their disposal that best defends these preferences irrespective of the other agents' actions.

A corollary of this theorem is Gibbard–Satterthwaite theorem about voting rules. The main difference between the two is that Gibbard–Satterthwaite theorem is limited to ranked (ordinal) voting rules: a voter's action consists in giving a preference ranking over the available options. 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 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^[2] and Hylland's theorem,^[3] 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.

Overview

Consider some voters ${\displaystyle 1}$, ${\displaystyle 2}$ and ${\displaystyle 3}$ who wish to select an option among three alternatives: ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle c}$. Assume they use approval voting: each voter assigns to each candidate the grade 1 (approval) or 0 (withhold approval). For example, ${\displaystyle (1,1,0)}$ is an authorized ballot: it means that the voter approves of candidates ${\displaystyle a}$ and ${\displaystyle b}$ but does not approve of candidate ${\displaystyle 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 ${\displaystyle a}$ and ${\displaystyle b}$, then ${\displaystyle a}$ wins.

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

• If the two other voters respectively cast ballots ${\displaystyle (0,1,1)}$ and ${\displaystyle (1,1,1)}$, then voter ${\displaystyle 1}$ has only one ballot that leads to the election of her favorite alternative ${\displaystyle a}$ : ${\displaystyle (1,0,0)}$.
• However, if we assume instead that the two other voters respectively cast ballots ${\displaystyle (0,0,1)}$ and ${\displaystyle (0,1,1)}$, then voter ${\displaystyle 1}$ should not vote ${\displaystyle (1,0,0)}$ because it makes ${\displaystyle c}$ win; she should rather vote ${\displaystyle (1,1,0)}$, which makes ${\displaystyle b}$ win.

To sum up, voter ${\displaystyle 1}$ faces a strategic voting dilemma: depending on the ballots that the other voters will cast, ${\displaystyle (1,0,0)}$ or ${\displaystyle (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 ${\displaystyle {\mathcal {A}}}$ be the set of alternatives, which can also be called candidates in a context of voting. Let ${\displaystyle {\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 ${\displaystyle i}$, let ${\displaystyle {\mathcal {S}}_{i}}$ be a set that represents the available strategies for agent ${\displaystyle i}$; assume that ${\displaystyle {\mathcal {S}}_{i}}$ is finite. Let ${\displaystyle g}$ be a function that, to each ${\displaystyle n}$-tuple of strategies ${\displaystyle (s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$, maps an alternative. The function ${\displaystyle 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 ${\displaystyle g}$ is strategyproof (originally called: straightforward) if for any agent ${\displaystyle i}$ and for any strict weak order ${\displaystyle P_{i}}$ over the alternatives, there exists a strategy ${\displaystyle s_{i}^{*}(P_{i})}$ that is dominant for agent ${\displaystyle i}$ when she has preferences ${\displaystyle P_{i}}$: there is no profile of strategies for the other agents such that another strategy ${\displaystyle s_{i}}$, different from ${\displaystyle s_{i}^{*}(P_{i})}$, would lead to a strictly better outcome (in the sense of ${\displaystyle P_{i}}$). This property is desirable for a democratic decision process: it means that once the agent ${\displaystyle i}$ has identified her own preferences ${\displaystyle P_{i}}$, she can choose a strategy ${\displaystyle 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 ${\displaystyle {\mathcal {S}}={\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$ and denote by ${\displaystyle g({\mathcal {S}})}$ the range of ${\displaystyle g}$, i.e. the set of the possible outcomes of the game form. For example, we say that ${\displaystyle g}$ has at least 3 possible outcomes if and only if the cardinality of ${\displaystyle g({\mathcal {S}})}$ is 3 or more. Since the strategy sets are finite, ${\displaystyle g({\mathcal {S}})}$ is finite also; thus, even if the set of alternatives ${\displaystyle {\mathcal {A}}}$ is not assumed to be finite, the subset of possible outcomes ${\displaystyle g({\mathcal {S}})}$ is necessarily so.

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

Examples

Notes and references

See also

• Arrow's impossibility theorem
• Gibbard–Satterthwaite theorem