Friday, July 16, 2010


Part Four: Collective Choice Theory

    Collective Choice Theory is the theory of how one selects a rule to go from a set of individual preference orders over alternatives available to a society of those individuals to a collective or social preference order over those same alternatives. [Or, as they say in the trade, how to "map a set of individual preference orders onto a social preference order."] There is a long history of debates about how to make social or collective decisions, going back at least two and a half millennia in the West. The simplest answer is to identify one person in the society and stipulate that his or her preference order will be the social preference order. L'etat, c'est moi, as Louis XIV is reputed to have said. A variant of this solution is the ancient Athenian practice of rotating political positions. One can also choose a person by lot whose preferences will thereupon become the social preference. A quite different method is that used by the old Polish parliament, which consisted of all the aristocrats in the country [there were quite a few, the entry conditions for being considered an aristocrat being low]. Since each of them thought of himself as answerable only to God, they imposed a condition of unanimity on themselves. If as few as one Polish aristocrat objected to a statute, it did not become law.

    These rules for mapping individual preference orders onto a social preference order, unattractive as they may be on other grounds, all have one very attractive feature in common: They guarantee that if all of the individual preference orders are ordinal orderings, which is to say if each of them is complete, reflexive, and transitive [you see, I told you we would use that stuff], then the social preference order will also be an ordinal ordering, and that is something you really, really want. You want it to be complete, so that it will tell you in each case how to choose. And you want it to be transitive, so that you do not get into a situation where your Collective Choice Rule tells the society to choose a over b, b over c, and c over a.

    To sum it all up in a phrase, the aim of Collective Choice Theory is to find a way of mapping minimally
