social choice theory

2019, Mar 28

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.

1. 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 \\\hline 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$’.

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.

2. 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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 \\\hline 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.

2017, Jun 25

The Impossibility of a Paretian Liberal

A foundational assumption in welfare economics is that, if everyone prefers A to B, then A is better than B. This normative claim is called the ‘weak Pareto principle’. At a first glance, this principle can appear unimpeachable. At the very least, it appears to be a sensible principle for policy makers to adopt.

Many of us are also committed to the principle that there are some choices that should be left up to the individual. Even if everyone else prefers that my nose be pierced, if I prefer it unpierced, then it is better for my nose to remain unpierced. A state-of-affairs in which I am compelled to pierce my nose, against my wishes, is worse than a state-of-affairs in which I get to make up my own mind about whether my nose is pierced. And that’s so no matter how many other people would prefer to see me with a pierced nose. Call this committment ‘minimal liberalism’.

In 1970, Amartya Sen produced an amazing result which seems to show that minimal liberalism and the weak Pareto principle are inconsistent with one another. Today I want to rehearse Sen’s result, and introduce an objection to Sen’s way of formalizing ‘minimal liberalism’ first made by Allan Gibbard. I think that Gibbard’s objection teaches us that Sen formulated liberalism incorrectly. However, I’ll conclude by showing that a better formulation of liberalism, one that avoids Gibbard’s objection, is also inconsistent with the weak Pareto principle.

The Impossibility of a Paretian Liberal, take 1

Sen’s result relies upon a formal framework in which we think of social goodness as determined by the preferences of the individuals living in a society. So we suppose that all the members of our society have their own preference ordering over state-of-affairs. Individual $i$ has the preference ordering $\succeq_i$. That’s a weak preference ordering; I’ll assume that we can get a strong perference ordering $\succ_i$ out of a weak one through the definition $A \succ_i B := A \succeq_i B \wedge B \not\succeq_i A$.

Given the preferences of every individual, $\succeq_i$, a social welfare function $W$ delivers a group preference ordering, $\succeq_G$, which tells us which states-of-affairs the group prefers to which other state-of-affairs.

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

An implicit normative assumption is that we may treat the group preference ordering as a betterness ordering. That is: if $A \succ_G B$, then $A$ is better than $B$. So we can think of the subscripted ‘$G$’ as standing either for ‘group’ or for ‘goodness’. (I’ll also assume throughout, by the way, that the social welfare function $W$ will always be defined, no matter which collection of individual preference orderings we hand it.)

Sen then interprets the weak Pareto principle and minimal liberalism in terms of this social welfare function. In these terms, the weal Pareto principle says that, if everyone prefers $A$ to $B$, then the group must prefer $A$ to $B$. And minimal liberalism says that every person is decisive with respect to some choice. That is: every person has at least one pair of options such that, whatever that person’s preferences are between those two options, that becomes the group’s preference. If I prefer my nose being pierced to my nose not being pierced, then that’s what the group prefers, too. And if I prefer my nose not being pierced to my nose being pierced, then that’s what the group prefers.

Weak Pareto Principle If $A \succ_i B$ for all $i$, then $A \succ_G B$.

Minimal Liberalism For all $i$, there is at least one pair of alternatives, $A$ and $B$, such that, if $A \succ_i B$, then $A \succ_G B$ and, if $B \succ_i A$, then $B \succ_G A$.

Sen additionally assumes that, if we’re going to interpret $\succeq_G$ as a social betterness ordering, then it had better not land us in cycles. That is, it had better not tell us that $A$ is better than $B$, $B$ is better than $C$, and $C$ is better than $A$.

No Cycles

There is no sequence of states-of-affairs $A_1, A_2, \dots, A_N$ such that $$ A_1 \succ_G A_2 \succ_G \dots \succ_G A_N \succ_G A_1 $$

Sen then proves that there is no social welfare function which satisfies Weak Pareto Principle, Minimal Liberalism, and No Cycles. I won’t go through the formal proof here; but I’ll go through a nice illustrative example from Sen (cultural references have been updated).

