A Social Choice Algorithm

Abstract

This paper presents an algorithm which represents a social welfare function that maps the domain of all possible combinations of individual choices into corresponding social choices. By means of a proper treatment of tie solutions, Condorcet’s method of determining the outcome of an election is extended to cases that have previously produced a “paradox of voting.”

Our method is based on pairwise comparisons of candidates by voters and meets Arrow’s five criteria and his axioms 1 and 2. Therefore, we have discovered a method which resolves the paradox of voting and extends to many other cases a generalized Condorcet solution.

Solutions for all cases involving the R (preference or indifference) operator are worked out for m (number of alternatives) = 3. This paper lays the groundwork. A companion paper defines the algorithm in complete detail and proves that it provides viable solutions in every case.

Introduction

In 1785 The Marquis de Condorcet (Granger [1989], McLean and Hewitt [1994]) published his Essai (1785) in which he pointed out the problems associated with an election in which there are three or more candidates. This has become known as the paradox of voting. Condorcet and the American President, Thomas Jefferson, were collaborators in the production of both the French and American Constitutions. Condorcet lost his life in the French Revolution because he left his secure hiding place when he learned that his host was subject to the death penalty for harboring him. He was preceded in the theory of elections by a few years by his friend Jean-Charles de Borda (1781) who proposed the rank-order count method of voting. The French Enlightenment philosophers hoped to “carry the methods of rigorous and mathematical thought beyond the physical and into the realms of the human sciences.” (Black[1958])

Over the years there have been various writers that have contributed to the theory of elections including E. J. Nanson (1907) and the Reverend C. L. Dodgson (Lewis Carroll) (1873, 1874, 1876). In 1951 Nobel Laureate Kenneth J. Arrow published Social Choice and Individual Values in which he explored the question of whether or not individual preferences could be aggregated in some rational way in order to form a social choice. He postulated five rational and ethical criteria and two axioms that such a social welfare function should meet, and then proceeded to prove that no such social welfare function existed. This theorem is known as Arrow's Impossibility Theorem, and an impressive literature concerning itself with what has come to be known as Social Choice theory has developed in the last  forty -six years. At least one author considers that Arrow's Theorem “has a good claim to be considered the outstanding problem in the philosophy of economics” (MacKay [1980]).

Some of the literature has been concerned with finding a way around Arrow's basic result that no rational social choice is possible by relaxing one or more of his criteria (Sen [1970], Riley [1988], Murakami [1968]). Arrow's theorem has important political, economic and social implications since, if indeed no rational way to aggregate individual preferences is possible and Pareto optimality is the best that can be achieved, then a populist democracy which closely reflects the will of the people becomes impossible and free market capitalism acquires a theoretically endorsed superiority over any kind of populist socialistic or democratic economic system. Liberal or Madisonian democracy in which the purpose of voting is just to elect leaders and lawmakers becomes all that is attainable while populist or direct democracy in which social policies are decided upon directly by voting becomes theoretically unfeasible. The notion of electronic democracy in which voters vote directly on issues from computer terminals and then supercomputers tally the results [what might be called an Information Age Utopia] is not theoretically acceptable. These realizations have produced pessimism and even nihilism among proponents of welfare economics (Bergson, 1966). However, advocates of democratic voting systems should be equally concerned as Arrow's result tarnishes the validity of democratic elections as well (Riker [1982], Schofield [1985]).

In this paper we will present an algorithm which provides a solution for the social choice problem for any number of alternatives without diluting Arrow's five criteria and two axioms for social choice. In fact we strengthen them considerably. We also give a more rigorous statement of those criteria. In the companion paper, Proving Social Choice Possiblee, we prove that the algorithm works for all values of m, the number of alternatives and for any number of voters, n. Our method is ordinal (rather than cardinal), based on pair-wise comparisons and independent of irrelevant alternatives. It is shown in this paper that the key to opening the door of social choice is the proper consideration of tie solutions.

Notation

We follow conventional notation. Let us assume that we have a society composed of n voters. For identification purposes, we can number them from 1 to n, 1< i ≤ n. We will refer to the ith individual. We assume an alternative set, S, consisting of m alternatives: a, b, c... . Let the set {x1, x2...xm} consist of some permutation of the alternative set {a,b,c...}. Arrow uses an R notation, which we will follow, which means “is preferred or is indifferent to.” To indicate that voter i prefers a to b or is indifferent between a and b, we would write aRib. We assume that each voter has a “preference or indifference” relationship, Ri, over the alternative set as follows:

Ri = xi1Rixi2Ri...xim-1Ri xim
where
		xik represents the kth “preference or indifference” of the ith voter. 

