Soc Choice Welfare (1991) 8:21-50

Social Choice dWelfare

© Springer-Verlag 1991

Relationship admitting families of candidates* D. G. Saari

Departments of Mathematics and of Economics, Northwestern University, Evanston, IL 60208, USA Received February 24, 1989/Accepted September 17, 1990

Abstract. A central theme in social choice is to determine when must there be a

relationship among a group's sincere election rankings of several different subsets of candidates. This issue is completely resolved here for positional voting methods. Namely, necessary and sufficient conditions are derived for a family of subsets of candidates to determine when there is a choice of positional voting methods so that there are relationships among the election rankings. The same issue is resolved for a related family of social choice mappings. Then, in part, these necessary and sufficient conditions are used i) to analyze sequential voting procedures, ii) to show how to create new classes of axiomatic representations for social choice mappings that uniquely characterize the Borda Count, and iii) to determine the limits of indeterminacy for positional voting election outcomes. In the companion paper Saari [10], it is shown that the Borda Count (BC) is the unique positional voting method that minimizes the kinds and number of single profile paradoxes. In turn, as proved in [10], this conclusion means that the BC maximizes the numbers and kinds of relationships that exist among the election rankings of the various subsets of candidates. It turns out that not all collections of subsets of candidates admit relationships, but, if a family of subsets - a specified collection of subsets of candidates - does admit relationships, then all of these relationships can be completely determined by using the techniques developed in [10]. This raises an interesting problem; is it possible to characterize all possible families of subsets of candidates for which there is some kind of relationship among the BC rankings of the candidates? This problem is solved here. It has been known for some time that there are families which do admit relationships among the BC rankings. For instance, consider the family of consisting of all N candidates and the N (N - 1)/2 pairs of candidates. Smith [13] showed that the BC rankings of this family are related. (In part, Smith showed * This research was supported in part by NSF grant IRI-8803505 and a Fellowship from the Guggenheim Memorial Foundation.

22

D.G. Saari

that the Condorcet winner - the winner of all pairwise elections - cannot be BC bottom ranked in the set of all N candidates. Also see Young [14] and Fishburn and Gehrlein [3].) In the companion paper [10] I generalized Smith's results to prove that if k is an integer satisfying 2 < k < N (N is the total number of candidates), then there are relationships among the BC ranking of all N candidates and the BC rankings of all sets of k candidates. As a different kind of generalization, I showed that if k satisfies 2 < k < N, and if just the BC rankings of the subsets of k candidates are considered, then there are relationships among these rankings. Evidently many different kinds of families of subsets of candidates admit relationships among the positional voting rankings. So, what are all possible choices? In addition to answering this question, I also answer it for a class of social welfare mappings described by their axiomatic properties. There are several reasons why this issue is an important concern for social choice. First, as shown in [10], if a collection of subsets of candidates admit a relationship among the positional election rankings, then this family also admits a relationship for the BC rankings. Thus, by answering this question for the BC, we determine all families where, for some choice of a positional voting method, there are relationships among the rankings. As a second example, recall that there are many choice procedures based on the positional rankings of subsets of candidates. For example, in the standard runoff election, the set of all candidates is ranked, and then the two top-ranked candidates are re-ranked in a runoff election. This means that this procedure is based on the election rankings of the set of all N candidates and the N(N- 1)/2 pairs of candidates. Different procedures, then, are based on the positional election rankings of different families of subsets of candidates. The properties of these procedures are strongly constrained by any existing relationships among the election rankings of the subsets in this family. Thus, the analysis of these procedures is significantly aided by knowing whether a family associated with a procedure admits any relationships (this is the theme of this paper) and by determining what are these relationships (these are found by the techniques of [10]). The basic issue of this paper, to determine when a family must admit relationships among the rankings of the subsets of candidates, is a central, reocurring theme in social choice. For instance, this concern is implicit in many of the voting paradoxes found in the literature. Here, the purpose of the paradox is to use an example to demonstrate that a tacitly assumed relationship among election rankings need not be honored. This theme is reflected by the axiom of independence of irrelevant alternatives (IIA) from Arrow's theorem. If a social welfare mapping, f , satisfies IIA, then f not only ranks all N candidates, but also it provides a ranking for each of the pairs of candidates. Arrow's theorem provides a negative answer to the question whether there exist mappings that provide a ranking for the set of all N candidates and a ranking for each of the pairs where the rankings always agree. This search for relationships is the theme of Nakamura's theorem [5] where the rankings for each of the different sets of candidates are determined by simple games. The "Nakamura number" determines those situations where relationships exist among the rankings of the sets of candidates because cyclic rankings are not admitted. This same concern about the existence of certain relationships for specified families is found in Arrow's weak axiom of revealed preferences (WARP). (Arrow [1]; also see Nurmi [6].) Here it is required that if cl is a top-ranked candidate when a set X is considered, then when the subset A is considered, cl ~ A, cl remains as a top-ranked candidate. As it is well known,

Relationship admitting families of candidates

23

when W A R P or IIA are combined with some other natural axioms, impossibility conclusions emerge. Therefore, it is of interest to find substitute axioms for specified families. Because all possible relationships among families can be determined, several possible substitute axioms can be derived that are related to the special (but important) case of positional voting. This approach is indicated in this paper. So far, the emphasis in this introductory section has been on my theme of finding necessary and sufficient conditions for a family to admit relationships among their positional voting rankings for at least one choice of positional voting methods (the BC). But, what happens if a family does not satisfy these specified conditions? This means that the election rankings for the different subsets of candidates need not have anything whatsoever to do with one another, and this is true for all choices of positional voting methods. The consequences for such families are much stronger; for instance, as shown here, if a family does not satisfy these conditions, then the rankings for each subset of candidates can be selected in any desired fashion - even by a random method. Then, for any choice of positional voting methods, there is a profile so that the sincere election outcomes are the specified ones. So, by choosing the rankings for the sets in an appropriate fashion, all sorts of wild paradoxes can be created. Indeed, in this manner, these conditions can be used to subsume and extend much of the literature containing single-profile positional voting paradoxes. As a "positive" application of these results, I show that once these set theoretic conditions identify the collections of subsets of candidates that admit a relationship, then the techniques of [10] can be applied to create many new classes of axiomatic representations of social choice mappings that uniquely characterize the BC. For the remainder of Sect. 1, notation is introduced and earlier results needed for this paper are reviewed. In Sect. 2, some easily used conditions that offer strong positive and negative conclusions are stated. The positive assertion involves nothing more than counting the number of candidates in the specified sets of candidates. If this number - the dimension of the family - is sufficiently large, then there exist relationships among the election rankings (at least if the BC is used). The negative statement involves two different, but easily verifiable conditions. The first is called binary inclusion property (bip). This condition characterizes a property that families of subsets of candidates must possess if they are to admit a relationship among the ordinal election rankings. Thus, if a family does not satisfy the bip property, then it cannot admit relationships for any choice of positional voting methods. So, as described above, such families admit all sorts of paradoxes. The second condition involves nested sets; if the subsets of candidates are nested by (set theoretic) containment, then no choice of a positional voting method ever will admit relationships among the positional voting methods. Somewhat surprisingly, these simple conditions include, as special cases, a considerable number of the election paradoxes that have made the topic of social choice and voting such a puzzling yet attractive research area, as well as some of the standard axioms from social choice. As a preview of the significance of the nested set condition, consider the choice procedure of runoff elections. This is where the set of candidates are ranked, and then a specified number are advanced to a second stage to be reranked. This process can continue; at each stage the remaining candidates are ranked, and a specified number of the candidates are advanced to the next stage. The process stops when a single candidate remains. A first order analysis of these

24

D.G. Saari

procedures involves the positional voting rankings of nested sets of candidates. The theorem asserts that there need not be any relationship whatsoever among the positional voting rankings; for any choice of a positional voting method, any collection of rankings can occur with sincere voting. This fact can be used to demonstrate several troubling consequences associated with these procedures. In Sect. 3, the cyclic symmetry dimension is introduced for a collection of subsets of candidates. The combination of the cyclic symmetry dimension and the dimension of the family provides the necessary and sufficient conditions for a family of subsets of candidates to admit relationships among the rankings of the candidates. If the sum of these two values exceeds N ( N - 1)/2, then a relationship is admitted. (Again, it may be that only the BC allows such relationships to occur.) On the other hand, if this sum is bounded above by N ( N - 1)/2, then no relationship ever can be admitted for the rankings of any choice of positional voting methods. Thus, with the cyclic symmetry dimension, the problem of characterizing all families of subsets of candidates that admit election relationships is completely resolved for the class of positional voting methods. It is interesting to consider this same issue for more general classes of social welfare functions specified in terms of axiomatic representations. Such an analysis is started in Sect. 4. The results in Sect. 4 include some new classes of axiomatic representations for the BC. In a different direction, I demonstrate that the positional election outcomes can be surprisingly indeterminate if a family of subsets does not satisfy the set theoretic conditions of Sect. 3; one can create even more imaginative paradoxes than the kinds indicated above. The limits of this indeterminacy, which significantly extend results from Saari [9, 10], are specified in Theorem 6. Also, I show how these results about relation admitting families can be used to analyze and compare the outcomes of different social choice mechanisms. Most of the proofs of the results are in Sect. 5. 1.1. Notation Most of the notation can be found in Sect. 1 of [10]. Some modifications are needed because in this paper, I am interested in collections of subsets of candidates. With N > 3 candidates, there are 2 N - ( N + 1) subsets where it makes sense to have an election as each of these subsets has at least two candidates. Denote the subsets by Sj,j = 1 .... ,2 W - ( N + 1). Call a specified collection of two or more subsets a family, F, where, by reassigning the indices if necessary, F = [SI,..., Sa]. Call F ' a subfamily of a family F if it is a family contained in F. Associated with the N candidates and a specified family F is the system voting vector WeN= (Wl,..., Wa) where W] is the voting vector defining the positional voting method used to tally the ballots for the subset of candidates S], j--- 1 .... , ft. For example, if F = [[cl, c2, ca], [c3, c5], [cl, C4, C5, C6]], then the system voting vector W 6-- ((1, 0, 0), (1,0), (3, 2, 1,0)) corresponds to where the first two sets are tallied with a plurality vote and the third with the BC. If each subset of candidates in a family F is tallied with the BC, denote the system voting vector by BF~. Finally, to designate the special status of the family consisting of all 2N - ( N + 1) subsets, when this family is used the subscript " F " is dropped. Let Rj be the set of all possible linear rankings, including those with tie votes, of the candidates in Sj. Thus, for the above choice of $2,R2 = [c3 > c5, c3 = c5, c5 > c3], while for the above S1, R1 consists of the 3[ rankings without ties and the 7 rankings with at least one tie vote. For a given family F,

Relationship admitting families of candidates

25

the universal set, UN, is the cartesian product of the Rj sets. This means that an element of Uu is a listing of rankings; there is one for each set represented by F. UJ contains all possible listings of this kind. To illustrate with the above F, [c3 > e2 > Cl, c5 > c3, cl > c4 > c5 > c6) is a listing that specifies a ranking for each set in F, so it is an element of U6e. Once the system voting vector, WeN, and a profile, p, are given, the unique election ranking for each of the subsets of candidates is determined in the obvious fashion. Denote the listing by f (p, WeN). This listing, f (p, WeN), is an element of UJ. The dictionary, D (WeN) is the collection of all possible listings, or words, that can be obtained in this manner with some profile. Namely, d

