Thanksgiving

This year we give thanks for Arrow’s Impossibility Theorem. (We’ve previously given thanks for the Standard Model Lagrangian, Hubble’s Law, the Spin-Statistics Theorem, conservation of momentum, effective field theory, the error bar, gauge symmetry, Landauer’s Principle, the Fourier Transform, Riemannian Geometry, the speed of light, the Jarzynski equality, the moons of Jupiter, space, black hole entropy, and electromagnetism.)

Arrow’s Theorem is not a result in physics or mathematics, or even in physical science, but rather in social choice theory. To fans of social-choice theory and voting models, it is as central as conservation of momentum is to classical physics; if you’re not such a fan, you may never have even heard of it. But as you will see, there is something physics-y about it. Connections to my interests in the physics of democracy are left as an exercise for the reader.

Here is the setup. You have a set of voters {1, 2, 3, …} and a set of choices {A, B, C, …}. The choices may be candidates for office, but they may equally well be where a group of friends is going to meet for dinner; it doesn’t matter. Each voter has a ranking of the choices, from most favorite to least, so that for example voter 1 might rank D first, A second, C third, and so on. We will ignore the possibility of ties or indifference concerning certain choices, but they’re not hard to include. What we don’t include is any measure of intensity of feeling: we know that a certain voter prefers A to B and B to C, but we don’t know whether (for example) they could live with B but hate C with a burning passion. As Kenneth Arrow observed in his original 1950 paper, it’s hard to objectively compare intensity of feeling between different people.

The question is: how best to aggregate these individual preferences into a single group preference? Maybe there is one bully who just always gets their way. But alternatively, we could try to be democratic about it and have a vote. When there is more than one choice, however, voting becomes tricky.

This has been appreciated for a long time, for example in the Condorcet Paradox (1785). Consider three voters and three choices, coming out as in this table.

Voter 1Voter 2Voter 3
ABC
BCA
CAB

Then simply posit that one choice is preferred to another if a majority of voters prefer it. The problem is immediate: more voters prefer A over B, and more voters prefer B over C, but more voters also prefer C over A. This violates the transitivity of preferences, which is a fundamental postulate of rational choice theory. Maybe we have to be more clever.

So, much like Euclid did a while back for geometry, Arrow set out to state some simple postulates we can all agree a good voting system should have, then figure out what kind of voting system would obey them. The postulates he settled on (as amended by later work) are:

  • Nobody is a dictator. The system is not just “do what Voter 1 wants.”
  • Independence of irrelevant alternatives. If the method says that A is preferred to B, adding in a new alternative C will not change the relative ranking between A and B.
  • Pareto efficiency. If every voter prefers A over B, the group prefers A over B.
  • Unrestricted domain. The method provides group preferences for any possible set of individual preferences.

These seem like pretty reasonable criteria! And the answer is: you can’t do it. Arrow’s Theorem proves that there is no ranked-choice voting method that satisfies all of these criteria. I’m not going to prove the theorem here, but the basic strategy is to find a subset of the voting population whose preferences are always satisfied, and then find a similar subset of that population, and keep going until you find a dictator.

It’s fun to go through different proposed voting systems and see how they fall short of Arrow’s conditions. Consider for example the Borda Count: give 1 point to a choice for every voter ranking it first, 2 points for second, and so on, finally crowning the choice with the least points as the winner. (Such a system is used in some political contexts, and frequently in handing out awards like the Heisman Trophy in college football.) Seems superficially reasonable, but this method violates the independence of irrelevant alternatives. Adding in a new option C that many voters put between A and B will increase the distance in points between A and B, possibly altering the outcome.

Arrow’s Theorem reflects a fundamental feature of democratic decision-making: the idea of aggregating individual preferences into a group preference is not at all straightforward. Consider the following set of preferences:

Voter 1Voter 2Voter 3Voter 4Voter 5
AAADD
BBBBB
CDCCC
DCDAA

Here a simple majority of voters have A as their first choice, and many common systems will spit out A as the winner. But note that the dissenters seem to really be against A, putting it dead last. And their favorite, D, is not that popular among A’s supporters. But B is ranked second by everyone. So perhaps one could make an argument that B should actually be the winner, as a consensus not-so-bad choice?

