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.
OK. So this may be coming from left field, but can we put additional constraints on the kinds of permissible preference orders in order to make S collapse into a basically 2-member set (where there Paradox of Majority Rule cannot be formulated)? Maybe I'm thinking too much about American-style voting as opposed to European parliamentary elections, but it seems as if, generally, you get a situation where there is a limited number of evaluative standards shared by the vast majority of voters and these standards tend to agree on much of the ranking, which is why 3rd party candidates never get much more than a few percent of the vote except on rare occasions. If we presuppose certain constraints as empirical facts, then could we design voting systems that satisfy all of the axioms? I imagine that different cases might have different "extra" facts, so that does not hurt the *general* impossibility theorem.
ReplyDeleteSure. On Wednesday, I will prove an important theorem about one such kind of constraint [a theorem proved by Duncan Black, not me, of course]. There are all sorts of ways to limit how people evaluate alternatives, and many of those constraints will serve to guaranhtee that Majority Rule produces a consistant social preference order. That is one of the functions of Arrow's Theorem, to offer a framework forme exploring such things.
ReplyDelete