Источник: Perspectives on Political Science, Winter97, Vol. 26 Issue 1, p23, 4p, 2 charts
Taylor, Alan D.
A GLIMPSE OF IMPOSSIBILITY
My starting point is the following question: How can we convey a sense of Kenneth Arrow's impossibility theorem (1950; 1963) to students of political science who have little background in welfare economics or mathematics? Common answers seem to range from, "We cannot" to "We can give them a precise statement of the theorem, but certainly nothing of the proof."
In what follows, I will present a very different answer. Arrow's impossibility theorem establishes the impossibility of designing a voting system for three or more candidates that avoids being flawed in certain fundamental ways. Using no mathematical formalization, I will prove a version of this to the reader through a voting-theoretic discussion.[1]
Let us begin with the case in which there are only two candidates. Here, there is absolutely no problem: Each voter casts a ballot indicating which candidate he or she prefers, and the candidate who receives a majority of the votes is declared the winner.[2] This voting system is called majority rule, and it may well be the only voting system for two alternatives that has occurred to our students. Assume for the moment that we are only interested in voting systems in which the result of an election will remain the same if some ballots are switched from being votes for the loser to votes for the winner. Assume also that there are an odd number of voters and that we are only interested in voting systems that never produce a tie. Kenneth May (1952) proved that majority rule is the only such voting system for two-candidate elections that is unbiased toward both candidates and toward all voters.
The most natural generalization of majority rule to elections with three or more candidates is plurality voting: Each voter submits a ballot indicating his or her most-favored candidate, and the candidate with the most votes wins. The problem with this voting system is that voters have no opportunity to indicate relative preferences among the other candidates. Our search for an ideal voting system will begin with the assumption that a ballot must allow a voter to provide more than a statement of which candidate is his or her favorite.
To be more specific, the context for our voting-theoretic discussion, in which we now allow the possibility that there are more than two candidates, is one in which each voter casts a ballot that provides a rank ordering, without ties, of the candidates. For example, if the candidates were Bush, Clinton, and Perot, then a voter would cast his or her vote by marking an X in a square on the ballot in table 1 (see next page) according to which of the six lists corresponds to his or her ranking of the candidates (with the most-favored candidate on top and the least-favored candidate on the bottom).
A voting system is a procedure for deciding who (if anyone) wins an election when ballots of this kind are cast. We allow the possibility that two or more candidates can tie for the win.[3] Common voting systems include the Borda count (wherein points are awarded each candidate based on how high up on a ballot he or she occurs, with those points summed across all ballots), and the Hare system (wherein candidates are repeatedly eliminated according to fewest first-place votes). However, we shall discuss neither of these systems here, as our present discussion will head in a very different direction. Before moving on, let us record assumption 1: Ballots will provide rank orderings, without ties, of the candidates.
In our search for an ideal voting system we will also assume that it should be rooted--in a sense that we will make precise--in the success that majority role enjoys for the two-alternative case. This view goes back at least to the Marquis de Condorcet (1785) and a voting system known today as Condorcet's method. The idea behind Condorcet's method is a simple one, and we shall illustrate it with the 1980 U.S. Senate race in New York among Alphonso D'Amato (a conservative), Elizabeth Holtzman (a liberal), and Jacob Javits (a moderate liberal).[4] Reasonable estimates, based largely on exit polls, suggest that if ballots had provided rank orderings without ties, as in assumption 1, the percentage of voters casting ballots of each possible type may well have been as illustrated in table 2.
The idea behind Condorcet's method is that ballots such as this one allow us to determine what the outcome would have been in any contest involving only two of the candidates. That is,
(1) Holtzman would have defeated D'Amato, with 15% + 29% + 7% = 51% of the vote for Holtzman and 22% + 23% + 4% = 49% of the vote for D'Amato.
(2) Holtzman would have defeated Jayits, with 22% + 15% + 29% = 66% of the vote for Holtzman and 23% + 7% + 4% = 34% of the vote for Javits.
(3) D'Amato would have defeated Javits, with 22% + 23% + 15% = 60% of the vote for D'Amato and 29% + 7% + 4% = 40% of the vote for Javits.
The important thing to notice is the following: Holtzman would have defeated both of the other candidates in a one-on-one election. This would make her what is called a Condorcet winner for those ballots. More generally, a candidate is said to be a Condorcot winner if he or she would--on the basis of the ballots cast--defeat each of the other candidates in a one-on-one contest. Notice that a single election (with no ties in the ballots, as we are assuming) can never give rise to more than one Condorcet winner.
Condorcet's method is now easy to describe. If there is a Condorcet winner, then that candidate is the unique winner of the election.
Condorcet's method has one rather serious drawback, and it was noticed by Condorcet himself. There can be elections in which there are no winners. For example, consider the situation wherein the electorate splits evenly among the three ballots of B, C, and P (one-third casting ballots of each type):
B C P
C P B
P B C
Two-thirds of the voters prefer B to C; two-thirds prefer C to P; and two-thirds prefer P to B. Thus, this election has no winners if Condorcet's method is used. We shall refer to these ballots as the voting-paradox ballots.
Our second and third assumptions will be that Condorcet's method is used when it applies, and that this "non-winner defect" (wherein some elections have no winner) is rectified by the ideal voting system that we seek. Assumption 2: If a candidate is a Condorcet winner, then he or she is the unique winner of the election. Assumption 3: There is a winner in every election (although we still allow more than one candidate to tie for the win).
The final assumption we shall make is based on another property that Condorcet's method satisfies. Suppose, for a moment, that we hold an election among several candidates using Condorcet's method, and that one candidate--call her Carol--wins, while another candidate--all him Bob--is among the nonwinners. Thus, in some sense, society has expressed a preference for Carol over Bob.
Suppose further that, for some reason, the results of the election are thrown out. Suppose ballots are recast and Bob now emerges as the winner. Could every voter who ranked Carol over Bob in the first election still have ranked Carol over Bob in the second election? That is, could Bob have gone from being a nonwinner to being a winner without any voter reversing the order in which Bob and Carol were listed on his or her ballot?
With Condorcet's method, this is easy to answer. Because Carol won the first election, she defeated every other candidate, including Bob, one on one. If no one reversed his or her ranking of Bob and Carol, then Bob would still lose to Carol one on one, and thus still be among the nonwinners in the second election.[5]
Thus, with Condorcet's method, the only way a candidate can go from being a nonwinner to a winner is if at least one voter reverses the order in which that candidate and the winner of the first election appeared on his or her ballot, This property is known as independence of irrelevant alternatives. (Intuitively, if society expresses a preference for Carol over Bob, then Bob should not be among the winners. Moreover, any movement of candidates other than Bob and Carol on individual ballots should be irrelevant in overriding society's preference for Carol to Bob.) This brings us to our fourth and final assumption: Independence of irrelevant alternatives will be satisfied.
In summary, if we take our four assumptions as the starting point in a search for an ideal voting system, then we are saying the following: Condorcet's method is fine when it works. But it does not always work, and so we must extend it to handle elections in which there is no Condorcet winner. This much is easy. The challenge is in trying to find such an extension that preserves an important property (independence of irrelevant alternatives) possessed by Condorcet's method. Alas, this is impossible.
Part of the challenge in presenting such material to students is in getting them to fully embrace the idea that we are not just saying that no one has yet found an extension of Condorcet's method that satisfies independence of irrelevant alternatives. We are saying that no one ever will--it is impossible. A true appreciation of this fact really requires (in my opinion) an understanding of the argument behind the result.
So let us give the argument. Assume you have some kind of "mystery voting system" that satisfies assumptions I to 4. Consider what the voting system does in a three-voter election in which the ballots of candidates B, P, and C are as follows:
B P P
C C B
P B C
The outcome is clear. Candidate P is a Condorcet winner, and thus (because we are assuming our mystery procedure satisfies assumption 2) candidate P is the unique winner of the election under the mystery voting system. In particular, P is a winner and B is a nonwinner for this election. Now, suppose we hold a new election in which the ballots are the voting-paradox ballots:
B C P
C P B
P B C
Notice that the first voter (column) has B over P in both the previous election and this one, and the second and third voters have P over B in both elections. Thus, independence of irrelevant alternatives now guarantees that our mystery procedure will make B a nonwinner in the election with the voting-paradox ballots. Thus, we have established the following: In an election with the voting-paradox ballots, candidate B is a nonwinner.
This is one-third of the battle, and students will see where we are now headed. In two similar arguments that follow, we can demonstrate that C and P are nonwinners. To show that C is a nonwinner in the election with the voting-paradox ballots, one begins with an election in which the ballots are as follows:
B C B
C P P
P B C
Here, B is a winner and C is a nonwinner, Thus, C remains a nonwinner when P is moved up on the third ballot. Similarly, to show that P is a nonwinner, one begins with an election in which the ballots are as follows:
C C P
B P B
P B C
Here, C is a winner and P is a nonwinner. Thus, P remains a nonwinner when B is moved up on the first ballot. From these demonstrations, one can conclude that: (1) in an election with the voting-paradox ballots, candidate B is a non-winner; (2) in an election with the voting-paradox ballots, candidate C is a nonwinner; and (3) in an election with the voting-paradox ballots, candidate P is a nonwinner. Together, these three conclusions show that our mystery procedure fails to produce a winner in an election with the voting-paradox ballots. This contradicts assumption 3 and completes the proof.
There is a version of the above argument that is more terse and yet establishes a slightly stronger result. Suppose you devise a voting system that extends Condorcet's method to handle at least one election (your choice) in which an odd number of ballots is cast and for which there is no Condorcet winner. (The voting-paradox ballots are an example, but I am allowing you to avoid this particular example if you so choose.) I claim that independence of irrelevant alternatives fails for the voting system that you devised.
To see this, consider the ballots in the election you chose for which there is no Condorcet winner. Choose one of the winners (call him Bob). Because Bob is not a Condorcet winner, there is some other candidate (call her Carol) who defeats Bob one on one according to the ballots. Now change all the ballots by placing all candidates other than Bob and Carol below both Bob and Carol (but not changing the position of Bob and Carol relative to each other on any ballot). In this election, Carol is a Condorcet winner, and thus the unique winner of this election. In particular, Bob is a nonwinner. Thus, if independence of irrelevant alternatives were satisfied, Bob would remain a nonwinner when the other candidates were returned to their original positions on each ballot. But Bob was a winner for this election, so independence of irrelevant alternatives must fail.
Thus, we have seen that it is impossible to devise a voting system that extends Condorcet's method (that is, produces the same winner as does Condorcet's method in elections in which there is a Condorcet winner), satisfies independence of irrelevant alternatives (as does Condorcet's method), and yet produces a winner in even a single election, with an odd number of voters, for which Condorcet's method fails to apply (the voting-paradox ballots provide one example of such an election). This, one hopes, will strike our students as a truly remarkable and troubling situation.
NOTES
1. I first noticed this result in the summer of 1994, and I included it in both Mathematics and Politics (Taylor 1995) and in For All Practical Purposes (COMAP 1996). Colleagues and I have presented this material to students in the humanities and social sciences for the past two years, with student evaluations suggesting it was very well received. Arrow's original theorem used weaker hypotheses than the result we present here.
2. In the present discussion, I am most interested in elections with three or more candidates. Thus, I am deliberately oversimplifying the two-alter-native case by ignoring some important aspects of real-world elections, such as the Electoral College.
3. In the real world, ties would have to be broken by some mechanism. However, our goal is to prove that certain things are impossible, and we want to make it clear that the difficulties that arise have nothing to do with any particular tie-breaking mechanism that is chosen.
4. The voting system that was actually used was plurality voting. D'Amato won with 45 percent of the vote: Holtzman had 44 percent, and Javits had 11 percent.
5. Notice that we are not saying that Carol should remain a winner. After all, every voter may have moved some other candidate (Ted) to the top of his or her list.
TABLE 1. A Rank Ordering Ballot, without Ties, of Three
Candidates
[ ] [ ] [ ] [ ] [ ] [ ]
Most favored Bush Bush Clinton Clinton Perot Perot
Clinton Perot Bush Perot Bush Clinton
Least favored Perot Clinton Perot Bush Clinton Bush

TABLE 2. Rank Ordering of New York 1980 U.S. Senate Race
(by percentage of voters)
Percentage of voters
29 23 22 15 7 4
Most favored Holtzman D'Amato D'Amato Holtzman Javits Javits
Javits Javits Holtzman D'Amato Holtzman D'Amato
Least favored D'Amato Holtzman Javits Javits D'Amato Holtzman

REFERENCES
Arrow, Kenneth. 1950. A difficulty in the concept of social welfare. Journal of Political Economy 58:328-46.
Arrow, Kenneth. 1963. Social choice and individual values. 2d. ed. New York: Wiley.
COMAP [Consortium for Mathematics and its Applications]. 1996. For all practical purposes: Introduction to contemporary mathematics. 4th ed. New York: W. H. Freeman.
Condorcet, Marquis de. 1785. Essai sur l'application de l'analyse a la probabilite des decisions rendues a la pluralite des voix. Paris: n.p.
May, Kenneth. 1952. A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica 20:680-84.
Taylor, Alan. 1995. Mathematics and politics: Strategy, voting, power, and proof. New York: Springer-Verlag.