Gibbard's theorem
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold: 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. 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. Overview. Consider some voters formula_1, formula_2 and formula_3 who wish to select an option among three alternatives: formula_4, formula_5 and formula_6. Assume they use approval voting: each voter assigns  to each candidate the grade 1 (approval) or 0 (withhold approval). For example, formula_7 is an authorized ballot: it means that the voter approves of candidates formula_4 and formula_5 but does not approve of candidate formula_6. 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 formula_4 and formula_5, then formula_4 wins. Assume that voter formula_1 prefers alternative formula_4, then formula_5 and then formula_6. Which ballot will best defend her opinions? For example, consider the two following situations . To sum up, voter formula_1 faces a strategic voting dilemma: depending on the ballots that the other voters will cast, formula_22 or formula_7 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 formula_33 be the set of "alternatives", which can also be called "candidates" in a context of voting. Let formula_34 be the set of "agents", which can also be called "players" or "voters," depending on the context of application. For each agent formula_35, let formula_36 be a set that represents the available "strategies" for agent formula_35; assume that formula_36 is finite. Let formula_39 be a function that, to each formula_40 -tuple of strategies formula_41, maps an alternative. The function formula_39 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 formula_39 is "strategyproof" (originally called: "straightforward") if for any agent formula_35 and for any strict weak order formula_45 over the alternatives, there exists a strategy formula_46 that is "dominant" for agent formula_35 when she has preferences formula_45: there is no profile  of strategies for the other agents such that another strategy formula_49, different from formula_46, would lead to a strictly better outcome (in the sense of formula_45). This property is desirable for a democratic decision process: it means that once the agent formula_35 has identified her own preferences formula_45, she can choose a strategy formula_46 that best defends her preferences, with no need to know or guess the strategies chosen by the other agents. We let formula_55 and denote by formula_56 the range of formula_39, i.e. the set of the "possible outcomes" of the game form. For example, we say that  formula_39 has at least 3 possible outcomes if and only if the cardinality of formula_56 is 3 or more. Since the strategy sets are finite, formula_56 is finite also; thus, even if the set of alternatives formula_33 is not assumed to be finite, the subset of possible outcomes formula_56 is necessarily so. We say that formula_39 is "dictatorial" if there exists an agent formula_35 who is a "dictator", in the sense that for any possible outcome formula_65, agent formula_35 has a strategy at her disposal that ensures that the result is formula_4, whatever the strategies chosen by the other agents . 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 formula_4 elected, then he just has to communicate a preference order where formula_4 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 formula_4 wins if it gets two thirds of the votes, and formula_5 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.