Fundamentals of social choice theory

17

other alternative x in Y\{y}.  The existence of a Condorcet winner requires very special

configurations of individual preferences.  For example, suppose that each voter's preferences is

selected at random from the (#Y)! possible rank orderings in L(Y), independently of all other

voters' preferences.  R. May (1971) has proven that, if the number of voters is odd and more than

2, then the probability of a Condorcet winner existing among the alternatives in Y goes to zero as

#Y goes to infinity.  (See also Fishburn, 1973.)

McKelvey (1976, 1979) has shown that, under some common assumptions about voters'

preferences, if a Condorcet winner does not exist then the top cycle is generally very large.  We

now state and prove a simple result similar to McKelvey's.

We assume a given finite set of alternatives Y, and a given odd finite set of voters N, each

of whom has strict preferences over Y.  Let 

)(Y) denote the set of probability distributions over

the set Y.  We may identify 

)(Y) with the set of lotteries or randomized procedures for choosing

among the pure alternatives in Y.  Suppose that each individual i has a von Neumann-

Morgenstern utility function U :Y 

6

 

ú such that, for any pair of lotteries, individual i always

i

prefers the lottery that gives him higher expected utility.  So if we extend the set of alternatives

by adding some lotteries from 

)(Y), then U  defines individual i's preferences on this extended

i

alternative set.    With this framework, we can prove the following theorem.

Theorem 1.3.  If the top cycle contains more than one alternative then, for any alternative

z and any positive number 

g, then we can construct an extended alternative set, composed of Y

and a finite subset of 

)(Y), such that the extended top cycle includes a lottery in which the

probability of z is at least 1-

g.

Proof.  If the top cycle is not a single alternative, then the top cycle must include a set of

three or more alternatives {w , w , ..., w } such that w  << w  << .. << w  << w .  

1

 

2

 

 

K

 

 

 

1

 

 

2

 

   

 

K

 

 

1

Von Neumann-Morgenstern utility theory guarantees that every individual who strictly

prefers w

 over w , will also strictly prefer (1-

g)q + g[w ] over (1-g)q + g[w ] for any lottery q. 

j+1

 

 

j

 

 

 

 

 

   

j+1

 

 

   

j

(Here (1-

g)q + g[w ] denotes the lottery that gives outcome w  with probability g, and otherwise

j

 

 

 

 

 

 

 

j

implements the outcome randomly selected by lottery q.)  Thus, by continuity, there must exist

some large integer M such that every individual who strictly prefers w

 over w , will also

j+1

 

 

j

strictly prefer 

---

18

(1-

g)

(

(1 - (m+1)/M)[w ] + ((m+1)/M)[z]

)

 + 

g[w ] 

1

   

   

j+1

over 

(1-

g)

(

(1 - m/M)[w ] + (m/M)[z]

)

 + 

g[w ]

1

   

   

j

for any m between 0 and M-1.  That is, the same majority that would vote to change from w  to

j

w

 would also vote to change from w  to w

 with probability 

g even when this decision also

j+1

 

 

 

   

 

 

j

   

j+1

entails a probability (1-

g)/M of changing from w  to z.

1

We now prove the theorem using the Y*(2) characterization of the top cycle.  Because w

1

is in the top cycle, we can construct a naive chain from any alternative x to w  (x <<...<< w ). 

1

   

 

1

This naive chain can be continued from w  to z as follows:

1

w  = (1-

g)[w ] + g[w ] 

1

   

1

   

1

<< (1-

g)

(

(1-1/M)[w ] + (1/M)[z]

)

 + 

g[w ]

1

   

   

2

<< (1-

g)

(

(1-2/M)[w ] + (2/M)[z]

)

 + 

g[w ]

1

   

   

3

... << (1-

g)[z] + g[w ]  (for some j).

j

So including all the lotteries of this chain as alternatives gives us an extension of Y in which a

lottery (1-

g)[z] + g[w ] can be reached by a naive chain from any alternative x.  Q.E.D.

j

The proof of Theorem 1.3 uses the naive-chain characterization of the top cycle (Y*(2)),

but the equivalence theorem tells us that this result also applies to agenda manipulation with

sophisticated voters.  That is, if the chairman can include randomized social-choice plans among

the possible outcomes of an agenda then, either a Condorcet winner exists, or else the chairman

can design a binary agenda that selects any arbitrary alternative (even one that may be worst for

all voters) with arbitrarily high probability in the majority-rule sophisticated outcome.

If more restrictions are imposed on the form of the agenda that can be used, then the set

of alternatives that can be achieved by agenda manipulation may be substantially smaller.  For

example, Banks (1985) has characterized the set of alternatives that can be achieved as

sophisticated outcomes of successive-elimination agendas of the following form:  The

alternatives must be put into an ordered list; the first question must be whether to eliminate the

first or second alternative in this list; and thereafter the next question is always whether to

eliminate the previous winner or the next alternative on the list, until all but one of the

---