Arrow's Impossibility Theorem

Social Welfare Functions

We should look at an example to get a more clear idea about what is going on.  Suppose that we have three agents, Bart, Lisa, and Maggie.  Suppose further that there are three consequences, and that the three agents have ordered the consequences according to their own preferences.
 

In the table, for example, Bart's favorite consequence is c₁, followed by c₂, followed by c₃.  A social welfare function takes these preferences and creates an ordering for the entire society.  One possible ordering is that society prefers c₁ to c₂, and c₂ to c₃ (since two out of three agents have these preferences).  Then the preferences for each agent stay the same, but the preference for society is given by

We have constructed this social welfare function by balancing Bart's preferences with Lisa's, Lisa's with Maggie's, and Maggie's with Bart's.

If actions are involved and if society has the power to enforce its preferences than Bart, Lisa, and Maggie must choose actions the generate consequence c₁.  In a way, society dictates what each agent should do.  This kind of feels funny to us because we like to think that we each can choose what we like.  We often don't like it when society (via the government, for example) tells us what to do, but it gets worse.  We are going to list a bunch of properties that any fair social welfare function should satisfy, perhaps one of the most desirable is that no individual should be able to dictate what is good for all of society.  What we'll find out is that we cannot simultaneoutly satisfy all of the properties because the properties cause our social welfare function to be dictated by a single individual.

It is important to be clear about what a social welfare function must do.  It must be able to look at the individual preference pattern for each individual, and combine the individual preference patterns into a preference pattern for society.  To get an idea of the complexity of defining such a social welfare function, consider Table 1.  This table represents a tiny portion of the social welfare function.  The table only tells us what the preference pattern for society is when Bart likes c1>c2>c3, Lisa likes c2>c1>c3, and Maggie likes c1>c3>c2.   The complete social welfare function will include another table for when Bart likes c1>c2>c3 and Lisa likes c2>c1>c3, but Maggie likes c1>c2>c3. 

Since, for three choices {c1,c2,c3}, there are 6 possible preference patterns for each individual, there are a toal of 6*6*6 possible tables of preference patterns like Table 1, and the social welfare function must unambiguously define the preference pattern for society for each of the 6*6*6 possible combinations of individual preference patterns.

We will use the term profile to mean a particular set of individual preference patterns.  So, Table 1 is one particular profile from the set of 6*6*6 possible profiles.

Desirable Properties of a Social Welfare Function

1. This first condition restricts the nature of the social preference structure.
1. The social preference ordering that results from applying the social welfare function should be defined for every pair of consequences.
2. The social preference ordering that results from applying the social welfare function should be transitive; i.e., xPy & yPz ==> xPz.
2. This condition deals with the size of societies, the domain of social welfare functions, and the number of consequences.
1. The number of elements in the set of consequences is greater than or equal to three.  C = the set of choices, so |C|>=3;
   
2. There are at least two agents in our society.  M denotes the set of all agents, so |M|>=2;
   
