9.5 9.4 Insurmountable Difficulties: Arrow’s Impossibility Theorem

All the voting systems for three or more candidates that we have discussed turn out to be flawed in one way or another. You may well ask at this point why we don’t simply present one voting method for the three-candidate case that has all the desirable properties that we want to satisfy. That is, after all, exactly what we did for the two-candidate case (with majority rule filling the bill, and being the only one to do so by May’s theorem).

The answer to this question is extremely important. The difficulties in the three-candidate case are not in any way tied to a few particular systems that we present in a text such as this (or that we choose to use in the real world). The fact is, there are difficulties that will be present regardless of what voting system is used, and this applies even to voting systems not yet discovered.

Nothing in the remarkable body of work produced by Nobel laureate Kenneth J. Arrow of Stanford University is as well known or widely acclaimed as the result known as Arrow’s impossibility theorem (see Spotlight 9.2).

Arrow’s Impossibility Theorem THEOREM

With three or more candidates and any number of voters, there does not exist—and there never will exist—a voting system that always produces a winner, satisfies the Pareto condition and IIA, and is not a dictatorship.

Arrow’s impossibility theorem isn’t obvious, and we won’t be saying anything about the proof. But we can state and prove a much weaker result of some interest in its own right. This version is taken from the 2008 text Mathematics and Politics (cited in the Suggested Readings on page 438), and replaces Arrow’s assumption of the Pareto condition and nondictatorship by the CWC.

425

Kenneth J. Arrow Spotlight 9.2

image

For centuries, mathematicians have been in search of a perfect voting system. Finally, in 1951, economist Kenneth Arrow proved that finding an absolutely fair and decisive voting system is impossible. Arrow is the Joan Kenney Professor of Economics and Professor of Operations Research, Emeritus at Stanford University. In 1972, he received the Nobel Memorial Prize in Economic Science for his outstanding work in the theory of general economic equilibrium. His numerous other honors include the 1986 von Neumann Theory Prize for his fundamental contributions to the decision sciences. He has served as president of the American Economic Association, the Institute of Management Sciences, and other organizations. Dr. Arrow talks about the process by which he developed his famous impossibility theorem and his ideas on the laws that govern voting systems:

My first interest was in the theory of corporations. In a firm with many owners, how do the owners agree when they have different opinions, for example, about the prospects of the company? I was thinking of stockholders. In the course of this, I realized that there was a paradox involved—that majority voting can lead to cycles. I then dropped that discussion because I was frustrated by it.

I happened to be working with The RAND Corporation one summer about a year or two later. They were very interested in applying concepts of rationality, particularly of game theory, to military and diplomatic affairs. That summer, I felt not like an economist but instead like a general social scientist or a mathematically-oriented social scientist. There was tremendous interest in game theory, which was then new.

Someone there asked me, “What does it mean in terms of national interest?” I said, “That’s a very simple matter.” He then asked me to write a memorandum on the subject. That memorandum led to a sharper formulation of the social-choice question, and I realized that I had been thinking of it earlier in that other context.

Society must choose among a number of alternative policies. These policies may be thought of as quite comprehensive, covering a number of aspects: foreign policy, budgetary policy, or whatever. Each individual member of the society has a preference, or a set of preferences, over these alternatives. I guess you can say one alternative is better than another. These individual preferences have a property I call rationality or consistency, or more specifically, what is technically known as transitivity: If I prefer to , and to , then I prefer to .

Imagine that society has to make these choices among a set. Each individual has a preference ordering, a ranking of these alternatives. But we really want society, in some sense, to give a ranking of these alternatives. You can always produce a ranking, but you would like it to have some properties. One is that, of course, it be responsive in some sense to the individual rankings. Another is that when you finish, you end up with a real ranking, that is, something that satisfies these consistency, or transitivity, properties. And a third condition is that when choosing between a number of alternatives, all I should take into account are the preferences of the individuals among those alternatives. If certain things are possible and some are impossible, I shouldn’t ask individuals whether they care about the impossible alternatives, only the possible ones.

It turns out that if you impose the conditions I just stated, there is no method of putting together the individual preferences that satisfies all of them.

The whole idea of the axiomatic method was very much in the air among anybody who studied mathematics, particularly among those who studied the foundations of mathematics. The idea is that if you want to find out something, to find the properties, you say, “What would I like it to be?” [You do this] instead of trying to investigate special cases. I was really accustomed to this approach. Of course, the actual process did involve trial and error.

But I went in with the idea that there was some method of handling this problem. I started out with some examples. I had already discovered that these led to some problems. The next thing that was reasonable was to write down a condition that I could outlaw. I constructed another example, another method that seemed to meet that problem, and something else didn’t seem very right about it. Then I had to postulate that we have some other property. I found I was having difficulty satisfying all of these properties that I thought were desirable, and it occurred to me that they couldn’t be satisfied.

426

After having formulated three or four conditions of this kind, I kept on experimenting. Lo and behold, no matter what I did, there was nothing that would satisfy these axioms. So after a few days of this, I began to get the idea that maybe there was another kind of theorem here, namely, that there was no voting method that would satisfy all the conditions that I regarded as rational and reasonable. It was at this point that I set out to prove it. It turned out to be a matter of only a few days’ work.