Perhaps! Methods like the Borda Count are intended to allow for just such a possibility. But it has it’s problems, as we’ve seen. Arrow’s Theorem assures us that all ranked-voting systems are going to have some kind of problems.

By far the most common voting system in the English-speaking world is plurality voting, or “first past the post.” There, only the first-place preferences count (you only get to vote for one choice), and whoever gets the largest number of votes wins. It is universally derided by experts as a terrible system! A small improvement is instant-runoff voting, sometimes just called “ranked choice,” although the latter designation implies something broader. There, we gather complete rankings, count up all the top choices, and declare a winner if someone has a majority. If not, we eliminate whoever got the fewest first-place votes, and run the procedure again. This is … slightly better, as it allows for people to vote their conscience a bit more easily. (You can vote for your beloved third-party candidate, knowing that your vote will be transferred to your second-favorite if they don’t do well.) But it’s still rife with problems.

One way to avoid Arrow’s result is to allow for people to express the intensity of their preferences after all, in what is called cardinal voting (or range voting, or score voting). This allows the voters to indicate that they love A, would grudgingly accept B, but would hate to see C. This slips outside Arrow’s assumptions, and allows us to construct a system that satisfies all of his criteria.

There is some evidence that cardinal voting leads to less “regret” among voters than other systems, for example as indicated in this numerical result from Warren Smith, where it is labeled “range voting” and left-to-right indicates best-to-worst among voting systems.

On the other hand — is it practical? Can you imagine elections with 100 candidates, and asking voters to give each of them a score from 0 to 100?

I honestly don’t know. Here in the US our voting procedures are already laughably primitive, in part because that primitivity serves the purposes of certain groups. I’m not that optimistic that we will reform the system to obtain a notably better result, but it’s still interesting to imagine how well we might potentially do.

8 Comments

