## Wednesday, July 21, 2010

### COLLECTIVE CHOICE THEORY THIRD INSTALLMENT

This is really a devastating theorem. Basically, it says that there is no voting mechanism that gets around the Paradox of Majority Rule. The proof proceeds as follows. First Arrow states a set of little results about the relations R, I, and P. You are already familiar with them. They are trivial, as we shall see. Then he proves a little Lemma about the choice function. Then he proves a big important Lemma that is really the guts of the theorem. Finally, he uses the Lemmas to prove what is essentially an extension of the Paradox of Majority Rule, and he is done. We are going to go through this slowly and carefully. Let us start with the two little lemmas. Lemma 1 and Lemmas 2.

Lemma 1:    (a)    For all x, xRx

(b)    If xPy then xRy

(c)    If xPy and yPz then xPz

(d)    If xIy and yIz then xIz

(e)    For all x and y, either xRy or yPx

(f)    If xPy and yRz then xPz

These all follow immediately from the definitions of R, I, and P, the assumptions of transitivity and completeness, and truth functional logic. Arrow includes them as an omnibus Lemma because at one point or another in his proof he will appeal to one or another of them. You should work through all the little proofs as an exercise. I will go through just one to show you what they look like.

(e) xRy or yRx [completeness]

So if not xRy, then yRx.

But the definition of yPx is yRx and not xRy

Therefore, either xRy or yPx

Lemma 2:    xPy if and only if x is the sole element of C([x,y])

If you review the definition of the Choice set, you will see that this Lemma is intuitively obvious. It says that in the little environment, S, consisting of nothing but x and y, if xPy, then x is the only element in the Choice set, C(S). Since this is a bi-conditional [if and only if], we have to prove it in each direction.

a. Assume xPy. Then xRy, by Lemma 1(b). [See, this is why he put those little things in Lemma 1]. Furthermore, xRx, by Lemma 1(a). So x is in C([x,y]), because it is at least as good [i.e., R] as each of the elements of S, namely x and y. But if xPy then not yRx. Therefore, y is not in C([x,y]). So x is the sole element of C([x,y]).

b. Assume x is the sole element of C([x,y]). Since y is not in C([x,y]), not yRx. Therefore xPy.

Lemma 3:    If an individual, i, is decisive for some ordered pair (x,y) then i is a dictator.

This is a rather surprising and very important Lemma. It is the key to the proof of Arrow's theorem, and shows us just how powerful the apparently innocuous Four Conditions really are. To understand the Lemma, you must first know what is meant by an ordered pair and then you must be given three definitions, including one for the notion of "decisive."

Easy stuff first. An ordered pair is a pair in a specified order. An ordered pair is indicated by curved parentheses. Thus, the ordered pair (x,y) is the pair [x,y] in the order first x then y. As we shall see, to say that individual is decisive for some ordered pair (x,y) is to say that i can, speaking informally, make the society choose x over y regardless of what anyone else thinks. But a person might be decisive for x over y and not be decisive for y over x. We shall see in a moment how all this works out. Now let us turn to the three definitions that Arrow is going to make use of in the proof of Lemma 3.

Definition 1: "A set of individuals V is decisive for (x,y)" =df "if xPiy for all i in V and yPjx for all j not in V, then xPy"

In other words, to say that a set of individuals V is decisive for the ordered pair (x,y) is to say that if everyone in V strongly prefers x to y, and everyone not in V strongly prefers y to x, then the society will strongly prefer x to y. Under majority rule, for example, any set of individuals V that has at least one more than half of all the individuals in the society in it is decisive for every ordered pair of alternatives (x,y).

Definition 2: "xḎy for i" or "i dictates over (x,y)" =df "If xPiy then xPy"

In words, we say that individual i dictates over the ordered pair (x,y) if whenever individual i strongly prefers x to y, so does the society regardless of how everyone else ranks x and y. [Notice that the capital letter D has a little line underneath it.]

Definition 3: "xDy for i" or "i is decisive for (x,y)" =df "If xPiy, and for all j not equal to i, yPjx, then xPy."

In words, i is said to be decisive for the ordered pair (x,y) if when i strongly prefers x to y and everyone else strongly prefers y to x, the society prefers x to y. [Notice that in this definition, the capital letter D does not have a little line underneath it.]

Ok. Now we are ready to state and prove the crucial Lemma 3.

Lemma 3: If xDy for i, then zḎw for i, for all z,w in S

In words, what this says is that if any individual, i, is decisive for some ordered pair (x,y) then that individual i is a dictator [i.e., dictates over any ordered pair (z,w) chosen from S]. This is an astonishing result. It says that if the Social Welfare Function allows someone to compel the society to follow her ranking of some ordered pair, no matter what, against the opposition of everyone else, then the Social Welfare Function makes her an absolute dictator. [L'ėtat c'est moi]. Here is the proof. It is going to take a while, so settle down. In order to make this manageable, I must use the various symbols we have defined. Let me review them here, so that I do not need to keep repeating myself.

An ordered pair is indicated by curved parentheses: (x,y), as opposed to a non-ordered pair, which is indicated by brackets: [x,y].

xḎy for i, which is D with a line under it, means "i dictates over (x,y)" (an ordered pair)

xDy for i, which is D with no line under it, means "i is decisive for (x,y)"

1. Quick typo: Lemma 3: If xDy for i, the*n* zḎw for i, for all z,w in S.

I'm not sure this will make much of a difference, but I'm curious why Arrow chooses to call the relation xDy "decisive". Maybe I just don't know what the word means (possible!) but I only think of someone being decisive when she is able to, for example, break a deadlock. If you want to say that someone is decisive whenever their choice decides the social welfare function, that obviously includes cases where everyone else is against them.

2. Thanks for picking up the typo. I have corrected it. I don't really know why Arrow chose "decisive," except that he already was using "dictates" and "is a dictator," so he needed some term that sounds like "dictates." But what do I know?

3. The definition of `i is decisive for (x,y)' is satisfied under several circumstances that I find very counterintuitive:
* when yPi x;
* when there's a distinct individual j such that xPj y; and most counterintuitively
* when xPy.

But then the antecedent of Lemma 3 is satisfied just by the fact that P is complete.