It should be made clear that my impossibility theorem is really a theorem [showing that] the contradictions are possible, not that they are necessary. What I claim is that given any voting procedure, there will be some possible set of preference orders for individuals that will lead to a contradiction of one of these axioms.

But you say, “Well, okay, since we can’t get perfection, let’s at least try to find a method that works well most of the time.” Then when you do have a problem, you don’t notice it as much. So my theorem is not a completely destructive or negative feature any more than the second law of thermodynamics means that people don’t work on improving the efficiency of engines. We’re told you’ll never get 100% efficient engines. That’s a fact—and a law. It doesn’t mean you wouldn’t like to go from 40% to 50%.

A Weak Version of Arrow’s Impossibility Theorem THEOREM

With three or more candidates and an odd number of voters, there does not exist—and there never will exist—a voting system that satisfies both the CWC and IIA and that always produces at least one winner in every election.

To see why this is true, we’ll handle only the case of exactly three voters. Our plan will be to assume that we have some kind of hypothetical voting system that satisfies both the CWC and IIA, and to show that when confronted by the Condorcet voting paradox ballots, it produces no winner.

The argument really comes in three separate, but extremely similar, pieces— one for each of the three candidates. Piece 1 argues that can’t be among the winners, piece 2 that can’t be among the winners, and piece 3 that can’t be among the winners. We’ll do piece 1 and leave the others for you. The sequence of ballots that we are considering is the following, which we have already seen has no Condorcet winner:

Rank Number of Voters (3)
First
Second
Third

427

Our starting point, however, will be to ask what our hypothetical voting rule must do when confronted by a slightly different sequence of ballots:

Rank Number of Voters (3)
First
Second
Third

Here, is clearly a Condorcet winner, and thus it must be the unique winner of the election contested under our hypothetical voting rule. Therefore, is a winner and is a nonwinner (for this sequence of ballots).

However, because our hypothetical voting rule satisfies IIA, we know that will remain a nonwinner so long as no voter reverses his or her ordering of and . But to arrive at the voting paradox ballots, we can move up (the candidate that is irrelevant to and C) one slot in the second voter’s list.

Thus, because of IIA, we know that is a nonwinner when our voting rule is confronted by the voting paradox ballots. This is one-third of the argument. As we mentioned before, similar arguments (see Exercise 32 on page 436) show that and are also nonwinners when our voting rule is confronted by the voting paradox ballots.

We conclude this section with an example that yields a somewhat surprising application of Arrow’s impossibility theorem in the context of what are called social welfare functions.

EXAMPLE 11 Organ Transplant Policies and Arrow’s Impossibility Theorem

Finding an equitable procedure for determining a rank ordering of patients in need of an organ transplant is complicated: there are several criteria that should be considered in arriving at such a “priority ranking.” Three such criteria are, for example, (1) the length of time that a patient has been waiting, (2) the probability of success as measured by the numbers of antigens that the patient and donor have matched, and (3) the fraction of the population unsuitable as donors for this potential recipient due to the presence of certain antibodies. A further discussion of these issues occurs in Section 13.3.

Each of the three criteria gives us a ranking (with ties) of the patients according to the more appropriate recipient of the next available organ, according to that particular criterion. Although these rankings are often determined by measurements, the use of different scales for different criteria muddies the water sufficiently so that you might want to work simply with the rankings derived from the measurements, as opposed to working directly with the measurements themselves. This is the context in which we will frame the problem.

So what does the search for a procedure to rank-order potential recipients of an organ have to do with voting? In a sense, everything, if looked at the right way. We can think of each criterion as a “voter” and each potential recipient as an “alternative.” The procedure that we seek is what social choice theorists call a social welfare function. It differs from a social choice procedure in that the result of an election is not a single winner or a group tied for the win, but a listing of the alternatives—the priority ranking, in our organ-transplant situation.

image

For a moment, let’s return to the particular task of seeking a priority ranking of the potential recipients of an organ based on how they are ranked according to each of several criteria, like the three we mentioned earlier. What “reasonable” properties might we expect any such procedure to satisfy? Consider the following:

428

  1. If one potential recipient is ranked above another potential recipient with respect to every single criterion, then we should expect to be ranked above in the priority ranking.
  2. If potential recipient is ranked above potential recipient in the priority ranking, and there are subsequent changes in how potential recipients are ranked with respect to one or more of the criteria, then potential recipient should not be ranked above potential recipient in the priority ranking unless has moved from being below to being above with respect to at least one criterion.
  3. No single criterion should dominate, in the sense that one potential recipient ’s ranking above another potential recipient ’s ranking, with respect to that criterion, guarantees that will be ranked above in the priority ranking.

If we accept these as being required of any “reasonable” procedure, then we have a striking (and highly non-obvious) fact to report: Our task of finding a reasonable procedure is impossible! In fact, this is precisely the statement of Arrow’s impossibility theorem in the context of social welfare functions: There is no social welfare function (for three or more alternatives) that satisfies Pareto (our first condition above), IIA (our second condition above), and nondictatorship (our third condition above).