Prude is outraged and offended by Fifty Shades of Gray. Lewd, on the other hand, is delighted by the book. Prude would most prefer that nobody read the filth. However, if somebody must read it, Prude would rather read it himself than expose a libertine like Lewd to its influence. Lewd would most prefer that both he and Prude read the book. However, if only one of them is to read it, Lewd would rather it be Prude—he relishes the thought of Prude’s horrified reactions.

Thus, Prude and Lewd’s preference orderings are given in the following table.

For the purposes of illustration, suppose that Prude and Lewd are the only people in this society. And let’s suppose that whether you read a book is a matter which ought to be left up to the individual. If you prefer to read, then it’s better that you read; if you prefer to not read, then it’s better that you refrain. That’s all we need to bring out the conflict between Weak Pareto Principle, Minimal Liberalism, and No Cycles.

The only difference between $P$ and $N$ is whether Prude reads. It should be entirely up to Prude whether he read or not. Since he prefers to not read, Minimal Liberalism tells us that it is better if he doesn’t. So $$ N \succ_G P $$ Note that both Prude and Lewd prefer $P$ to $L$. So, by the Weak Pareto Principle, $$ P \succ_G L $$ And, the only difference between $L$ and $N$ is whether Lewd reads. It should be entirely up to Lewd whether he read or not. Since he prefers to read, Minimal Liberalism tells us that it is better if he does. So $$ L \succ_G N $$ But now we’ve violated No Cycles.
$$ N \succ_G P \succ_G L \succ_G N $$

So it seems that we face a choice: either reject the Weak Pareto Principle, or reject Minimal Liberalism. You can’t be both a Paretian and a liberal. If you want to be a liberal, you’d better reject the Weak Pareto principle.

The Impossibility of a Liberal?

Actually, matters are worse. Even rejecting the Weak Pareto Principle won’t get you out of trouble. Allan Gibbard showed that Minimal Liberalism leads to cycles all by itself, even without the Weak Pareto Principle.

Consider Match and Clash. Clash is a non-conformist. She would prefer having a pierced nose, but what’s most important to her is that her fashion be different from Match’s. So she wants to pierce her nose if (but only if) Match doesn’t pierce hers. Match is a follower. She doesn’t want to pierce her nose, but she does want her fashion to match Clash’s. So she wants to pierce her nose if (and only if) Clash pierces hers. Therefore, Clash and Match’s preferences are given by the following table.

For the purposes of illustration, let’s suppose that Match and Clash are the only people in this society. And Let’s suppose that whether your nose is pierced is the kind of thing which ought to be left up to the individual. If you prefer a pierced nose, then it’s better if your nose is pierced. And if you don’t, then it’s better if it’s not pierced.

Note that the only difference between $C$ and $N$ is whether Clash pierces. And Clash prefers $C$ to $N$. So the liberal says that $C$ is better than $N$. $$ C \succ_G N $$ The only difference between $N$ and $M$ is whether Match pierces. And Match prefers $N$ to $M$. So the liberal says that $N$ is better than $M$. $$ N \succ_G M $$ The only difference between $M$ and $B$ is whether Clash pierces. And Clash prefers $M$ to $B$. So the liberal says that $M$ is better than $B$. $$ M \succ_G B $$ And, finally, the only difference between $B$ and $C$ is whether Match pierces. Since Match prefers $B$ to $C$, the liberal says that $B$ is better than $C$. $$ B \succ_G C $$ But now we’ve contradicted No Cycles. $$ C \succ_G N \succ_G M \succ_G B \succ_G C $$ So Minimal Liberalism is inconsistent with No Cycles all by itself. We didn’t have to bring up the Weak Pareto Princple at all.

The Impossibility of a Paretian Liberal, take 2

Sen’s principle Minimal Liberalism assumes that the right way to think about liberalism is in terms of the decisiveness of individual preference. Sen’s liberal thinks that, if Prude prefers to not read, then it’s better if Prude not read (all else equal). And, if Lewd prefers to read, then it’s better if Lewd read (again, all else equal). What Gibbard’s case shows us, I think, is that this way of understanding liberalism is misguided.

And, in retrospect, we should recognize that we ought to have rejected Minimal Liberalism as a characterization of liberalism on independent grounds. Liberals think that certain self-regarding decisions should be left up to the individual. One of Mill’s arguments for this was that the individual is in a better position to know what’s best for them than the rest of society. However, Mill didn’t think that individuals were necessarily right about what’s in their own best interest.

