Unqualified Offerings

By Thoreau

Since I’ve resumed work on my paper on the mathematics of voting, I want to blog about Arrow’s Theorem, one of the most important theorems in the mathematics of voting. The first thing you should know about it is that it doesn’t quite say that there’s no “perfect” voting method. “Perfect” is a word that only makes sense if you first define what it is that you’re looking for. Rather, it proves that no voting method (in a fairly wide class of methods) can simultaneously satisfy certain criteria (more on those criteria below). Also, it certainly does not say (contrary to some popular accounts) that the only “perfect” voting method is a dictatorship. The word “dictatorship” does come up in the theory, but I’ll explain below.

Also, I’m not blogging about this to advocate for or against alternative voting systems. The desirability (or undesirability) and feasibility (both technical and political) of alternative voting systems is certainly an interesting topic, but it’s not one that I feel like arguing over right now. The science of voting is interesting even just as an intellectual topic, because it is closely related to certain issues in formal logic and computer science: Given certain information, can you construct a procedure for making a decision from that information, and ensure that the procedure will satisfy certain properties?

Let’s start by defining the types of voting methods under consideration. We’ll focus on voting methods in which every voter writes down a ranking of the candidates: First choice, second choice, third choice, etc. The election outcome is then decided solely from this information. Examples of such methods include Instant Runoff, Condorcet voting, Bucklin, Borda Count, and numerous others that you can google for. Even our current voting system is in some sense equivalent to a ranked voting system, because it would be equivalent to a system where you submit your list but the people tallying the votes only pay attention to the first name on your list.

While most alternative voting systems fit that description, not all do. The most popular example of one that doesn’t use ranked lists is Approval Voting (a method that I like, actually, but we’ll leave that aside for another time). In Approval Voting, you basically write “yes” or “no” for each candidate, and the candidate with the most “yes” votes wins. This is different from a ranked voting method because you can’t infer the yeses and nos from somebody’s list. If a person put down 5 names in order, did he intend to say “yes” to the top 4? Top 3? Top 2? Top 1? Different voters could have different cutoffs. So it uses a different type of information. The nature of the information is important here, and is part of the reason why this is academically interesting: The type of information that you start form constrains some of the properties of the decision procedure.

Anyway, there are lots of possible procedures, and Arrow decided to impose 2 requirements on them: (Some people impose additional requirements, state it differently, or include some additional assumptions very explicitly, but this isn’t a formal proof here)

1) Pareto: If every single voter prefers candidate A to candidate B, then candidate B can’t win. (A might not win either, of course, if, for instance, enough people prefer C to A.) This is an easy requirement to satisfy, and just about every voting procedure that I’m aware of satisfies it.

2) Independence of Irrelevant Alternatives (IIA): Suppose that candidate C wins the election. Suppose that we then take the set of ballots and cross off some candidate (let’s call him “Ralph”) while leaving the relative rankings of the other candidates unchanged. If we then look to see who the new winner is, the winner should be the same (unless “Ralph” was the original winner). There are other ways of stating this condition, but it’s an especially simple one.

Interestingly, Arrow did not assume that all candidates are treated equally, nor did he assume that all voters are treated equally. Leaving aside the Florida and Diebold jokes, that actually makes the theorem more applicable to real situations, because there are situations like shareholder meetings where different voters carry different weight, and situations like legislative votes where some options (equivalent to candidates) require a simple majority to pass while others will need 2/3 to pass. All he assumed was that the method uses ranked ballots, and that conditions 1 and 2 are met.

Surprisingly, there is only one procedure that satisfies these requirements: A procedure where a single voter ALWAYS makes the choice. No other procedure can always satisfy 1 and 2. Say what you will about your favorite method (Instant Runoff, for instance, has a ton of fans) but if you search hard enough you’ll find a case where it fails one of those requirements, and in every case that I’m aware of it’s the IIA requirement that’s failed.

People draw a variety of conclusions from this. Some make a big deal about the fact that the only method satisfying 1 and 2 is a method where the same voter always gets his way, and conclude that Arrow was arguing for dictatorship. No, not really. He was just observing that if you impose those requirements, that’s what you’re left with. So find some other criteria. Others say “There are no good voting methods, so just go with (insert that person’s preferred method here) because they all suck, man.” No, not quite. Different methods do have different properties, some might be better than others, depending on your criteria. You just have to pick some criteria, argue for why those criteria are desirable, and then see if you can find any methods satisfying those criteria. Finally, some make a related argument and say that all alternative voting methods suck just as much as the status quo, so stick with that. Again, no. If the status quo has properties that you like, fine, argue for it. But don’t drag Arrow into it, because his critique of the other methods is just as applicable to the status quo.

Anyway, let me give a simplified proof of a weaker version of Arrow’s Theorem. Instead of imposing Pareto, I’ll impose a more limiting requirement: If there are only 2 candidates in the race, then we have a simple majority vote to pick between them. I’ll then prove that any method which reduces to a simple majority vote in the case of 2 candidates cannot satisfy IIA.

Suppose we have a case where a majority of the electorate prefers candidate A to candidate B, a majority of the electorate prefers B to C, and a majority of the electorate prefers C to A. That may sound irrational, and it is unlikely to happen if all of the voters and candidates line up along a single left-right issue axis. However, if candidates are evaluated along multiple issue axes (e.g. social and economic) and many of them (and many voters) are not on the main left-right axis, then it’s quite likely.

Anyway, let’s say C is our winner. We then start removing candidates, and (in keeping with IIA) C remains the winner. Eventually, we get to the point where only 3 candidates remain: A, B, and C. If we remove candidate A, then the final choice is between B and C, and a majority prefer B to C. So by removing A (a losing candidate) we change the outcome. This violates IIA. Switch around candidate names, say that A is your winner when you have 3 left, and then remove B, and it’s an A-C face-off, and IIA is violated again. And switch names around yet again, so that A is your winner in the 3-way race, remove B, and it’s an A-C face-off and C wins when you remove losing candidate B. So no matter how you do it, if there’s a cyclic paradox (B beats C, C beats A, A beats B) you violate IIA. This is simpler than the case Arrow did (he didn’t assume that 2-way races reduce to majority vote) but it illustrates the point.

All this is a fancy way of saying that the spoiler effect happens. Still, Arrow’s work is significant for 2 reasons. First, he proved that it’s impossible to get rid of the spoiler effect. It happens less frequently in some methods, but you can never completely get rid of it. (No, not even in Instant Runoff, but thanks for asking.) Second, more importantly, he demonstrated that voting procedures could be analyzed by very general methods, and that you could make statements that apply to all possible procedures. That’s an important thing, just as in computer science and formal logic it’s significant that we have theorems that limit wide classes of algorithms and procedures, not just methods for analyzing some particular algorithm, and then having to redo the analysis every time the algorithm is tweaked.

Anyway, that’s what Arrow’s Theorem is about.