Arrow’s impossibility theorem: One-shot proof made accessible
by H. Reiju Mihara First version: July 19, 2012 Last revised: July 22, 2012
Arrow's Theorem (1963; the first edition 1951) is a fundamental result in economics. It opened up the field of social choice theory. This note gives a full proof of the theorem, without assuming strict preferences for individuals and the society. The proof is largely based on Yu's (2012) recent proof, which attempts to improve on Geanakoplos (2005). Yu's proof is one of the simplest and the shortest that I have ever seen. I have tried to make it more accessible by filling in missing details. Remark. I guess I am pretty qualified to discuss Arrow's Theorem, since I am one of the few contemporary social choice theorists that are still publishing papers on the theorem in outlets like Economic Theory, Journal of Mathematical Economics, and Social Choice and Welfare. If you are a novice, you might be interested in watching aten-minute introduction to the theorem on YouTube. The video also contains a very short introduction to later developments. You can find most of my papers mentioned in the video from the link above. Finally, the FAQs contain more on Arrow's theorem.
2. Arrow's Theorem
Let be the set of voters (individuals), where is finite. Let be a set of at least three alternatives (candidates). A preference is a complete and transitive (see the Remark below) binary relation on the set of alternatives. A (preference) profile is an -tuple of individual preferences. We write (read " prefers to ") if (read " weakly prefers to ") but not . We write (read " is indifferent between and ") if and .
Remark. A binary relation on is complete if for all and , we have either or . It is transitive if for all ,, , and imply .
A (preference) aggregation rule (often called a social welfare function) is a function that maps each profile into a preference , called the group preference. We write (read " is ranked above " or "the group prefers to ") if but not . (The Unrestricted Domain condition is incorporated in the definition of an aggregation rule; it requires the domain of the rule to contain all profiles.)
Arrow's Theorem asserts that there is no aggregation rule that satisfies the following three conditions:
Unanimity (Weak Pareto). If every voter prefers to , then the group prefers to .
Independence (Independence of Irrelevant Alternatives). Whether the group prefers to can depend only on the relative positions of and in each voter's preference.
Nondictatorship. There is no voter that can always determine the group's preference whatever the preferences of the others. That is, there is no voter such that whenever prefers to the group prefers to . (Such an is called a dictator, if there is one.)
Remark. More formally, these conditions can be expressed as follows:
Unanimity. For any and for any profile , if for all , , then .
Independence. For any and for any profiles and , if for all , then .
Nondictatorship. There is no such that for all and for all profiles , implies .
Suppose that an aggregation rule satisfies Unanimity and Independence. We prove that there is a dictator.
We first give the following definitions: A voteris decisive for(the ordered pair) if, whenever he prefers to the group prefers to . A voter is decisive for (the set) if he is decisive for and for . So a dictator is a voter that is decisive for all pairs .
Consider an arbitrary profile where for all . Swap the positions of and sequentially from to . Because of Unanimity, we start with ("the group prefers to ") and end with . Let be the first voter (-pivotal voter) that causes the violation of (the violation is written , "the group does not prefer to "). Note that this definition of is independent of the profile because of Independence. (Verify this.)
Lemma. Let be arbitrary distinct alternatives. Then we have:
is decisive for (the set).
Proof of the Lemma. Consider any profile in which
voters through prefer to to ; and
voters through prefer to to .
Then, we have , where the first relation is by the definition of and the second by Unanimity. Next, consider any profile in which
voters 1 through prefer bothand to but order and in any way (they may be indifferent between and );
voter prefers to to ; and
voters through prefer to both and but order and in any way.
Then, we have , where the first relation is by the definition of and the second by Independence (individual preferences between and are the same inand in ). Since the positions of and are arbitrary for each voter except in , Independence implies the following Claim 1. is decisive for (ordered pair).
We next prove the following Claim 2. .
To show , suppose otherwise. Then just after swaps the positions of and in the swapping process that defines , we have . Since still prefers to at this point, Claim 1 implies , a ontradiction.
To show , suppose otherwise. Then just after swaps the positions of and in the swapping process that defines , we have by Claim 1. Since still prefers to at this point, we have , a ontradiction.
Since are arbitrary and distinct, we can replace in Claim 1 and Claim 2 by (that is, we can exchange the roles of and in the claims). This gives
is decisive for (ordered pair).
Combining the second statement with Claim 2 gives the second assertion () of the lemma. Combining the first statement with Claim 1 gives the first assertion ( is decisive for (the set)) of the lemma, since . [End of the proof of the Lemma]
Choose two distinct alternatives and fix them for the rest of the proof. Replace in the Lemma by , where is any alternative distinct from . The following claim follows from the Lemma: Claim 3. is decisive for and .
We conclude by showing that is a dictator; that is, is decisive for all satisfying .
Case 1: Both and belong to . By Claim 3, is decisive for . (Since is decisive both for and for , we can conclude that is decisive for , whether or .)
Case 2: Exactly one of belongs to .
If or , we can assume without loss of generality. Replacing in the Lemma by , we conclude that is decisive for But by Claim 3.
If or , we can assume without loss of generality. Replacing in the Lemma by , we conclude that is decisive for
Case 3: Neither nor belongs to . Replacing in the Lemma by , we conclude that is decisive for But follows from replacing in the Lemma by .
The assumption that is finite is crucial for this proof. In fact, when there are infinitely many voters, aggregation rules exist that satisfy the three conditions of Unanimity, Independence, and Nondictatorship. However, Mihara (1997) shows that such rules violate algorithmic computability, thus strengthening Arrow's theorem.
The assumption that there are at least three alternatives is also crucial, since we need to pick three distinct alternatives in the Lemma. In fact, when there are only two alternatives, simple majority rule, for example, satisfies the conditions. More generally, one can assign a number called the Nakamura number to each aggregation rule satisfying conditions such as neutrality (equal treatment of alternatives) and show that this number plays a similar role: when the number of alternatives is less than , the rule can pick a "best" alternative rationally, but otherwise a voting paradox (a cycle such as beats , beats , and beats ) will arise for some profile. Some super-majority rules (such as those requiring 2/3 of the votes) have a Nakamura number greater than 3, but such rules violate the conditions of Arrow's theorem. Kumabe and Mihara (2011) extend the above result (Nakamura's theorem) in several directions.
I'm saying this again, but the FAQs contain more on Arrow's theorem.
Arrow, K. J. (1963). Social Choice and Individual Values (2nd ed.). New Haven: Yale University Press. Geanakoplos, J. (2005). Three brief proofs of Arrow’s Impossibility Theorem. Economic Theory, 26(1), 211-215. doi:10.1007/s00199-004-0556-7
Kumabe, M. & Mihara, H. R. (2011). Preference Aggregation Theory Without Acyclicity: The Core Without Majority Dissatisfaction. Games and Economic Behavior, 72, 187--201. doi:10.1016/j.geb.2010.06.008 [working paper]