Arrow's Impossibility Theorem, Resolved

Before you cringe, I am not, as a random blogger, claiming to have resolved a 70-year-old Nobel-prize-winning dilemma.

Instead, the answer comes from Eric Pacuit who wrote Stanford Encyclopedia of Philosophy’s excellent summary of Voting Methods and Wesley H. Holiday, a professor at Berkeley.

Before we get into the solution, a brief introduction to the problem itself. If you’re familiar, jump to the page break.

Michael Nielsen once wrote: “You are almost certainly better off reading deeply in the ten most important papers of a research field than you are skimming the top five hundred.”

In voting and in social choice theory more generally, Arrow’s original paper certainly qualifies. It is approachable, clearly argued, and from one of the greatest economists of the last century at his absolute best.

But if you really don’t have time, the brief summary is: it is formally impossible to produce a voting system (of a certain class) that satisfies 3 basic criteria, including Independence of Irrelevant Alternatives. As Arrow states: “the choice made by society from any given set of alternatives should be independent of the very existence of alternatives outside the given set.”

This seems obvious, but is totally violated by many common voting systems. In Plurality Voting, a “spoiler” candidate is one who has no chance of winning, but alters the results for other candidates. Consider a close race between a Democrat and Republican “spoiled” when votes are diverted to a Green Party or Libertarian candidate.

IIA is also violated by Ranked Choice Voting implemented by Borda Count (candidates get points according to their rank). The voter preferences:

  • 40% prefer Alice, Carol, Bob
  • 60% prefer Bob, Alice, Carol

Are spoiled by Carol. Without her, Alice gets (4 _ 2 + 6 _ 1 = 14 points) while Bob gets (6 _ 2 + 4 _ 1 = 16 points). With Carol’s inclusion, Alice still gets 14 points, but Bob falls to (6 * 2 = 12) points and loses the election.

There are voting systems that satisfy IAA, but are either outside the class Arrow describes, or violate other criteria.

As Arrow’s proof is formal and flawless, the solution is not a new system that somehow escapes its claims, but rather, an argument that convincingly dissolves it’s assumptions.

In their recent pre-print Axioms for Defeat in Democratic Elections, Holliday and Pacuit leverage another seminal paradox in social choice, that of circularity. In Condorcet’s Paradox, aggregations of linear preferences result in circular preferences, sometimes leading to instability: i.e. a winner is declared even though more than 50% of voters would prefer switching to an alternative.

In the top example, it’s clear that A defeats B, and the inclusion of C makes no difference; however, in the second, the introduction of C changes our intuitions about the relationship of A to B. If we have the same n for all ballots, it is not at all clear that A should defeat B, or in fact, who the winner should be at all!

So the introduction of a new candidate, without affecting voters’ relative rankings for existing candidates, convincingly and justifiable changes the aggregate rankings.

In a more extreme case, our intuitions might actually flip. Without C, we have:

  • 6 prefer A, B
  • 4 prefer B, A

Which is a clear win for A. But with the introduction of C, the first 6 voters split, and we get:

  • 3 prefer: A, B, C
  • 3 prefer C, A, B
  • 4 prefer: B, C, A

In this second case, A beats B on 6 ballots, B beats C on 7 ballots, and C beats A on 7 ballots, so B appears to be dominant.

This is the same logic we used above to demonstrate a flaw in Borda Count, but with the renewed intuition that it’s a sensible result, rather than an “unfair” spoiler.

The authors go on to propose Coherent IIA as an amendment. Another recent preprint of theirs introduces Split Cycle Voting which escapes the revised Impossibility Theorem, and is also Condorcet consistent.

I haven’t finished a thorough read of both papers yet, but was excited about this particular result, and eager to share it.