We will use a shorthand notation as follows: abcd for aRib Ric Rid.

The Social Welfare Function

A function is a mapping from a set of elements known as the domain to a set of elements known as the range in such a way that each element of the domain is connected with not more than one element of the range. Now the mapping from domain to range can be in such a way that for every element of the range there is at most one corresponding element of the domain (one-to-one or injective); for every element of the range there is one or more corresponding elements of the domain (onto or surjective) or for every element of the range there is one and only one corresponding element of the domain (one-to-one correspondence or bijective). 

The Social Welfare Function (SWF) maps the domain which consists of all possible combinations of Ri, 1≤ i ≤ n, votes onto the range, each element of which is a possible social “preference or indifference” relationship, R, which is equivalent to the whole set of relationships, Ri, available to the individual voter. The domain can be represented as the set of all possible combinations { R1, R2,... Rn} where each Ri can take on one of m! values. (If there are m alternatives, there are m! permutations of those alternatives.) There are thus (m!)n elements in the domain. The corresponding range would be the set of values

{R} = {x1Rx2R...xm-1R xm}

where the set {x1, x2...xm} can take on m! possible values. The set {R}, the possible social choices, is identical to the set { Ri} available to any individual.
At this point we are in complete agreement with Arrow's definition of a SWF which states:

“By a social welfare function will be meant a process or rule which, for each set of individual orderings R1,...,Rn for alternative social states (one ordering for each individual), states a corresponding social ordering of alternative social states, R.” (1951).

In addition, we consider the possibility of social choices which are tie sets. To motivate our discussion of tie sets, we take as an example the binary case of two alternatives, a and b, and n voters. This is the typical, traditional voting situation. The individual voters vote either aPib or bPia where aPib means voter i prefers a to b. The corresponding social choices are aPb and bPa. If n is an even number and n/2 voters vote aPib  while the other n/2 voters vote bPia, then we have a tie which we indicate {aPb,bPa}. Therefore, the set of range elements that can be considered social choices are aPb, bPa and  the tie set, {aPb,bPa}. 

Let N(a,b) be the number of voters who vote aPib , and N(b,a) be the number who vote bPia. The rule connecting domain and range elements is as follows: If N(a,b) > N(b,a), the social choice is aPb. If N(b,a) > N(b,a), the social choice is bPa. If N(a,b) = N(b,a) (which can only happen if n is even), the social choice is a tie {aPb,bPa}. We denote a tie as follows: aTb. Clearly, this element needs to be considered in the range as a distinct possibility.

Now let us consider preferences and indifferences. The individual indifference realationship is aIib which means the ith voter is indifferent between a and b while the social indifference relationship is aIb. The individual now can vote in one of three ways: aPib, bPia or aIib. The social choices are aPb, bPa, {aPb,bPa}  aTb and aIb. Note that a distinction needs to be made between a social indifference and a social tie which are logically distinct. Now a particular SWF might map the case, N(a,b) = N(b,a), refered to above, into the social choice aIb while another SWF might map the same case into aTb. It is important to preserve the distinction between these two cases so that the same options are available in the world in which P and I are possible as are available in the world in which just P is possible.

Arrow (1951) claims to treat ties. He asserts: “...Axioms I and II do not exclude the possibility that for some distinct [alternatives] x and y, both xRy and yRx. A strong ordering, on the other hand, is a ranking in which no ties are possible.” Arrow is implying here that a social choice could consist of the tie set {xRy, yRx}. Clearly, this would not apply to individual choice since each individual would submit his vote in the form xRiy or yRix but not both. It should be pointed out that the tie set  {xRy, yRx}  xTy is not the same as indifference and does not imply the social choice xIy. Analagous to the case considered previously in which half the voters prefered a to b, half b to a and the social choice was {aPb,bPa}, the situation here might be that half the voters vote xRiy and half vote xRiy. The social choice  {xRy, yRx} needs to be available as a distinct and logically separate possibility from the social choice xIy. 

Arrow’s(1951) proof that social choice is possible for two alternatives is questionable because he doesn’t deal with the tie case, N(x,y) = N(y,x), properly. Arrow states: “DEFINITION 9: By the method of majority decision is meant the social welfare function in which xRy holds if and only if the number of individuals such that xRi y is at least as great as the number of individuals such that yRi x.”

Therefore, the case in which N(x,y) = N(y,x) would be decided xRy. But this violates the principal of neutrality or self-duality that requires every alternative to be treated in exactly the same way. Murakami (1968) states: “As long as we are considering the world of two alternatives, self-duality can be regarded as impartiality or neutrality with respect to alternatives. A self-dual social decision function has exactly the same structure regarding issue x against y as it does regarding issue y against x.” Self-duality is a stronger version of Arrow’s Condition 3 — Citizen’s Sovereignty, but one would think that, since Arrow provided for the possibility of the tie set, {xRy, yRx}, in Axiom I, it should be called for in this case.

