Teaching Arrow's Impossibility Theorem

I regularly teach undergrads about Arrow’s impossibility theorem. In previous years, I’ve simply presented a statement of the theorem and provided a proof in the optional readings. Arrow’s proof is rather complicated; and while there are several simpler presentations of the proof, they are still too complicated for me to cover with philosophy undergraduates.

Preparing for class this year, I realized that, if Arrow’s theorem is slightly weakened, we can give a proof that is much easier to follow—the kind of proof I’m comfortable presenting to undergraduate philosophy majors. The point of the post today is to present that proof.

Stage Setting

Suppose that we have three voters, and they are voting on three options: $A, B,$ and $C$. The first voter prefers $A$ to $B$ to $C$. The second prefers $B$ to $C$ to $A$. The third prefers $C$ to $A$ to $B$. We can represent this with the following table. $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & B & C \\
2nd & B & C & A \\
3rd & C & A & B \end{array} $$ This table gives us a voter profile. In general, a voter profile is an indexed set of preference orderings, which I’ll denote with ‘$ \succeq_i$‘. (By the way, I’ll assume that, once we have a weak preference ordering $X \succeq_i Y$—read as “$Y$ is not preferred to $X$”—we can define up a strong preference ordering $X \succ_i Y$—read as “X is preferred to Y”—and an indifference relation $X \sim_i Y$—read as “$X$ and $Y$ are preferred equally”. We can accomplish this with the following stipulative defintions: $X \succ_i Y := X \succeq_i Y \wedge Y \not\succeq_i X$ and $X \sim_i Y := X \succeq_i Y \wedge Y \succeq_i X$.)

A social welfare function is a function from a voter profile, $\succeq_i$, to a group preference ordering, which I’ll denote with ‘$\succeq$‘.

$ \left [ \begin{array}{c} \succeq_1 \\
\succeq_2 \\
\vdots \\
\succeq_N \\
\end{array} \right ] \,\,\to \,\,\,\,\, \succeq $

(By the way, I’m going to assume throughout that, in order to count as a social welfare function, you must be well-defined for all voter profiles. I’ll also assume that $\succeq$ is a total pre-order—that is, I’ll assume that $\succeq$ is a transitive relation, and that, for any two options $X$ and $Y$, either $X \succeq Y$ or $Y \succeq X$.)

There are several ways of interpreting a social welfare function. If you think that an individual’s well-being is a function of how well satisfied their preferences are, and you think that how good things are overall is just a question of aggregating the well-being of all the individuals (this thesis is called welfarism), then you could think of the social welfare function as providing you with a betterness ordering. Alternatively, you could understand the social welfare function as a voting rule which tells you how to select between options, given the preferences of the voters. (For ease of exposition, I’ll run with this second interpretation throughout, though nothing hangs on this choice.)

Here are some features you might want a social welfare function to have: firstly, you don’t want it to privilege any option over any other. It should be the preferences of the voters which determines which option comes out on top and not the way those options happen to be labeled. So, if we were to re-label the options (holding fixed their position in every voter’s preference ordering), the group preference ordering determined by the social welfare function should be exactly the same—except, of course, that the options have now been re-labeled. Call this feature “Neutrality”.

Neutrality Re-labeling options does not affect where options end up in the group preference ordering.

Similarly, we don’t want the social welfare function to privilege any particular voter over any other. All voters should be treated equally. So, if we were to re-label the voters (holding fixed their preferences), this shouldn’t make any difference with respect to the group preference ordering. Let’s call this feature “Anonymity”.

Anonymity Re-labeling voters does not affect the group preference ordering.

Next: if all voters have exactly the same preference ordering, then this should become the group preference ordering. Let’s call this feature “Unanimity”.

Unanimity If all voters share the same preference ordering, then this is the group preference ordering.

And: if the only change to a voter profile is that one person has raised an option, $X$, in their individual preference ordering, this should not lead to $X$ being lowered in the group preference ordering. Let’s call this feature “Monotonicity”.

Monotonicity If one voter raises $X$ in their preference ordering, and nothing else about the voter profile changes, then $X$ is not lowered in the group preference ordering.

Finally, it would be nice if, in order to determine whether $X \succeq Y$, the social welfare function only had to consider each voter’s preferences between $X$ and $Y$. It shouldn’t have to consider where they rank options other than $X$ and $Y$—when it comes to deciding the group preference between $X$ and $Y$, those other options are irrelevant alternatives. Call this principle, then, the “Independence of Irrelevant Alternatives”, or just “IIA”.

Independence of Irrelevant Alternatives (IIA) How the group ranks $X$ and $Y$—i.e., whether $X \succeq Y$ and $Y \succeq X$—is determined entirely by each individual voter’s preferences between $X$ and $Y$. Changes in voters’ preferences which do not affect whether $X \succeq_i Y$ or $Y \succeq_i X$ do not affect whether $X \succeq Y$ or $Y \succeq X$.

What Arrow showed was that there is no social welfare function which satisfies all of these criteria. Actually, Arrow showed something slightly stronger—namely that there’s no social welfare function which satisfies Unanimity, Monotonicity, and IIA other than a dictatorial social welfare function. A dictatorial social welfare function just takes some voter’s preferences and makes them the group’s preferences, no matter the preferences of the other voters. Any dictatorial social welfare function will violate Anonymity, so our weaker impossibility result follows from Arrow’s. While this result is slightly weaker, Anonymity and Neutrality are still incredibly weak principles, and this result is much easier to prove.

