Mathematical Democracy: Mission Impossible? Maybe not…

In 1950, a 29-year-old PhD candidate at Columbia published a stunning theorem that later won him a Nobel Prize: “There is no such thing as a fair voting system.”  Or so the legend goes.  Let’s dive into this claim and see to what extent Arrow’s Impossibility Theorem does and does not quash our hopes for a fair representative democracy.  For a background of voting systems, see Rina Friedberg’s post last month or Stephanie Blanda’s 2014 post on how Olympic host cities are chosen.

What does Arrow’s Impossibility Theorem actually say? Like Euclid’s parallel postulate, Arrow’s Theorem is frequently transformed into a variety equivalent formulations that are either more intuitive to grasp or more relevant to problem at hand (to read Kenneth Arrow’s original paper, click here).  The formulation below is based on a paper by John Geanakopolos, who according to the acknowledgments, consulted Kenneth Arrow prior to publication.

Consider a society of N voters and at least 3 candidates.  Each voter has transitive preferences, meaning they can mentally rank all the candidates (with ties allowed).  A voting system is a system that produces a single ranking on behalf of society (i.e. it determines a winner, but also a second place runner-up, third place, etc.).  Consider the following three fairness criteria:

1. Universal Domain: Voters can rank their candidates in any order they like.  No matter what combination of ballots it receives, the system will always produce a ranking.
2. Unanimity: If everyone prefers A to B, the voting system should rank A above B.
3. Independence of Irrelevant Alternatives (IIA): Whether the voting ranks A above B should not depend on how voters rank C (or any other candidate).

Theorem: The only voting system that respects universal domain, unanimity, and IIA is a dictatorship.

Note: The dictator in this case is not a candidate, but a rather voter who has the power to decide the winner every time, no matter what the rest of society thinks (more precisely, a dictator can always force the voting system to rank A above B).

A two-page proof, accessible to any outsider who is used to proving things, can be found here.  To give you a taste, I’ll walk you through the first lemma (or you can skip to the next section see why Arrow’s Theorem might not be so doomsaying after all):

Lemma: If every voter ranks one candidate as their highest or lowest choice, then the voting system must as well.

Proof: Suppose, on the contrary, that even though every voter has put B either first or last, the voting system ranks A>B>C.  Thus every individual voter ranks B>(A and C) or (A and C) > B.  Suppose every voter decides they like C better than A, but leaves B’s rank unchanged (they’re allowed to rank them however they want under universal domain). By the independence of irrelevant alternatives condition, the voting system must still rank A>B and B>C. Now, every voter’s mental ranking is now C>A>B or B>C>A.  By the unanimity criterion, the voting system must rank C > A. The two rankings A>C and C>A are not compatible so our original assumption is impossible. The voting system must rank B either first or last. QED

The proof then uses this lemma to show that there is a unique voter who can cause B to go from being last to first in the rankings and that this voter must in fact be a dictator.

Is there no hope?

Before we throw up our hands and declare that no voting system can be fair, let’s pause and consider how reasonable these assumptions and “fairness” criteria actually are.  Unanimity does not sound like an assumption we ought to relax: directly contradicting the wishes of literally every voter sounds about as bad dictatorship.  Likewise, we could limit the voting system’s universal domain, but prohibiting voters from ranking candidates a certain way because it will cause the system to malfunction hardly seems fair either.  If we force there to only be two candidates, then all our contradictions go away, but presumably you will need some system of primary elections to narrow your choices down to two, so this only kicks the can back up the road.  Even if we don’t need our voting system to produce a ranking but rather just a single winner, unanimity affects affects “winner” just as much as any other choice.  But what about IIA?

On its surface, this criterion seems like the sort of fairness we would want in a system, though like Euclid’s parallel postulate, it does seem a bit more complex than the other basic assumptions. Most systems around the world violate IIA.  The 2000 Gore versus Bush election, for example, likely constituted an IIA violation: that is, presence of third party candidate Ralph Nader tipped the election from Gore to Bush, even though the Nader voters did not necessarily like Bush more Gore.  This does seem unfair, at least to Gore and Bush, though not necessarily for the voters.  Arrow’s Impossibility Theorem assumes the people actually vote according to their mental ranking of the candidates: that is, they vote naively, not strategically.  If you assume these Nader voters knew the potential outcome of their actions (and that’s a big “if”), then the system was taking into account their preferences: that is, they cared so much about Nader that they were willing risk Gore losing even if they preferred him over Bush.  Note that Arrow’s Impossibility Theorem only takes into account rankings, not ratings. Allowing voters to rank each candidate on scale of 1-10 (or grade them A-F), a system known as range voting actually avoids Arrow’s paradox altogether.  However, if at least some of our voters are strategic, then this system is highly manipulable (e.g. even if don’t think your second choice candidate is so bad, you give her an F if you think the election is going to be close).  In fact, the even more consequential (though less famous) impossibility theorem known as Gibbard–Satterthwaite Theorem states that every voting system is either:

1. A dictatorship,
2. Prevents one of the candidates from ever winning, or
3. Is vulnerable to strategic voting (i.e. savvy voters can tip the election by misrepresenting their true preferences).

Again, whether strategic voting is a bad thing depends on your point of view.  It does seem unfair in that some voters who are less informed might naively vote their true preferences, while others may vote strategically and exert an undue influence.  Even if everyone had perfect information, some voters (say, voters who prefer a hopelessly small party) are in a much better position to swing the election to their second choice than anyone else.  But perhaps this is a difference we can live with—after all, a voter who is fiercely dedicated to one candidate and will vote for them come hell or high water is far less influential than a swing voter who can be persuaded to change their vote, no matter what the system.  Still, it seems prudent to try to limit the advantage that a small group of savvy, strategically-minded voters have over the rest of us, just as it seems prudent to lessen the chances of an irrelevant alternative causing an upset.

This observation then, bring us to our solution, if you can call it that, to the seeming impossibility of a fair system.  While in theory no system can meet all the fairness criteria we may desire, our challenge is to design a system that will minimize the likelihood of an unfair outcome. Thus, our “perfect design” problem becomes an optimization problem, and luckily there are many candidates: instant runoff voting, approval voting, and the Condorcet method to name a few (Wikipedia’s coverage of these topics is extensive).  The plurality system (the most common one used in the US) is almost certainly not the optimal solution since its highly manipulable by strategic voters and violates a number of other fairness criteria, though its simplicity does have great appeal.  Instant runoff voting, used in Australia and some local U.S. elections, has a number of weird flukes, such as a vote for your favorite candidate actually hurting their chances, though it’s unclear if this is more of a concocted scenario that is likely never to pop up in the real world.  “Most systems are not going to work badly all of the time,” Kenneth Arrow stated, in the lead up to the 2008 election. “All I proved is that all can work badly at times.”  (See here for full discussion this paragraph is based on). Perhaps one of you will find a system that is likely to never behave badly in real world conditions.  While that may sound modest, finding such a system could still be a huge contribution of mathematics to the the fairness of democracies around the world.

Works Cited:

Arrow, Kenneth J. “A difficulty in the concept of social welfare.” The Journal of Political Economy (1950): 328-346.

Geanakoplos, John. “Three brief proofs of Arrow’s impossibility theorem.” Economic Theory 26.1 (2005): 211-215.

McKenna, Phil. “Vote of no confidence.” New Scientist 198.2651 (2008): 30-33.

Graphics in public domain, available: https://en.wikipedia.org/wiki/Voting#/media/File:Vote_12345.jpg

Also consulted: https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem

I am a second-year Network Science doctoral student at Northeastern University in Boston. I model homophily and time-varying dynamics on social networks.
This entry was posted in Math, Math in Pop Culture, Mathematics in Society, Social Justice, Uncategorized, Voting Theory and tagged , , , , . Bookmark the permalink.

3 Responses to Mathematical Democracy: Mission Impossible? Maybe not…

1. Kyle Bunkers says:

You missed another important way out — namely cardinal voting systems. Why not allow voters to rank every candidate independently of the others (on a scale from 0 to 10, or a scale from 0 to 1, even)? Then you have a ranking for each candidate rather than a list or an ordinal ranking. You can say the winner is the one with the most “points”. For example, look at https://en.wikipedia.org/wiki/Range_voting or see https://en.wikipedia.org/wiki/Approval_voting, although approval voting is really just a special case of range voting.

With these cardinal methods you are easily able to satisfy all of Arrow’s requirements, thus making the “impossible” possible. I recommend the rangevoting.org website. See http://rangevoting.org/ArrowThm.html for a quick check that range voting satisfies Arrow’s theorem’s requirements.

I am not really sure why cardinal voting systems are often overlooked. They seem to me to be the best way of incorporating the intensity of people’s preferences. They may have some problems (the people with the most intense preferences have a stronger effect on the vote, which I would think is a feature rather than a bug), but the simplicity and satisfiability of most reasonable desires for a voting system seems like a huge advantage to me.

2. Kyle Bunkers says:

Sorry, I see you got out of that and I just poorly skimmed the end. I am sorry for my comment, I should have more carefully the ending.

3. Dave Brooks says:

I’m a tech reporter in NH who has written about Arrow’s Theorem and alternative voting. I’d like to feature this in my weekly GraniteGeek email newsletter and Concord Monitor blog. If by any chance you are around today (Tuesday, Nov. 22) and could call me, please do: 603-369-3313