rational individual preferences onto a minimally rational social preference.

    For the past several hundred years, everybody's favorite candidate for a Collective Choice Rule has been majority rule. This is a rule that says that the social preference between any two alternatives is to be decided by a vote of all those empowered to decide, with the alternative gaining a majority of the votes being preferred over the alternative gaining a minority of the votes. Should two alternatives, in a pairwise comparison, gain exactly the same number of votes, then the society is to be indifferent between the two.

         Enter the Marquis de Condorcet, who published an essay in 1785 called [in English] Essay on the Application of Analysis to the Probability of Majority Decisions. In this essay, Condorcet presented an example of a situation in which a group of voters, each of whom has perfectly rational preferences over a set of alternatives, will, by the application of majority rule, arrive at an inconsistent group or social preference. This is, to put it as mildly as I can, a tad embarrassing. Indeed, it calls into question the legitimacy of majority rule, which lies at the heart of every variant of democratic theory that had been put forward at that time, or indeed has been put forward since.

    Let us take a moment to set out the example and examine it. In its simplest form, it involves three voters, whom we shall call X, Y, and Z, and three alternatives, which we shall call a, b, and c. We may suppose that a, b, and c are three different tax plans, say. Let us now assume that the three voters have the following preferences over the set of alternatives S = (a, b, c).

    X prefers a to b and b to c. Since X is minimally rational, he also prefers a to c.

    Y prefers b to c and c to a. Since she is also minimally rational, she prefers b to a.

    Z prefers c to a and a to b. As rational as X and Y, she naturally prefers c to b.

    Now they take a series of pairwise votes to determine the collective or social preference order among the three alternatives. When they vote for a or b, X and Z vote for a, Y votes for b. Alternative a wins. When they vote for b or c, X and Y vote for b, Z votes for c, alternative b wins. Now, if the social ordering is to be transitive, then the society must prefer a to c. What happens when X, Y, and Z choose between a and c? X prefers a to c. But Y and Z both prefer c to a. So the society must, by majority rule, prefer c to a. Whoops. The society's preference order violates transitivity.

    And that is the whole story. The selection of a social or collective preference order by majority rule cannot guarantee the transitivity of the social preference order, and therefore does not even meet the most minimal test of rationality. There are, of course, lots and lots of sets of individual preference orders that generate a consistent social preference order when Majority Rule is applied to them. The problem is that here is at least one, and actually many more, that are turned by Majority Rule into an inconsistent preference order.

    If you have never encountered this paradox before [the so-called paradox of majority rule], you may be inclined to think that it is a trick or a scam or an illusion. Alas, not so. It is just as it appears. Majority Rule really is capable of generating an inconsistent social preference ordering.

    All of this was well known in the eighteenth century, and was, as we shall see later on, the subject of some imaginative elaboration by none other than the Reverend Dodgson, better known as Lewis Carroll. Enter now the young, brilliant economist Kenneth Arrow in the middle of the twentieth century. Coming out of a tradition of economic theorizing called Social Welfare Economics, to which a number of major figures, such as Abram Bergson, had contributed, Arrow conceived the idea of analyzing the underlying structure of the old Paradox of Majority Rule and generalizing it. The result, which he presented in his doctoral dissertation no less, was The General Possibility Theorem. Arrow published the theorem in 1951 in a monograph entitled Social Choice and Individual Values.

    Another great economist and fellow Nobel Prize winner, Amartya Sen, in 1970 published Collective Choice and Social Welfare, in which he generalized and extended Arrow's work in astonishing ways. Sen's book is difficult, but it is simply beautiful, and deeply satisfying. I strongly urge you, if you have a taste for this sort of thing, to tackle it. Sen has written widely and brilliantly on a host of extremely important social problems, including economic inequality, famine, and the demographic imbalance between men and women in the People's Republic of China. His little series of Radcliffe Lectures, published in 1973 as On Economic Inequality, is the finest use of formal methods to illuminate and analyze a social problem of which I am aware. It is a perfect example of the proper use of formal methods in social philosophy, and as such deserves your attention.

    In Collective Choice and Social Welfare, Sen gives a simpler and more elegant proof of Arrow's General Possibility Theorem. Nevertheless, I have chosen in this blog to expound Arrow's original proof. Let me explain why. It often happens that the first appearance of an important new theorem is somewhat clumsy, valid no doubt, but longer and more complicated than necessary. Later theorists refine it and simplify it until what took many pages can be demonstrated quickly in a few lines. Sometimes, this development is unambiguously better, but at other times, the original proof, clumsy though it may be, reveals the central idea more perspicuously than the later simplifications do. I find this to be true in the case of Arrow's theorem. Sen's simplification serves several purposes, not the least of which is to set things up formally for his extremely important extension and elaboration of Arrow's work. Therefore, I urge you to look at it, once you have worked with me through Arrow's original proof.

    Now let us begin. This is going to take a while, so settle down. Before we get into the weeds, let me try to explain in general terms what Arrow is doing. He asks, in effect, what are the underlying general assumptions of majoritarian decision making? What is it about voting with majority rule that appeals to us? He identifies five conditions or presuppositions [later reduced and simplified to four] that capture the logic of majority rule in a general way, and then shows that no way of making collective decisions that satisfies all four of them guarantees that the resulting social or collective choice will be consistent. This way of thinking about the problem accomplishes three things simultaneously. First, it unpacks majority rule voting into its component parts so that we can look at it and understand it better. Second, it generalizes the Paradox of Majority Rule so that we realize we cannot avoid it simply by tweaking Majority Rule a bit [for example by requiring a two-thirds majority.] And finally, it allows us to see just exactly what Majority Rule does not do -- in other words, it gives us insight into what would be totally different ways of making collective decisions.

    We start with a series of assumptions, definitions, and notational conventions, some of which are already familiar to you from the opening segments of this general tutorial. This is going to be tedious, but learning these up now will make it infinitely easier to follow the proof. Here they are:

(a) We start with a set of mutually exclusive alternatives, x, y, z, ..... These may be all of the possible candidates in an election [i,.e., every single person who is eligible to hold office under the rules governing the election], every possible tax scheme that might come before Congress, all of the various possible decisions a City Council might take concerning zoning regulations, and so forth. The point of the phrase "mutually exclusive" is to rule out, for example, "Obama" and "Obama or Clinton" as two of the available alternatives.

(b) On any give occasion when a decision is to be made, there is a subset, S, of the available alternatives, which will be called The Environment. This might be, for example, the relatively small number of people who have stated publicly that they would like to be elected to that office, or all the people who have formed campaign committees, or all the people who survive the primary season and are on the final ballot. Each of these is a subset of all the people eligible to hold the office [not necessarily a proper subset -- i.e., not necessarily smaller than the total set of alternatives. All that is required is that S be included in the set of all alternatives, not that it be smaller than that set].

(c) There is a set of individuals ["voters"], identified by numerical subscripts, 1, 2, 3, 4, ....

(d) Each individual is assumed to have a complete, transitive ranking of the entire set of alternatives, which we indicate using the notation introduced earlier -- the binary relations R, I, and P. Just to review, xRiy means that individual i considers alternative x to be as good as or better than alternative y. xPiy and xIiy are derived from R in the way indicated in the opening segments of this tutorial. What we are aiming for, of course, is a collective or social ranking, and that is indicated by the same letters, R, P, and I without the subscripts. So xPy means that the society prefers s to y. The whole point of this exercise is to start with complete, transitive individual rankings of the alternatives and then see whether there is any way of going from the individual rankings to a social ranking that satisfies certain conditions [see below] and results in a social ranking that is complete and transitive.