In showing connectivity Arrow states: “Clearly, always either N(x,y) ≥ N(y,x) or N(y,x) ≥ N(x,y), so that, for all x and y, xRy or yRx.” This is an incorrect statement. One could say correctly that ‘either N(x,y) ≥ N(y,x) or N(y,x) > N(x,y)’ or  ‘either N(x,y) > N(y,x) or N(y,x) ≥ N(x,y)’ or ‘either N(x,y) > N(y,x) or N(y,x) > N(x,y) or N(y,x) = N(x,y).’ The latter restatement then would suggest the conclusion that either xRy or yRx or {xRy, yRx}. However, Arrow’s definition of majority rule would have to be changed to allow for the tie case. With these changes one could then go on to prove that social choice was indeed possible for the case of two alternatives.

Arrow’s statement that in a “strong ordering ... no ties are possible” violates the common sense notion considered above in which (when only preferences are considered) n/2 voters prefer a to b and n/2 voters prefer b to a. Clearly, this is a tie, and clearly we cannot have the social choice aIb since the indifference operator is not a part of the domain or the range. The social choice must be {aPb, bPa}.

In accordance with Arrow’s Axiom I which states: “For all x and y, either xRy or yRx” and about which he states: “Note also that the word ‘or’ in the statement of Axiom I does not exclude the possibility of both xRy and yRx.”, the social choice tie set, {xRy, yRx}, is made possible because of the assumption by Arrow of the inclusive or in Axiom I. If we would have had xRy AND yRx as a possibility in Axiom I, then indeed this would imply xIy. When the “inclusive or” interpretation of Axiom I is extended to three alternatives, we would have social choice solutions, for instance, of the form {xRyRz,yRxRz,zRyRx}.

An important thing to keep in mind here is that a tie refers to elements of the range and not to alternatives. If there are just two alternatives in an election, we say, sloppily, that it's possible for there to be a tie between x and y when what we mean (considering just preference relationships) is that there is a possibility of a tie between xPy and yPx which are the social choices. In other words, xPy and yPx are the social choices for which a tie may exist not x and y which are the alternatives. The same should hold true for xRy and yRx.

Therefore, in general we consider that the range consists of all possible elements, {R} = {x1Rx2R...xm-1R xm}, plus elements which represent all possible combinations of these elements. 

Paradox of Voting

According to the Condorcet method for determining the outcome of an election, we consider each of the alternatives in pairs, determine the winner for each pair and then determine the final social ordering by combining these results. For example, if there are 4 alternatives and 5 voters with votes abcd, abcd, adcb, cdab and acbd, clearly, aRb (since there are 5 votes for ab and none for ba), aRc (since there are 4 votes for ac and 1 vote for ca), aRd (4 votes for ad and 1 for da), cRb (3 votes for cb and 1 for bc), bRd (3 votes for bd and 1 for db) and cRd (4 votes for cd and 1 for dc). So the winner is acbd. However, there are cases for which this method will not work. 

Consider the following: 3 alternatives and 3 voters. Voter 1 votes abc; voter 2 votes bca; and voter 3 votes cab. If we consider the alternatives pairwise we have 2 votes for ab and 1 for ba; 2 votes for bc and 1 vote for cb; 2 votes for ca and 1 for ac. Therefore, a is preferred to b is preferred to c is preferred to a, and we have the cycle discovered by Condorcet. This is called the “paradox of voting.” Clearly, any of the choices, abc, bca or cab would be incorrect.

The heart of Arrow's analysis is the criterion known as the Independence of Irrelevant Alternatives. Arrow (1951) states that “...suppose that an election system has been devised whereby each individual lists all the candidates in order of his preference and then, by a preassigned procedure, the winning candidate is derived from these lists. ...Suppose an election is held, with a certain number of candidates in the field, each individual filing his list of preferences , and then one of the candidates dies. Surely the social choice should be made by taking each of the individual's preference lists, blotting out completely the dead candidate's name, and considering only the orderings of the remaining names in going through the procedure of determining a winner.”

