Arrow's Impossibility Theorem: Summary and Explanation

Overview

A central idea in democracy is that in voting for what the community should do, each individual gets to express their preference for one thing over another. If individual preferences don't all align then sometimes there will be a puzzle about what the community should do--assuming policy decisions are ideally supposed to represent the aggregation of individual preferences. Let me make explicit the assumption in that last sentence.  The assumption is that a community's ranking of options should be derived only from the individual rankings.

Arrow's theorem shows that, given 3 or more policy alternatives, it is sometimes impossible to sum up individual preferences to derive a community-wide ranking without violating at least 1 of 4 minimal constraints. Another way to express this is to say that sometimes you can't move from individual rankings of preferences to a community ranking of preferences without violating 1 of 4 ideal criteria for a community ranking.

Before getting all fancy, there's a simpler illustration that demonstrates that there will be cases where it's impossible to derive a community ranking of alternatives from individual rankings.

Let's suppose there's a community of 3 people. They have to vote on how to rank 3 alternative. It can be a ranking of anything: people to hold office, priorities for funding certain programs, and so on. To keep things simple we'll just call the three alternatives A, B, and C. Here are the individual rankings:

Person 1: A>B>C

Person 2: B>C>A

Person 3: C>A>B

Notice there's a problem right away.  As you might expect, people rank things differently. Democratic theory tells us that in order to figure out how the community ought to rank the alternatives (for policy purposes) we need to aggregate the individual rankings. Let's do that and see what happens.

Doh! We can't because there's a three way tie for the first priority, a three way tie for the second priority, and a three way tie for the third priority. So, now what? Do we reject democracy and do what Plato told us to do 2, 400 years ago: Put the philosophers in charge? I say "yes" but some of you might not agree. For those that disagree there's still hope...

The Condorcet Method 

Let's take each set of alternatives as pairs and compare them that way. If a majority prefer one alternative over another, that might help give us a social ranking. That is, we will apply a simple majority rule to pairs of alternatives

Look at pair (A, B). Person 1 and Person 3 prefer A to B. Even though Person 2 prefers B to A, we say majority rules in terms of generating a society-wide ranking. Perfect. Now we have part of our social ranking:

A>B

Let's now turn to the relationship between B and C. Person 1 and 2 both rank B ahead of C, majority wins so our social policy should reflect this. We add it to our social ranking:

B>C

Now we can do a little basic logic to figure out the rest. If A is preferred to B and B is preferred to C then it follows (by transitivity) that A is preferred to C. That's just elementary school logic! Amiright? The last pair in our social ranking should look like this:

A>C

Now hold on a tick. Let's look at the individual preference orderings again because that's what's supposed to generate the social ordering. Take a look and see if you notice something funky. 

I'll wait....

You should have noticed that Person 2 and Person 3 prefer C to A. Our majority rule tells us that our social ranking should then be 

C>A

Well, that's a problem. 

Ok, fine. Let's just ignore the illogicality of the social ranking and stick to our majority rule.

We now have C>A, A>B and logically it must follow that C>B. But look back to the individual preferences. They tell us that B>C. To quote the great philosopher Britney Spears, "Oops, we did it again...." (and we could continue the process ad infinitum) 

So, what's the point of all this? The point is that even with a very simple voting rule there will be occasions where you can't generate a social ordering of preferences that conforms a basic norm of rationality (i.e., transitivity) if that social ordering is derived from individual orderings alone...which is kinda at the heart of democracy.  Democracy can't do the very thing that it's supposed to do! Therefore, Plato was right, philosophers should be put in charge immediately. Report to your reeducation camps. Ayn Rand book-burning party scheduled at 11. 

The end.

Ok, I lied. That's not the end. But things don't get better, they get worse.  But we're going to need to get a bit fancy to show why...


Vocabulary:
A preference is a ranking of one outcome/policy/thing over another. A preference in economics is a technical term. It doesn't mean "liking". It is always comparative: E.g., Bob prefers x to y. When one thing is preferred to another it is said that x gives Bob more utility than y (i.e., it has more value); so preferences are represented in terms of utility.

A utility function is a ranking of a set of preferences in terms of utility. Suppose Bob can choose from 3 kinds of fruit: apples, pears, and bananas. Suppose Bob prefers apples to bananas and bananas to pears. His utility function will rank apples above bananas and bananas above pears. Notice that transitivity is implied. That is, x>y and y>z, then x>z.

An individual utility function is simply the utility function of a single person. That is to say, it's how a particular individual ranks all the possible options. Bob's ranking of {apples, bananas, and pears} is an example of an individual utility function. It one particular person's (i.e., Bob's) ranking of available options.

A social or welfare utility function is the utility function you get when you aggregate all the individuals in a particular community. Basically, take all the individual rankings of options and add them all up. That's the social utility function.

Minimum Criteria for Establishing a Social Welfare Function (in a Democratic Society)
Here comes the tricky part. Who needs the Quickee Mart? There are 4 (actually 5) minimal conditions that we don't want to violate is coming up with a community wide ranking of preferences.

Condition T: This one's the key.
Condition T is transitivity. It's not often directly stated but implied by the conditions of rationality. As mentioned above, if someone prefers x to y and y to z then transitivity requires that they prefer x to z.

Transitivity is said to be a rational constraint on generating a social utility function. The remaining four are said to be normative constraints; i.e., they are values that constrain how to generate a social utility function.

Condition U: Let's go to the zoo.
Condition U is unrestricted domain. This means that in a democratic society, at least pre-constitutionally, no preference orderings can be precluded from the social utility function. For example, suppose a set of 3 things {apples, guns, the bible}. One person ranks them {Bible, guns, apples} and another person ranks them {guns, Bible, apple}. There are still ways to rank these options by putting apples ahead of guns and the Bible. Any ranking that puts apples ahead of guns and the Bible are clearly irrational and not socially justified, however, unrestricted domain says that you can't exclude these rankings from a social welfare function no matter how crazy they are.

Condition P: Learn it with me!
Condition P is weak Pareto principle. Without getting too fancy, the weak Pareto principle is simply that if every individual in a society prefers guns to apples (i.e., their individual utility functions rank guns above apples) then the social utility function must also rank guns above apples.

Condition I: Buzz like a fly.
Condition I is independence of irrelevant alternatives. Suppose all individuals prefer guns to bananas. So, condition P obtains. However, Bob's ranking is {guns, Bible, bananas} and Mary's is {Bible, guns, bananas}. The fact that Bob ranks guns ahead of Bible and Mary ranks Bible ahead of guns should have no bearing on the fact that when we aggregate their preferences (i.e., construct the social utility function) guns must be ahead of bananas. The alternative "bible" is irrelevant to constructing the social utility function. The only thing that matters is whether each individual ranks guns higher than bananas. If this is the case, then the social utility function must put guns ahead of bananas.

Condition D: It's so cooooold in the D....
Condition D is non-dictatorship. Consider all the possible things that individuals could have preferences over that will be relevant to social policy. Think of all the different things that get voted on. Simply put, non-dictatorship stipulates that there's no individual who gets their way for everything. In other words, there can be no individual who's individual utility function (i.e., ranking of all the possible policy options) matches the social utility function (i.e., the aggregate of all the individual utility functions). In short, there is no person that can always get their way because this would imply dictatorial power and that's unamerican! (and undemocratic). The social utility function needs to represent (by definition) the preference rankings of various individuals and so if it represents the ranking of a single individual it can't be the ranking of all individuals.

Back to Arrow's Theorem: The social utility function is defined as the aggregate of all individual utility functions. Arrow's theorem says there is no way to construct a social utility function without violating one of the 4 (5 including transitivity) conditions. Why should we care? Because if we conceive of democracy of taking the aggregate of each individual's preference ranking and enacting policy according to that aggregate ranking, we can't get the ranking without violating one of the 4 criteria. 

