## Monday, July 26, 2010

### COLLECTIVE C HOICE FIFTH INSTALLMENT

Proof of Arrow's Theorem

Step 1.     By Condition P, there is at least one decisive set for each ordered pair, namely the set of all the individuals. From all the decisive sets, choose a smallest decisive set, V, and let it be decisive for some ordered pair (x,y). What I mean is this: Consider each set of individuals that is decisive for some ordered pair or other. Since there is a finite number of individuals, each of these sets must have some finite number of individuals in it. And the sets may have very different numbers of individuals in them. But one or more of them must be the smallest set. So arbitrarily choose one of the smallest, call it V, and label the pair of alternatives over which it is decisive (x,y).

Step 2:     By Condition P, V cannot be empty. [Go back and look at Condition P and make sure you see why this is so. It is not hard]. Furthermore, by Lemma 3, V cannot have only one member [because Lemma 3 proved that no single individual, i, can be decisive for any ordered pair (x,y) ]. Therefore, V must have at least two members.

Step 3: Partition the individuals 1, 2, ......, n in the following way:

The set of all individuals

---------------------------------------------------------------

| |

V V3

---------------------

V1 V2

Where V1 = a set containing exactly one individual in V

V2 = the set of all members of V except the one individual in V1

V3 = the rest of the individuals, if there are any.

Is this clear? V is a smallest decisive set. It must have at least two individuals in it. So it can be divided into V1 containing just one individual, and V2 containing the rest of V. V3 is then everyone else, if there is anyone else not in the smallest decisive set V.

Step 4: Now let the individuals in the society have the following rankings of three alternatives, x, y, and z. [And now you will see how this is an extension of the original Paradox of Majority Rule with which we began.]

V1: x > y and y > z

V2: z> x and x> y

V3: y>z and z>x

[You see? This is one of those circular sets of preference orders: xyz, zxy, yzx]

V1 is non-empty, by construction.

V2 is non-empty, by the previous argument.

V3 may be empty.

Step 5: a) By hypothesis, V is decisive for x against y. But V is the union of V1 and V2, and xPiy for all i in V1 and V2. Therefore, xPy. [i.e., the society prefers x to y.]

b) For all i in the union of V1 and V3, yPiz. For all j in V2, zPjy. If zPy, then V2 is decisive for (x,y). But by construction, V2 is too small to be decisive for anything against anything, because V2 is one individual smaller than a smallest decisive set, V. Therefore not zPy. Hence, yRz [see the definitions of P and R].

c) Therefore xPz by Lemma 1(f) [go back and look at it].

d) But xP1z and zPix for all i not in V1, so it cannot be that xPz, because that would make V1 decisive for (x,z), which contradicts Lemma 3. Therefore, not xPz.

Step 6: The conclusion of Step 5d) contradicts Step 5c). Thus, we have derived a contradiction from the assumption that there is a Social Welfare Function that satisfies Conditions 1', 3, P, and 5. Therefore, there is no SWF that satisfies the four Conditions. Quod erat demonstrandum.

OK. Everybody, take a deep breath. This is a lot to absorb. Arrow's Theorem is a major result, and it deserves to be studied carefully. Go back and re-read what I have written and make sure you understand every step. It is not obscure. It is just a little complicated. If you have questions, post them as a comment to this blog and I will answer them.

1. 2. 