3. The social welfare function F is defined for all possible profiles of individual orderings.
3. (This condition is known as the positive association of social and individual values.) If an individual promotes (makes more preferred than it used to be) a consequence c_i then the social preference has the following characteristic:
1. For any pair of consequences c_k and c_m where c_k is socially preferred to c_m (k and m different from i) before c_i is promoted by an individual, then c_k is still socially preferred to c_m after the promotion.
2. Any social preference ordering that compares c_i with any other alternative either remains unchanged or is changed in favor of c_i; for example, if c_i is socially preferred to c_k before the an individual promotes c_i, then c_i cannot be less socially preferred than c_k after the promotion.
4. (This condition is known as the independence of irrelevant alternatives.)  Consider a set of consequences C1 that is a subset of a larger set of consequences C.  Suppose that I ignore the larger set of consequences for a minute, and ask each agent to create an ordering over the elements of C1.  I then apply my social welfare function and generate a preference pattern for society as a whole.  Suppose that I then include a consequence c_k that is in C but not in C1 and ask each agent to put c_k in its proper place in the preference ordering.  (This keeps the relative (pairwise) orderings of elements in C1 constant.) The ordering imposed by the social welfare function when it acts on the new set created from the union of C1 with {c_k} should make sure that the pairwise orderings of C1 do not change.
5. (This condition is known as citizen's sovereignty.)  For each pair of alternatives c_i and c_j, there is some profile of individual orderings such that society prefers c_i to c_j.
6. (This condition is known as non-dictatorship.)  There is no individual agent with the property that whenever he or she prefers c_i to c_j (for any c_i and c_j) society does likewise, regardless of the preferences of other individuals.  This just means that a single individual cannot determine society's preferences no matter what others think.

Let's begin by talking about property 3 --- the positive association of social and individual values.  Let's return to our example in Table 1, but we'll "promote" c₂ such that it is more desirable.

The only difference between Table 1 and Table 2 is that Maggie now prefers c₂ to c₃ (Maggie promoted c₂).  Since society preferred c₂ to c₃ before c₂ was promoted, it better still prefer c₂ to c₃.

Now, let's turn to property 4 --- the independence of irrelevant alternatives.  The best way to illustrate this is to use an example of when it is violated.  Suppose that the consequences of the game are potential presidents: Bush, Gore, and Nader.  Suppose that rather than having a one-vote per person distribution, we instead give N points to the top choice of the individual, N-1 to the next choice, and so on, where N is the number of candidates.  We then add up the total points for each candidate, and the candidate with the highest number of points wins.
 

Now suppose that we introduce a new candidate: Buchanan.  We use the same scoring scheme as before, but include Buchanan in the mix.
 
 

Notice how Buchanan, the least popular candidate according to the table, tilted the vote in Gore's favor.  Property 4 states that we don't want this irrelevant alternative to affect the social choice.

The Impossibility Theorem

• Example 1:
• Bart: c1>c2>c3
• Lisa: c1>c3>c2
• Maggie: c3>c2>c1
• Society must have c1>c2 since Bart and Lisa are decisive for c1 over c2 AND since both Bart and Lisa have c1>c2.  Thus, the preference pattern for society can only be one of the following (decisiveness doesn't tell us which one):
• c1>c2>c3
• c1>c3>c2
• c3>c1>c2
• Example 2:
• Bart: c1>c2>c3
• Lisa: c2>c1>c3
• Maggie: c1>c2>c3
• Society need not have c1>c2.  Bart and Lisa are decisive for c1 over c2, but since Lisa prefers c2 over c1 we cannot make any conclusion about how society feels about c1 and c2 using only decisiveness.  Note further that both Bart and Lisa like c1 over c3, but this doesn't help us.  Since Bart and Lisa are not decisive for c1 over c3, it is possible for society to have c3>c1.
  

Pareto Optimality Theorem: The set of all individuals is decisive for every ordered pair (c₁,c₂).  In other words, if each individual prefers c₁ to c₂ then so does society.

It is useful to make one statement about how this proof would proceed.  Note that we cannot prove the Pareto Optimality Theorem using property 5 (citizen's sovereignty) alone.  All that citizen's sovereignty guarantees us is that, for a given pair of choices c1 and c2,  there is some set of individual profiles that will make society like c1 more than c2.  Returning to the three agent problem wtih Bart, Lisa, and Maggie, it may be that the precise set of profiles for which the social welfare function concludes c1>c2 is for Bart, Lisa, and Maggie to all express c3>c2>c1.  However, when we combine citizen's sovereignth with the positive association of social and individual values, we see that if everyone likes c1>c2 than so will society.

We now move to a useful equivalence.  This equivalence is the key to the proof so take some time to understand it.

Decisiveness Lemma: Assume condition 3.  A set S is decisive for (c₁,c₂) if and only if the following holds: society prefers c₁ to c₂ when all of the members of S prefer c₁ to c₂  and all other agents prefer c₂ to c₁.
Proof:  Since this is a standard if and only if proof, we'll take the standard approach.  We'll begin by showing that if a set S is decisive for (c₁,c₂) then society prefers c₁ to c₂ when all of the members of S prefer c₁ to c₂  and all other agents prefer c₂ to c₁.  Since, by the definition of decisiveness, the opinions of agents not in S have no influence over society's preference, it follows as a special case that when all members of S prefer c₁ to c₂  and all other agents prefer c₂ to c₁ then society prefers c₁ to c₂.

We'll now show that if society prefers c₁ to c₂ when all of the members of S prefer c₁ to c₂  and all other agents prefer c₂ to c₁, then set S is decisive for (c₁,c₂).  Every agent not in S prefers c₂ to c₁, so any changes in the individual preferences between these two consequences must promote c₁.  But, by property 3, society must still prefer c₁ to c₂.  This means that no matter what agents not in S have to say, society still prefers c₁ to c₂ which means that the set S is decisive for (c₁,c₂).
Q.E.D.

Before we move onto the main theorem, we should probably talk about what this decisiveness lemma says.  Observe that decisiveness is a characteristic of the social welfare function itself and does not indicate anything about any individual agent's profile.  This means that if I am given the decisiveness property then the individuals in the decisive set can impose their will if they have the same preferences, but it does not mean that they will impose their will.  It is a statement of the potential for a group to impose their will if they choose to.

The first direction in the lemma says that if there is a decisive set then the agents in a decisive set can impose their preference pattern even if all other agents hold the exact opposite point of view; we get this just by the definition of decisiveness. 

The second direction is the more powerful direction.  It says that whenever we can show (a) society prefers c₁ to c₂, (b) a set S prefers c₁ to c₂, and (c) agents not in S prefer c₂ to c₁, then we can conclude that S is decisive for c₁ for c₂.  Let's be a bit more concrete about this.  Suppose that I have three agents, {Bart, Lisa, and Maggie}, and three choices, {c1,c2,c3}.  We have previously shown that the social welfare function for such a problem consists of 6*6*6 tables, one for each of the possible preference orderings of the agents.  Each of these tables shows what society would like if the agents had the preferences given in the table; it does not necessarily mean that the agents actually feel that way, just that if they did then we would know how society would order the choices.  Suppose that I start searching through the tables and found one table where (a) Bart and Lisa liked c1 more than c2, (b) Maggie liked c2 more than c1, and (c) society liked c1 more than c2.  By the decisiveness lemma, I would conclude that Bart and Lisa are decisive for c1 over c2, which means that I could conclude that every other table in which Bart and Lisa both had c1>c2 would imply that society also had c1>c2.  From that one table, I can conclude something about the social welfare function and, consequently, about a whole bunch of other tables in the definition of that function.

Thus, the second direction of the theorem means that if I can show that the social welfare function produces a social preference ordering that agrees with the preferences from a particular group even when everyone else disagrees, then I can say that that group is decisive.  Let me illustrate again using a slightly more abstract example.  In this example, there are three choices {A,B,C} and two groups (of possibly very many agents}, {S,T}.  Suppose that while I am searching through the definition of the social welfare function, I observe the following table: 

Note how S prefers A to B, T prefers B to A, and Society prefers A to B.  From this table alone and from the lemma we can conclude that S is decisive for A against B.  This means that I know that if I was considering a table where S liked A>B then I would be abel to conclude that society would also have A>B.

Arrow's Impossibility Theorem:  There does not exist a welfare function which possess the properties demanded by these conditions.  More specifically, if conditions 1 through 5 are satisfied then there exists an individual (a dictator) who is decisive for every ordered pair of alternatives.
Proof: We'll do this proof in eight steps.  There will be several mini-proofs and examples within the proof, so be careful to not lose the main thread of the proof.

• We'll begin by talking about a minimal decisive set.  A minimal decisive set is a set S that is decisive for some c₁ against c₂, whereas no proper subset of S is decisive for any ordered pair of alternatives.  We want to show that such a set exists and that it is not the empty set.  Note that saying that a minimal decisive set exists does not say anything about the preferences of the individuals in the society; it only says that if all individuals in S prefer c₁ to c₂, then so does society.  Thus, the definition of a minimal decisive set takes into consideration all possible preference patterns of the individuals, and finds the smallest set such that whenever all individuals in this set prefer c₁ to c₂ then so does society.

1. Lemma 1: A minimal decisive set exists: Proof:  By the Pareto Optimality Theorem, the set M of all individuals is decisive.  Individuals can be removed one at a time from M until the remaining set S' is no longer decisive for any pair.   S can be constructed from S' by adding the last individual removed.
2. Lemma 2: The minimal decisive set is not empty:Proof:  Suppose that the minimal decisive set S is empty.  To say that S is empty means that neither M nor any subset of M is decisive (by existence), but we already know that M is decisive.  This is a contradiction, so S cannot be empty.
3. Interpreting the meaning of the minimal decisive set.  Most people in previous semesters have had to wrestle with the meaning of this lemma.  It is helpful to look at some pseudo-code to see what it means and does not mean.  I claim that the following pseudo-code will find the minimally decisive set.  Recall that M denotes the set of all agents.  Let C be the set of all choices.  Let |M|>=2 denote the size of the society and |C|>=3 denote that number of choices.  The power set of M will be denoted 2^M.  Assume without loss of generality that 2^M is ordered from smallest to biggest.
   

• We'll now introduce some notation, and consider a special preference pattern.  Let j be a specific individual in S, T the remaining individuals in S (T=S-{j}), and R the set of all individuals not in S (R=M-S).  Since |M| (the number of individuals in the set M)  is greater than or equal to two by property 2.2, it follows that R and T may not both be empty.  Let c₁ and c₂ denote the alternatives that S is decisive for, and let z represent any third alternative that differs from both c1 and c2.  Consider the following profile of preference orderings. Notice that we intelligently chose one of the possible profiles that must be listed in the collection of tables that define our social welfare function.  We chose this profile because it allows us to apply the decisiveness lemma and make some conclusions about the social welfare function.  Note that we can ignore all other alternatives except c1, c2, and z by the independence of irrelevant alternatives property.
  

Table 3: A Pattern of Preferences (Profile) for Society M

	{j}	T	R
top	c1	z	c2
middle	c2	c1	z
bottom	z	c2	c1

• We now want to think about what happens when we apply the fact that S (={j}+T) is the minimal decisive set (decisive for  (c₁,c₂)) to this preference pattern.  Since S is decisive for  (c₁,c₂) and since all individuals i in the decisive sub-society (i.e., both j and all members of T) prefer c₁ to c₂, it follows that society prefers c₁ to c₂; i.e., c₁Pc₂, (or c₁ > c₂) where P indicates the preference pattern for society. Thus, if the individuals in S hold this preference pattern then so does society.
• Let's now try to figure out how society feels about z.  Suppose that society preferred z to c₂.  Since only individuals in T hold this preference pattern, if z is preferred to c₂ it follows from the decisiveness lemma that T is decisive for (z,c₂).  Since S is the minimal decisive set (think of the psuedo-code which returned the smallest possible decisive set) and since T is a proper subset of S, it follows that society does not prefer z to c₂; i.e., zPc₂ is false.  This is the same as saying that c₂ must be at least as preferred as z; i.e., c₂>~z.
• Putting these pieces together, if the preferences in Table 3 hold then we know that c₁>c₂ and c₂>~z, which means that c₁>z; i.e., if this preference pattern holds then society prefers c₁ to z.
• But j is the only individual that prefers c₁ to z, so it follows from the decisiveness lemma that {j} is decisive for c₁ against z.  But, by definition, {j} is an individual from S and S is the minimally decisive set.  The only way these two facts can both be true  is if S={j} and T is empty.  This means that the pseudo code must of necessity return a singleton if the social welfare function satisfies all of Arrow's desirable properties.
  

• We now want to find out what kind of power this peculiar individual {j} has on the entire society.  We are going to show that this individual is a dictator.  Notice that z is an arbitrary alternative, so it follows that {j} is decisive for c₁ against any z different from c₁.   This means that if {j} is decisive for the special case for c₁ against any c₂ then it is also decisive for c₁ against any z.
  
• To show that j is a dictator, we need to show that when we pick any w different from c₁ then when j prefers w to c₁ or j prefers w to z then so does society; i.e., for w!=c₁, if j prefers w to c₁ then wPc₁ and if j prefers w to z then wPz.  Let's look at a profile of preference patterns again.  Once again, we intelligently chose a profile from the set of tables that define our social welfare function.  We'll do this in two parts (i.e., for two profiles).  Note that for both profiles we can ignore T since it is the empty set.
• Consider the profile of preferences for society M shown in Table 4 where w!=c₁.  By the Pareto Optimality Theorem, wPc₁ and, since {j} is decisive for c₁ against z, c₁Pz.  By transitivity, it follows that wPz.  But clearly R prefers z to w, so once again j has imposed its will on society and, by the decisiveness lemma, is decisive for w against z.  This means that whenever j prefers w to z (for z not equal to c₁) then so does society.

 

Table 4: A Pattern of Preferences (Profile) for Society M

	{j}	R
top	w	z
middle	c1	w
bottom	z	c1


 
• Let's now turn to the other thing we wanted to prove, and that is whenever j prefers w to c₁ then so does society.  We will do this by considering a pattern of preferences where j prefers w to c₁ but the rest of society does not.  Such a preference profile is shown in Table 5.  I already know that j is decisive for w against z so wPz.  Looking at the profiles I see that both j and R prefer z over c₁ so zPc₁.  By transitivity, it follows that wPc₁.  But j is the only member of society who prefers w to c₁ so, by the decisiveness lemma, j is decisive for w against c₁ which was what we set out to show.
 

Table 5: A Pattern of Preferences for Society M

	{j}	R
top	w	z
middle	z	c1
bottom	c1	w

• Let's now wrap up our proof.  We first showed that, for a society who made choices according to a social welfare function that satisfied properties 2-5, the minimal decisive set was a singleton.  We then looked at what would happen when this member of society preferred an arbitrary action over any other arbitrary action, and found out that society copied this preference.  This leads us to the conclusion that this individual was a dictator.  But this, in turn, implies that the six desirable properties of a social welfare function are inconsistent.  Our proof is done.