The Proof

Here’s the general shape of the proof: we will assume that there is some social welfare function which satisfies Anonymity, Neutrality, Unanimity, and IIA, and, by reasoning about what this function must say about particular voter profiles, we will show that it must violate Monotonicity. This will show us that there is no voter profile which satisfies all of these criteria.

Let’s begin with the voter profile from above: $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & B & C \\
2nd & B & C & A \\
3rd & C & A & B \end{array} $$ Notice that the three options, $A$, $B$, and $C$, are perfectly symmetric in this voter profile. By re-labeling voters, we could have $C$ appear wherever $A$ does, $B$ appear wherever $C$ does, and $A$ appear wherever $B$ does. For instance: re-label voter 1 “voter 2”, re-label voter 2 “voter 3”, and re-label voter 3 “voter 1”, and you get the following voter profile, in which $A$ has taken the place of $B$, $B$ has taken the place of $C$, and $C$ has taken the place of $A$. $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & C & A & B \\
2nd & A & B & C \\
3rd & B & C & A \end{array} $$ By Anonymity, this makes no difference with respect to the group ordering. Note also that we may view this new voter profile as the result of re-labeling, not the voters, but rather the options (replacing $A$ with $C$, $B$ with $A$, and $C$ with $B$). Then, by Neutrality, after this re-labeling, $A$ must occupy the place of $B$ in the old group ordering, $B$ must occupy the place of $C$ in the old group ordering, and $C$ must occupy the place of $A$. Since the group ordering must also be unchanged (because of Anonymity), this means that the group ordering must be: $$ A \sim B \sim C $$ That is: the group must be indifferent between $A$, $B$, and $C$. (Call this “result #1”) This is exactly what we should expect, given the symmetry of the voter profile. There’s nothing that any option has to raise it above the others.

Now, suppose that, in our original voter profile, voters 1 and 3 change their minds, and they raise $B$ above $A$ in their preference ordering. And suppose that voter 2 raises $C$ above $B$ in their preference ordering. Then, the voter profile would change as shown: $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & B & C \\
2nd & B & C & A \\
3rd & C & A & B \end{array} \qquad \Longrightarrow \qquad \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & B & C & C \\
2nd & A & B & B \\
3rd & C & A & A \end{array} $$ Notice first that these changes didn’t affect any voter’s ranking between $A$ and $C$. Voter 1 prefers $A$ to $C$ both before and after the changes. And voters 2 and 3 prefer $C$ to $A$ both before and after the changes. Since $A \sim C$ before the changes (by result #1), IIA tells us that, after the changes, it is still the case that $A \sim C$. (Call this “result #2”.)

Notice also that everybody now ranks $B$ above $A$. So, from this voter profile, we could reach a unanimous voter profile in which everybody ranks $B$ above $A$ above $C$, by just having voters 2 and 3 lower $C$ to the bottom of their preference ranking. $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & B & C & C \\
2nd & A & B & B \\
3rd & C & A & A \end{array} \qquad \Longrightarrow \qquad \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & B & B & B \\
2nd & A & A & A \\
3rd & C & C & C \end{array} $$ By Unanimity, in the voter profile on the right, $B \succ A$. But, in moving from the voter profile on the left to the one on the right, we didn’t change anybody’s ranking of $A$ and $B$, so, by IIA, $B \succ A$ in the voter profile on the left, too. (Call this “result #3”)

Putting together result #2 and result #3, we have that, in this voter profile, $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & B & C & C \\
2nd & A & B & B \\
3rd & C & A & A \end{array} $$ $B \succ A \sim C$. Therefore, in this voter profile, $B \succ C$. Call this “result #4”.

Suppose that we begin with the voter profile immediately above, and voters 1 and 3 change their minds, raising $A$ above $B$, and leaving everything else unchanged. This gives us the voter profile on the right. $$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & B & C & C \\
2nd & A & B & B \\
3rd & C & A & A \end{array} \qquad \Longrightarrow \qquad \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & C & C \\
2nd & B & B & A \\
3rd & C & A & B \end{array} $$ This change does not affect anyone’s ranking of $B$ and $C$. Voter 1 prefers $B$ to $C$ both before and after the change. And voters 2 and 3 prefer $C$ to $B$ both before and after the change. Since $B \succ C$, given the voter profile on the left (this was result #4), we must have $B \succ C$ on the right, too. Call this “result #5”.

Now, watch this: consider these two voter profiles.
$$ \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & B & C \\
2nd & B & C & A \\
3rd & C & A & B \end{array} \qquad \Longrightarrow \qquad \begin{array}{l c c c} \text{Voter #} & 1 & 2 & 3 \\
1st & A & C & C \\
2nd & B & B & A \\
3rd & C & A & B \end{array} $$ The voter profile on the left is just our original voter profile. On the right is the voter profile from the right-hand-side of the paragraph immediately above. Result #1 tells us that, on the left, $B \sim C$. Result #5 tell us that, on the right, $B \succ C$. But notice that the only difference between the voter profile on the left and the one on the right is that voter 2 has raised $C$ in their preference ordering. Monotonicity tells us that this shouldn’t lower $C$ in the group preference ordering. So result #1 and result #5 together contradict Monotonicity.

So: any social welfare function which satisfies Anonymity, Neutrality, Unanimity, and IIA will end up violating Monotonicity. So there is no social welfare function which satisfies all of these criteria.