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.

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.

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.

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

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).