Now let's reconsider the voting paradox considered above, assume that one candidate dies and recompute from the individual lists. Clearly, if c dies, ab should be  the winner since there are 2 abs to 1 ba. Similarly, if b dies, ca should be the winner, and, if a dies, bc should be the winner. Why shouldn't a similar demand be made of the social choice i.e. if a candidate dies, the new social choice is determined by blotting out the dead candidate's name from the social choice list? For example, if the social choice were abcd and c died, why shouldn't the new social choice be abd? This is precisely the case when the Condorcet criterion is used in a situation where it actually works. Let's consider the example considered previously in which there were 4 alternatives and 5 voters with votes abcd, abcd, adcb, cdab and acbd. Clearly, aRb, aRc, aRd, cRb, bRd and cRd. The winner was acbd. Let's say c dies. We have aRb, aRd and bRd from a consideration of the individual lists which leads by combination to the social choice abd, and we have the social choice abd by considering the social choice acbd and blotting out c. So we get the same social choice by building the solution from individual lists (blotting out the dead candidate) as we do by considering the social choice and blotting out the dead candidate.

Generalizing this notion, consider the tie solution {abc, bca, cab} for the voter's paradox case considered above. If c dies, we have the solution {ab, ba, ab}. Now we need come sort of combination rule to reduce this solution down to either ab or ba. This is not necessary when the solution is not a tie, but is necessary (although Arrow doesn’t consider it) when there is a tie and the solution at the next lower stage contains less elements than the present stage solution. The rule that would produce correct results in the example under consideration would be: choose the element or elements whose number is greatest in the tie set after the appropriate alternative has been blotted out. There are 2 abs and 1 ba in the solution so we determine the reduced solution to be ab which matches with our intuitive knowledge of what the solution should be. Similarly, we get bc and ca, respectively if a or b dies. So we can expand the 3 stage 2 solutions, ab, bc and ca to the stage 3 solution {abc, bca, cab} and we can reduce the stage 3 solution {abc, bca, cab} to the 3 stage 2 solutions ab, bc and ca.

An Algorithm which Generates Social Choices 

We now consider a general algorithm for generating solutions to the social choice problem. In a real sense the algorithm is the SWF. We build the solution stage by stage starting at the binary level. We first determine all the social choices by pairwise comparisons of the m alternatives as determined by the individual voter lists. These are the social choice solution sets for stage 2, one set for each possible pair of alternatives. Then we build the stage 3 solution sets by taking a binary solution and expanding it by combining it with another alternative such that the expanded stage 3 solution reduces correctly to the  stage 2 solution when each alternative is blotted out as in the above example. We do this for each possible combination of 3 alternatives.  We continue in this way until, if there are m alternatives, we have generated the stage m solution.

Now for some more terminology. We call the members of a social choice tie set “elements.” We say that a social choice i-ary element “covers” an (i‑1)-ary element if a letter can be blotted out of the i-ary element in such a way that the reduced i-ary element is identical with the (i‑1)-ary element. For example, abcd covers abc since, if a d is blotted out of abcd, we have abc. 

A “combination rule” tells us how to combine terms when a letter is blotted out in a tie solution set, and the solution set at the next lower level contains less elements. We use the following combination rule when reducing an i-ary solution to an (i-1)-ary solution: 1) blot out a particular letter in each element of the tie solution set; 2) out of this set of elements, choose that set of elements as the reduced solution if, for each element in the reduced solution, there are more of them than there are of any element not in the reduced solution and there are the same number of them as there are for every other element in the reduced solution. Let's call this the “majority” combination rule.

For example, let us assume that the stage 3 and 4 solution sets are the following:

Letter Combination	Stage 3 Solution Sets	Stage 4 Solution Set

	a,b,c				abc			{abcd, acdb,adbc}
a,b,d				adb
a,c,d				acd
b,c,d				{bcd, cdb, dbc}

In this example, if we blot out a d at stage 4, we have the modified set, {abc, acb, abc}. There are 2 abcs and 1 acb. Therefore the reduced solution set at stage 3 is abc. If we blot out a c, we have the modified set, {abd, adb, adb}. There are 2 adbs and 1 abd. Therefore, the reduced solution set is adb. If we blot out a b, we have the  modified set {acd, acd, adc}. There are 2 acds and 1 adc. Therefore, the reduced solution set is acd. Finally, if we blot out an a, we have the set {bcd, cdb, dbc} which is the solution set since all three elements occur the same number of times.

We generalize these notions to the following definition:

Definition 1: The Lawrence SWF is an algorithm which, for m alternatives and n voters, generates, for any stage i (2<i≤m),  solution sets such that, when any letter is blotted out and using the majority combination rule, the solution set reduces to a correct solution for stage i-1.

It should be pointed out that this is one very specific SWF which we will use to prove that social choice is possible by proving that it always (for any m,n) produces solutions which meet Arrow’s five criteria and two axioms. Other SWFs may exist as well.

Examples

