Notes on Arrow's Impossibility Theorem

COURSE OUTLINE

Definitions and Notation

1. We will reproduce Geanakoplos' short proof for a world with 5 alternatives, which we label A, B, C, D, and E, and 6 voters who we will label 1, 2, 3, 4, 5, and 6.

2. A profile of voter preferences is just a list ranking the alternatives of each voter with alternatives higher on the list being more preferred.   Example:

We will use the notation AP(i)B to indicate that voter i prefers option A to B.  We assume that all voters preferences over alternatives are transitive, so that if AP(i)B and BP(i)C then AP(i)C

3. A constitution is voting rule (also called a social choice function) which associates a transitive social preference ordering over all possible alternatives with any profile of individual voter preferences.  We will use the notation APB to indicate social preference.

4. A constitution respects unanimity if society ranks alternative X over alternative Y (where X and Y are any possible alternatives) whenever every individual voters ranks X over Y.

5. A constitution respects independence of irrelevant alternatives   if the social relative ranking of alternatives X and Y depends only on the relative ranking between X and Y of individual voters.  To illustrate this, consider a pairwise majority rule constitution and the profile of preferences given above.  In this profile, voters 1, 2, 3, 5, and 6 all prefer option A to option B.  Only voter 4 prefers B to A.  Under the majority rule constitution, then, society prefers A to B.   Independence of irrelevant alternatives requires that this remain the case even if we change the profile so that voter 4 likes B the best (leaving A is the worst position), and changing the rankings of every other voter so that B is the worst alternative, and A is the second worst.  Clearly, under pairwise majority rule, society would continue to rank A over B in this case (i.e. pairwise majority rule satisfies independence of irrelevant alternatives).

6. A constitution is a dictatorship of individual n if whenever individual n prefers X to Y, society prefers X to Y.

Arrow's Impossibility Theorem

During the 1960's, Stanford University economist Kenneth Arrow proved the following remarkable result.

Arrow's Theorem:  Any constitution that respects transitivity, independence of irrelevant alternatives, and unanimity is a dictatorship, as long as there are at least 3 alternatives.

The following simple proof (which we carry out for the 5 alternative, 6 voter case) is due to John Geanakoplos.

1. Choose an alternative arbitrarily (say B).  We will show first that in any profile in which every voters ranks option B either best or worst, then the social ranking must also rank option B as either best or worst.  The table below shows an example of such a profile.

Suppose now that the assertion is not true, and that for the given profile and distinct alternatives A, B, and C it is the case that APB and BPC.   By independence of irrelevant alternatives, this would continue to be true if every voter moved C to a position above A (as in the profile below) because this can be arranged without disturbing any voters ranking of A and B, or of their ranking of B and C.

Voter 1	Voter 2	Voter 3	Voter 4	Voter 5	Voter 6
B	B	B	B	C	C
C	D	C	D	E	D
A	E	A	C	A	E
E	C	D	A	D	A
D	A	E	E	B	B

Note that our ability to make this change depends on the fact that alternative B occupies an extreme position (i.e. at the top or bottom of every voter's preference).   If B were not in an extreme position, it might be the case that to move C over A for some voter, we would have to move C over B, which changes the relative ranking of B and C for that voter.

By transitivity of the social preference, we know (since APB and BPC) that APC.  But by unanimity, since all voters now prefer C to A, it must be that CPA, a contradiction.  Since we derived this contradiction from the assumption that the social ranking could have B in the middle even though all voters have B either on the top of their ranking or the bottom, this assumption must be false.  Hence, the social ranking corresponding to this kind of profile must put B either on top or on bottom.

2. We show next that there is some voter n* who is pivotal in the sense that by changing his vote at some profile, he can move alternative B from the bottom of the social ranking to the top.  Since the identity of such a voter might depend on which alternative is in the extreme position (B in the case we have been examining), we will write n*=n(B) to indicate that this voter's identity depends on the alternative.   To show the result, consider a profile in which every voter has B at the very bottom of their (otherwise arbitrary) ranking.  By unanimity, society must also have B at the bottom of its ranking.  Now, starting with voter 1 and proceeding to voter 6, let every voter successively move B from the bottom of their ranking to the top, leaving all other relative rankings the same.  Let n* be the first voter whose switch causes the social ranking of alternative B to change.  (By unanimity, the social ranking must switch at the latest when n*=6.)  Let P1 denote the profile just before voter n* moves B from the bottom to the top.  Similarly, let P2 denote the profile just after voter n* has moved B from the bottom to the top.  We illustrate two such profiles below.  In the example, we have n*=4.

Profile P1

Profile P2

Voter 1	Voter 2	Voter 3	Voter 4	Voter 5	Voter 6
B	B	B	B	C	C
C	D	C	E	E	D
A	E	A	D	A	E
E	C	D	C	D	A
D	A	E	A	B	B

Since in switching from profile P1 to P2 the social ranking of B changes, while every voter has B either at the top or bottom of their ranking, we conclude from the argument given in part 1 that the social ranking must now have B at the top (i.e. the ranking has switched from putting B at the very bottom, to putting B at the top).

3. We are now going to show that voter n* identified above is in fact a dictator over any pair of alternatives A, C not involving B.  To see this, choose one element (say A) from the pair A, C.  Construct a profile (which we will call P3) from profile P2 by letting n* move A above B, so that AP(n*)B and BP(n*)C.   Also, let all other voters rearrange their relative rankings of A and C while leaving B in its extreme position.  We illulstrate this below for the profile based on P2 above.

Profile P3

Independence of irrelevant alternatives now implies that APB.   To see why notice that all voters other than n* (=4 in our example) have rankings similar to those in profile P1 in the sense that B is on top for all voters up to n*, and all voters after n* have B on the bottom.  Since voter n* prefers A to B, this will continue to be the case (by independence of irrelevant alternatives) if we have voter n* move B to the bottom of her ranking.  In this case, however, we know that society must prefer A to B since B is at the bottom of the social ranking for this profile.

By the same reasoning, we can infer that BPC.  In profile P3, every voter before n* has B on top, while every voter after n* has B on the bottom.  When voter n* has B on top, we know that society prefers B to C.  Since moving voter n*'s ranking of A above B doesn't change n*'s relative ranking of B and C, independence of irrelevant alternatives implies that in profile P3, society prefers B to C. 

Now, by transitivity of the social preference, we must have APC.   Again using independence of irrelevant alternatives and the fact that our choice of alternatives A and C was arbitrary, we conclude that APC whenever AP(n*)C. 

This doesn't quite prove the n* is a dictator, since it doesn't tell us what happens when we compare A and B.  But in this case, we can choose an alternative C distinct from A and B and put C in the extreme position as in the construction above.  From the result above, though, this tells us that there is a voter n'=n(C) such that APB whenever AP(n')B.  Let us show that n'=n*.  Take the profile with all voters other than n' having C in an extreme position, and such that AP(n')B.   Use independence of irrelevant alternatives to move B to the top of the rankings of any voters who like B better than A.  Similarly, move B to the bottom of the rankings of voters who like A better than B.  This gives us a profile in which we know that voter n* is pivotal: if n* likes A better than B, then n* will have B at the bottom or her ranking.  If she likes B better than A, she will have B at the top.   Furthermore, because n* is pivotal, if she switches her ranking of B, society's ranking will switch.  Thus, since we have APB, it must be that AP(n*)B, and if n* switches so that BP(n')A, then we will have BPA, so n* is a dictator.