Thursday, November 03, 2005

Arrow's Theorem - Proof

I decided I'd once again split my Theory of Voting paper into two more manageable parts. 'Enjoy':

Prove and Evaluate Arrow’s Theorem

Arrow’s theorem states that no (transitive and complete) Social Welfare Function (SWF) satisfies four desirable conditions:
U: universal domain – all preference orderings are possible
P: weak Pareto principle – “if every individual in a society prefers x to y, the social choice procedure should pick x over y”[1]
I: independence of irrelevant alternatives – choice between x and y depends only on voters’ rankings of x and y, not comparison to z.
D: non-dictatorship – there is no voter such that when xPiy society prefers x (i.e. xPy) whatever other voters’ preferences.
This is because, assuming a finite number of voters, conditions U, P and I imply a dictator.

Suppose group M prefers x to y, and group N prefer y to x. Suppose x is the social preference (it doesn’t matter which way round this is done, the argument can be applied with all variables reversed). Group M is almost decisive over this pair, where almost decisiveness means they determine the social preference when all others (here, N) are opposed[2].

Theorem 1: If M are almost decisive over one pair, they are over all pairs.
Suppose M rank (a, x, y, b) and N rank (y, b, a, x). We know xPy (since M are almost decisive over x and y). We must show this implies and is implied by aPb. But a is socially better than x and y is socially better than b – both by Pareto. If aPxPyPb then aPb by transitivity.

Theorem 2: If M are almost decisive over a pair, they are decisive over that pair.
It would certainly be odd for M to be almost decisive but not decisive – it would mean their choice is the social choice only when opposed, but not when unopposed, which would imply a perversity about social responsiveness to N’s preferences.

Suppose M rank x, z, y and N rank z top (with any preferences between x and y). Thus, by Pareto, zPy. Since M is almost decisive over x and y, then xPy. By theorem 1, if M are almost decisive over some pair, then are over all, thus also xPz. As xPzPy then xPy by transitivity. Thus xPy irrespective of how members of N rank x and y – M are decisive over this pair.

So far, if M are almost decisive over a pair, they are decisive over that pair, and if they are almost decisive over a pair they are over all pairs – thus if they’re almost decisive over a single pair they’re decisive over all pairs. This establishes that a group can be ‘dictatorial’ – which is obvious and uncontroversial in one sense, as Arrow assumes the whole group are dictatorial in this way[3]. The problem comes when smaller groups can dictate over the rest, irrespective of their preferences. However:

Theorem 3: If M is a decisive group (any size over one), there must be a subgroup of M that is decisive without the rest.
Let us subdivide M1 and M2. M1 rank (x, y, z) and M2 (y, z, x) – with the others, N, still ranking (z, x, y). Since M are assumed decisive over y and z, then yPz[4].

It’s either the case that yPx or xRy (where xRy means ‘x is at least as good as y’, i.e. xPy or xIy). If yPx then M2 are almost decisive over x and y. If xRy then from xRyPz we can conclude xPz by transitivity, and thus M1 are almost decisive over x and y. Thus some subgroup of M, either M1 or M2, is bound to be decisive.
If we keep repeating this division of the divisive group to its logical limit – i.e. a single decisive person – we have violated non-dictatorship. That is, “the set of all members of society is decisive (Condition P). But this set can always be partitioned in such a way that one of the subsets is decisive (by Theorem 3) unless the decisive subgroup has only one member, which violates Condition D.”[5]

[1] I. McLean (1987) Public Choice: An Introduction p.173 (I have italicised the variables for consistency).
[2] Note this is logically weaker than decisiveness, which requires M determine the outcome, whatever N’s preferences (i.e. in cases where N are opposed and cases where they aren’t).
[3] I. McLean (1987) p.176/A. Sen (1982) ‘Personal Utilities and Public Judgements: or What’s Wrong with Welfare Economics?’ in his Choice, Welfare and Measurement p.334, see below. W. Riker (1982) Liberalism against Populism labels this ‘citizen sovereignty’, though for the reason just explained it is unnecessary as a separate axiom.
[4] All in M prefer y to z, so it follows from Pareto that the group (M) does and thus so does society.
[5] McLean (1987) p.176.

1 comment:

  1. Anonymous9:50 pm

    While Arrow's proof is not completely logically correct, the problem with it is one tends to get lost in the details which all seem correct. I think his 5 "logical and ethical" conditions are subject to debate especially Condition 3 "Independence of Irrelevant Alternatives." See my website for examples to back this up. I also have a blog: