Proving Arrow’s Impossibility Theorem

Let’s prove, using colour coded diagrams to follow the argument visually, why group decisions, from democracy to take-away choice, are always flawed. You’ll get a taste of advanced mathematical reasoning, presented in an accessible way!

Primer

Arrow’s Theorem invites us to consider how to make a decision as a group, when people have different preferences. This can be described as a function; the input to the function is everyone’s preferences over the takeaway options, and the output of the function gives a group preference over the takeaway options. The function essentially tries to find represent a group’s preferences as an individual’s preferences. This is needed sometimes; for instance, it’s a massive pain to order take away from 10 different stores and pay 10 different delivery fees, so you want a way to map from everyone’s preferences to a group preference.

We want several properties to hold. If we decide, as a group, to pick A over B, and B over C, then we should pick A over C. (A bit like, if 5 is greater than 3 and 3 is greater than 1, then 5 is greater than 1). This is technically called ‘Transitivity’

We also want switching other preferences not to matter. Suppose everyone says which they prefer out of pizza or salad bar, and you make your decision. That decision shouldn’t depend on if Grandpa Joe suddenly changes his mind on whether he wants to get socks or oven gloves for christmas. This is technically called the ‘Independence of Irrelevant Alternatives’, or IIA for short.

We also want to respect unanimity. If everyone prefers salad to pizza, it’d be mad to say the group would rather get pizza. This is given the not-so-technical name of ‘Unanimity’.

We want our choice making procedure to be prepared for every eventuallity. This is technically called ‘unrestricted domain’

Finally, we don’t want it to be dictatorship. Little brother Joe shouldn’t get his way all the time on every decision because he has big cute eyes and cries when his Mom asks him to eat salad.

Arrow’s Theorem says that if there are more than two options, ‘Transitivity’, ‘IIA’, ‘unrestricted domain’ and ‘Unanimity’ hold, we are in a dictatorship. Sorry about that.

Definitions

A local dictator on (B,A) is someone where the following holds

Let’s just explain what my diagram says. The columns represent all the people. The choices are colour coded. The | is to make it clear who the person or people of interest are for a given manipulation. For each person, the letter on top is the one they prefer. We’ll normally only be examining cross sections fo a few of the options at a time, as this helps us wrap our heads around it, but with some magic will be enough to prove the Theorem.

A sub-dictator: Consider what happens when we hold one person’s preferences constant, and look how the social choice changes as we vary everyone elses. Perhaps Uncle Tim never changes his mind, but all the children change decision every few minutes and we have to recalculate every time they do so. Suppose Uncle Tim fixes his choice at preferring Salad over Pizza, and Pizza over Curry, but then, no matter what other people do, Joe gets his way now. Then Joe is a subdictator.

Step 1: More Is Better

This step is important, because it allows us to convert the extreme case to cover many cases. It basically says that, if we choose option B, and then more people change their mind to prefer B over A, or they previously preferred A and now they tie A and B, then we will pick B. In other words, More Is Better

Here we want to show that if choose B, and then some people switch to preferring B from preferring A or putting them as a tie, then we still choose A. I use | | to demarcate who switched, and I group them together so it is easier to see why the technique works. When you see AB next to each other, it means that that person has tied them.

What we are about to do is introduce a third option C. As our Group Choice has ‘Unrestricted domain’ (you might need to scroll up and check what that means), we can introduce C in a context of our choosing, and use our other properties to make deductions.

But this is a contradiction! Looking at the colour codings, we can see the C-B profile is the same in the last two preference profiles. Everyone who placed C above B before still places C above B. This contradicts IIA, as the same C-B profile gives a different choice in two different settings.

Step 2: a Local dictator on (A,B) implies a Global Dictator, ‘Local implies Global’

Suppose Pete is a local dictator on (A,B). Now take choices (E,F). We want to prove that Pete is a dictator on (E,F).

As Pete is local dictator on (A,B) we have:

Now consider an ordering which includes:

Observing F and E alone, we have an (E,F) dictatorship after using Step 1:

Below I formally extend this to all cases. You can read it, or skip it. The visual intuition above is the core of the argument.

The case for comparing (A,E) or (A,F) is a simple adjustment. To compare (A,E) for instance, remove F. This means we have a local dictator on all pairs (M,U), where M can be any policy except B, and U can be any policy except A. So we are nearly there!

If there are 4 or more policies, our new knowledge that they are dictator on (E,F), where E and F are neither A nor B allows us to use (E,F) dictatorship to prove dictatorship on the remaining cases. If there are three policies only, (A,B) dictatorship implies (C,B) dictatorship implies (C,A) dictatorship implies (B,A) dictatorship implies (B,C) dictatorship. As we can also get (A,C) dictatorship from (A,B) dictatorship, we have now covered every pair in the 3 policy case.

Step 3: A dictator in the case with N-1 players implies a local dictator in the case with N players

What does this mean? Suppose we knew the Theorem was true when there were only two players. Then we have a dictator in the N-1 = 2 case. Thus we have a local dictator in the N=3 case. From this we use step 2 (‘Local implies Global’ to show a global dictator in the N=3 case. And we continue like this upwards indefinitely, so we have shown it to be true for all possible cases!

For every preference profile the Nth player, Tim, can choose, holding his choice constant, we get a mapping from the remaining players’ choices to a preference ranking. (Recall, Tim makes his choice. Then all teh children keep changing their preferences, and we observe how our outputted group preference changed). Suppose that, for a function, there exists an (A,B) where player Tim is a local dictator. Then we are done, as we have a local Dictator.

Suppose instead there is no such case. Then each of the subfunctions defined for keeping the Tim’s choice constant fulfils the axioms. In particular, unanimity now holds, as if the the others agree that A is to be preferred to B, we have already assumed that Tim isn’t a local dictator, so Tim cannot veto them. Thus, for each subfunction, we have a global dictator.

Now, take a subfunction for a profile where the Nth Person ranks B above A.

Thus, this person is local dictator on (A,B), and by Lemma 2, she is Global Dictator.

And so we are done!! Either the function has the Nth person being a local dictator somewhere, which implies they are a Global Dictator, or someone of the other N-1 people can be shown to be a Local Dictator somewhere, and hence a Global Dictator.

Base Case

Remember we still needed to prove it was true with two players?

With two players we have a local dictator on (A,B) by virtue of there being only two of them. Thus we have a global dictator.

Some remaining thoughts…

Is Democracy/Take-Away Ordering/whatever doomed? The implications of Arrow’s Theorem

Not quite.

Arrow’s proof gives strict conditions for failure. In the real world, there are other considerations. After all, we might be able to compare across individuals: as Amartya Sen put it, Emperor Nero’s enjoyment from burning down Rome was less than the harm caused to the people of Rome.

Also, in real life, we aren’t looking for perfect — we want decision making procedures which can fudge their way through our messy world, generally do well and avoid peoples’ differences resulting in conflict. So, even if the Independence of Irrelevant Alternatives is occasionally, breached, it doesn’t matter that much!

Nevertheless, some implications are inescapable. If you are designing a voting system, you have a trade off between the consistency of people’s voting and having choice beyond two parties (or people). Sorry.

Remarks on the subtle relationship between mathematics and the real world

The genius of Kenneth Arrow’s Theorem is not actually the mathematics. The proof is hard, but not ridiculously so. In fact, I proved it over about 2 days in preparation for writing this essay, so can actually verify this. Arrow’s genius came in finding conditions which were both mathematically precise and also had a precise real world meaning. That’s what enabled me to explain a mathematical proof in terms of real-world things you understand, such as pizza choices.