Gibbard's Theorem
   HOME

TheInfoList



OR:

In the fields of
mechanism design Mechanism design (sometimes implementation theory or institution design) is a branch of economics and game theory. It studies how to construct rules—called Game form, mechanisms or institutions—that produce good outcomes according to Social ...
and
social choice theory Social choice theory is a branch of welfare economics that extends the Decision theory, theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures (social welfare function, soc ...
, Gibbard's theorem is a result proven by philosopher
Allan Gibbard Allan Fletcher Gibbard (born 1942) is an American philosopher who is the Richard B. Brandt Distinguished University Professor of Philosophy Emeritus at the University of Michigan, Ann Arbor. Gibbard has made major contributions to contemporary e ...
in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold: # The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome. # The process limits the possible outcomes to two options only. # The process is not straightforward; the optimal ballot for a voter "requires
strategic voting Strategic or tactical voting is voting in consideration of possible ballots cast by other voters in order to maximize one's satisfaction with the election's results. Gibbard's theorem shows that no voting system has a single "always-best" strat ...
", i.e. it depends on their beliefs about other voters' ballots. A corollary of this theorem is the
Gibbard–Satterthwaite theorem The Gibbard–Satterthwaite theorem is a theorem in social choice theory. It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961 and then proved independently by the philosopher Allan Gibbard in ...
about voting rules. The key difference between the two theorems is that Gibbard–Satterthwaite applies only to
ranked voting Ranked voting is any voting system that uses voters' Ordinal utility, rankings of candidates to choose a single winner or multiple winners. More formally, a ranked vote system depends only on voters' total order, order of preference of the cand ...
. 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. 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 Rated, evaluative, graded, or cardinal voting rules are a class of voting methods that allow voters to state how strongly they support a candidate, by giving each one a grade on a separate scale. The distribution of ratings for each candidateâ ...
). Gibbard's theorem can be proven using
Arrow's impossibility theorem Arrow's impossibility theorem is a key result in social choice theory showing that no ranked-choice procedure for group decision-making can satisfy the requirements of rational choice. Specifically, Arrow showed no such rule can satisfy the ind ...
. Gibbard's theorem is itself generalized by Gibbard's 1978 theorem and Hylland's theorem,Hylland, Aanund
Strategy proofness of voting procedures with lotteries as outcomes and infinite sets of strategies
1980.
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. A similar result for multi-winner voting is the
Duggan–Schwartz theorem The Duggan–Schwartz theorem (named after John Duggan and Thomas Schwartz) is a result about voting systems designed to choose a nonempty set of winners from the preferences of certain individuals, where each individual ranks all candidates in or ...
.


Overview

Consider some voters 1, 2 and 3 who wish to select an option among three alternatives: a, b and c. Assume they use
approval voting Approval voting is a single-winner rated voting system where voters can approve of all the candidates as they like instead of Plurality voting, choosing one. The method is designed to eliminate vote-splitting while keeping election administration ...
: each voter assigns to each candidate the grade 1 (approval) or 0 (withhold approval). For example, (1, 1, 0) is an authorized ballot: it means that the voter approves of candidates a and b but does not approve of candidate 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 a and b, then a wins. Assume that voter 1 prefers alternative a, then b and then c. Which ballot will best defend her opinions? For example, consider the two following situations. * If the two other voters respectively cast ballots (0, 1, 1) and (1, 1, 1), then voter 1 has only one ballot that leads to the election of her favorite alternative a : (1, 0, 0). * However, if we assume instead that the two other voters respectively cast ballots (0, 0, 1) and (0, 1, 1), then voter 1 should not vote (1, 0, 0) because it makes c win; she should rather vote (1, 1, 0), which makes b win. To sum up, voter 1 faces a strategic voting dilemma: depending on the ballots that the other voters will cast, (1, 0, 0) or (1, 1, 0) can be a ballot that best defends her opinions. We then say that approval voting is not
strategyproof In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private ...
: 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'').


Formal statement

Let \mathcal be the set of ''alternatives'', which can also be called ''candidates'' in a context of voting. Let \mathcal = \ be the set of ''agents'', which can also be called ''players'' or ''voters,'' depending on the context of application. For each agent i, let \mathcal_i be a set that represents the available ''strategies'' for agent i; assume that \mathcal_i is finite. Let g be a function that, to each n-tuple of strategies (s_1, \ldots, s_n) \in \mathcal_1 \times \cdots \times \mathcal_n, maps an alternative. The function 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 g is ''strategyproof'' (originally called: ''straightforward'') if for any agent i and for any
strict weak order In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered set ...
P_i over the alternatives, there exists a strategy s_i^*(P_i) that is ''dominant'' for agent i when she has preferences P_i: there is no profile of strategies for the other agents such that another strategy s_i, different from s_i^*(P_i), would lead to a strictly better outcome (in the sense of P_i). This property is desirable for a democratic decision process: it means that once the agent i has identified her own preferences P_i, she can choose a strategy 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 \mathcal = \mathcal_1 \times \cdots \times \mathcal_n and denote by g(\mathcal) the range of g, i.e. the set of the ''possible outcomes'' of the game form. For example, we say that g has at least 3 possible outcomes if and only if the cardinality of g(\mathcal) is 3 or more. Since the strategy sets are finite, g(\mathcal) is finite also; thus, even if the set of alternatives \mathcal is not assumed to be finite, the subset of possible outcomes g(\mathcal) is necessarily so. We say that g is '' dictatorial'' if there exists an agent i who is a ''dictator'', in the sense that for any possible outcome a \in g(\mathcal), agent i has a strategy at her disposal that ensures that the result is a, whatever the strategies chosen by the other agents.


Examples


Serial dictatorship

We assume that each voter communicates a
strict weak order In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered set ...
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 equally 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 a elected, then he just has to communicate a preference order where a 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 a wins if it gets two thirds of the votes, and b 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 The Borda method or order of merit is a positional voting rule that gives each candidate a number of points equal to the number of candidates ranked below them: the lowest-ranked candidate gets 0 points, the second-lowest gets 1 point, and so on ...
. 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.


Extensions

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. Nondeterministic methods have been devised that approximate the results of deterministic methods while being strategyproof.


Notes and references


See also

*
Arrow's impossibility theorem Arrow's impossibility theorem is a key result in social choice theory showing that no ranked-choice procedure for group decision-making can satisfy the requirements of rational choice. Specifically, Arrow showed no such rule can satisfy the ind ...
*
Gibbard–Satterthwaite theorem The Gibbard–Satterthwaite theorem is a theorem in social choice theory. It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961 and then proved independently by the philosopher Allan Gibbard in ...
{{Portal, Economy Voting theory Economics theorems Theorems in discrete mathematics