D (WN) = [ f (p, WeN)I p is a profile; the number of voters in a profile can vary) . To avoid some technical definitions associated with the (vector) space of election tallies, I define the dimension of a family in the following way. Let I Sj-[ denote the number of candidates in the set Sj. For a family F = [$1,..., SB], let dim(F) =~j-=l

.....

fl(lSj[ - 1) .

1.2. Restatement of the basic issue

To restate the principal objective of this paper with this terminology, note that by definition D (W N) is a subset of UFu. If there is a relationship among the rankings of the sets of candidates, then certain listings of rankings cannot occur; e.g., it may be that cyclic rankings are not admitted, or it may be that a Condorcet winner cannot be bottom ranked in the set of all N candidates. This means that these particular listings from Uu are not admitted in D (weN); these are the WeN election outcomes that never could occur with any choice of a profile. Conversely, if there is a choice of W N and a listing from Uu that is not in D (WEN), then the excluded listing defines a relationship among the positional voting rankings. (For instance, w = [ c 1 > c2, c I > c3, c 2 > e3, c 3 > c 2 > c I ] ~ U 3, but w~ D 3 (B3). The fact that this listing is not admitted for the Borda method reflects the relationship that if cl is the Condorcet winner, she cannot be BC bottom ranked.) Consequently, the basic issue of this paper is to characterize the families F for which there exists a WeN so that D (WEN) is a proper subset o f UN. Definition. A family, F, is relation admitting iff there is a WeNso that D (WeN) is a proper subset of UFN. The characterization of relation admitting families is considerably simplified with the following statement. Theorem 1. For N>= 3, a family F, and a system voting vector WeN, D (BeN)is a subset of D (WeN). Indeed, for w ~ D (BeN), there is a profile so that for any choice of WeN, the listing o f election outcomes over the sets in F is w. This theorem, which is included for completeness, is a special case of one of the main results in Saari [10]. Theorem 1 implies that if a listing, or word, is admitted by the BC, then it is admitted by all other choices of system voting vectors. Indeed, the last statement of the theorem asserts that for any word from D (BeN) (any listing of BC election rankings for the subsets of F) there is a profile that preserves the same word no matter what choices of positional voting systems

26

D.G. Saari

are being used. Consequently, it follows from this theorem that to determine the relation admitting families, it suffices to characterize the families F for which D (BN) is a proper subset of UNF . On the other hand, this theorem also explains the comments made above that if F is relation admitting, the relations over the election rankings may be admitted only by the BC. This is because it often happens that D (BFN) is the only dictionary that is a proper subset of Uff; all other methods do not admit any relationship. Finally, because of Theorem 1, the largest set of relationships admitted by a relation admitting family are by the BC; thus, as already asserted, by using the techniques of [10] these relationships can be determined. (So far I have only required that some relationship exists among rankings; I have not imposed any condition that the relationship is one that most observers would agree is a desirable trait. However, it follows from [10] that the relationships are of the kind that if a candidate is highly ranked in certain subsets, then she cannot be poorly ranked in other subsets.)

2. A positive and a negative result

My first statement provides a simple but useful condition to show that several families are relation admitting. Theorem 2. Let N>=3. If F is a family where dim(F) > N ( N - 1)/2, then F is relation admitting. One positional voting vectors that admits relationships among N N the election rankings is the BC. That is, D (BF) is a proper subset of Uj~. As shown below with Theorem 4 (as illustrated by Example 3), Theorem 2 is sharp in that there are many examples of non-relation admitting families with dimension N ( N - 1 ) / 2 . To see the power of this theorem, consider the family F = [[Cl, C2, C3, C4) , ~Cl, C2, C3) , [Cl, C2, C4) ). There is no reason, a priori, to believe that F should be relation admitting. However, d i m ( F ) = 7 > N ( N - 1 ) / 2 = 6 for N---4. Consequently, according to Theorem 2, F is relation admitting. For instance, by use of the techniques of [10], it follows that if cl is top-ranked in two of the sets, she cannot be bottom ranked in the remaining set. This example shows that the conclusion of Theorem 2 is quite strong even though the verification of the hypothesis involves nothing more complicated than counting the number of candidates in each set in the family F. Indeed, the conclusion is sufficiently strong to subsume and extend several of the important conclusions from the literature. This is illustrated in Corollary 2.1. For example, part a of this corollary is Smith's result, part b shows that Smith's conclusion can be extended to the situation where the rankings of several of the pairs of candidates are ignored. Part c of the corollary includes my earlier results about sets of k candidates, and part d extends it. In part d, the function 17 is the greatest integer function where [z] is the greatest integer less than or equal to z. Part e illustrates another natural family of candidates. Corollary 2.1. a. (Smith [13]). If F consists of the set of all N candidates and the N ( N - 1)/2 pairs of candidates, then F is relation admitting. b. I f F contains a subfamily consisting of the set of all N candidates and all but N - 2 of the pairs of candidates, then F is relation admitting. e. (Saari [10]). Let k be an integer satisfying 2 < k < N and let F contain a subfamily consisting of a l l sets of k candidates. The family F is relation admitting.

Relationship admitting families of candidates

27

¢1. For k as in part c, if F contains a subfamily consisting of IN (N - 1)/2 (k - 1)] + 1 sets of k candidates, then F is relation admitting. e. For N>= 4, let F be the family consisting of all subsets that contain both cl and c2. F is relation admitting. Again, because each of these families are relationship admitting, the techniques described in Sect. 3 of [10] can be used to determine these relationships. It is interesting to note that parts b and d of the corollary are "sharp" in the sense that there are examples of families that satisfy these conditions, yet all proper subfamilies are not relation admitting. (This is illustrated in Sect. 3.) Even part e is sharp because, as shown below with Theorem 3, it is false for N = 3. Before proving the corollary, note that several of these assertions involve families that contain a specific subfamily of sets. These statements depend upon the following observation. Proposition 1. Suppose F is relation admitting. I f F" is any family that contains F as a subfamily, then F" is relation admitting. Proof of the corollary. Part a. As dim ( F ) = ( N - 1)+ ( N ( N - 1)/2) > N ( N - 1)/2, the conclusion follows from Theorem 2. Part b. By virtue of the proposition, it suffices to prove this assertion for the specified subfamily. Notice that in computing dim (F), each pair of candidates adds unity to the value. Therefore, even if N - 2 pairs of candidates are dropped from the family in part a, the condition of Theorem 2 is satisfied. Part c. Again, by virtue of the proposition, if suffices to consider the family consisting of the N ! / ( N - k ) ! k ! sets of k candidates. For this family, dim (F) = N!(k - 1)/(N- k)!k! > N ( N - 1)/2 if k > 2. Part d. If F consists of a sets of k candidates, dim (F) = a ( k - 1). Thus, dim (/7) satisfies the conditions of Theorem 2 if a >=[ N ( N - 1)/2 (k - 1)] + 1. Part e. This is a simple counting argument. [] To see another application of Theorem 2, consider a family F that involves only m < N of the candidates. Here, the value m can replace N in the hypothesis of the theorem. As an example, let N = 4 and F = [[Cl, C2] , [Cl, C3] , [Cl, C2, C3~]. As dim (F) = 4 < N ( N - 1)/2 for N = 4, it appears that Theorem 2 does not apply. However, each set in the family F involves only the m = 3 candidates [c~, c2, c3], and dim (F) > m (m - 1)/2 = 3. Thus, with this small adjustment, it follows from Theorem 2 that F is relation admitting. This same approach of replacing N with m has other interesting implications. For instance, in [9], it is shown that D (B u) always is a proper subset of U N, and in [10] I characterized the words (i.e., all relationships among the rankings) that are in the Borda Dictionary D (BN). But, what happens if only some of the components of a system vector W N are Borda Vectors? The next result shows that for any such choice of W N, D (W N) is a proper subset of U u. The proof of this statement outlines an approach to determine the entries of D (wN). Corollary 2.2. For the family of all 2 N - (N + 1) subsets of candidates, suppose that some of the components of the system voting vector, W u are Borda vectors. Then D (W N) is a proper subset of U u. Proof Define a family F in the following way. First, include in F all subsets of candidates that, according to W N, are BC ranked. Next, let B be the union of these sets; namely, B consists of all of the candidates that belong to a subset that

28

D.G. Saari

is BC ranked. Complete the definition of F by including in F all pairs of candidates that can be formed from B. (Notice that B may, or may not be in F. The choice depends on whether W ~ uses the BC to rank the subset B.) So, if B has k candidates, then, just because the pairs of candidates are included in F, it follows that d i m ( F ) > k ( k - 1 ) / 2 . Thus, according to Theorem 2, D (BEN) is a proper subset of Uu. Although the assertion now follows from Proposition 1, what follows is an explicit construction (which is essentially the proof of the proposition) given to emphasize the ideas. To show that D (W N) is a proper subset of U N, define the natural projection of D (W N) to D (weN). This is done by deleting from each word in D (wN) those symbols that correspond to rankings for subsets that are not in F. Suppose the assertion is false; namely, suppose D (W N) = U u. By projection, this forces D (WEN)= U~ which is a contradiction as D (wFN) -----D (BEN)is a proper subset of UN. [] The same approach can be used to approximate the words in D (WN). This is because D (W N) is in the inverse of the projection of D (BEN).This inverse image means that D (BEN)determines the symbols for the sets in F and the other symbols can be defined in an arbitrary fashion. The entries of D (BEN)can be characterized by using the techniques of [10].

2.1. A negative result While the approach suggested by Theorem 2 is very useful, it is not as strong result as we would like. This is because Theorem 2 only provides a sufficient condition; it is not a necessary and sufficient condition for a family F to be relation admitting. Second, Theorem 2 does not lend any insight about the set theoretic relationship required among the sets in F to make F relation admitting. More specifically, if dim (F) = c2 > c3 and c3 > c4 > c5 would impose some constraint on the possible BC rankings of the set [cl, c5, C6]. It does not; the first part of Theorem 3 asserts that the sets in a relation admitting family need to satisfy a stronger set theoretic condition. Definition. A family F satisfies the binary inclusion property (bip) if i. at least one subset of candidates in F has at least three candidates ii. if Sj e F is such that [Sj ] > 3, then there is a set Sk e F, S~* Sj, and a pair of candidates from Sj that are also in S~.

Example 1. It is easy to verify whether a family satisfies the bip; one just checks whether each set of three or more candidates has a pair that is in some other set of candidates. (This second set may have only two candidates.) For instance, if

Relationship admitting families of candidates

29

F = [[cl, c2, c3], [c3, c4, c5], [c2,c4, c5}~, then F does not satisfy the bip because no pair of candidates from [cl, c2, c3] is contained in either of the other two subsets. On the other hand, the subfamily consisting of the last two subsets does satisfy the bip. [] No subfamily of the important family consisting of all N ( N - 1)/2 pairs of candidates satisfies the bip. Also, as we know [9], this family of pairs is not relation admitting; all possible election rankings from this set are possible. The first part of the next theorem generalizes this statement to assert that if no subfamily of F satisfies the bip, then F is not relation admitting. The second part of this theorem considers a situation at the other extreme. It describes a situation whereby not only does F satisfy the bip, but so do all subfamilies of F. Nevertheless, this family still remains outside of the relation admitting class. So, the second part of this theorem offers another important, but easily verifiable situation when a family is not relation admitting. Theorem 3. a. I f no subfamily o f F satisfies the bip, then F is not relation admitting. Namely, for any choice of W~F, D ( W ~ ) = U~. b. (Saari [8]) Assume that n >=_3. Let F be a family of nested sets IS1, $2 .... , Sa] where Sj is a proper subset of Sj+ l for j = 1,...,t~- 1. The family F is not relation admitting. These results are sharp; as I show in Example 3, there are examples satisfying these conditions where if just one set is added to the family, the new family is relation admitting. As is true for Theorem 2, the hypotheses of Theorem 3 are easy to verify and the conclusions are strong. To see some applications of this theorem, note that many of the paradoxes in the literature either involve families that do not satisfy bip, or a nested family. For instance, the motivating example (stated just before Example 1) involves a family, F = [[Cl,C2, C3~, [C3,C4, C5~ , [Cl, c5, c6~ ~, for which no subfamily satisfies bip. Consequently, this choice of F is not relation admitting. So for any rankings of these sets and for any choice of positional voting methods, there is a profile that realizes the outcomes. This means that the specified rankings of Cl > c2 > c3 and c3 > c4 > cs can be accompanied by all possible rankings of the set [cl, c5, c6~. To illustrate the condition about nested sets, recall P. Fishburn's widely quoted paradox [2] where the group's plurality ranking is c~ > c2 > c3 > c4. Now, suppose c4 is removed. In such a situation, it is not uncommon for the group to behave as through their ranking for the remaining candidates is cl > c2 > c3. Thus, what is striking about Fishburn's example is that the same group's plurality ranking actually is the reversed c3 > c2 > c~. This example is based on the nested family F = [[cl, c2, C3, e4), [Cl, c2, C3)), SO it follows from Theorem 3 that this same outcome holds not only for the plurality vote, but also for all possible choices of a positional voting method, even the BC. Indeed, it now is possible to create even more surprising paradoxes. For instance, by combining the conclusions of Theorems 1 and 3, it now follows that there is a single profile of voters so that Fishburn's example holds for all possible choices of positional voting methods. In a different direction, it now follows that there is a profile of voters so that for all possible positional voting methods, the group's ranking of the four candidates always is c~ > ca > c3 > c4. However, if c2 is removed, then, for all possible choices of a positional voting method, this same group's ranking is c4 > c3 > Cl. If c4 is removed from this last set, then this same group's majority

30

D.G. Saari

ranking is cl > e3. Again, because the family is not relationship admitting, all sorts of other examples can be created; one can even use a random method to select the rankings for each subset of candidates. As a different kind of illustration, notice how this nested set condition is related to Arrow's conditions in his definition of the weak axiom of revealed preference, W A R P (Arrow [1], also see Nurmi [6]). To see the connection, suppose when the choice procedure is applied to the set X, then c~ is selected. If cl ~ A, and A is a subset of X, then one might expect Cl to be selected when the procedure is restricted to A. If the procedure is based on the positional voting rankings of a set, then W A R P defines a setting of nested sets, so it need not be satisfied. One way to avoid this problem is to define a procedure so that when it is restricted to X the selected outcome is based on the positional election rankings of X and all subsets of X. In this way, it may be possible to define procedures that do admit relationships, but W A R P is not one of them. As another application of Theorem 3, recall that part e of Corollary 2.1 holds for N=> 4. This conclusion is sharp because the assertion fails to hold for N = 3. This is because the family determined by this assertion, [ [ q , c2, c3~, [el, c2~], is nested. Thus, according to Theorem 3, this family is not relation admitting. To see a further application of the nested set assertion, consider the wide class of social choice mechanisms based on elimination procedures. These are the procedures where a set of candidates are ranked, and then a criterion is used to eliminate certain of these candidates from further consideration. The remaining set of candidates is reranked. Elimination procedures, by definition, define nested subsets of candidates. According to Theorem 3, any ranking can be assigned to these sets of candidates, and then, for any choice of positional voting methods, there is a profile of voters so that the designated outcomes occur. Consequently, the assignment of the rankings can be made to illustrate all sorts of "paradoxes" or difficulties when such procedures are employed. Example 2. a. Consider the nested family where S j = [ c ~ , . . . , c j + ~ , for j = 1 .... , N - 1. According to Theorem 3, even the BC cannot avoid allowing all possible listings from Uu into its dictionary. Thus, it follows from Theorem 1 that there is a profile of voters so that for all possible choices of a system voting vector, the outcome for Sj always is c~ > c2 > ... > cj+~ i f j is a multiple of 3, cj+ 1 > cj > ... > c~ if j + 1 is a multiple of 3, and ej+ 1 > c~ > ej > ... if j + 2 is a multiple of 3. Namely, the election outcomes are c2 > e~,c~ > c2 > ca, C4 ~ Cl ~ C3 ~ C2~ C5 ~ 6'4 ~ 6'3 ~ C2 ~ Cl ," "T h i s example illustrates that there are situations

where sharp theoretical conclusions can be obtained by using a combination of Theorems 2 and 3. To see this, note that because F is nested, it is not relation admitting. On the other hand, dim ( F ) = N ( N - 1)/2. Thus, according to Theorem 2, if just one more subset of candidates is added to F, then the augmented family is relation admitting. This conclusion is independent of the choice of the new subset. b. Corollary 2.1 asserts for N = 4 that there is a relationship among the BC tally for all four sets of three candidates. One might wonder whether this assertion extends to the more general situation of any family of four sets of three candidates. It need not; for example, it follows from part a of the above theorem that there is no restrictions on the BC rankings of the sets [{cl, 6">6"3~, [C3, Ca, c5~, [c5, c6, c7], [c7, c8, c ~ . []

Relationship admitting families of candidates

31

The concept of bip is introduced in Saari [8]. (The discussion paper [8] is the basis for the results given here and in [9, 10].) For some interesting, added discussion about the bip along with some challenging conjectures, see J. Kelly's column [4]. In Theorem 8 (Sect: 4), I use the bip to identify those families that admit axiomatic representations of social choice methods to uniquely characterize the BC and to identify those families for which D (BN) is a proper subset of D (W N) for all other choices of positional voting methods.

3. Cyclic symmetry What remains is to derive a necessary and sufficient condition to determine whether a family is relation admitting. This condition, which is specified in this section, is related to the bip concept. The condition is based on those properties of pairs of candidates that often correspond to a cycle; hence the name of cyclic symmetry. This cyclic symmetry condition is used to characterize the relation admitting families. Let Ind (Si) denote the set of subscripts of the candidates in

si. Definition. Let F = [$1 .... , S ~ . Let D be the set of scalar constants [dj, k], 1 _
z~,~ % - e~) = 0 ,

(3.1)

where the summation is over all pairs of indices in Ind (Si) and ej is the unit vector in R n with unity in t h e j th component. Let D be the vector in R "("- 1)/2 where the (i, j) component is dij. Consider the subspace of R n(n- 1)/2 spanned by all vectors D defined by F. The dimension of this subspace is called the cyclic symmetry dimension of F, and it is denoted by CS (F). The cyclic symmetry dimension, then, can be computed by use of standard techniques from linear algebra. For "general statements" that are to hold for all values of N, standard induction arguments from linear algebra can be used. Theorem 4. The family F = ~SI .... , Sp ] is relation admitting iff

CS(F) + dim (F) > N ( N - 1)/2] .

(3.2)

In particular, if Inequality (3.2) is satisfied, then D (B~) is a proper subset of UN. The number of independent relationships among the BC tallies is CS(F) + dim (F) - N ( N - 1)/2. The number of independent relationships can change with the family. For instance, a family may admit situations whereby only candidate Cl is precluded from being bottom (or top) ranked; with a larger family the same privilege now may be accorded to other candidates. In the companion paper [10], the actual relationships among the election rankings are determined by using scalar products in a vector space with certain, specified vectors. (These are the normal vectors.) The number of independent relationships admitted by a family is based on the dimension of the space of specified vectors. This dimension is given in the statement of the theorem.

32

D.G. Saari

The cyclic symmetry dimension of a family is non-negative, so Theorem 2 is an immediate special case of Theorem 4. Conversely, it is interesting to note that the cyclic symmetry dimension is precisely what is missing from Theorem 2 in order to have a complete characterization of relation admitting families. (So, for example, an immediate corollary is that if dim (F) = N ( N - 1)/2, then F is not relation admitting iff CS(F)--0.) The dimension of F involves counting the number of times a candidate appears in the subsets of F. As will become apparent, CS (F) involves counting either the candidates that are not in the family, or how often the effects of certain sets of candidates can be "cancelled" because of certain cyclic effects. The combination of these two counting arguments characterizes all of the relation admitting families. Because the relation admitting families are completely determined by Theorem 4, Theorem 3 (as well as all of the other results given above) must be a special case. That the nested set assertion of Theorem 3 is a special case of Theorem 4 is shown in Example 3a. (On the other hand, it is simpler to directly verify the bip assertion of Theorem 3, and this is given in Sect. 5.) The following examples are chosen to illustrate Theorem 4 and to show in what ways Theorems 2 and 3 are, and are not "sharp."

Example 3. a. I start by showing why part b of Theorem 3 is a consequence of Theorem 4. A simple counting argument shows that if F is a nested family, then dim (F) < N ( N - 1)/2. It remains to show that CS (F) = 0. I prove this by induction for F = [$1 .... , S N - 1 2 , where Ss= [ C l , . . . , Cjq- 1 2, by showing that all choices of d/,k must be zero. The only way Eq. (3.1) can hold for $1 --- [Cl, c22 is for dl,2 = 0. Assume the induction hypothesis that d/,~ = 0 for 1 < j < k < a. It must be shown that dj,a = 0 for all j < a. According to the induction hypothesis, the only possible nonzero terms in Eq. (3.1), when applied to Sa-1 = [Cl, ..., ca2, are those with the coefficients d/,,. Thus Eq. (3.1) can be expressed as (~1 SJ< adj, a)ea = Z 1
(3.3)

The vectors [es} are linearly independent, so each coefficient in the summation of the right hand side of Eq. (3.3) is zero. This completes the induction argument and the proof that CS (F) -- 0. As Inequality (3.2) is not satisfied, the conclusion follows from Theorem 4. (Compare this short, simple proof with the original one in [8] that is complicated and fairly long.) b. In this part of the example, I show that i) Theorem 3 does not completely characterize those families that are not relation admitting. Also, I show that ii) a family need not be nested to have CS ( F ) = 0. Both points are illustrated with

F=[[Cl,C22, [c1,e2, e32, [c2, c3,c4, c52, [c1,c2, c3,e5,c62, [Cl,C2, C3,c4,e5,c62~. This family is not nested, and F does satisfy the bip so Theorem 3 does not apply. On the other hand, using an argument similar to that of part a, it follows that C S ( F ) = 0 . As Eq.(3.2) is not satisfied, F is not relation admitting, so D (B~-) = U~. As described above, this means that all sorts of paradoxical examples can be created. As a special case, this result means there exists a profile so that for any choice of positional voting methods the election rankings of the first, third and fifth subsets of F are given by the order in which the candidates are listed, but the election rankings of the second and fourth subsets are in the reversed order.

Relationship admitting families of candidates

33

c. The purpose of this part of the example is to show that i) there are situations where the bip condition of Theorem 3 is sharp. Then, I modify the family to show that there are relation admitting families F where dim (F) < N ( N - 1)/2. Thus, this provides an example of a family not covered by Theorem 2. Let F = [ [ C l , C 2 , C3) , ~C3,C4, e5~ , [C1,C4~ , [C1,C5~ , [C2, C4] , [c2, c 5 ~ , No subfamily of F satisfies the bip, so, according to Theorem 2, F is not relation admitting. For F, dim (F) -- 8 and CS (F) = 2, so dim (F) + CS (F) = N ( N - 1)/2 for N = 5 . (The CS(F) value is given by the two D sets [d12--d23=-d~3= 1; all other dj~=0) and [d34=d45= - d 3 5 = 1; all other djk=0).) If a new family, F', is created by adding a subset to F, then it may be that dim (F) + CS (F) > N ( N - 1)/ 2. For example, if the new set is a triplet, then d i m ( F ' ) = d i m ( F ) + 2 and C S ( F ' ) = 1, so F ' is relation admitting. On the other hand, if the subset added to F t o create F" is a pair, then d i m ( F ' ) = d i m ( F ) + 1 and C S ( F ' ) = 1 so F" is not relation admitting. This shows that the choice of which subset is added to a family strongly determines whether the new family is relation admitting. Also, this example illustrates the following interesting feature. Proposition 2. Let N>= 3 be given. I f F is a proper subfamily o f F ' , then d i m ( F ' ) > dim(F) ,

but C S ( F ' ) < CS(F) .

(3.4)

As another, somewhat surprising example start with the nested family in part a and replace the pair of candidates $1 = [Cl, c2) with any other pair of candidates except ~cl,c2), {cl,c3), and [c2, c3). It is easy to show that C S ( F ) = 1, where D = [dl,2 = 6(2,3= - dl,3 = 1, all remaining 4-,k's equal zero). Because dim ( F ) = N ( N - 1 ) / 2 , it follows from Theorem 4 that F is relation admitting. Thus, by slightly altering the nested family, a relation admitting family arises. On the other hand, in part b, a nested family was altered significantly, yet the new family remained outside of the relation admitting class. d. It is possible for a relation admitting family F to have CS (F) = 0. For instance, let F ' be the family of all pairs of candidates. Clearly, d i m ( F ' ) = N ( N - 1 ) / 2 and C S ( F ' ) = 0, so this family is not relation admitting. (Also, Theorem 3 applies because no subfamily of F ' satisfies the bip.) Thus, for any family F that includes F' as a proper subfamily, it follows from Proposition 2 that dim (F) > N ( N - 1)/2 and CS ( F ) = 0. This illustrates one kind of situation where F is relation admitting even though CS ( F ) = 0; for all such families, Theorem 2 is "sharp". e. The modifier "cyclic" comes from a geometric representation of the relationship among the candidates. Identify the N candidates with the N vertices [ej) in R N, and identify pairs of candidates with the edges connecting the vertices. In this manner, the signs of the dj,k'S imposes a direction on the edges. For instance, the choice of the set D in part c, {dl,2---d2,3 --= -6;/1,3 = 1; all remaining dz~'s equal zero), corresponds to the cycle c~ > c2, c2> c3, c3 > c~. (There is another cycle; c3 > c=, c2 > c~, Cl > c3. However, this cycle corresponds to [dl,= = d2,3 = - d l , 3 = - 1; all remaining dj,k's equal zero). This cycle defines a D vector that is a scalar multiple ( - 1) of the original D vector. Thus, this second cycle does not affect the value of CS(F).) So, one use of the cyclic symmetry concept is to determine the number of independent cycles that are admitted by all subsets of a family. Conversely, the cycles admitted by the sets in F suggest the choices of the sets D.

34

D.G. Saari

This geometric interpretation can be used to create another example to show that even if CS (F) > 0, the family F need not be relation admitting. To see this, consider F=[[cl,c2], [Cl,C2, C3, C4~. Here C S ( F ) = 2 as defined by the two cycles C2>C3, C3>C4, c4 > c2([d2,3-~-d3,4-=-d2,4= l,djk-=O~) and c1>c3, c3 > c4, c4 > cl ([dl,3 =d3,4 = - d l , 4 = 1, all remaining dj~=0]). However, with N = 4, dim (F) = 4, so F is not relation admitting because dim (F) + CS (F) = N ( N - 1)/2. f . In the above examples, all of the dj,k's are either zero or of the same magnitude. This is not true in general. To see this, for N = 6 consider F = [[c3, c5~, [c4, c5, c6], [el, C2, c3, c43 , [Cl, c2, c3, c4, c6] , [Cl, c2, c3, c4, c5, C6] ]. Here dim(F) = N ( N - 1)/2 and CS (F) -- 4. It is interesting to compare this family with the somewhat related ones in parts a and b which are not relation admitting. Not only is F relation admitting, but it has three independent relationships among the BC tallies. To compute the cyclic symmetry dimension of F, note that G = [Cl, c2, c3~ is a subset of $3 and that if a pair from G is in Sj-, then so is G. This means that each of the sets in F admits the cycle characterized by the D set [d1,2=d2,3 = - d l , 3 = 1~. Using the same kind of argument, the other D sets are obtained by replacing G with [cl, c2, c4], [cl, c3, c4~, [c2, c3, c4], and [Cl, c2, c3, cg~. However, one of the D sets is of the form [dl,2= - d , 3= 1, d2,3=d2,4= -d3,4 = 1/2]. These different values reflect topological differences between a face constructed by three vertices, and one constructed by four of them. g. The cyclic symmetry not only picks out triplets of candidates that define a cycle, but also several other features. For instance, suppose c1 is not in any of the sets of F. From this assertion, it follows that CS(F)> N - 1 where N - 1 different D sets are given by [dlj = 1, all other d~,s= 0~. The corresponding vectors D determine projection operators. This formalizes the above, ad hoc description used to allow Theorem 2 to be applied to families involving only m < N candidates. As a more subtle feature, consider the family, F, that consists of all subsets of the N candidates except those containing the pair [ca, c2]. For this family, each candidate is in some subset in F, and CS(F)= 1, as given by d1,2 = 1. Thus, this family is relation admitting if N > 3. h. Corollary 2.1b asserts that if F consists of the set of all N candidates and all but N - 2 of the pairs, then F is relation admitting. In this part of the example, I verify my earlier assertion that there are choices of F where this statement is sharp because all proper subfamilies of F are not relation admitting. On the other hand, I also show that if attention is paid to which particular pairs of subsets are included in a family, a stronger conclusion can be obtained. To see that a stronger conclusion is possible, let F = [[Cl,...,CN], [Cl,C2~, [cl,c3~ .... ,[Cl,CN~]. Even though d i m ( F ) = 2 ( N - 1 ) and F has only N - 1 ( < N ( N - - 1)/2 -- (N-- 2) for N > 3) of the pairs, F is relation admitting for N > 3. This is because CS(F) > ( N - 2) ( N - 3)/2. (This value comes from the possible cycles that can be formed from the set [c2, c3,..., CN]. Equality is achieved only if N = 3.) Using the same ideas, one can find an example of a family F that is not relation admitting where F consists of the set of all N candidates and all but N - 1 of the pairs. As d i m ( F ) = N ( N - 1 ) / 2 , the family must be chosen so that CS (F) = 0. This can be accomplished if any triplet of candidates contains a pair that is in F. (If [c~, cj] is in F, then dz,s= 0.) One such family is where F consists of the set of all N candidates and all pairs of candidates except the N - 1 pairs [c~, c2], [c2, c3],..., [CN-1, CN~. This proves that there are families where the

Relationship admitting families of candidates

35

estimate in Corollary 2.1 is sharp. A related kind of construction can be used to show that the estimate in part d of that corollary also is the best possible estimate without added information about the sets in F. [] Theorem 4 completely characterizes those families that are relation admitting, but it does not address the choice of the relationships. While the exact relationships are determined by use of the techniques developed in [10], some insight can be obtained by applying Theorem 4 to the subfamilies of a relation admitting family F. The simple idea uses the following definition. For a relation admitting family F, call a proper subfamily F ' a maximal subfamily of F if i) F' is not relation admitting and ii) all subfamilies of F t h a t contain F' as a proper subfamily are relation admitting. Suppose F' is a maximal subfamily ofF. Because F" is not relation admitting, the (positional voting) rankings can be assigned in an arbitrary manner to the sets in F'. Thus the maximal subfamily indicates one choice of sets in F whereby there need not be any consistency or order among the election rankings. This means that the relations among the rankings of the set in F can arise only when enough additional sets are introduced. Namely the relationships emerge only after the rankings of the sets in F k F ' also are considered. Thus, the rankings of the sets in F ~ F ' can be viewed as consequences, or as the image of the rankings in F'. Loosely speaking, this means that the rankings over a maximal subfamily F' can be viewed as being the independent variables for a correspondence that determines the rankings for FxF'; the rankings of the sets in F~F' depend on the rankings for the sets in F ' . Therefore the maximal subfamilies of F indicate the kinds of relationships one might expect. As an illustration, let F' be the family of all pairs of candidates. According to part d of Example 3, F' is not relation admitting, but all superfamilies of F ' are. This means that if F" is a proper subfamily of F, then F" is a maximal subfamily. In turn, this means that the rankings of the sets in F~F' are determined by the pairwise rankings of pairs. While this does not specify the relationship even whether it is a relationship that would be viewed as a positive or a negative trait - it does provide valuable information about what is possible. As another example, consider parts c, d of Corollary 2.1 where the rankings of all subsets of k candidates are being considered. With the techniques used in Example 3, it follows that there is a maximal subfamily consisting of [ N ( N - 1)/2 ( k - 1)] of these sets. The rankings of the remaining subsets in F~F' can be viewed as being determined by the rankings of the sets in F'. Finally, it is worth noting that a maximal subfamily can be selected in many different ways. To see this, consider the relation admitting F = [[Cl, c2, c3), [cl, c2), [Cl, c3)). One choice for F" would be the two pairs. Here, the relation is if cl is top (respectively, bottom) ranked in both pairs, then she cannot be BC bottom (respectively, top) ranked in the set of all three candidates. Another choice for F ' could be the first two sets of F; here one relationship is that if ca is BC top-ranked, and she loses to c2, then she cannot lose to c3. 4. Axiomatic characterizations of the BC and even more voting indeterminacy

Theorem 4 completely characterizes the families of subsets of candidates that are relation admitting for positional voting methods. As emphasized above, if a family F is not relation admitting, then one can choose in a random fashion a ranking

36

D.G. Saari

for each subset in the family, and there is a profile so that for each choice of positional voting methods the sincere election rankings coincide with the selected rankings. It is natural to wonder whether there are other implications associated with the non-relation admitting families. There are, and some of them are described below. One of the statements shows how the above results can be used to analyze classes of social choice mechanisms. Another conclusion describes the limits of indeterminacy admitted by the election rankings of non-relation admitting families. A third considers the relation admitting families for smaller classes of positional voting methods. In a different direction, one might wonder whether these results are restricted to positional voting methods, or whether they extend to more general classes of social welfare functions. Namely, for a given class of social welfare methods represented by an axiomatic characterization, what are the necessary and sufficient conditions on a family F that admit relationships among the group rankings for at least one choice of welfare mappings? (Here, for subset of candidates Sj, the social welfare mapping is a mapping fj from the space of profiles to Rj.) In the concluding subsection of this section, this problem is completely resolved for a particularly appealing class of axioms that includes positional voting as a special case. In general this issue remains open, and it would be interesting to characterize the relation admitting class of families for other "natural" classes of social welfare and choice mappings.

4.1. Social choice procedures In this subsection 1 indicate how the above results can be used to analyze some longstanding social choice concerns. This involves the comparison of different social choice mechanisms; the purpose of the comparison is to determine for a fixed profile p whether the outcomes of different procedures agree with one another. (Recall, a social choice mechanism is a mapping from the space of profiles to the set of all subsets of candidates. The idea is that rather than ranking the candidates, the procedure selects the "best" candidates.) Here I consider those mechanisms based on the positional voting rankings of sets of candidates. For example, for the same sincere voters, must the choice procedures of an agenda and a runoff election always select the same candidate? As another example, notice that a much discussed question in the literature is to determine whether a given choice method is "Condorcet preserving." (A procedure is Condorcet preserving if it always selects the Condorcet winner (when one exists).) These two examples are special cases of the more general issue of comparing the outcomes of two different procedures. My objective here is to develop an easily used approach to address this kind of question. To start with some examples, consider the standard runoff election. This is where after the set of all N candidates is ranked, the two top-ranked candidates are advanced to the runoff. The selected candidate is the majority winner. The outcome of this procedure is based on the positional voting ranking of the set of all candidates; because any pair of candidates can be advanced, the procedure involves the rankings of each of the pairs of candidates. This means that the family associated with this procedure is the set of all N candidates and the N (N-- 1)/2 pairs of candidates. However, if we have additional information about the ranking of the set of all N candidates, then we can restrict attention to a much smaller subfamily. For instance, should we know that cl and c3 are the

Relationship admitting families of candidates

37

two top-ranked candidates for the set of all N candidates, then we are interested only in the rankings of the sets in the family F1 = [fci, c2,..., CN), [Cl, C3)). As a second example, recall that an agenda is based on a specified listing of the N candidates, say, [c2, c3, c~.... , cN]. In an agenda, the first two candidates, here [c2, c3), are ranked according to the majority vote, and the winner is advanced to be compared with the third listed candidate, c~. The process continues, and the winner of the last pairwise election is the selected candidate. For a given agenda and for any two candidates, there exists profiles so that at some stage of the process this particular pair will be compared. Thus, the family associated with this procedure is the collection of all pairs of candidates. On the other hand, with some additional information about the rankings of the certain pairs, we can ignore the rankings of candidates in certain pairs. For instance, if c2 beats c3, it is not of any importance (for the procedure) to learn how c3 fares against c~. As an extreme, there exist election rankings (i. e., profiles leading to election rankings) where the final comparison is between c2 and CN. For all such rankings, this procedure is based on the rankings of the family of subsets F2= [[c2, c3), ~c2, cl) .... , [c2, c ~ ) ) .

In general, the same kind of situation prevails. A procedure is based on the election rankings of a family of subsets. If more than one subset is involved, then, by restricting attention to certain profiles - profiles that define certain kinds of rankings for some of the subsets in the family - the analysis of the procedure can be restricted to a particular subfamily. This observation is basic for what follows. We now return to the issue which is to determine whether two different choice procedures must always select the same candidates when applied to the same profile. While there are methods to analyze this issue (see, for example, [9]), the next theorem offers an easily used approach to answer this comparison problem for a wide class of procedures. To see the ideas of the approach, consider the above examples of a runoff and an agenda. Here, the examples seem to indicate that the outcomes differ. For instance, with the imposed restrictions on profiles, the runoff outcome is either ci or c3 and the agenda outcome is either c2 or CN. The remaining problem is to show that these two imposed restrictions can be satisfied by a single profile. Namely, we must show that there is a nonempty intersection for those profiles used to create the restrictions on the rankings that are needed to define the two families F~ and F2. The argument goes as follows; the two families FI and F2 are disjoint; they have no subset of candidates in common. (This eliminates the danger that the same set of candidates needs to be ranked in two different ways.) Also, the union of/71 and F2 is not relation admitting. From this last fact, it follows that one can choose any rankings for each of the subsets in the union - in particular, we can choose these rankings required for the definition of the families/71 and F2 - and we know that there exists a profile where the election outcomes coincides with these rankings. This establishes the existence of the desired profile. Therefore, it now follows that a runoff and an agenda need not have the same outcome. It also follows that there exist settings where one procedure has the outcome c~ while the other procedure has the outcome c2. The same idea is used in general. Suppose we are comparing two different procedures. The outcome of the i th procedure is based on the rankings of a specific family of sets of candidates. Choose rankings for these subsets to satisfy two different conditions. The first condition is to select rankings so that ci is the

38

D.G. Saari

outcome of the i tla procedure; this forces the different methods to have different outcomes. The second condition is a set theoretic one. Associated with the i th procedure is a family of subsets. As discussed above, by imposing certain rankings on certain subsets, attention can be focussed on the rankings of a subfamily, F~. For many procedures, such as the agenda and the runoff election, one can change the choice of F~ just by changing the imposed rankings. (For instance, for the runoff, by changing the imposed ranking to where c=, c4 are top-ranked, the family now becomes [ [cl,..., cN), [c2, C4)).) Therefore, if possible, choose the rankings so that 1) the families, F~, are disjoint and 2) their union is not relation admitting. This set theoretic condition ensures that there exists a profile that leads to the imposed rankings for the different subsets of candidates. Therefore, for this profile, the outcome of the i tu procedure is ci. In other words, the approach is to start by imposing certain rankings on particular subsets of candidates. Associated with these imposed rankings are families of sets of candidates. If the families satisfy certain properties, then the theory developed in this paper justifies the existence of a profile where the election outcomes coincide with the imposed rankings. This is the content of Theorem 5; it reduces the comparison problem to a set theoretic computation. The statement of the theorem uses the following definition. Definition. For a given social choice procedure f , a family of subsets, F, is called a basic family for f and ci if i) there exist rankings for the subsets in F where the final outcome is ci, and ii) the same property does not hold for any proper subfamily of F. As an example of this concept, consider a runoff election where the runoff is between the two top ranked candidates. Here F 1= [[Cl, c2,... , CN] , (Cl, C2) ) is a basic family for c~ and for c2. Note that a basic family for a specified candidate need not be unique. For instance, [[el, c2..... CN), [Cl, Cj)) is a basic family for a runoff and cl for any choice of j . 1 . On the other hand, [[cl,cj), [cl, ca) ..... [cl, CN)) is the unique basic family for the Condorcet winner el. Theorem 5. For two given social choice mechanisms, f j , j = 1, 2, suppose each admits a basic family, Fj, for cj where F1 and F2 are disjoint. I f the family F defined by the union ofF1 and F2 is not relation admitting, then there exists a profile of voters, p, so that fj (p) = cj, j = 1, 2. The virtue of Theorem 5 is that it can be used to significantly reduce the number of situations that need to be investigated with care. Namely, by use of the theorem, one can determine relatively easily what combinations of procedures need not have the same outcomes. However, this theorem only gives a sufficient condition for different procedures to have different outcomes; it does not give a necessary condition. So, if Theorem 5 does not apply, then the next step is to analyze the relationships admitted by the joint family to determine whether they allow the procedures to have the same outcome. These relationships are determined by the methods developed in [10]. To illustrate this procedure, consider the above question of comparing the outcome of a runoff election with that of an agenda for all values of N > 3. A basic family for a cl winner of an agenda is [[C3, C4) , [C4, C5), [c5, c6) ..... ~CN- 1, CN), [C~, C=), [C=,Cl )) while a basic family for a runoff election for c2 is [[c~, c2,..., cN), [c2, c3~). The two families are disjoint, and their union is the family F = [[cl, c2,..., CN], [C=,C3), [C3, C4], [C4, C5~, [C5, C6] ..... [C~-1, CN),

Relationship admitting families of candidates

39

[CN, C2) , [6'2, C1 ) ). For F, dim (F) = 2 N - 1 is bounded above by N ( N - 1)/2 for N>=4. For N = 4, C S ( F ) = 0, so Theorem 5 applies. (The computation of CS is simple; each triplet of candidates must always contain a pair of candidates from F.) It now follows that the outcomes from the two procedures can disagree for any choice of a positional voting method. A similar computation holds for N > 4. So, Theorem 5 has eliminated the need to investigate this issue for any value of N=> 4. All that remains is the much simpler task of considering what can happen for N = 3. (It follows from the results in [10] that even here the answer is negative.) Theorems 4 and 5 provide a strong tool to analyze social choice procedures. According to Theorem 5, the goal is to show that the union of two of the basic families is a non-relation admitting family of sets. By use of Theorem 4, one knows how to construct families that are not relation admitting. Thus, Theorem 4 serves as a guide for the selection of the basic families for each procedure. Because Theorem 5 serves as a useful tool for the analysis of social choice procedures, one might wonder whether it can be improved upon. After all, it is easy to construct examples that have the same conclusion as this theorem, but where the basic families need not be disjoint. To illustrate, consider two different runoff systems. The first is where the top two ranked candidates are advanced to a majority vote runoff. Here a basic family for el is F a = [[C1,... , CN) , It1, C2) ). For the second runoff procedure, the three top ranked candidates are advanced to be reranked with a positional voting method where the top ranked candidate is the winner. For this procedure, a basic family for cz is F2=[[Cl,...,CN], [Cl, c2, C3~. Because these families are not disjoint, Theorem 5 does not apply. However, the joint family F defined by the union is nested, so F is not relation admitting. Consequently, it follows that there need not be any relationship between the rankings of the two sets [cl, c2~ and [ca, c2, c3 ]. This is relevant because it is the rankings of these two sets that determines the outcomes for the two procedures. Thus, because there is no relationship between these rankings, the two procedures need not have the same winner. Again, this conclusion is independent of the choice of the positional voting procedures. To extend Theorem 5, one needs to restrict the class of social choice procedures in terms of their properties. The choice of properties is based on which sets of candidates are needed to determine the final outcome of each procedures. If these subsets form disjoint subfamilies, then the immediate extension of Theorem 5 applies. However, without considering such additional features, Theorem 5 is the best one can do. To see this, consider the Condorcet winner and the winner of an agenda. The unique basic family for the Condorcet winner cl is [[C1, C2~ , [Ca, C3] .... , [Cl, CN] ]. On the other hand, a basic family for an agenda needs to involve a pair [ca, cj~ for some choice o f j . Thus the two families are not disjoint, so Theorem 5 does not apply. This is fortunate because, even though the union of the two families is not relation admitting, it is well known (and easy to show) that the winner of an agenda always is the Condorcet winner (when she exists). As a different example for N = 3, consider whether the runoff winner needs to be a Condorcet winner. The basic family for the Condorcet winner ca is Fa = [[ca, c2~, [cl, c3~ while there are at least two choices for a basic family for a c2 runoff election. The first is where F2 = [ [ca, c2, c3 ], [c2, ca ] and a second one is [ [cl, c2, c3 ], [c2, c3 ]. For the first choice of F2, the families are not disjoint, so Theorem 5 does not apply. The second choice of F2 is disjoint from F~, but the

40

D.G. Saari

union is relation admitting, so, again, Theorem 5 is not applicable. Indeed, it is known that for N = 3, the winner of a runoff election that is tallied with the BC must be the Condorcet winner. Thus, it is impossible for the winner to be c2 should Cl be the Condorcet winner. (Indeed, note that if cl is a Condorcet winner, then Theorem 5 does not apply for any procedure that must admit a basic family including a set with cl. This is because either the two families are not disjoint, or the joint family is relation admitting. Thus such procedures must be analyzed in terms of the relationships as derived from the techniques of [10].)

4.2. Even more indeterminacy Families that are not relation admitting allow even more indeterminacy among the election rankings than indicated by the definition. The next result delineates the boundaries of unrestricted paradoxes. To see other kinds of paradoxes could be created, consider the example where, for N - - 3 , six voters have the ranking ca > c3 > c2, five have the ranking c2 > c3 > Cl, and four have the ranking c3 > c2 > cl. The plurality ranking associated with this profile is cl > c2 > c3 while, for the same voters, the (1, 1, 0) ranking is Ca > c2 > c~. Evidently, it is possible that when the same voters use different choices of positional voting methods to rank the same set of candidates, they can end up with quite different election rankings. The issue is to examine the limits of this indeterminacy. It is known [7] that if ISj[ - 1 voting vectors are selected for Sj where these vectors and (1 .... ,1) are linearly independent, then one can arbitrarily choose I Sjl - 1 rankings of the candidates in Sj. The conclusion is that there exists a profile of voters so that when these voter's ballots are tallied with the k th positional voting method, then the outcome is the k th chosen ranking of the candidates. Thus, even for the same set of candidates, there need not be any relationship whatsoever among the positional voting rankings. On the other hand, if one adds one more method so that there now are ] Sj[ voting vectors, then there must exist relationships among the election outcomes. This is because one of the [ Sj ] voting vectors can be expressed as a linear combination of the rest of them. So the election tally based on this voting vector must be a linear combination of the election tallies of the other methods. (For instance, with the above example, any other voting vector can be expressed as a linear combination of (1,0, 0) and (1, 1, 0).) An immediate relationship is if all of the other methods have c1 as top ranked, then so must the last method. Thus, this upper bound on the number of voting vectors indicates one boundary for the indeterminacy of election outcomes. It is interesting to learn whether this same indeterminacy where several different election outcomes can occur over the same set of candidates can be extended to hold for a family of subsets. It can, and this is the content of Theorem 6. Theorem 6. Let F = [ $1 ..... Sp~ be a family that is not relation admitting. For each Sj, select I S:l - 1 voting vectors that, along with (1 .... ,1) are linearly independent. Select [Sjl - 1 rankings of the candidates in Sj, j = 1 ..... ~. There exists a profile o f voters so that when the results for Sj are tallied with the k th selected voting vector, the outcome is the k th selected ranking, j = 1,...,/~, k = 1 .... , I Sjl - 1. This theorem (which generalizes the main result in [7] from a family of nested sets to wider classes of families) asserts that if F is not relation admitting, then not only is there no relationship for the rankings of the sets of F, but there is no

Relationship admitting families of candidates

41

relationship among the same group's rankings of the same set of candidates when different positional voting methods are used. Thus, if a family is not relation admitting, all sorts of indeterminacy can occur with the election rankings. Theorem 6 is sharp in the sense that the conclusion does not hold if the family F does not satisfy the hypothesis, or if more voting vectors are used for any of the sets of F. For instance, if F is relation admitting and if one of the chosen voting vectors for each of the sets in F is the BC, then not all possible election rankings can occur. Indeed, even if none of the voting vectors is a Borda vector, some order and consistency among the rankings still may occur should a Borda vector be in the span of the selected voting vectors. In other words, the closer one comes to admitting a Borda vector, the more order is introduced into the election outcomes. Second, i f k > I Sjl - 1 voting vectors are used for Sj, then the k vectors and (1,..., 1) cannot be linearly independent. This means that a relationship will exist among the k election rankings of Sj.

Example 4. For the family [[cl, c2~, [cl, c2, c3], [c2, c3, c4, c5~, [Cl, c2, c3, Cs, c6~, [cl, c2, c3, c4, c5, c6~ described in part b of Example 3, it follows from Theorem 6 that there is a profile so that cl > c2 is majority outcome, c2 > c3 > Cl is the Borda outcome, while the plurality vote is the reversed ranking, c3 > c4 > c5 > c2 is the Borda outcome, the reversed ranking is the plurality outcome while c4 > Cs > c2 > c3 is the (1, 1, 0, 0) outcome, c6 > Cs > c3 > c2 > ci is the Borda outcome, the reversed ranking is the plurality outcome, c2 > c3 > c5 > c6 > cl is the (1, 1, 0, 0, 0) outcome, while the reversed ranking is the (1, 1, 1/2, 0, 0) outcome, and cl > c2 > c3 > c4 > c5 > c6 is the Borda outcome, the reversed ranking is the plurality outcome, c3 > c6 > c2 > c5 > cl > c4 is the (1, 1, 0, 0, 0, 0) outcome, the reversed ranking is the (1, 1, 1, 0, 0, 0) outcome, and c2 > c3 > c4 > cs > c6 > cL is the (1, 1, l, 1/2, 0, 0) outcome. There is not too much consistency among these rankings. [] Applications of Theorem 6 are obvious, and they include, for example, the comparisons of different runoff procedures, etc. The statement extends to the scoring methods described in Young [14] and in Saari [10]. As such, this theorem can be used to compare outcomes associated with the Coombs method [6], where the candidate eliminated at each step is the one with the largest (0,..., 0, 1) vote (the most number of last place votes). This theorem also can be used to illustrate notable difficulties that occur when one uses procedures, such as Approval Voting, where each voter has more than one way to have his ranking of the candidates tallied. By using the different methods, one can introduce a wide discrepancy in the final outcomes. (A different, more detailed analysis of this kind of procedure is given in [11, 12].)

4.3. More specific choices of positional voting methods In the above characterization of the relation admitting families, it is stated that there exists some choice of a positional voting method where the outcomes admit relationships. It follows from Theorem 1 that one choice always is the BC. However, one might be interested in using a smaller class of positional voting methods; maybe a class that does not include the BC. Indeed, it may be that one is interested in using a specific voting method, say, the plurality vote. The same question holds. For the specified class of positional voting methods, what are the relation

42

D.G. Saari

admitting families? Here, I have only partial results, but the following theorem indicates the general situation. Theorem 7. a. Let F be any family of subsets. For almost all choices of W N, F is

not relation admitting. In particular, if the plurality vote is used to rank each subset of candidates, then there does not exist a relation admitting family of subsets. h. Let G be a collection of positional voting methods used to tally the ballots of all subsets of candidates. I f G includes the Borda Count, then the relation admitting families for G is characterized by Theorem 4. I f G does not include the Borda Count, then the relation admitting families for G form a proper subset of the relation admitting families for the BC. It is known that if N > 4, then there are choices of W N that differ from the BC that do admit relation admitting families. The associated class of relation admitting families for these choices of W u remains to be characterized.

4.4. Axiomatic representations for the BC To conclude, I now discuss the same basic question of finding relation admitting families, but for social choice methods described in an axiomatic fashion. Phrased in this fashion, the issue becomes to select the appropriate class of axiomatic representations. As such, this analysis becomes an extension of the discussion in the companion paper [10]. The difference is that with the characterization of the relation admitting families developed in this paper, we now can outline all possible "single profile" axiomatic representations of the BC - something that was not possible in [10]. The following are slight modifications of definitions discussed in [10] where the modifications reflect restrictions to families. If F = IS1, $2,... , $6, ] is a family of sets, then G r = [gl .... ,g¢] is a family of social choice functions where gj is the social choice function for Sj. A natural condition to impose on each of the gj is neutrality. This is where if a is a permutation of the indices of the candidates, then gj (a (p)) = a (gj (p)). Loosely speaking, neutrality means that the outcome is not influenced by the names of the candidates, only by the choice of the profile. A second condition is anonymity; this is where the outcome does not depend on the names of the voters, only on how many have each ranking of the candidates. A third one, consistency, was introduced by Young [14]. Formally, this is where if p and p' are two different profiles and if g ( p ) n g ( p ' ) . 0 , then g (p + p ' ) = g ( p ) n g (p') where p + p' is the profile resulting from the combination of the two original profiles. One interpretation of this statement is that if two subcommittees do not completely disagree (g ( p ) n g ( p ' ) ~ 0), then the full committee adopts those candidates for which there is a common consensus (g (p + p ' ) = g ( p ) n g (p')). A social choice function, g, is somewhat faithful if the image of g contains at least one singleton and if for a profile, p, of a single voter, his bottom ranked candidate is not in the set g (p). Finally, I impose a form of the condition of independence of irrelevant alternatives (IIA). Namely, the independence of missing alternatives (IMA) conditions is if gj is the social choice mapping for Sj and if p and p' are two profiles such that the relative rankings of the candidates in Sj remain the same, then gj(p) =gj-(p').

Relationship admitting familiesof candidates

43

Theorem 8. For a given family F, consider the set of all mappings GF that cons&ts of anonymous, neutral social choice functions satisfying IMA that are somewhat faithful and consistent over each of the sets in F. 1. The family F is relation admitting for this class of social choice mechanisms if_/" F satisfies the conditions of Theorem 4. One class of the social choice mechanisms is where each set Sj is BC ranked and the top ranked candidates are selected 2. The family F is relation admitting iff the relationship among the choices is admitted by the selecting the top ranked candidates from the BC rankings. 3. Suppose F is relation admitting and F satisfies the bip. There exist relationships among the rankings and the selected outcomes that are satisfied only by the BC. In particular, zf wX:l: B N, then D (BN) is a proper subset of D OW~). In one direction, the first part of this theorem is not surprising, After all, the positional voting methods where the top ranked candidate(s) is selected satisfy the specified conditions on the social choice mechanisms. So if a positional voting method allows a family to be relation admitting, then so must this class of choice mechanisms. What is surprising is that the larger class of choice mechanisms does not admit any new relation admitting families. For instance, from Theorem 7 we find that if the BC is excluded from the possible choices of positional voting methods, then the class of relation admitting families shrinks. In the opposite direction, Theorem 8 states that no new families are admitted by enlarging the class of procedures in the specified manner. Secondly, even in this larger class, the BC is the method that admits the relationships among the outcomes. Thus, if the BC is excluded from this larger class, then a result of the kind given in Theorem 7 applies. An interpretation of the last part of Theorem 8 is that each relation admitting family F that satisfies the bip gives rise to an axiomatic characterization of the BC. This is because there are certain relationships among the election rankings that are satisfied only by the BC. Consequently, by expressing these relationships in axiomatic terms, one has a set of axioms that uniquely determine BC. This allows one to create even more axiomatic characterizations of the BC of the kind advanced by Young [14] and by Saari [10]. Indeed, it follows from the above that for each family of subsets that is relation admitting and satisfies the bip, there is an axiomatic characterization of the BC. The remaining step in such a program is to determine these BC relationships. But, if F is relation admitting, then the BC relationships over F can be found by using the techniques and results of [10]. An example of this is in Corollary 8.1a using what are called in [10] central candidates.

Example 5. a. Let m be such that 2 < m < N. There exists an axiomatic representation of social choice functions over the family consisting of all sets of m candidates that uniquely characterizes the BC. One such characterization is given in the next corollary for N = 4, m = 3. b. Let m satisfy the inequalities 2 < m < N. For the family consisting of all sets of m candidates and the set of N candidates, there is an axiomatic representation of social choice functions that uniquely characterizes the BC.

Corollary 8.1 a. Let N = 4 and let

F = [ [ C l , C 2 , C3] , [C2, C3, C4~ , [C1,C3,C4~ ,

[c~,c2, c4]] be the family of the four subsets of three candidates. Let g = (g~, g2, g3, g4) be an anonymous, neutral social choice function satisfying IMA that is somewhat faithful and consistent over each of the sets in F. I f g satisfies the

44

D.G. Saari

condition

that

gl (P)

g2 (P) = C3, g3 (P) =

impossible for the four selected outcomes to be c 4 , andg4 (p) = Cl, then each gi corresponds to ranking the set Si with the BC and the top ranked candidate is selected b. Let F be a relation admitting family that satisfies the bip. l f W N is not a Borda system vector, then D (BEN) is a proper subset of D (WEN). =

C2,

it

is

Part b of this corollary asserts that for the relation admitting families that satisfy the bip, the dictionary for any non-Borda system includes many paradoxes not admitted in the Borda Dictionary.

5. Proofs

The proofs of the main theorems depend upon the theory and the notation developed in Saari [9, 10]. Proof of Theorem 1. The assertion of this theorem for the family of all subsets is proved in Saari [10]. Thus, the proof of this theorem follows from a simple restriction to the subsets of candidates represented by family F much like that given in the proof of Corollary 2.2. []

The proofs of the rest of the results uses a vector space representation of the space for all voting tallies as given in [9, 10]. Here I introduce an abbreviated version of this representation. For a more detailed (but slightly different) description, see [10]. For each set of candidates, Sj, in a family F, consider the Euclidean space E k where k-- ] Sj[. The coordinates in this space are identified with the "names" of the candidates. For instance, if Sj= [c:, cs, c7~, then a vector in the associated E k would be denoted by (x2, Xs, XT) where a basis for this subspace is given by [e2, es, e7). Let EF be the cartesian product of the E k sets. If WeN is a given positional voting vector for the family F, WeN~ EF. Indeed, as each vector component of W N specifies the way to tally the ballots for the associated set of candidates, this vector WeNcan be viewed as representing the tally for each subset for a voter with the ranking cl > c2... > c N. As shown in [10], if W is a voting vector for a set of k candidates, W can be replaced by aW + b (1 .... ,1) for any choice of a > 0 and b, and the outcome of the new voting vector always agrees with that of w. For instance, the plurality voting vector for k candidates, (1, 0,..., 0), can be replaced by the equivalent vector k (1, 0,..., O) - (1, 1,..., 1)= ( k - 1, - 1 ..... - 1). Consequently, I assume that each of the voting vector components of WeN is replaced by an equivalent vector where the sum of the components equals zero. Because of this, the election vector is in the subspace E ,k of E k with the normal vector (1 ..... 1). Let f~u be the subspace of EF determined by the cartesian product of the E ,k subspaces. Notice that the vector dimension of g?x agrees with dim (F). Also notice that f2F N can be identified with a subspace of ~u. Let A denote the ranking cl > c2... > CN. Each ranking of the candidates (without ties) is given by some permutation of A, ~ (A). The tally of the ballots over F for a ballot for a voter with the ranking rc (A) is given by a permutation of the vector components of WeN. Let WF, N zc(A) represent this tally. Notice that this vector is in f2N. To find the final election outcome, let n~(A) denote the fraction of all voters that have the ranking rc (A). The election rankings for each

Relationship admitting families of candidates

45

subset of candidates are given by the appropriate vector component of N Z~(~)n~(A)WF,~(A~ e ON

(5.1)

where the summation is over all N! permutation zt (A). In each component space of EF, the resulting vector is orthogonal to (l .... ,1). (This is a consequence of the fact that the sum of the components of the voting vector equals zero.) Let V(WFN) be the vector space in f2F N that is spanned by all possible election tallies given by the sum in (5.1). As shown in [9, 10], the election outcomes are completely determined by the properties of this subspace. The general situation is that V(W N) = O N. It follows from the development in [9, 10] that whenever V0N N) is a proper subspace of f2N, then F is a relation admitting family for W N. As described in [10], the relationships among the election rankings are determined by the normal bundle of V(W N) in g2F N, SO the number of independent relationships is determined by the dimension of this normal bundle. Also as shown in [10], there exist equivalent representation of the vectors in WFN SO that V(B N) is a subspace of v(wN). (Here I assume that the constant difference between weights for any Borda Vector is 2.) Thus, the problem is to find those families F whereby V(B N) is a proper subspace of f2)-~. Let PF: f2N--+f2N be the projection mapping. By construction, it is clear that Pe(V(BN)) = V(BN). Therefore, the central problem of this paper is to determine when this projection defines a proper subspace of O N.

Proof of Theorem 2. It is shown in [9, 10] that d i m ( V ( B N ) = N ( N - 1)/2. As dim (PF(V(BN))< dim (V(BN)), it follows that V(B N) must be a proper subset of £2N whenever dim (g2N) = dim (F) > N ( N - 1)/2. [] Proof of Theorem 3. Part b of this theorem is proved in Example 3a. Thus, only part a needs to be proved. To prove part a, assume that no subfamily o f f satisfies the bip. Since B~,~(A):ve V(BN), so is any linear combination of these vectors. Choose some subset of candidates, Sj, and choose any pair of candidates, [ci, ck], contained in Sj. Now, consider any two ranking, C, of the N candidates where ci is top ranked and c~ is second ranked, and let D be the ranking where the relative ranking of this pair is reversed. This interchange of the relative rankings N N is reflected in the vectors BF, C, BF,D. But, as no subfamily o f F satisfies the bip, this particular pair only is in Sj; it is in no other subset of F. Thus, the only place N N where the two vectors BFoc, BF, D can differ is in the vector component correB N sponding to Sj. Therefore, the vector Be, c - BF,D has zero in all component spaces of ~2N that do not correspond to Si, and it has the value 2 ( e i - %) e V(B N) in the component space that does correspond to Sj. By continuing this construction over all pairs in all subsets of F, a basis for £2F N is given. This means that V(B N) = f2N, so the family is not relation admitting. [] The proof of Theorem 4 involves the properties of the projection operator P~:. These properties involve the orientation of V3(BN) with respect to the family F. To see the idea, consider the plane x = y in R . When this plane is projected to the x - z plane or the y - z plane, the image is two dimensional. On the other hand, when the plane is projected to the x - y plane, the dimension of the image is one dimensional. The simple linear algebra reason for the difference in the dimension is that the normal vector to the x - y plane, (0, 0, 1), is in the x = y plane, but the normal vectors to the other two coordinate surfaces are not in the x = y plane. In general, suppose the normal bundle of the image space intersects

46

D.G. Saari

the linear subspace that is to be projected, and let fl be the dimension of this intersection. The dimension of the image of the projected linear subspace is fl less than the dimension of the original plane. The next proposition restates this fact in terms of V(BN). To describe the statement, 9 ~ is viewed as being a linear subspace of f2N. Let N F denote the normal bundle of f2u in ~r~N. Proposition 3. Iffl = dim (NFn V(BN)), then dim (V(BJ) = ( N ( N - 1)/2) - ft.

Proof of Theorem 4. Suppose it can be shown that CS (F) = fl = dim (Nvn v(BN)). It would follow that

V(BJ) is a proper

subspace of f2x iff dim(F)

> (N ( N - 1 ) / 2 ) - CS(F). That is, the family F would be relation admitting iff CS(F) + dim ( F ) > N(N-1)/2. The dimension of the normal bundle for V(BF~) (in f2~) is equal to d i m ( F ) + C S ( F ) - ( N ( N - 1 ) / 2 ) . Thus, it remains to prove that CS (F) = dim ( N / a V(BN)). For i < j , let the vector Vi,j e ~e-~Nbe defined in the following manner. For each subset &, consider the subpace of f2~ identified with &. If Sk does not contain both e/and ej, then the component of V/,j for this component space is 0. If it does contain both candidates, then the vector component of Vii for this component subspace is 2(e~-ej). As shown in [9, 10], a basis for 'V(B N) is [Vi,j},=<~
<-- i,j <=N d i , j V i , j

.

(5.2)

But, v e NF iff the vector components of v are equal to 0 for those subspaces corresponding to subsets in F. This is true for the above choice of [d~,j] iff for each Sk in F

X,
(5.3)

where the summation is over all pairs of indices (i,j) where ci and cj are in &. Each vector in N u n V(B N) has a representation of the form Eq. (5.2) the scalars [d~,j] associated with a vector va define a vector D a. If [va}, a = 1,..., k, are linearly independent, then so are the vectors [D~}, a = 1,..., k. (This is because the vectors [D ~] define the linear transformation from V(B/) to NF, so the rank of the matrix corresponds to the dimension of the image.) Thus, dim ( N u n V(BN)) equals the dimension of the space spanned by all D ~ vectors defined as above. This is the definition of CS (F), so the proof is completed. []

Proof of Proposition 2. Let F be a subfamily of F ' . If D = [d~,j] is a set of scalars satisfying the cyclic scalar condition for the computation of CS (F'), then, by definition, X 4 o ( e ~ - e j ) = 0 where, for each & in F ' , the summation is over all pairs of indices in Ind (&). As F is a subfamily of F', the same choice of D applies for the computation of CS (F). Thus, CS (F)>= CS (F'). []

Proof of Theorem 5. Let F, F1, and F2 be as specified in the theorem. If F is not relation admitting, then any desired rankings can be imposed on the sets in Fs, and there is a profile where these rankings are the outcomes. So, choose rankings for the sets in F1 and rankings for the sets in F2 so that the two social choice procedures yield different outcomes. For the profile associated with these rankings, the social choice procedures give the specified, different outcomes. [] Proof of Theorem 6. If Vii.e= Pe(V~j), then it follows from the representation of the basis for V(B x) that' V(BJ) is'spanned by [Vi,j;F]I
Relationship admitting families of candidates

47

the hypothesis, v ( B N ) = I 2 Fu, s o [ V i , j ; F ~ l Z i < j < = N also serves as a basis for f2u. Another basis for f2F N is found by defining the vector E~j;e in the following manner. It has a zero vector component in all component spaces of g2e N that are not associated with Sk (a subset in F). In a component space for Sx, the vector is ei--e j if ci and cs are both in S~, and zero otherwise. The set of vectors' [E~d;F~ forms a basis for g2N . Note that Vi.j;F = 227xE~j-;F where the summation is over all sets Sk in F where ci and cj are both in Sg. Because each vector in one basis can be expressed as a linear combination of the vectors in another basis, it follows that there exist scalars [a;j~ k so that E/~,j; F = Z'i < j a k i , j V i , j ; F .

(5.4)

In the statement of the theorem, k = ]Sjl - 1 linearly independent voting vectors are assigned to tally the ballots for the candidates in Sj. Let these vectors be denoted by (W{, W~) and let FFbe the vector that is the collection of all the different voting vectors assigned to each of the subspaces. For example, if F = [[cl, c3, c5), [Cl, C2, C5, C6)), then the vector I F = ((2, - 1, - 1); (2, 0 , - 2); (3, - 1, - 1, - 1); (1, 1, - 1, - 1), (3, 1, - 1, - 3)) denotes the situation where $1 is ranked by the plurality vote (recall, (2, - 1, - 1) is a voting vector equivalent to (1, 0, 0) where the sum of the components equals zero), and by the BC, while $2 is ranked by the three methods of i) the plurality vote, ii) where each voter votes for his top two candidates (1, 1,0, 0), and iii) the BC. Extending the earlier notation, when the appropriate permutation of Fe is used to tally the ballots for the ranking re(A), this permutation is represented by FF.~(A~. Recall that 12N F is the cartesian product of the spaces E .k, where there is one of these subspaces for each set Si in the family F. In the setting of Theorem 6, we are concerned about the I Sj I - 1 different tallies of the candidates, so we need the product of ISj I - 1 copies of the associated E .k space. Thus, the dimension of the resulting cartesian product, TF, is X(IS]I - 1 ) 2 where the summation is over the subsets in F. Denote the vector space spanned by [FF,,(A)~ as V(FF); V(FF) is a linear subspace of TF. The object is to show that V(FF)= TF. A basis for TF is given by the following vectors. Let 0~s;a ~ TF be the vector that has the vector component e i - e s in the a th subspace associated with Sk, and a zero vector component in all other subspaces. (So, 0~j;a is the obvious extension

of E~s;~.) For each pair of candidates [c;, @ , i < j , that are in some subset of F, let R (s; i,j) denote a ranking where cl is ranked in s th place a n d j is ranked in (s + 1) th place. Let R - (s; i,j) be the ranking that differs from R (s; i,j) only in that the ranking of c~ and cj are reversed. Now, for all choices of i < j , compute U1;i,j = FF, R(1;i,j) - - FF, R - (1;i,j) •

(5.5)

In each of the component spaces associated with an S~ that contains ci and cj, this vector is a scalar multiple of e ; - es where the scalar multiple is determined by the associated voting vector. In particular, if the voting vector is W = ( W l , w2, w3,...), the scalar is w ~ - we. (This reflects that the two rankings differ in the first and second positions; everything else is the same.) In all other component spaces, the vector component is the zero vector. The vector Us; i,j = rF, R(s;i,j) - - I F , R - (S; i,j)

(5.6)

has a slightly different representation. Even though c~ is s th ranked in the total

48

D.G. Saari

set of all N candidates, it could be higher ranked in the subsets of F. Therefore, the scalar multiple of e i - ej is determined by the difference in the components in the weight vectors that represent the position of the candidates in the specified subset. (Notice, by taking different choices of which candidates are ranked above c,- and cj, different vectors emerge. Therefore, the emphasis is on a fixed choice.) Consider the vector sum

Is; i,j =

"~i < j a ik, j U s ; i,j

(5.7)

where the scalars are defined in Eq. (5.4). In each of the subspaces of g?u, each of the vector terms in the sum in Eq. (5.4) have the same coefficients. The same k are in the is true in Eq. (5.7). Therefore, the only non-zero components of Xs;~d ]S~ I - 1 subspaces identified with Sk. These non-zero components are a scalar multiple (more precisely, 1/2) of the vector components of U~;~dthat are in these Sk subspaces. Thus, the vectors [X ks;j are all in TF for each choice of k, s, i < j. k For a specific choice of k, consider [Xs,i.j-~ for all relevant choices of s and i < j . It is shown in [9] that with the assumptions on the voting vectors, the space spanned by these vectors includes [~j;a] for all relevant choices of i < j , and a. Therefore, V(FF)= TF, and this completes the proof. []

Proof of Theorem 7. This follows immediately from the main results of [9, 10]. Proof of Theorem 8. Parts 1 and 2. The proof of this theorem follows from Corollary 3.2 of [10]. This statement from [10] concerns the social choice methods that are anonymous, neutral, consistent, and somewhat faithful and that satisfy any other specified relationship among the sets of F. The conclusion is that if this added condition is not satisfied by the BC, then no such social choice method exists. On the other hand, if this condition is satisfied by the BC, then the BC is one possible choice. In our setting, the added conditions are any relationships among the elections rankings. Thus, if they are not satisfied by the BC, no social choice method satisfies them. Therefore, the relation admitting family is the same family that is relation admitting for the BC. This is the family characterized by Theorem 4. Part 3. According to Young [15], the class of mechanisms that are anonymous, neutral and satisfy the consistency condition are equivalent to scoring methods. These methods are similar to positional voting methods for k candidates. The major exception is that the monotonicity conditions on the weights for the voting vectors (i.e., wj>=wj+ 1,J = 1,..., k - 1, wl > w~) are replaced with the much weaker condition that not all of the wi's are equal. For instance, the vector (3, 5, 1) is not a voting vector because a larger number of points are assigned to the second place candidate than for the first place one. However, because the weights are not all equal, this is a scoring method. On the other hand, the somewhat faithful condition requires that WK, the weight assigned to the bottom ranked candidate, must be strictly bounded above by at least one other weight, wj. For a family F, extend the definition of W x to be a vector of the somewhat faithful scoring methods (rather than just voting vectors) for each subset in F. The results of [10] hold equally well for these scoring methods as for positional methods. In particular, there exists an equivalent representation of each scoring method so that V(W N) has V(B N) as a subspace. The third part of this theorem is proved if it can be shown that whenever W N is not a Borda system vector for the specified family, then V(B N) is a proper subspace of v(wN).

Relationship admitting families of candidates

49

As W N is not a Borda system vector, the scoring vector component for some subset in the family F is not a Borda voting vector for a subset of at least three candidates. Assume this set is St and assume that cl and c2 are a pair of the candidates in $1 that are in at least one other subset, say $2, of F. (Recall, F satisfies the bip.) Using the notation of Eq. (5.6), consider N N W F , R (s; 1,2) - - W F , R - (s; 1,2) •

(5.8)

As true with the argument for Theorem 6, this vector is a scalar multiple of el - e2 in each component space of O N associated with a set in F that contains the pair ct and c2. Now, if WeN = BeN, then this vector sum would be V1,2; F for all choices of s; one of the basis vectors of V(BeN). Thus, to prove the theorem, it suffices to show that for all choices of s, the vector in Eq. (5.8) cannot be a scalar multiple of V1,2;F. To do this, it suffices to examine the components for St and $2. The scalar multiple of el - ez in the component space of DeN corresponding to Sj is determined by the scoring vector Wj = (wt.j, w2j,...) and the candidates in the sets. So, if w (s,j)= w ~ j - w s + 1,j, then if s = 1, the scalar multiples defining the vector are w(1,j), j = 1,2. If this vector is in V(BeN), it must be that w (1, 1 ) = w (1, 2); if not, then the assertion is proved. To see the basic argument for s > 2, note that all choices of R (s; 1, 2) given by the possible ways candidates can be selected to be ranked above Cl can be used. If all of these candidates can be selected from the candidates in St n $2 that differ from cl and c2, then the scalars for Eq. (5.8) must be w (s,j) and if the resulting vector is to be in the Borda vector space, w (s, 1 ) = w (s, 2). However, the two sets are not the same, so there always are candidates that are in one set that are not in the other. When these candidates are ranked above ct in R (s; 1,2), then one of the scalars must be w (fl, j) where/~ < s. F o r instance, if the candidate is in St but not $2, then the scalars are w (s, 1) = w ( s - 1, 2). There are three cases to consider. First assume that $2 is a proper subset of $1. At least for s < [S2I - 1 , we have that w(s, 1 ) = w ( s , 2). By choosing k candidates from $I that are not in $2 to be ranked above ci, we have for s < IS2] + k - 1 that w(s+k, 1 ) = w(s, 2). This means that all of the w(s,j) terms are equal, so the scalar difference between the components in either of the two scoring vectors are a fixed constant. Thus, the two vectors are either a Borda vector, or a negative multiple of a Borda vector. The first cannot occur because of assumption. The second cannot occur because of the somewhat faithful assumption. Thus, the assertion is proved if $2 is a subset of St. I f St is a subset of $2, a similar argument holds. I f neither is contained in the other, then the argument is even simpler. For instance, for s = 2, first choose a candidate from $1 that is not in $2, and then choose a candidate from $2 that is not in St to be ranked above ct. The first choice leads to the relationship w (2, 1 ) = w (1, 2) while the second leads to w ( 1 , 2 ) = w(2, 1). Continuing in this fashion, the same conclusion is attained. [] References l. Arrow KJ (1959) Rational choice functions and orderings. Econometrica 26:121-127 2. Fishburn P (1981) Inverted orders for monotone scoring rules. Discrete Appl Math 3: 327-336 3. Fishburn P, Gehrlein W (1976) Borda's rule; positional voting, and Condorcet's simple majority principle. Public Choice 28:79-88

50

D . G . Saari

4. Kelly J (1987) Conjectures and unsolved problems. Soc Choice Welfare 4:235-239 5. Nakamura K (1975) The core of a simple game without ordinal preferences. Int J Game Theory 4:95-104 6. Nurmi H (1987) Comparing voting systems. Reidel, Dordrecht 7. Saari DG (1984) The ultimate of chaos resulting from weighted voting systems. Adv Appl Math 5:286-308 8. Saari DG (1985) The optimal ranking method is the Borda Count. Collabortive Paper CP85-4, IIASA, Laxenburg, Austria, also, a 1985 NU Center for Math Econ Discussion paper 9. Saari DG (1989a) A dictionary for voting paradoxes. J Econ Theory 48:443-475 10. Saari DG (1991) The Borda dictionary. Soc Choice Welfare 8: (to be published) 11. Saari DG, Van Newenhizen J (1988 a) The problem of indeterminacy in approval, multiple, and truncated voting systems. Public Choice 59:101-120 12. Saari DG, Van Newenhizen J (1988b) Is approval voting "an unmitigated evil"; a response to Brams, Fishburn and Merrill. Public Choice 59:133-147 13. Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41: 1027-1041 14. Young P (1974) An axiomatization of Borda's rule. J Econ Theory 9:43-52 15. Young P (1975) Social choice scoring functions. SIAM J Appl Math 28:824-838