If m=3, there are 27 possible combinations of pairwise comparisons since all domain elements can be collapsed down to 27 different cases. At the binary level we have either xRy or yRx or xTy. We work out the solutions as follows for each case. Each possible solution is rated to see how well it covers the solution sets at stage 2 (1 point for each stage 2 element covered). Since there are 3 stage 2 solution sets each consisting of one element, a rating of 3 means that all stage 2 elements are covered by 1 stage 3 element and that element is, hence, the stage 3 solution. If there are no stage 3 elements with a 3 rating, then there will be more than 1 stage 3 element in the solution set.

Case 1:	aRb, aRc, bRc

	Stage 3 Alternatives		Rating

		abc					3
		acb					2
		bac					2
		bca					1
		cab					1
		cba					0

Solution:	aRbRc	Check: 	Blot out a; Solution—bRc;
					Blot out b; Solution—aRc;
					Blot out c; Solution—aRb;

Case 2:	aRb, aRc, cRb

	Stage 3 Alternatives		Rating
		
		abc					2
		acb					3
		bac					1
		bca					0
		cab					2
		cba					1

Solution:	aRcRb	Check: 	Blot out a; Solution—cRb;
					Blot out b; Solution—aRc;
					Blot out c; Solution—aRb;

Case 3:	aRb, cRa, bRc

	Stage 3 Alternatives		Rating
		
		abc					2
		acb					0
		bac					1
		bca					2
		cab					2
		cba					1

Solution:	{aRbRc, bRcRa, cRaRb}	Check:	Blot out a; Solution—bRc;
							Blot out b; Solution—cRa;
						Blot out c; Solution—aRb;

Case 4:	aRb, cRa, cRb

	Stage 3 Alternatives		Rating
		
		abc					1
		acb					2
		bac					0
		bca					1
		cab					3
		cba					2

Solution:	cRaRb	Check: 	Blot out a; Solution—cRb;
					Blot out b; Solution—cRa;
					Blot out c; Solution—aRb;

Case 5:	bRa, aRc, bRc

	Stage 3 Alternatives		Rating
		
		abc					2
		acb					1
		bac					3
		bca					2
		cab					0
		cba					1

Solution:	bRaRc	Check: 	Blot out a; Solution—bRc;
					Blot out b; Solution—aRc;
					Blot out c; Solution—bRa;

Case 6:	bRa, aRc, cRb

	Stage 3 Alternatives		Rating
		
		abc					1
		acb					2
		bac					2
		bca					1
		cab					1
		cba					2

Solution:	{aRcRb, cRbRa, bRaRc}	Check:	Blot out a; Solution—cRb;
							Blot out b; Solution—aRc;
						Blot out c; Solution—bRa;

Case 7:	bRa, cRa, bRc

	Stage 3 Alternatives		Rating
		
		abc					1
		acb					0
		bac					2
		bca					3
		cab					1
		cba					2

Solution:	bRcRa	Check: 	Blot out a; Solution—bRc;
					Blot out b; Solution—cRa;
					Blot out c; Solution—bRa;

Case 8:	bRa, cRa, cRb

	Stage 3 Alternatives		Rating
		
		abc					0
		acb					1
		bac					1
		bca					2
		cab					2
		cba					3

Solution:	cRbRa	Check: 	Blot out a; Solution—cRb;
					Blot out b; Solution—cRa;
				Blot out c; Solution—bRa;

Cases 9 through 27 are covered in Appendix 1.

For m=4, there are 64 cases not counting ties. These solutions are given in Appendix 2.

Proof that Algorithm Satisfies Arrow's Criteria

 Axiom I: Connectivity

Either xRy or yRx or {xRy, yRx} by construction.

Axiom II: Transitivity

For all x, y and z, xRy and yRz imply xRz by construction; xRy and yTz imply xRz; xTy and yRz imply xRz; and xTy and yTz imply xTz. As long as a solution can be expressed in the form aQ1b Q2c...y Qm-1z where Qi  can be either R or T, the solution is transitive. Alternatively, any solution expressed in the form ab(c,d)e(f,g,h)ij is transitive.

Condition 1: Existence of a free triple

Arrow only required that some set of three alternatives be available for any logical ordering. Our algorithm assigns solutions for every logical ordering of every individual voter.

 Condition 2: Positive Association of Individual and Social Values

