Fundamentals of social choice theory

14

for at least one terminal node.  Given a binary agenda, a sophisticated solution extends the

labelling to all nodes so that, for every nonterminal node 

2, the label at 2 is the alternative in Y

that would be chosen by a majority vote among the alternatives listed at the two nodes that

directly follow 

2.  A sophisticated outcome of a binary agenda is the outcome assigned to the

initial node (or root) of the agenda tree in a sophisticated solution.

Given any preference profile for an odd number of voters, each binary agenda on Y has a

unique sophisticated solution, which can be easily calculated by backward induction.  (See

Farquharson, 1969, and Sloth, 1993.)  Thus, once a binary agenda has been specified, it is

straightforward to predict the outcome that will be chosen under majority rule, assuming that the

voters have a sophisticated understanding of each others' preferences and of the agenda.

But different agendas may lead to different majority-rule outcomes for the same voters'

preferences.  Thus the chairman who sets the agenda may have substantial power to influence the

sophisticated majority-rule outcome.  To quantify the extent of such agenda-setting power, we

want to characterize the set of alternatives that can be achieved under binary agendas, for any

given preference profile.

To compute sophisticated solutions, it is only necessary to know, in each pair of

alternatives, which one would be preferred by a majority of the voters.  That is, we only need to

know, for each pair of distinct alternatives x and y in Y, whether x >> y or y >> x.  (Read ">>"

here as "would be preferred by a majority over.")  

The ABC paradox shows the majority-preference relation >> is not necessarily transitive,

even though each individual voter's preferences are assumed to be transitive. In fact, McGarvey

(1953) showed that a relation >> can be generated as the majority-preference relation for an odd

number of voters whose individual preferences are transitive if and only if it satisfies the

following completeness and antisymmetry condition:

 

x >> y or y >> x, but not both, 

œx0Y, œy0Y\{x}.

Any such relation >> on Y may be called a tournament.  

1.5  The top cycle

Let >> be any fixed tournament (complete and antisymmetric) on the given set of

---

15

alternatives Y.  We now consider three definitions that each characterize a subset of Y.  

Let Y*(1) denote the set of all alternatives x such that there exists a binary agenda on Y

for which x is the sophisticated outcome.  That is, Y*(1) is the set of outcomes that could be

achieved by agenda-manipulation, when the agenda-setter can plan any series of binary

questions, subject only to the constraint that every alternative in Y must be admitted as a

possibility under the agenda, and all questions will be resolved by sophisticated (forward-

looking) majority votes.

Let Y*(2) denote the set of alternatives y such that, for every alternative x in Y\{y}, there

must exist some chain (z ,z ,...,z ) such that x = z , z  = y, and z

 << z  for every k = 1,...,m. 

0 1

m

 

 

     

0

 

m

     

 

k-1

 

 

k

That is, an alternative y is in Y*(2) iff, starting from any given status quo x, the voters could be

manipulated to give up x for y through a sequence of replacements such that, at each stage, the

majority would always prefer to give up the previously chosen alternative for the manipulator's

proposed replacement if they believed that this replacement would be the last.  In contrast to

Y*(1) which assumed sophisticated forward-looking voters, Y*(2) is based on an assumption

that voters are very naive or myopic.

Let Y*(3) be defined as the smallest (in the set-inclusion sense) nonempty subset of Y

that has the following property:  

for any pair of alternatives x and y, if y is in the subset and x is not in the

subset then y >> x.

An argument is needed to verify that this set Y*(3) is well defined.  Notice first that Y is itself a

"subset" that has this property (because the property is trivially satisfied if no x outside of the

subset can be found).  Notice next that, if W and Z are any two subsets that have this property

then either W 

f 

Z or Z 

f

 W.  (Otherwise we could find w and z such that w

0W, wóZ, z0Z, and

z

óW; but then we would get w >> z and z >> w, which is impossible in a tournament.)  Thus,

assuming that Y is finite, there exists a smallest nonempty set Y*(3) that has this property, and

which is a subset of all other sets that have this property.

A fundamental result in tournament theory, due to Miller (1977), is that the above three

definitions all characterize the same set Y*.  This set Y* is called the top cycle.

Theorem 1.2.  Y*(1) = Y*(2) = Y*(3).

---

16

Proof.  We first show that Y*(1) 

f

 Y*(2).  Suppose that y is in Y*(1).  Then there is

some binary agenda tree such that the sophisticated solution is y.  Given any x, we can find a

terminal node in the tree where the outcome is x.  Now trace the path from this terminal node

back up through the tree to the initial node.  A chain satisfying the definition of Y*(2) for x and y

can be constructed simply by taking the sophisticated solution at each node on this path, ignoring

repetitions.  (This chain begins at x, ends at y, and only changes from one alternative to another

that beats it in the tournament.  For example, Figure 1.2 shows that alternative b is in Y*(2), with

chains a << c << b and c << b.)

We next show that Y*(2) 

f

 Y*(3).  If not, then there would be some y such that y 

0

Y*(2) but y 

ó Y*(3).  Let x be in Y*(3).  To satisfy the definition of Y*(2), there must be some

chain such that x = z  << z  << ... << z  = y.  This chain begins in Y*(3) and ends outside of

0

 

 

1

 

   

 

m

Y*(3), and so there must exist some k such that z

 

0 Y*(3) and z  ó Y*(3), but then z  << z

k-1

   

 

 

k

   

 

 

 

k-1

 

 

k

contradicts the definition of Y*(3).

Finally we show that Y*(3) 

f

 Y*(1).  Notice first that Y*(1) is nonempty (because binary

agendas and their sophisticated outcome always exist).  Now let y be any alternative in Y*(1) and

let x be any alternative not in Y*(1).  We claim that y >> x.  If not then we would have x >> y;

but then x would be the sophisticated outcome for a binary agenda, in which the first choice is

between x and a subtree that is itself a binary agenda for which the sophisticated outcome would

be y, and this conclusion would contradict the assumption x 

ó Y*(1).  So every y in Y*(1) beats

every x outside of Y*(1); and so Y*(1) includes Y*(3), which is the smallest nonempty set that

has this property.

Thus we have Y*(1) 

f

 Y*(2) 

f

 Y*(3) 

f

 Y*(1).  Q.E.D.

In the ABC paradox from the previous section, the top cycle includes all three alternatives

{a,b,c}.  If we add a fourth alternative d that appears immediately below c in each individual's

preference ranking (so that b >> d and c >> d but d >> a), then d is also included in the top cycle

for this example, even though d is Pareto-dominated by c. 

When the top cycle consists of a single alternative, this unique alternative is called a

Condorcet winner.  That is, a Condorcet winner is an alternative y such that y >> x for every

---