(e) Ri all by itself refers to individual i's ranking of the entire set of alternatives, x, y, z, .... Correspondingly, R all by itself refers to the society's ranking of the entire set of alternatives.

(f) We shall have occasion to refer to different possible rankings, by an individual i, of the set of alternatives. We will indicate these different rankings by superscripts. So, for example, Ri is one ranking by individual i of the entire set of alternatives. Ri' is a second ranking. Ri'' is a third ranking. And Ri* is a fourth ranking. A ranking Ri can be thought of either as a list showing the way individual i ranks the alternatives, including ties [indifference], or as a set of all the ordered pairs (x,y) such that xRiy.

(g) A Social Welfare Function [ an SWF ] is a function that maps sets of individual rankings onto a social ranking. Such a mapping function qualifies as an SWF just in case both the individual rankings, the Ri, and the social or collective ranking, R, satisfy Axioms I and II below -- which is to say, just in case the rankings, both individual and social, are complete and transitive.

(h) A Social Welfare Function is said to be Dictatorial if there is some individual i such that, for all x and y, xPiy implies xPy regardless of the orderings of all of the individuals other than i. Thus, in particular, to say that an SWF is dictatorial is to say that there is some individual who can impose his or her will on the society with regard to the choice between any pair, x and y, even if everyone else in the society has the opposite preference as between those two alternatives.

     (i) Finally, we define something called a Social Choice Function [ symbolized as C(S).] C(S) is the set of all alternatives x in the Environment S such that for every y in S, xRy. In other words, C(S) is the set of top alternatives or best alternatives in S. Quite often, C(S) will contain only one alternative, the one that the society prefers over all the others. But it may include more than one if the society is indifferent as among several best alternatives.

    Those are the nine definitions and stipulations. The key new ones that we have not met before are S, the set of available alternatives, R, the social ranking, SWF, a Social Welfare Function, and C(S), the Choice Function. Now Arrow lays down two Axioms governing the social ordering, R. These are:

Axiom I: For all x and y, xRy or yRx [Completeness]

Axiom II: For all x, y, and z, if xRy and yRz then xRz. [Transitivity]

    O.K. So much for the preliminary throat clearing. I want you to go over these definitions and stipulations until you are comfortable with them. The proof is going to be a formal argument couched in terms of these symbols and appealing to these assumptions and axioms. You will find it impossible to follow if you do not have a solid grasp on these preliminary definitions and so forth. While you are doing that, I want to talk for a bit about several important points that are implicit in what we have just laid down, but may not be obvious.


  1. C(S) is the set of all alternatives in the Environment S such that, for every x and y in S, xRy.

    This seems garbled. For one thing, nothing after the `such that' appears to depend on C(S) in any way. For another, the definition implies that everything is S is ranked as good or as better than everything in S, which rules out transitivity right off the bat.

    Perhaps it's supposed to be something like this: C(S) is a subset of the environment S such that, for every x in C(S) and y in S, xRy?

  2. Rats. yes, that is right. I will fix it right away. Sorry about that

  3. OK. I have changed it. Check it to make sure it makes sense now.

  4. For the second vote in the paradox, why is their preference about the ordering of {b,c} used to determine how they will vote? They already know that they have voted for a ahead of b. So, you would think that their second vote would be determined by their preferences between (a,b,c), (a,c,b), and (c,a,b). But you haven't said anything about their preferences between those.

    On a related note, why is preference only treated as a binary relation?

  5. There's a small typo where you introduce the Condorcet example:

    "X prefers a to be and b to c. Since X is minimally rational, he also prefers a to c."

    I had a double take there till I realised 'be' should be 'b'.

  6. Question (maybe this should be answered later): it seems from the kind of preferences needed for the paradox majority voting, the cardinality of S must be greater than 2. Could there be proof that when voting over two options, all of the population's preferences can map into a social preference order satisfying all of the desired axioms? I know that this case is so particular that it would rarely (never) apply, but it would be an interesting formal result nonetheless.

  7. Marinus, that is a really funny typo. I am almost tempted to leave it, but I guess I better fix it. Vlasits, you are of course correct. For the paradox, the number of alternatives must be greater than 2.

  8. What's a preference order? And how do I know that I have one? It's supposed to play a role in the rational decision making that I make: in my beliefs about what I should do, or what I shouldn't, if I am to be a rational agent. And, of course, I want to be a rational agent. Should I pay for the beer that I just bought at the bar, or not? Should I vote in the upcoming election, or not?