Gibbard's theorem

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.

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.

• Arrow's impossibility theorem
• Gibbard–Satterthwaite theorem