8 thoughts on “Thanksgiving”

  1. Matthew Morycinski

    I wonder what people think of the following system. The setup is exactly the same as for plurality voting, but instead of counting the ballots, only one ballot is picked at random. This way: 1. the probability of electing a candidate is strictly proportional to the proportion of votes the candidate gets. 2. The final result is that the makeup of the elected body is similar to the makeup of voter preferences. 3. Strategic voting makes no sense in this system. 4. Multiple candidates who differ little from each other are at a disadvantage compared to candidates who differ a lot (this may be a disadvantage!) 5. Easy to understand and show to be fair (I hope).

  2. “On the other hand — is it practical? Can you imagine elections with 100 candidates, and asking voters to give each of them a score from 0 to 100?”
    Is there a reason 100 is being used here. Most implementations of score/range voting I have seen/heard of involve at most a rating from 1 to 10 (often 2, usually called approval voting). And it seems like we do this all the time when we rate products or movies. Perhaps one could argue that factoring in strength of preference is not a good idea, but I don’t see why it would be impractical, since it is easier to implement than IRV as an algorithm.

    There are reasons to believe instant runoff voting (IRV) is worse than plurality in many circumstances because increasing your preference for a candidate in IRV can cause them to lose (and decreasing your preference for a candidate can cause them to win), which is called the monotonicity criterion. I also disagree that voting for a third party in IRV is safe. It’s really only true so long as you believe the third party will be eliminated initially, otherwise it may cause your least-preferred candidate to win in a three-way race. The studies I have seen also seem to indicate that it is not a rare enough occurrence that it should be ignored (especially considering that score/range voting is an option).

    One good way of visualizing the non-monotonicity of IRV is with Yee diagrams (see the wikipedia examples on the Monotonicity criterion). Also, an example (one can look at https://www.rangevoting.org/Monotone.html for more)
    Suppose there are 3 candidates A, B, C in an IRV system. If there are 17 voters, a possible election could be:
    6 vote C>B>A,
    2 vote B>A>C,
    3 vote B>C>A,
    4 vote A>B>C,
    2 vote A>C>B.
    Then first round C=6, B=5, A=6, and B is eliminated. Second round C=9 and A=8. C wins.

    Suppose that the 2 A>C>B voters have a change of heart as they are about to vote and decide they like C more than A. They switch to C>A>B. Now the first round is C=8, B=5, A=4. So A is eliminated. The second round gives C=8, B=9 and B wins. Increasing support for C among some voters would cause C to lose.

  3. For my previous post, I should have said the two examples (increasing support for a candidate causes that candidate to lose and decreasing support for a candidate causes that candidate to win) show that instant runoff voting fails the monotonicity criterion, rather than that they “are” the monotonicity criterion.

    I also apologize if it comes across as saying that score/range voting or plurality voting are necessarily better. I hope that I just highlighted a key problem with instant runoff voting. As you point out, different voting systems have different trade-offs. I have just found that many people who like instant runoff voting that I have talked to seem to be unaware of, and do not like the non-monotonicity property of instant runoff voting once they learn of it. Especially when they learn cases of non-monotonicity are probably not that rare in instant runoff voting elections.

  4. Social-choice theory has been a decades-long interest of mine. My conclusion: “Approval” voting is the best system to try next. (yes, “try” – if it doesn’t work as well as hoped, then try something else!). Approval means that each voter ‘approves” as many candidates on their ballot as they like, ignoring the others. Each voter has the freedom to decide for themselves what meets their threshold for approval. The winner is the candidate so has the most people ‘approving’ of their candidacy,

    0. above all, why shouldn’t the candidate who meets the “approval” of the greatest number of voters be the one elected? Can’t think of why that would not be a good idea!
    1. it is a range-voting method, so side steps Arrow
    2. its how people make a huge number of group decisions informally anyways! If 5 people head out to dinner, and two have a favourite Restaurant A, while the other three choose three different favourites, they don’t necessarily go to A! They talk it over until they find a restaurant that all “approve” of at some level. i.e. they are all at least OK with it though maybe not thrilled. You can think of many many other circumstances where we all do this. Movies, travel, etc etc.
    3. it would be trivial to implement it: just add two words, “or more”, to the top of each ballot. i.e. “Select one or more candidates…”. yes, that means ballots can have more than one check mark. 1 voter, 1 ballot. Count the number of check marks per candidate exactly as before.

    #3 is the kicker for me. It would be SO easy to transition to approval compared to ALL other systems. It’s improvement/effort ratio is easily the highest. Here in B.C. years ago they had a people’s electoral commission to select a new voting system. One of the delegates called out my suggestion to go Approval as the best, but sadly the group chose a hybrid single-transferable vote system that was too complicated for most to digest, so it did not receive the 60% supermajority the gov’t required (though it did receive more than 50%). so we are still stuck with plurality.

    I am still convinced that offered the choice of something very simple that is much much better, people will go for it. Probably won’t happen in my lifetime, sadly.

    thanks for the article!

  5. No discussion of preferential voting, as used in Australia? Voters preferentially rank their candidates. Any candidate with more than 50% first preferences wins immediately. If none appears, then the candidate with the least first preference votes has their second preferences distributed. The process of distributing the votes of losers continues until a candidate has a plurality. It works very well, when the number of candidates is around 10 or less. But in Senate elections we can sometimes have up to 100 candidates on the ballot, grouped by party, so to simplify choices voters will usually work from a party how to vote card which ranks the choices by party group. That opens the door to preference gaming by the minor parties, who ‘trade’ preferences with each other via their official how to vote cards. This sometimes means little known candidates end up higher in the rankings than they (arguably) should. Conclusion: No system is perfect. Arrow’s theorem is the proof!

  6. Hi Sean,

    Dropping you this note from Melbourne Australia in the hopes that you might spot it. I just wanted to say – with all sincerity – thank you. Thank you for the Mindscape podcast, for your AMAs, for your seemingly endless list of fascinating guests and erudite conversations.

    There are plenty of us out there who by virtue of age, or a severe lack of mathematical prowess, will never get to take physics as seriously as you do. We’re not going to get a PhD, or win a Nobel Prize, or discover a new particle.

    But we’re still going to dream.

    We’re still going to look up at the night sky and wonder.

    We’re still going to get excited about a greater understanding of the Universe around us.

    And we’re lucky to have people such as yourself, people we can lean on who’ll share knowledge, understanding and enthusiasm with us. People who take us on the journey through unraveling these mysteries – gently – but with no fear of getting into ‘the technical details’.

    So yes. Thank you.

Comments are closed.

Scroll to Top