Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 37 ยท Applications

Voting, Condorcet Paradox and Arrow's Theorem

Compare plurality, runoff, Borda and Condorcet voting in Python, see why rankings can cycle, and learn what Arrow's impossibility theorem and Gibbard-Satterthwaite say.

When a group must choose among alternatives, the rule for combining individual preferences into a collective choice can change the winner. Social choice theory studies such rules. It is closely tied to game theory because voters can vote strategically, and because the main results say that no perfect rule exists. This lesson implements the common voting systems, finds situations where they disagree, and states the two big impossibility theorems.

Preference profiles and voting rules

A preference profile lists, for each voter, a ranking of the candidates. A voting rule maps a profile to a winner. We use "ballots with counts": 6 voters rank A > B > C, and so on.

Python Four voting rules on one profile

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rules disagree. Plurality picks A (35 first-place votes). The runoff method, which eliminates the weakest candidate round by round, picks C, and so does Borda. The Condorcet test finds yet another winner, B, who beats every rival head to head (for example 60 to 40 against C). Three different winners from one set of ballots. Which is "right" depends on what you value.

Common voting rules

Plurality Most first-place votes wins
Runoff Drop the weakest, recount
Borda Points for each rank position
Condorcet Beats everyone head to head

Different rules can pick different winners.

1 / 2

The Condorcet paradox

A Condorcet winner beats every other candidate in a head-to-head vote. It need not exist. Take three voters with rankings A > B > C, B > C > A and C > A > B. A majority (2 of 3) prefers A to B, a majority prefers B to C, and a majority prefers C to A. Group preferences cycle, even though each voter is perfectly consistent.

Python A cycle in majority preferences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a cycle exists, the agenda (the order of pairwise votes) determines the outcome, which is why controlling the agenda is powerful.

Strategic voting

Voters can misreport. In plurality, a voter whose favorite has no chance may vote for a "lesser evil", which is why small parties struggle (Duverger's law). The program checks whether a group of voters can change the plurality result by switching their ballots.

Python Strategic voting under plurality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Honestly, R wins with 40 votes, the outcome the centrists like least. If 11 of them vote for L instead of their true favorite, L wins with 41. Those voters gained by misreporting. The general fact is the Gibbard-Satterthwaite theorem below.

Arrow's impossibility theorem

Kenneth Arrow asked: is there a way to combine rankings into a group ranking that is always sensible? He listed reasonable requirements:

  • Unrestricted domain: any set of voter rankings is allowed.
  • Pareto efficiency: if everyone prefers X to Y, the group does too.
  • Independence of irrelevant alternatives (IIA): the group's ranking of X and Y depends only on how voters rank X and Y, not on other candidates.
  • Non-dictatorship: no single voter determines the group ranking.

Arrow's theorem: with three or more alternatives, no rule that produces a complete ranking satisfies all four. Every rule violates at least one. Borda violates IIA (adding a third candidate can flip the order of two others), plurality violates it too, and so on.

Gibbard-Satterthwaite

For strategies rather than rankings: any voting rule with three or more possible winners that is onto (every candidate can win) and non-dictatorial is manipulable: for some profile, some voter can get a better result by lying. So strategy-proofness, in the sense of VCG for money, is impossible for general voting without money (it is possible in restricted settings, such as single-peaked preferences, where the median voter rule is strategy-proof).

Python The median voter rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No lie moves the median past the third voter's ideal point 30: the extreme voter cannot do better than the truth, illustrating that the median rule is strategy-proof for single-peaked preferences.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a Condorcet winner?

    It can fail to exist, as the Condorcet paradox shows.
  2. 2. What is the Condorcet paradox?

    Even with consistent individual rankings, the group ranking can be intransitive.
  3. 3. Which of these is NOT one of Arrow's conditions?

    Majority rule is a particular rule, not one of the conditions.
  4. 4. Gibbard-Satterthwaite says that any onto, non-dictatorial voting rule with three or more candidates is...

    Some voter can sometimes get a better outcome by misreporting preferences.

Summary

  • Plurality, runoff, Borda and Condorcet rules can choose different winners from the same ballots.
  • Majority preferences can cycle (Condorcet paradox), so a Condorcet winner may not exist.
  • Strategic voting is common under plurality.
  • Arrow's theorem: with three or more alternatives, no rule satisfies unrestricted domain, Pareto, IIA and non-dictatorship.
  • Gibbard-Satterthwaite: every reasonable voting rule is manipulable, except in restricted domains such as single-peaked preferences, where the median rule works.

Next: Project: An Axelrod Tournament