Welcome to NRICH.

 
Fair voting system
By Meretsky Meretsky on Thursday, May 23, 2002 - 09:53 am:

I am curious about any information regarding the difficulties(impossibilities) of devising a fair voting system.

By Dan Goodman on Thursday, May 23, 2002 - 11:41 am:

You're in luck, as it happens I've written an article about this for a non-mathematical website. It does include the mathematical details though. You can read it at http://www.bbc.co.uk/dna/h2g2/alabaster/A520372. I've copied and pasted it below as well. The formatting will work better if you follow the link. I should mention that since writing this article, I've found out that there are a wide range of cases in which voting does work, you could look up Black's Median Voter Theorem, and there's a theorem by Amartya Sen which is even stronger, but I can't remember the name at the moment.

Arrow's Possibility Theorem



In August 1950, Kenneth Arrow published a paper in The Journal of Political Economy proving a rather startling fact. Roughly, what he proved is that there is no perfect voting system. Of course, this is enormously important for democratic theory and economics, since it undermines the basis of representative democracy and free market economics. However, the theorem is little known and less understood by the majority of people, and this entry is intended to rectify that. The first two sections give an intuitive feel for Arrow's possibility theorem (little to no maths), the third section gives some discussion of the relevancy of the possibility theorem to the world, and the last three sections give a more precise, rigorous mathematical explanation. If you're not happy with maths, skip the last three sections. If you are happy with the maths, you can skip the intuitive discussion of the possibility theorem, because it is just the mathematical explanation with the maths taken out.

Historical Context

The Marquis de Condorcet (1743-1794) noticed, around 1785, that there was a paradox in the idea of voting. He posed the following problem: Suppose there are three citizens A, B and C and three policies which society could follow x, y and z. A prefers x to y and y to z. B prefers y to z and z to x. C prefers z to x and x to y. What policy should this society of three people enact? Two citizens (A and B) prefer y to z, but A and C prefer x to y. Confusingly, two citizens (B and C) also prefer z to x. So none of the policies x, y or z will do, since whichever one the society chooses, the majority of citizens will prefer a different one. Arrow's 1950 paper generalised this result and showed that whatever voting system you used, situations like this would arise. In fact, if you work through the proof of the theorem, this is basically how it works.

The Possibility Theorem - Intuitive

The situation to which the possibility theorem applies is when there is a society of citizens, a set of policies which they are going to vote on such that each citizen has certain preferences about the different policies. The simplest example is the case of a general election (or presidential election for Americans) where there are various candidates (these are the policies) standing for election and each citizen casts a vote for their preferred candidate (who they cast their vote for represents their preference). A social welfare function is a rule which gives us a "preference for society" based on the preferences of the citizens. For example, in the US and UK, we use a "first past the post" social welfare function, which says that "society prefers" policy x to policy y if more people voted for x than y.

We say that a social welfare function is imposed if the "preference for society" is the same whatever the preferences of the citizens are. For example, if we had a rule that said "the Liberal Democrats win whatever anyone votes for" then this would be an imposed social welfare function. We say that a social welfare function is dictatorial if the "preference for society" is chosen to be the preference of some particular citizen. For example, if we had a rule that said "Whoever Frank Bruno votes for wins the election", then this would be dictatorial.

There are three more conditions we need to impose on our social welfare function to make it meaningful. The first says that our social welfare function gives us a "preference for society" whatever the preferences of the citizens are. For example, a society which would only elect a party to power if everyone unanimously voted for them would not satisfy this condition, because unless everyone votes for the same party, nobody would be elected to power. The second condition is a bit more complicated to state, but is very important. Suppose that "society prefers" policy x to policy y. If policy x now increases in the estimation of one citizen and everyone else's preferences stay the same, then the second condition says that now our social welfare function should ensure that society still prefers x to y. For example, this condition is certainly true for our (UK and US) "first past the post" electoral system, because if the Republicans would be voted in and then one citizen who previously voted democrat changed his mind and voted Republican, the Republicans would still get in. Obviously a "perfect" voting system would have this property. The third and final condition on our social welfare function is even more complicated to state. It says, basically, that "society's preference" should stay the same if we rule out one of the policies. Again, this seems reasonable since it shouldn't change the election result if one of the candidates who didn't win dies before all the votes are counted up. This condition is called the "independence of irrelevant alternatives". Slightly more precisely, if "society prefers" policy x to policy y, and then we ignore policy z, then afterwards, society should still prefer policy x to policy y.

