In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973.
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).
[citation needed] 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.
is an authorized ballot: it means that the voter approves of candidates
Once the ballots are collected, the candidate with highest total grade is declared the winner.
faces a strategic voting dilemma: depending on the ballots that the other voters will cast,
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 (unilateral), or if the process limits the outcome to two possible options only (duple).
be the set of alternatives, which can also be called candidates in a context of voting.
be the set of agents, which can also be called players or voters, depending on the context of application.
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.
is strategyproof (originally called: straightforward) if for any agent
This property is desirable for a democratic decision process: it means that once the agent
that best defends her preferences, with no need to know or guess 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.
We assume that each voter communicates a strict weak order over the candidates.
If there is still several non-eliminated candidates after all ballots have been examined, then an arbitrary tie-breaking rule is used.
It is also dictatorial, and its dictator is voter 1: if he wishes to see candidate
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).
Many other game forms are strategyproof and not dictatorial: for example, assume that the alternative
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.
Gibbard's 1978 theorem states that a nondeterministic voting method is only strategyproof if it's a mixture of unilateral and duple rules.
For instance, the rule that flips a coin and chooses a random dictator if the coin lands on heads, or chooses the pairwise winner between two random candidates if the coin lands on tails, is strategyproof.