Gibbard–Satterthwaite theorem

In social choice theory, the Gibbard–Satterthwaite theorem is a result published independently by philosopher Allan Gibbard in 1973[1] and economist Mark Satterthwaite in 1975.[2] It deals with deterministic ordinal electoral systems that choose a single winner. It states that for every voting rule, one of the following three things must hold:

  1. The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
  2. The rule limits the possible outcomes to two alternatives only; or
  3. The rule is susceptible to tactical voting: in certain conditions some voter's sincere ballot may not defend their opinion best.

While the scope of this theorem is limited to ordinal voting, Gibbard's theorem is more general, in that it deals with processes of collective decision that may not be ordinal: for example, voting systems where voters assign grades to candidates. Gibbard's 1978 theorem and Hylland's theorem are even more general and extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the voters' actions but may also involve a part of chance.

Informal description

Consider some voters named , and , who wish to select an option among four candidates named , , and . Assume that they use the Borda count: each voter communicates her preference order over the candidates. For each ballot, 3 points are assigned to the top candidate, 2 points to the second candidate, 1 point to the third one and no point to the last one. Once all ballots have been counted, the candidate with most points is declared the winner.

Assume that preferences are as follows.

This notation means that voter prefers , then , and ; voters and both prefer , then , and . If the voters cast sincere ballots, then the scores are: . Hence, candidate get elected, with 7 points.

But voter can figure out that another ballot defend her opinions better. Assume that she modifies her ballot, in order to produce the following situation.

Voter has strategically upgraded candidate and downgraded candidate . Now, the scores are: . Hence, is elected. Voter is satisfied of her ballot modification, because she prefers the outcome to , which is the outcome she would obtain if she voted sincerely.

We say that the Borda count is manipulable: there exists situations where a sincere ballot does not defend a voter's preferences best.

Unfortunately, the Gibbard–Satterthwaite theorem states that a voting rule must be manipulable, except possibly in two cases: if there is a distinguished voter who has a dictatorial power, or if the rule limits the possible outcomes to two options only.