Finally, now that the definitions and conditions are out of the way, we can state the possibility theorem. It says that if we have a social welfare function satisfying the above conditions then it must be either imposed or dictatorial. In other words, there is no perfect voting system that works for societies of two or more people. This is truly amazing, since it means that just from the conditions given above on the social welfare function (all of which seem like they are "obviously true" for any decent social welfare function), we can deduce that there is no acceptable way, in general, to decide what society should do based on what the citizens of that society prefer!

Discussion

Does this mean that democracy is doomed and we should resign ourselves to anarchy or government by a tyrant? Well, not necessarily. Many democratic theorists think that this result is not as important as it seems at first. They have criticised it on, amongst others, the grounds that the "social welfare function" doesn't have to give a result whatever the preference relations of the citizens are. They argue that it is very unlikely that any society would be so diverse that any conceivable set of preference relations was possible. Moreover, it does not mean that we cannot do better than the current system, only that we can never get a perfect one. Many argue, for example, that the proportional representation method of voting (used in some countries in Europe) leads to a considerably more representative government than the first past the post system used in the US and the UK. Although a discussion of these is beyond the scope of this entry, the interested reader might enjoy The Proportional Representation Library which contains lots of discussion of this method of voting.

Note: skip the next three sections if you don't like mathematics.

Preference Relations

To understand Arrow's possibility theorem mathematically, we need to understand the (simple) mathematical idea of a "preference relation". We write xPy to mean "x is preferred to y". Here P is called the "preference relation". A preference relation must also satisfy the following condition (called transitivity): If xPy and yPz then xPz. All this says is that if someone prefers x to y and y to z then they will prefer x to z. Preference relations must also satisfy the condition (called anti-symmetry) that xPy and yPx cannot both be true. Again, this is obvious since it just says that one cannot prefer x to y and y to x. If neither xPy or yPx is true, then we say that we are indifferent between x and y, which we write xIy (I is called the the "indifference relation"). When economists say that people are "acting rationally", it means that their "preference relation" satisfies the conditions above (transitivity and anti-symmetry).

The Possibility Theorem - Precise

The possibility theorem assumes the following conditions. We have a society of citizens, C1, C2 and so on. There is a collection of policies, x1, x2, and so on. Each citizen has a preference relation P1, P2 and so on. A social welfare function is a rule which gives us a "preference for society" based on the preferences of the citizens. In other words, given the preference relations P1, P2 and so on, we get a new preference relation P. For example, in the US and UK, we use a "first past the post" social welfare function, which says that "society prefers" x to y if more people voted for x than y.

We say that a social welfare function is imposed if the "preference for society" is the same whatever the preferences of the citizens are. For example, if we had a rule that said "the Liberal Democrats win whatever anyone votes for" then this would be an imposed social welfare function. We say that a social welfare function is dictatorial if the "preference for society" is chosen to be the preference of some particular citizen. For example, if we had a rule that said "Whoever Frank Bruno votes for wins the election", then this would be dictatorial.

There are three more conditions we need to impose on our social welfare function to make it meaningful. The first says that our social welfare function gives us a "preference for society" whatever the preferences of the citizens are. For example, a society which would only elect a party to power if everyone unanimously voted for them would not satisfy this condition, because unless everyone votes for the same party, nobody would be elected to power. The second condition is a bit more complicated to state, but is very important. It says that if the "preference for society" P given by the preferences P1, etc. is such that xPy, then if one citizen (call him C1 to make it simple) changes their mind so that x increases in their estimation (i.e. if they change their mind to xP1y or xI1y from yP1x, or if they change their mind to xP1y from xI1y), but everyone else stays the same, then the "preference for society" P given by the new preferences still satisfies xPy. This sounds quite complicated, but all it means is that if a policy goes up in one person's estimation and everyone else stays the same, then the policy won't fall in the "estimation of society". This seems a perfectly reasonable condition to impose on our social welfare function, because we want to rule out social welfare functions which, for example, choose the least popular policy. The third and final condition on our social welfare function is even more complicated to state. It says, basically, that "society's preference" should stay the same if we rule out one of the policies (assuming that removing this policy doesn't change the citizen's preferences, which it might). Again, this seems reasonable since it shouldn't change the election result if one of the candidates who didn't win dies before all the votes are counted up. If you don't feel entirely comfortable with the idea of preference relations, ignore the next two sentences which express this third condition mathematically. The third condition, mathematically, says that if P1, P2, etc. and Q1, Q2, etc. are two different collections of preference relations for the citizens such that xP1y implies that xQ1y and xQ1y implies xP1y (and the same condition on P2, Q2, etc.), for all policies x and y part of some collection of policies S (a subset of all of the policies), then "society's preference relation" P given by the P's and Q given by the Q's is the same for policies which are in the collection S. In other words, if x and y are policies part of S, then xPy implies xQy and xQy implies xPy.