This Condition requires that, if every individual voter raises some candidate in his “preference or indifferenve” list, that candidate must not be lowered in the social choice. The algorithm considered here satisfies an even stronger criterion which is, if any individual voter raises a candidate in his “preference or indifference” list, that candidate must not be lowered in the social choice. 
Since the social choice is based on the choices made on binary pairs, let us consider only one voter and only two candidates, a and b. Let us say this voter originally preferred or was indifferent between a and b and then switched his vote to b over a. As long as the majority of voters still prefer or are indifferent between a and b after the switch, there will be no change in the social choice. However, there is the possibility that the change of one vote will change the majority to b over a. Then, at stage 2, bRa. At stage 3, if we originally had a unique solution, then it would have to be either abc or acb. If we originally had a tie solution, then it would have to be {abc, bca, cab} or {acb, cba, bac}. If we originally had a unique solution, then (after the change) we would either have a unique solution in which b is preferred to a or a tie solution in which, in at least one element, b is ranked higher than a. If we originally had a tie solution, then (after the change) we would have a unique solution in which b is ranked higher than a. In any case, if a switch between two candidates by one individual voter affects the social choice at the binary level, it will affect the social choice at any other level since those social choices are built up from the binary level. 

Condition 3: The Independence of Irrelevant Alternatives

Since the solution is computed stage by stage from binary pairs, it will always be the same if one or more candidates dies or drops out. In fact the solution can be recomputed starting at stage m and going down in stage number as well as starting at stage 1 and going up.

Condition 4: Citizens' Sovereignty

The social choice is imposed if there is some pair of alternatives a and b such that the Social Choice will always be bRa even if, for every individual voter aRib. In the algorithm under consideration here, if the majority of voters prefers a to b, then aRb and vice versa by construction.

Condition 5: The Condition of Nondictatorship

There is no dictator by construction, if the majority prefers a to b, then aRb and vice versa.

Conclusions

We have demonstrated an algorithm which generates social choices and, therefore, constitutes a SWF. We allow a social choice to consist of a set of tie elements. The algorithm is based on binary, pairwise comparisons and satisfies all of Arrow’s conditions and axioms as originally expounded . A companion paper, The Possibility of Social Choice, proves that the algorithm provides solutions for all values of m (number of alternatives) and n (number of voters). 

We have shown a SWF that generalizes Condorcet’s social choice rule and provides solutions in cases that Condorcet found to be unsolvable. Thus the “paradox of voting” has been resolved. It remains to prove that our method works not just in a limited number of cases but in fact in every case. We could provide a computer program which would generate all solutions for very large values of m (much like Fermat’s Last Theorem was shown to be true for very large values of the appropriate index prior to being proven generally by Andrew Wiles in 1994), but this would not prove that our algorithm provides solutions in every case. Therefore, a general mathematical proof is necessary in order to prove finally that social choice is possible and that Arrow’s Impossibility Theorem is false.
Appendix 1

Social Choice Solutions for m=3 

(Both “preferences or indifferences” and ties)

Case 9:	aRb, aRc, bTc

	Stage 3 Alternatives		Rating
		
		abc					2
		acb					2
		bac					1
		bca					0
		cab					1
		cba					0
		a(b,c)					3
		(b,c)a					1
		b(a,c)					0
		(a,c)b					1
		c(a,b)					0
		(a,b)c					1
		(a,b,c)					1

Solution:	aRbIc  [a(b,c)]	Check:	Blot out a; Solution—bIc;
						Blot out b; Solution—aPc;
					Blot out c; Solution—aPb;

We will just present the rest of the solutions without giving the details.

Case 10:	aRb, cRa, bTc		Solution:		cab, a(b,c), (b,c)a
Case 11:	bRa, aRc, bTc		Solution:		bac, a(b,c), (b,c)a
Case 12:	bRa, cRa, bTc		Solution:		(b,c)a
Case 13:	aRb, aTc, bRc		Solution:		abc, b(a,c), (a,c)b
Case 14:	aRb, aTc, cRb		Solution:		(a,c)b
Case 15:	bRa, aTc, bRc		Solution:		b(a,c)
Case 16:	bRa, aTc, cRb		Solution:		cba, b(a,c), (a,c)b
Case 17:	aTb, aRc, bRc		Solution:		(a,b)c
Case 18:	aTb, aRc, cRb		Solution:		acb, (a,b)c, c(a,b)
Case 19:	aTb, cRa, bRc		Solution:		bca, (a,b)c, c(a,b)
Case 20:	aTb, cRa, cRb		Solution:		c(a,b)
Case 21:	aRb, aTc, bTc		Solution:		a(b,c), (a,c)b, (a,b,c)
Case 22:	bRa, aTc, bTc		Solution:		b(a,c), (b,c)a, (a,b,c)
Case 23:	aTb, aRc, bTc		Solution:		a(b,c), (a,b)c, (a,b,c)
Case 24:	aTb, cRa, bTc		Solution:		c(a,b), (b,c)a, (a,b,c)
Case 25:	aTb, aTc, bRc		Solution:		b(a,c), (a,b)c, (a,b,c)
Case 26:	aTb, aTc, cRb		Solution:		c(a,b), (a,c)b, (a,b,c)
Case 27:	aTb, aTc, bTc		Solution:		(a,b,c)

