Maths●●●●●Difficulty 5 of 5

Is there any voting system where telling the truth is always your best move?

In 1876 Lewis Carroll warned that a voting rule can make an election "more of a game of skill than a real test of the wishes of the electors". Nearly a century later two theorists proved that any ranked rule picking one winner from three or more options can be gamed, unless one voter is a dictator.

▶ Start the story

Not for any ranked rule with three or more possible winners, unless one voter holds all the power. That is the Gibbard–Satterthwaite theorem. It deals with deterministic ordinal electoral systems, where voters rank the candidates, and shows that for every voting rule of this form at least one of the following must hold. The rule is dictatorial: there is a distinguished voter who can choose the winner. Or the rule limits the possible outcomes to two alternatives only. Or the rule is manipulable: there is no single always-best strategy, meaning one that does not depend on other voters' preferences or behavior.

Manipulable means a sincere ballot is not always your best ballot. In a standard example, three voters named Alice, Bob and Carol choose among four candidates, a, b, c and d, with the Borda count (3, 2, 1 and 0 points). Alice ranks a-b-c-d, while Bob and Carol both rank c-b-d-a. Honest ballots give c 7 points, b 6, a 3 and d 2, so c wins. But Alice can vote strategically and change the result. If she ranks b-a-d-c instead, b scores 7 and c 6, so b is elected, and Alice is satisfied, because she prefers b to c, the outcome she would have obtained by voting sincerely. The Borda count is manipulable: there are situations where a sincere ballot does not defend a voter's preferences best.

The theorem 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 1973 and the economist Mark Satterthwaite in 1975. Its meaning is disputed. The old interpretation sees it as a proof that "democracy is impossible", since a rule that must yield a single winner is either dictatorial or open to manipulation. The modern interpretation sees it as a proof that there is no point looking for an agreement using a voting rule when there is no agreement, and so as an argument for a "none of above" option in every vote, as the Debian General Resolution Procedure does.

From a warning to a theorem
  1. 1876

    Lewis Carroll notices the strategic side of voting

  2. 1961

    Dummett and Farquharson conjecture it

  3. 1973

    Gibbard proves it

  4. 1975

    Satterthwaite publishes his independent proof

Quiz me

0/3

  1. 1.For a deterministic ranked voting rule with at least three possible winners, which statement does the theorem support?
  2. 2.Why is a dictatorship strategyproof, though nobody wants it?
  3. 3.What restriction on voters' preferences makes an honest rule possible, as the median rule shows?

Recap

With three or more possible winners, any ranked rule either gives one voter all the power or sometimes rewards a voter for lying.

💡 A trick to remember it · With three or more doors, either one person holds the key to all of them, or somebody can pick the lock.

Surprising fact · Lewis Carroll noticed in 1876 that voting could become a game of skill rather than a test of the electors' wishes.

Sources (1)

No source, no claim. Every fact in this lesson (22 claims) cites at least one of these.

  1. [1]Gibbard–Satterthwaite theorem · Wikipedia
More lessons in ➗ Maths (3) See all maths lessons →

One more light on your map.

Get one lesson like this every day, about the things you love. Free, in two or five minutes.

Get the share card for this lesson ↗