Finally, now that the definitions and conditions are out of the way, we can state the possibility theorem. It says that if we have a social welfare function satisfying the above conditions then it must be either imposed or dictatorial. This is truly amazing, since it means that just from the conditions given above on the social welfare function (all of which seem like they are "obviously true" for any decent social welfare function), we can deduce that there is no acceptable way, in general, to decide what society should do based on what the citizens of that society prefer!

Proof of the Possibility Theorem

The proof of the Possibility Theorem is necessarily quite technical, even those reasonably comfortable with maths might find it hard going. However, it is included here for completeness. You'll lose nothing by skipping this section. With that said, let us continue.

First of all, we introduce a couple of new relations. We've already mentioned the indifference relation I and the preference relation P, it remains to introduce a new relation R, the "preferred or indifferent" relation. This is defined as xRy if xPy or xIy. In other words, xRy unless yPx, or x is preferred to or indifferent to y if y is not preferred to x. The axioms on P being a preference relation now immediately turn into properties of R: (1) for all x,y, we have xRy or yRx, and (2) for all x,y,z, if xRy and yRz then xRz (i.e. R is transitive).

Some simple consequences follow from easy manipulations or just from translating the statements into sentences and considering what they mean: (a) For all x, xRx, (b) If xPy then xRy, (c) For all x,y either xRy or yPx, (d) If xPy and yRz then xPz.

We define Pi, Ri and Ii to be the relations for citizen Ci. Also, when P, R or I is written, this indicates the preference for society obtained from the social welfare function. The proof of the theorem proceeds by assuming that the social welfare function is neither imposed nor dictatorial, from which is derived a contradiction, proving that any social welfare function satisfying the first three conditions is either imposed or dictatorial.

We need only consider the case when there are two individuals in our society and three alternatives, the general result follows easily from this (basically, we can restrict the social welfare function for a society of more people than this to a social welfare function for a society of just two people and three policies - if there was a social welfare function for a larger society it would imply that there was one for our baby society of two individuals and three policies, which would be a contradiction). So from now, there are two individuals C1 and C2 and three policies x, y and z, we will also write x' and y' for variables representing policies, i.e. each of x' and y' could be any of x, y or z.

Result 1 - If x'P1y' and x'P2y' then x'Py'. This should be obvious because both individuals prefer x' to y', but it does require proving. The proof is omitted as it is intuitively obvious and little understanding is gained from the proof.

Result 2 - Suppose that for some x' and y', whenever x'P1y' and y'P2x' we have x'Py'. Then, for that x' and y', whenever x'P1y' we have x'Py'. This again seems obvious, because the condition says that C1's will prevails over C2's will as far as x' and y' are concerned, so if C2 now becomes indifferent between x' and y' or agrees with C1, then the social preference will remain the same. Again, intuitively obvious but requires a proof (omitted).

Result 3 - If x'P1y' and y'P2x' then x'Iy'. In other words, if the two citizens have exactly opposite interests then society cannot favour the will of one person over the will of another. The proof of this (omitted) follows using the previous results and demonstrating that one or the other of C1 and C2 must be a dictator, which is not allowed by our assumptions.

Now suppose that C1 has the ordering x,y,z (i.e. xP1y, xP1z, yP1z, etc.) and C2 has the ordering z,x,y. From result 1, we see that xPy (since C1 and C2 both prefer x to y). From result 3 we have yIz (since yP1z and zP2y). From xPy and yIz we have xPz (just using the fact that P is a preference relation). However, we also know that xIz by result 3 (since xP1z and zP2x). This is a contradiction, because xPz and xIz cannot both happen (as P is a preference relation). The required contradiction gives us the proof of the Possibility Theorem.

For those interested in the complete proof of the theorem or who would like some very interesting further discussion, I recommend the original paper which is no more difficult to understand than this entry, possibly even easier as Kenneth Arrow is a very lucid writer. The original paper is entitled "A Difficulty in the Concept of Social Welfare" and can be found in The Journal of Political Economy, Volume 58, Issue 4 (August, 1950), pages 328-346.