Appendix 2

Social Choice Solutions for m=4 (no ties considered)

Case 1:	aRb, aRc, aRd, bRc, bRd , cRd		Solution:	abcd
Case 2:	aRb, aRc, aRd, bRc, bRd, dRc		Solution:	abdc
Case 3:	aRb, aRc, aRd, bRc, dRb, cRd		Solution:	abcd, acdb, adbc
Case 4:	aRb, aRc, aRd, bRc, dRb, dRc		Solution:	adbc
Case 5:	aRb, aRc, aRd, cRb, bRd , cRd		Solution:	acbd
Case 6:	aRb, aRc, aRd, cRb, bRd , cRd		Solution:	abdc, acbd, adcb
Case 7:	aRb, aRc, aRd, cRb, dRb , cRd		Solution:	acdb
Case 8:	aRb, aRc, aRd, cRb, dRb , dRc		Solution:	adcb
Case 9:	aRb, aRc, dRa, bRc, bRd , cRd		Solution:	abcd, bcda, dabc
Case 10:	aRb, aRc, dRa, bRc, bRd , dRc		Solution:	abdc, bdac, dabc
Case 11:	aRb, aRc, dRa, bRc, dRb, cRd		Solution:	abcd, dabc, cdab
Case 12:	aRb, aRc, dRa, bRc, dRb, dRc		Solution:	dabc
Case 13:	aRb, aRc, dRa, cRb, bRd , cRd		Solution:	acbd, cbda, dacb
Case 14:	aRb, aRc, dRa, cRb, bRd , dRc		Solution:	acbd, bdac, dacb
Case 15:	aRb, aRc, dRa, cRb, dRb , cRd		Solution:	acdb, cdab, dacb
Case 16:	aRb, aRc, dRa, cRb, dRb , dRc		Solution:	dacb
Case 17:	aRb, cRa, aRd, bRc, bRd , cRd		Solution:	abcd, bcad, cabd
Case 18:	aRb, cRa, aRd, bRc, bRd , dRc		Solution:	abdc, bdca, cabd
Case 19:	aRb, cRa, aRd, bRc, dRb , cRd		Solution:	adbc, bcad, cadb
Case 20:	aRb, cRa, aRd, bRc, dRb , dRc		Solution:	adbc, dbca, cadb
Case 21:	aRb, cRa, aRd, cRb, bRd , cRd		Solution:	cabd
Case 22:	aRb, cRa, aRd, cRb, bRd , dRc		Solution:	cabd, abdc, dcab
Case 23:	aRb, cRa, aRd, cRb, dRb , cRd		Solution:	cadb
Case 24:	aRb, cRa, aRd, cRb, dRb , dRc		Solution:	cadb, dcab, adcb
Case 25:	aRb, cRa, dRa, bRc, bRd , cRd		Solution:	abcd, bcda, cdab
Case 26:	aRb, cRa, dRa, bRc, bRd , dRc		Solution:	abdc, bdca, dcab
Case 27:	aRb, cRa, dRa, bRc, dRb , cRd		Solution:	cdab, bcda, dabc
Case 28:	aRb, cRa, dRa, bRc, dRb , dRc		Solution:	dcab, dbca, dabc
Case 29:	aRb, cRa, dRa, cRb, bRd , cRd		Solution:	cabd, cbda, cdab
Case 30:	aRb, cRa, dRa, cRb, bRd , dRc		Solution:	cabd, bdca, dcab
Case 31:	aRb, cRa, dRa, cRb, dRb , cRd		Solution:	cdab
Case 32:	aRb, cRa, dRa, cRb, dRb , dRc		Solution:	dcab
Case 33:	bRa, aRc, aRd, bRc, bRd , cRd		Solution:	bacd
Case 34:	bRa, aRc, aRd, bRc, bRd , dRc		Solution:	badc
Case 35:	bRa, aRc, aRd, bRc, dRb , cRd		Solution:	acdb, bacd, dbac
Case 36:	bRa, aRc, aRd, bRc, dRb , dRc		Solution:	adbc, badc, dbac
Case 37:	bRa, aRc, aRd, cRb, bRd , cRd		Solution:	acbd, bacd, cbad
Case 38:	bRa, aRc, aRd, cRb, bRd , dRc		Solution:	adcb, badc, cbad
Case 39:	bRa, aRc, aRd, cRb, dRb , cRd		Solution:	acdb, bacd, cdba
Case 40:	bRa, aRc, aRd, cRb, dRb , dRc		Solution:	adcb, badc, dcba
Case 41:	bRa, aRc, dRa, bRc, bRd , cRd		Solution:	bacd, bcda, bdac
Case 42:	bRa, aRc, dRa, bRc, bRd , dRc		Solution:	bdac
Case 43:	bRa, aRc, dRa, bRc, dRb , cRd		Solution:	bacd, cdba, dbac
Case 44:	bRa, aRc, dRa, bRc, dRb , dRc		Solution:	dbac
Case 45:	bRa, aRc, dRa, cRb, bRd , cRd		Solution:	acbd, bdac, cbda
Case 46:	bRa, aRc, dRa, cRb, bRd , dRc		Solution:	dacb, bdac, cbda
Case 47:	bRa, aRc, dRa, cRb, dRb , cRd		Solution:	acdb, dbac, cdba
Case 48:	bRa, aRc, dRa, cRb, dRb , dRc		Solution:	dacb, dbac, dcba
Case 49:	bRa, cRa, aRd, bRc, bRd , cRd		Solution:	bcad
Case 50:	bRa, cRa, aRd, bRc, bRd , dRc		Solution:	badc, bcad, bdca
Case 51:	bRa, cRa, aRd, bRc, dRb , cRd		Solution:	cadb, bcad, dbca
Case 52:	bRa, cRa, aRd, bRc, dRb , dRc		Solution:	adbc, bcad, dbca
Case 53:	bRa, cRa, aRd, cRb, bRd , cRd		Solution:	cbad
Case 54:	bRa, cRa, aRd, cRb, bRd , dRc		Solution:	badc, cbad, dcba
Case 55:	bRa, cRa, aRd, cRb, dRb , cRd		Solution:	cadb, cbad, cdba
Case 56:	bRa, cRa, aRd, cRb, dRb , dRc		Solution:	adcb, cbad, dcba
Case 57:	bRa, cRa, dRa, bRc, bRd , cRd		Solution:	bcda
Case 58:	bRa, cRa, dRa, bRc, bRd , dRc		Solution:	bdca
Case 59:	bRa, cRa, dRa, bRc, dRb , cRd		Solution:	bcda, cdba, dbca
Case 60:	bRa, cRa, dRa, bRc, dRb , dRc		Solution:	dbca
Case 61:	bRa, cRa, dRa, cRb, bRd , cRd		Solution:	cbda
Case 62:	bRa, cRa, dRa, cRb, bRd , dRc		Solution:	bdca, dcba, cbda
Case 63:	bRa, cRa, dRa, cRb, dRb , cRd		Solution:	cdba
Case 64:	bRa, cRa, dRa, cRb, dRb , dRc		Solution:	dcba
References