Liberals should acknowledge that people can and do make self-regarding choices that make them worse off. A libertine liberal like Lewd will grant that what Prude reads should be left up to him. But that won’t keep Lewd from thinking that Prude’s diet of religious drivel is making his life worse. And surely Lewd should also think that, all else equal, it’s better for people’s lives to go better, and worse for them to go worse.

So the liberal shouldn’t think that, when it comes to self-regarding decisions, people’s actual preferences are objectively best. What they should think is that, when it comes to self-regarding decisions, it is better to allow people to choose for themselves than for the state to choose for them. That is: the liberal ought to think that, when it comes to self-regarding decisions, it is worse to deprive people of liberty than it is to allow them to make their own poor choices.

(At least, this is what a consequentialist liberal ought to think—though a non-consequentialist liberal is free to admit that things would be better if people were compelled to make the right choices, though such an arrangement would be unjust in spite of its betterness. I’m very sympathetic to this kind of position, but I’ll put it aside for the nonce.)

Our earlier discussion did not draw any distinction between possibilities in which people were forced to take certain options and those in which they freely chose those options. Let’s introduce this distinction, and use it to formulate our principle of liberalism.

Liberalism as Non-Compulsion does not fall prey to Gibbard-style objections. It is easy to see that the principle on its own could never give rise to cycles of betterness. The set of all possible states-of-affairs is partitioned by those in which all self-regarding choices are free and those in which some self-regarding choice is not free. And all Liberalism as Non-Compulsion says is that everything in the former set is better than everything in the latter set. On its own, this won’t lead to a cycle.

However, conjoined with the Weak Pareto Principle, this new principle of liberalism does run into cycles, in precisely the same way as before.

Let’s return to Sen’s example of Prude and Lewd. First, we’ll distinguish between those possibilities in which all choices are free and those possibilities in which some choices are compelled. We’ll subscript each of the previous states-of-affairs with an ‘$F$’ if they are states-of-affairs in which all choices are free and with a ‘$C$’ if it is a state-of-affairsin which people are compelled against their will to act in a certain way.

• $N_F$: Both Prude and Lewd freely choose to not read.
• $N_C$: Both Prude and Lewd are forced to not read.
• $L_F$: Lewd freely chooses to read and Prude freely chooses to not read.
• $L_C$: Lewd is forced to read, and Prude is forced to not read.
• $P_F$: Prude freely chooses to read and Lewd freely chooses to not read.
• $P_C$: Prude is forced to read and Lewd is forced to not read.
• $B_F$: Both Prude and Lewd freely choose to read.
• $B_C$: Both Prude and Lewd are forced to read.

Now suppose that, while both Prude values freedom—so that, all else equal, he would rather have Lewd and himself choose freely than be compelled—he values it less than he does keeping the filth of Fifty Shades from spreading. And, while Lewd values freedom—so that, all else equal, he would rather have Prude and himself choose freely than be compelled—he values it less than Prude’s disgust, and his delight, at the book’s depravity. So, if we ignore the subscripts, their preferences are the same as before, and otherwise, each of them prefers outcomes where choices are free.

Now, by Liberalism as Non-Compulsion, the outcome where Lewd freely chooses to read and Prude freely refrains is better than the outcome where Prude is forced to read and Lewd to refrain. $$ L_F \succ_G P_C
$$ But both Prude and Lewd prefer $P_C$ to $L_F$. So, by the Weak Pareto Principle, $$ P_C \succ_G L_F $$ And this contradicts No Cycles. $$ L_F \succ_G P_C \succ_G L_F $$

In sum: Gibbard showed us that we ought to reformulate Sen’s Minimal Liberalism. However, the best reformulation doesn’t get us out of the conflict with the Weak Pareto Principle. So the conflict is genuine. If you are a liberal, you cannot be a Paretian. If you are a liberal, you should deny that people’s preferences determine goodness in the way that Pareto imagined. If you are a Paretian, then you cannot be a liberal. If you are a Paretian, you should deny that it’s always best for self-regarding decisions to be left to the individual.