In the fields of
mechanism design
Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts a ...
and
social choice theory
Social choice theory or social choice is a theoretical framework for analysis of combining individual opinions, preferences, interests, or welfares to reach a ''collective decision'' or ''social welfare'' in some sense.Amartya Sen (2008). "Soci ...
, Gibbard's theorem is a result proven by philosopher
Allan Gibbard
Allan may refer to:
People
* Allan (name), a given name and surname, including list of people and characters with this name
* Allan (footballer, born 1984) (Allan Barreto da Silva), Brazilian football striker
* Allan (footballer, born 1989) (Al ...
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
A dictator is a political leader who possesses absolute power. A dictatorship is a state ruled by one dictator or by a small clique. The word originated as the title of a Roman dictator elected by the Roman Senate to rule the republic in times ...
, i.e. there exists a distinguished agent who can impose the outcome;
# The process limits the possible outcomes to two options only;
# The process is open to
strategic voting
Strategic voting, also called tactical voting, sophisticated voting or insincere voting, occurs in voting systems when a voter votes for another candidate or party than their ''sincere preference'' to prevent an undesirable outcome. For example, ...
: 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
In social choice theory, the Gibbard–Satterthwaite theorem is a result published independently by philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a s ...
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
Cardinal voting refers to any electoral system which allows the voter to give each candidate an independent evaluation, typically a rating or grade. These are also referred to as "rated" (ratings ballot), "evaluative", "graded", or "absolute" ...
). Gibbard's theorem can be proven using
Arrow's impossibility theorem
Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral syst ...
.
Gibbard's theorem is itself generalized by
Gibbard's 1978 theorem and
Hylland's theorem
Aanund Hylland (born 19 October 1949) is a Norwegian economist.
He completed a master's degree in mathematical logic at the University of Oslo in 1974, and a Ph.D. at the John F. Kennedy School of Government, Harvard University in 1980. He worked ...
, 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. The Gibbard's theorem assumes the collective decision results in exactly one winner and does not apply to
multi-winner voting.
Overview
Consider some voters
,
and
who wish to select an option among three alternatives:
,
and
. Assume they use
approval voting: each voter assigns to each candidate the grade 1 (approval) or 0 (withhold approval). For example,
is an authorized ballot: it means that the voter approves of candidates
and
but does not approve of candidate
. 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
and
, then
wins.
Assume that voter
prefers alternative
, then
and then
. Which ballot will best defend her opinions? For example, consider the two following situations.
* If the two other voters respectively cast ballots
and
, then voter
has only one ballot that leads to the election of her favorite alternative
:
.
* However, if we assume instead that the two other voters respectively cast ballots
and
, then voter
should not vote
because it makes
win; she should rather vote
, which makes
win.
To sum up, voter
faces a strategic voting dilemma: depending on the ballots that the other voters will cast,
or
can be a ballot that best defends her opinions. We then say that approval voting is not
strategyproof In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
: 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
be the set of ''alternatives'', which can also be called ''candidates'' in a context of voting. Let
be the set of ''agents'', which can also be called ''players'' or ''voters,'' depending on the context of application. For each agent
, let
be a set that represents the available ''strategies'' for agent
; assume that
is finite. Let
be a function that, to each
-tuple of strategies
, maps an alternative. The function
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
is
''strategyproof'' (originally called: ''straightforward'') if for any agent
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 ...
over the alternatives, there exists a strategy
that is ''dominant'' for agent
when she has preferences
: there is no profile of strategies for the other agents such that another strategy
, different from
, would lead to a strictly better outcome (in the sense of
). This property is desirable for a democratic decision process: it means that once the agent
has identified her own preferences
, she can choose a strategy
that best defends her preferences, with no need to know or guess the strategies chosen by the other agents.
We let
and denote by
the range of
, i.e. the set of the ''possible outcomes'' of the game form. For example, we say that
has at least 3 possible outcomes if and only if the cardinality of
is 3 or more. Since the strategy sets are finite,
is finite also; thus, even if the set of alternatives
is not assumed to be finite, the subset of possible outcomes
is necessarily so.
We say that
is ''
dictatorial
A dictator is a political leader who possesses absolute power. A dictatorship is a state ruled by one dictator or by a small clique. The word originated as the title of a Roman dictator elected by the Roman Senate to rule the republic in times ...
'' if there exists an agent
who is a ''dictator'', in the sense that for any possible outcome
, agent
has a strategy at her disposal that ensures that the result is
, 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 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
elected, then he just has to communicate a preference order where
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
wins if it gets two thirds of the votes, and
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 count is a family of positional voting rules which gives each candidate, for each ballot, a number of points corresponding to the number of candidates ranked lower. In the original variant, the lowest-ranked candidate gets 0 points, the ...
. 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.
Notes and references
See also
*
Arrow's impossibility theorem
Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral syst ...
*
Gibbard–Satterthwaite theorem
In social choice theory, the Gibbard–Satterthwaite theorem is a result published independently by philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a s ...
{{Portal, Economy
Voting theory
Economics theorems
Theorems in discrete mathematics
Social choice theory