Arrow, Kenneth J. (1951) Social Choice and Individual Values  (John Wiley & Sons Inc., New York).
Bergson, Abram (1966) Essays in Normative Economics  (Harvard University Press, Cambridge, Mass.).
Black, Duncan (1958 The Theory of Committees and Elections  (Cambridge University Press, London) 184.
Borda, J-C de, 1784 (1781) “Mémoire sur les élections par scrutin”, Mémoires de l'Academie Royale des sciences année 1781, 657-65.
Condorcet, M. J. A. N., marquis de (1785) Essai sur  l'application de l'analyse á la probabilité des décisions rendues á la pluralité des voix  (Imprimerie Royale, Paris).
Dodgson, Rev. C. L. (1873) “A Discussion of the Various Methods of Procedure in Conducting Elections”, (1874) “Suggestions as to the Best Method of Taking Votes, Where More than Two Issues are to be Voted on,”  (1876) “A Method of Taking Votes on More than Two Issues.”
Granger, Gilles-Gaston (1989) La mathématique sociale du marquis de Condorcet (Éditions Odile Jacob, Paris).
MacKay, Alfred F. (1980) Arrow's Theorem  (Yale University Press) 2.
McLean, I. and F. Hewitt (1994) Condorcet  (Edward Elgar).
Murakami, Y. (1968) Logic and Social Choice  (Routledge & Kegan Paul Ltd., London).
Nanson, E. J. (1907) “Methods of Election” , in British Government blue book, Misc. No. 3, Cd. 3501.
Riker, William H. (1982) Liberalism Against Populism: A Confrontation Between the Theory of Democracy and the Theory of Social Choice  (W. H. Freeman, San Francisco).
Riley, Jonathan (1988) Liberal Utilitarianism  (Cambridge University Press, Cambridge).
Schofield, Norman (1985) Social Choice and Democracy ( Springer-Verlag).
Sen, A. K. (1970) Collective Choice and Social Welfare  (Holden-Day, San Francisco).