In other words, to construct a community-wide ranking of preferences, we will have to violate either transitivity (i.e., although everyone ranks x higher than y and y higher than z, we will rank z higher than x); unrestricted domain (i.e., we will have to exclude some preference orderings as possibilities. E.g., "You aren't allowed to prefer z to y."); weak Pareto (i.e., we will have to rank y higher than x even though everyone individually ranks x higher than y); independence of irrelevant alternative (i.e., even though everyone ranks x higher than y, if some people rank z higher than y then y will be ranked higher than x); non-dictatorship (i.e., someone will always get their way: their preferences ranking will become society's preference ranking).

I'm going to do two different proofs for Arrow's Theorem. The first is an informal proof. The second is a formal proof. 

Strategy:

The first part of the proof is to prove a conditional: If an individual is almost decisive over one pair of options for f, he will be decisive over all pairs and therefore be a dictator. We apply the minimal conditions for constructing the social welfare function (f) from individual functions and show that this can't be done without violating D. The second part of the proof is to show that there is such an individual.

We're gonna need some formal definitions: Using variables to stand in for terms will help us cut down on awkward phrases...

Notes/defining variables: V=a subset of individuals in the community. xPy= x is preferred to y (in the social utility function). yPx=y is preferred to x (in the social utility function. i=individual. xPiy= some individual prefers x to y; i.e., this is a preference ranking for an individual utility function. f=social utility function.

Almost Decisive:  A set of individuals V is almost decisive for some x against some y if, whenever xPiy for every i in V and yPix for every i outside of V, x is socially preferred to y (xPy). In English this means that a subgroup (identified with the variable V) of the community is almost decisive if V's preference ranking for x over y sets the social utility function in terms of ordering x and y even if other members of the community (not V) rank y ahead of x. This is a very common scenario. Usually, we have a rule that says if there isn't agreement over a ranking then the majority wins. We can think of V as the majority in a community.

Decisive: A set of individuals V is decisive for some x against some y if, whenever xPiy for every i in V, xPy.  In English: If there's a subgroup in the community and every member of that subgroup ranks x ahead of y and the social utility function adopts this ranking (xPy) then V is decisive. Notice the difference with 'almost decisive'. With almost decisive V's preference ranking sets the social utility function if V's conflict with non-V members of the community. In Decisive, it doesn't matter whether V's ordering conflicts or not. Whatever V's ranking of x and y, that's what the social ordering of x and y will be too.

Informal Proof
In the informal proof we're going to prove the contagion principle: The contagion property explains why all four conditions can't be met simultaneously. In short, if one individual's preferences over one pair of alternatives are almost decisive (i.e., generate a ranking in the social utility function) this decisiveness spreads to all other pairs of alternatives.  

For example: suppose there are 2 people, Abe and Bob. Abe prefers guns to bananas but Bob prefers bananas to guns. If the social utility function becomes guns over bananas (maybe there's a voting rule that says in case of tie we go according to alphabetical order) then we say that Abe's preferences are almost decisive. I.e., his preferences set the social utility function. The contagion property says that once one individual's preferences become almost decisive (i.e., are the ones that set the social utility function) then that decisiveness will spread to other pairs of preferences. We can see how this result occurs by doing an informal proof.

Up until now we've talked about a subgroup (V) in the community being decisive or almost decisive. We now introduce a particular individual, J. He prefers x to y (xPjy). Suppose J's ranking of x and y is almost decisive. To symbolize this we will use this: D(x,y). To symbolize that J's ranking is decisive we'll use this: D*(x,y). Notice that if a person or group's ranking is decisive, it's also almost decisive. 

Why? This is almost trivial but it's because if a particular individual's ordering of preferences over 2 options set the ordering in the social utility function then it's also true that that individual's preference over 2 options set the ordering of the social utility function even if other members of the community rank those same options differently. In short, D*(x,y) implies D(x,y). Otherwise stated, if there's a rule that your preferences set the social preferences then your preferences will also set the social preferences even if other individuals don't have the same preferences as you. Seems trivial but it'll matter later.

Lemma  1
Prove that if there is some individual J who is almost decisive for some ordered pair of alternatives (x,y), then that individual's preferences will be decisive for all pairs in f.  (If one individual's ordering preferences set the entire social utility function then that person is a dictator and Condition D has been violated.)  In other words, if f satisfies U, P, and I, it can't also satisfy D. 

Proof:
Step 1: Assume that some individual J is almost decisive for some x against some alternative y. (J prefers x to y and this preference sets f even if other members of the community rank y ahead of x.) Assume also there is a third alternative z. Let's also refer to the collection of all individual utility functions other than individual J's as i. (i=the utility functions for all members of the community except J).

According to U (unrestricted domain) we can order x, y, z in any way possible. Individuals are allowed to order them however they want even if preferring z to x seems loco. So, let's suppose the following preference orderings:

xPjy,  yPjz  and
yPix,  yPiz

Notice that transitivity imposes a complete ordering on J's preferences. If he prefers x to y and y to z then he must also prefer x to z. In the case of i, however, things are different. Transitivity doesn't impose any ordering between x and z. All we know is that y is preferred to both x and z but we don't know how x and z are ranked against each other.

We've stipulated that J's ranking of x and y is almost decisive--meaning that even if other members of the community rank them differently, f is set by J's ranking. Since J ranks x ahead of y, f will also rank x ahead of y. So, xPy for f.

Next we notice that both J and i rank y ahead of z. This activates condition P (weak Pareto) which stipulates that if every individual in the community ranks y ahead of z then  f also ranks y ahead of z. (Recall that i=all individuals except J). So, now f has two rankings xPy and yPz.

Our social utility function ranks x ahead of y and y ahead of z. Condition T (transitivity) now kicks in. If x>y and y>z transitivity demands that x>z.

Recap so far: We started out by saying that J's preference for x over y is almost decisive and so part of f is xPy. Applying condition U told us that f must take into account all possible orderings of x, y, and z. Applying condition P added yPz to f.  So now f contains xPy and yPz. Transitivity completes the ordering for f by setting xPz.

Why should we care? Notice that for all individuals except J the relationship between x and z is still open. Some might prefer x to z while others might prefer z to x. However, because we applied conditions U, P, and T, the social utility function (f) reflects J's complete ordering of the three variables. This shows that if one individual is almost decisive in setting the social ordering (f) for a single pair, this decisiveness spreads to all other rankings in f (i.e., the contagion principle is instantiated).  Well, not quite. We still have to finish the proof...

We said that applying conditions T, U, P, I would lead to a violation of Condition D. That is, you can't simultaneously uphold condition T, U, P, and I without undercutting D. We still need to apply condition I to finish the proof.  So, let's do eet!

Recall that condition I (independence of irrelevant alternatives) stipulates that if everyone ranks some option x above some option y then it doesn't matter to the social utility function (f) where they rank a third option so long as x is always ahead of y. So, maybe you have 3 people with the following ordered sets A {x, y, z}, B {z, x, y}, C {x, z, y}. In each of these individual utility functions x is ahead of y and so when we construct the social utility function, the ranking of z should have no bearing on the ordinal ranking of x and y; i.e., f=xPy.

Also, (and this is the important part for the proof) f can only be informed by individual rankings. Notice that for i we stipulated yPix and yPiz. The relationship between x and z was left undetermined. Maybe people in i are indifferent to x and z. The point is that the ordering of x and z for the social utility function can only come from individual orderings. By definition, it is merely a representation of those orderings and so if individuals don't have an ordering of two options (as in i) then those individuals aren't relevant to the social ordering.  There's nothing for the social ordering to represent!

What follows from this is that the social ordering of x to z is purely a consequence of J's orderings. That is, since i doesn't have an ordering of x and z it can't be represented in f and so the actual ordering in f is a consequence of only one individual's ordering (i.e., J's). In short, by applying T, U, P, and I we end up with a violation of D. The contagion principle effectively makes J a dictator. The social utility function and J's individual utility function are one and the same. J gets everything he wants.

Since J sets the social ranking of x in respect to z then he is decisive (not just 'almost decisive'). In short, if J is almost decisive for x and y (that is, there is some voting rule that lets J's preference for one set of options be represented in f) then J's preferences will be decisive for some other set of options (x and z).

Step 2:
Let's again assume that there is some voting rule that makes it so J is almost decisive for x and y (xPjy).

Let's further assume some new preference orderings

zPjx,  xPjy   and
zPix,  yPix      (recall that i=everyone except J)

Since J is almost decisive for the ordering of x and y and xPjy the social utility function is ordered accordingly, xPy.

Condition P tells us that f must also order zPx because both i and J order z ahead of x. So far, our f looks like this: zPx and xPy. Transitivity now kicks in (if z>x and x>y then z>y) so the social ordering of z and y will be zPy.

We now apply Condition I. The only thing relevant to a social ordering are individual ordering. Since i doesn't have a ranking of z and y it can't factor into how f ranks them. It follows that the ordering of z ahead of y in f is a consequence of J's preferences alone. And so J is a dictator in terms of setting the social utility function.

J started out with almost decisive power to set a pair ordering in f. In this case it was xPy. To order the unsettled options in f we applied conditions T, U, P, and I.  The result was that where there wasn't total unanimity, the ordering (zPy) was set based on J's ordering alone. No other individual had an influence on f. And so condition D (non-dictatorship) was violated. It also follows that if one individual is almost decisive for setting one pair ordering in f then they will be decisive for the entire ordinal ranking of f.

Part 2
If you're like me when I first saw the first part of the proof, I was like, "Ok, sure maybe if someone were almost decisive over one pair they'd end up being decisive over all pairs, but how likely is it that such a person exists?" Well, as it happens, this is the second part of the proof. You can prove that such an individual must exist!  

Before doing that, however, I'm going to present the formal version of the 1st part of the proof. Feel free to skip it and go straight to the last part of the proof; that there is indeed a dictator. 


Formal Proof:
Symbolization: 

1. x>y = x is preferred to y (xPy). 

2. x<y = y is preferred to x (yPx).

3. J= a particular individual.

4. i= everyone in the community except J.

5. xPy=x is preferred to y in the social utility function (f); xPjy= J prefers x to y; xPiy=everyone except J preferes x to y.

Step 1

J: x>y>z

i: x<y>z

Therefore

f:  If xPy (because J is almost decisive for x,y), yPz (because condition P) then xPz (because condition T and I).

Therefore if D(x,y) (i.e., if someone is almost decisive for x, y) then D*(x,z) (then they are decisive for x,z) then D(x,z) (because D* implies D).

Step 2

J: z>x>y

i: z>x<y

Therefore, 

f: zPx (from condition P), xPy (J is almost decisive for x,y) implies zPy (Condition T and I).

So, if D(x,y) then D*(z,y) then D(z,y).

Step 3

J: y>x>z

i: y>x<z

Therefore,

f: yPx, xPz implies yPz

So, if D(x,z) then D*(y,z) then D(y,z).

Step 4

J: y>z>x

i: y<z>x

Therefore,

f: yPz, zPx implies yPx

So, if D(y,z) then D*(y,x) then D(y,x).

Step 5

J: z>y>x

i: z>y<x

Therefore,

f: zPy, yPx implies zPx

So, if D(y,x) then D*(z,x) then D(z,x).

Step 6

J: x>z>y

i: x<z>y

Therefore,

f: xPz, zPy implies xPy

So, if D(x,z) then D*(x,y) then D(x,y).

Part 2: Finding the Dictator
Part 1 of the proof was to prove the hypothetical: If an individual is almost decisive over one pair of options he will be decisive over all pairs (via contagion). In Part 2 we prove that there is such an individual. To do this we'll need to show that there really is an individual that is almost decisive over one pair.


We know that for any set of ordered pairs in f there is a decisive set of individuals. We also know that if a group is decisive they are also almost decisive over that pair. In short, the fact that pairs are ordered in f implies that some voting rule made some group of individuals decisive for that pair. We scan all the ordered pairs in f and pick the one that has the smallest decisive set of individuals. Call these individuals V and let's assume they're decisive for (x,y).


If V contains just one individual, we've found the dictator. If V contains more than one let's divide it into two groups with the following preference orderings (recall everyone in V ranks x>y):
V1 (only one person): x>y>z
V2 (everyone who is decisive for xPy except the person in V1): z>x>y
and
O is everyone else in the community: y>z>x


By definition, f = xPy because V is almost decisive for (x,y). Where do z fit into f? Let's first look at the relationship between y and z. Can f = zPy? We've already defined V as the smallest decisive set and since V2 is a subset of V it can't be decisive. Since f can't be zPy, f must be yPz. Now, f = xPy and yPz. Transitivity implies further that f = xPz. In short, f = x>y>z. If that ordering looks familiar it's because it belongs to V1. Notice also that neither V2 nor O rank x ahead of z. Only the individual V1 does. So, despite the fact that everyone one except V1 ranks z ahead of x, f = xPz. We've found our dictator.



From the first part of the proof we proved that if an individual is almost decisive over one pair of options by contagion he will be decisive (and almost decisive) over all other pairs in f. We've proven that there is such an individual and so the proof is complete: You cannot achieve a social ordering of alternatives by simply aggregating all individual rankings without violating one of the 4 ideal conditions! (5 if you include transitivity.