Stephen Eppley <seppley@alumni.caltech.edu>

Revised: January 29, 2003

Unless the set of alternatives is
fixed by nature, election outcomes may be manipulated by

adding alternatives to (or
removing alternatives from) the set of nominees. Satisfaction

of TN Tideman's criterion *independence of clone alternatives* (*ICA*) may be more

important
than satisfaction of other criteria such as *reinforcement*, *participation*
and

*cancellation* since voting procedures which fail * ICA* appear to be much more manipulable

than those which satisfy *ICA*. (The Borda procedure satisfies *reinforcement*,
*participation*

and *cancellation* but fails *ICA* and even fails a weaker criterion
*independence from exact
clone alternatives*.)

The existence of Condorcet-consistent
voting procedures which also satisfy a stronger

criterion *independence from similar alternatives* (*ISA*) is demonstrated, indicating

resistance to clone manipulation is robust under voter preference perturbations which

make *ICA*'s "clone" premise not strictly hold. Furthermore, it is established in
other

documents that voting procedures can satisfy not only * ICA* and * ISA* but also other

desirable
criteria such as *top cycle*, *monotonicity*,
*resolvability*,
*strong Pareto*,

*minimal
defense*, *truncation
resistance* and *immunity
from majority complaints*.

Considerable social choice
literature exists regarding manipulability of voting procedures

by voters misrepresenting their preferences. But this is not
the only kind of strategy by

which outcomes can be manipulated. If the set of
alternatives is endogenous (not fixed by

nature), outcomes can be manipulated by adding
alternatives to or removing alternatives

from the set of alternatives being voted upon. Such strategies may take various
forms:

One
is to add an alternative which reveals voters' collective preferences are cyclic

(Condorcet's paradox), with the hope or expectation that the procedure will resolve

the cycle favorably from the point of view of the manipulator. However,
this particular

strategy may sometimes be deemed benign, when there is no *a priori* reason to
believe

the additional preference information leads to an outcome worse
for the society.

Another such strategy requiring little
skill is to add (or remove) alternatives which are

"similar" to another already on the ballot. Institutional rules often make it easy for

individuals or for small minorities to add alternatives to the ballot; thus this
form of

manipulation may be easier
than coordinating a coalition to strategically misrepresent

preferences or gerrymandering of subsets of voters. A lone
individual can remove

an alternative (him/herself) when the context is electing
a person to an office, and

in some societies a lone individual can add
him/herself to the set of alternatives. In

many assemblies only two
members are needed to add an alternative, one to propose

and another to second the proposal. Since it is easy to generate
similar proposals

and since it may be fairly easy to find additional candidates who espouse policies

similar to those advocated by other candidates, and since a would-be manipulator

can
reasonably expect voters to be nearly indifferent between similar alternatives,

manipulation using similar alternatives may
occur frequently if the voting procedure

is not independent from similar alternatives.

A familiar
example of this strategy is when a political party nominates only one

candidate to run for an office even though they are divided over which party
member

is the best for the office (or divided over who has the best chance of winning),
when

the voting procedure in the general election is plurality rule, majority runoff,
Hare

(also known as Instant Runoff, Single Transferable Vote and the Alternative
Vote) etc.

The party's winnowing process (e.g., partisan primary elections) may itself be flawed--

sensitive to financial
resources, voter turnout, etc.--and manipulable. Thus reasonable

candidates can be deterred from competing for office, out of fear
that a similar candidate

who would otherwise win will be defeated and
a candidate who is worse elected.

(That outcome is commonly known as a "spoiled"
election.) As an example, consider

a hypothetical election
with three potential candidates: Gore and Bradley (Democrats)

and Bush (Republican). Suppose the Democrats believe
both Gore and Bradley would

beat Bush if either one of them ran against
Bush. In other words, they believe Gore and

Bradley are similar candidates according to our
definition in section 2. Under plurality

rule, however, the Democrats can expect the voters who prefer Gore and Bradley
over

Bush would split their votes and Bush would be elected, so they would nominate
only

one of them to run against Bush. This strategy may deprive the voters the
chance to

elect the best candidate. But given a voting procedure which is independent from

similar candidates, it would be unnecessary to nominate only one of them.
Indeed,

they would have incentives to nominate more than one: to increase the turnout of
the

party's supporters on election day, and to avoid putting all their eggs in one
basket.

For an example involving the Borda
voting procedure (which awards a point to
each

candidate for every candidate it
outranks, for each voter, then elects the candidate having

the most
points), consider a
spatial model involving two salient issues in which three

candidates *x*, *y* and *z* take
positions on the issues, and *y*'s positions are similar to *z*'s:

y

z

x

Suppose there are five voters,
each having preferences
regarding the possible positions.

Suppose * x* is at the ideal point of voters 1-3 and *y* is at the
ideal point of voters 4-5.

If only *x* and *y* compete, one may predict *x* would be chosen
under any voting procedure

since a majority prefer *x* over *y*. And since it is difficult,
if not impossible, to compare

intensities of voters' preferences, we have no reason to believe voters 4-5's preferences

for * y* over * x* should be accorded more weight than 1-3's preferences for
* x* over *y*. Thus

it is not only predictable that *x* would be chosen if only *x* and *y*
compete, it is reasonable

to choose *x* if only *x* and *y* compete. Suppose also
that voters 1-3 rank *y* over *z* since *y* is

slightly closer than *z* to their ideal. Thus voters 1-3 rank *x*
over *y* over *z*. And suppose

voters 4-5 rank *z* over *x*
since *z*
is much closer than * x* to their ideal. Thus voters 4-5 rank

*y* over *z* over *x*. The Borda procedure erroneously divines
stronger preferences by 4-5

for *y* over * x* than by 1-3 for
* x*
over * y* since 4-5 rank *z* between *y* and *x*, and thus
would

elect *y*. Thus Borda is
prone to manipulation by adding or removing similar alternatives

such as *z* to the
ballot.

*IECA*, *ICA* and
* ISA* (defined in section 3) are
weaker criteria than the modern form of

Kenneth Arrow's *independence of irrelevant alternatives* (*IIA*),
which requires the

outcome not change if a losing alternative is deleted from the voters' rankings.
That is

such a strong criterion that no reasonably democratic voting procedure which
tallies

rankings can always comply. *IECA*, * ICA* and * ISA* demand voting
procedures satisfy a

form of consistency having to do
with alternatives which are sufficiently similar to other

alternatives
that adding them to the ballot (or removing them) should not significantly

affect the outcome. If the outcome can be affected by adding or
removing similar

alternatives, the outcome may be easily manipulated in this manner, particularly if

voters are
unsophisticated or have their strategic options constrained by
accountability

to constituents who are unsophisticated.

We argue that since manipulation
of procedures which fail these criteria is so easy, they

are more important than the *reinforcement* criterion [Young,
1974], the *participation*

criterion [Moulin,
1988], and *cancellation*. *Reinforcement* requires that when the votes

of two separate groups of voters would each elect the same alternative, their votes

aggregated together must also elect that alternative. (Manipulation based on
failure

of *reinforcement* can be considered a special case of gerrymandering.)
But since

institutional rules can easily deny to a minority the power to choose between an at-large

vote and a
strategically-designed division of the voters into subsets, it can be made

impossible for a minority to exploit failure of *reinforcement*. (Another option, if a society

is concerned about manipulation due to failure of *reinforcement*, is to modify their voting

procedure so that whenever a voter subset's top cycle
includes the alternative which

would win the at-large tally, that at-large
winner is the choice of the subset.) Hence we

argue that satisfaction of *reinforcement* is of little importance for deterring manipulation.

As Hervé Moulin [1988] wrote, *reinforcement* is reasonable "when the overall voting

body is likely to
split into many subsets." We consider it unimportant when such
splitting

cannot occur or must occur or cannot be easily exploited by a minority.

Another argument for *reinforcement*
is its aesthetic appeal to our sense of rationality.

In other words, it is a consistency axiom. But * IECA* has the same appeal since voters'

indifference between exact clone alternatives provides no
additional information which

should affect the outcome. Thus * IECA* is also a
fundamental consistency axiom. To a

lesser extent, * ICA* and * ISA* also share that appeal to consistency.

We also argue that *IECA*, *ICA* and
* ISA* are
more important than *participation*

[Moulin,
1988]. *Participation* requires no voter must ever prefer the outcome

given her abstention (non-participation) more than the outcome given her sincere vote.

But when a voter has information about other
voters' preferences and strategies which

suggests she would likely prefer the outcome
given abstention over the outcome given

her sincere vote,
that information should suffice to suggest a voting strategy better than

abstention. Thus it seems myopic to focus on abstention versus sincere voting
and

ignore other strategies, particularly strategies where the only misrepresentation
is

expression of indifference between a compromise and a preferred
alternative.

Our argument
against requiring satisfaction of *participation* may be less persuasive

when considering unsophisticated voters, but they are also the most
vulnerable to

being manipulated by addition or deletion of similar alternatives. There is also
the

relevant empirical question regarding whether a significant number of voters would

choose not to participate simply due to general knowledge that the
voting procedure

does not always satisfy *participation*; the answer may well be that insignificant numbers

of voters abstain due to this occasional failure and that other factors,
such as other

flaws in the voting procedure would be much more significant.
For both these reasons,

it seems premature to assert without empirical evidence that *participation* is as
important

as criteria such as *IECA*, *ICA* and *ISA*.

Here are three examples which demonstrate violations of
*IECA*, *ICA* and * ISA* by the

Borda procedure. For greater clarity, the first and second examples assume voters
are

allowed to vote indifference. Those examples could be easily modified,
however, to

demonstrate Borda violations even when votes must be strict rankings of the
alternatives

(except of course that technically no alternatives are called exact clones if
voters cannot

express indifference).

Example 1.1: "Spoiling" under Borda

11 voters rank four alternativesw,x,y,zas follows:

74wx,yx,yzzw

In example 1.1, *x* and * y* can be considered exact
clones since every voter is indifferent

between them. Borda
elects *w* with (7×3)+(4×0)=21
points, since *x* and *y*
have only

(7×1.5)+(4×2.5)=20.5
points and *z* has even fewer (4). But Borda would elect *x* if *y*

were not on the
ballot (and would elect *y* if * x* were not on the ballot) since (7×1)+(4×2)

exceeds (7×2)+(4×0).
In a scenario where *x* and * y* are similar to each other but not

exact clones, the better of the two might be deterred from competing, implying a loss

for society.

Example 1.2: "Relevant turkeys" under Borda

7 voters rank four alternativesw,x,y,zas follows:

5 |
2 |

w |
x |

x |
y,z |

y,z |
w |

In example 1.2, *y* and * z* can be considered exact
clones since every voter is indifferent

between them. Note *y* and *z* are ranked last by most voters
and next to last by the other

voters. Thus it seems reasonable to say neither *y* nor *z*
should be elected (and under

most voting procedures their presence on the ballot would not affect the
outcome).

Borda elects *x* with (5×2)+(2×3)=16
points, since *w* has
only (5×3)+(2×0)=15 points

and *y* & *z* have only (5×0.5)+(2×1.5)=5.5
points. But Borda would elect *w* if *z* were

not on the ballot since (5×2)+(2×0)
exceeds (5×1)+(2×2).
This implies Borda outcomes

can be affected by the presence on the ballot of sure-losers
("turkeys" in Gary Cox'

terminology).

Example 1.3: "Rich party problem" under Borda

5 voters rank three alternativesx,y,y'as follows:

32xyyy'y'x

In example 1.3, *y* and * z* are
deemed clones since no voter ranks any alternative between

them. (That is, every voter who rank * x* over * y* also ranks *
x* over *y'*, every voter who ranks

*x* over *y'*
also ranks * x* over *y*, every
voter who ranks * y* over * x* also ranks *y'* over *x*, and

every voter who ranks *y'* over * x* also
ranks *
y* over *x*.) Borda elects *y* with (3×1)+(2×2)=7

points, since *x*
has only 3×2=6 points and *y'* has only 2×1=2
points. But *
x* would win if

*y'* were not on the ballot (3>2). Clearly the "*y* &
*y'*" minority party has an incentive to

place both *y* and *y'* (and as many clones of * y* as possible) onto the ballot.
(Note that

this is like the problem illustrated above in the two-issue spatial model.)
Similarly, the

"*x*" party has an incentive to place as many clones of *x*
onto the ballot as possible,

so elections under Borda could become farces.

Examples showing the Copeland procedure fails *IECA*,
*ICA* and *
ISA* and the Simpson-

Kramer procedure fails * ICA* and * ISA* can easily be
constructed.

*ICA* is essentially equivalent to a criterion promoted by
TN Tideman, TM
Zavist,
and

others. *IECA* is weaker and * ISA* is
stronger. *IECA* is the easiest of the three criteria

to justify since the massive indifference between exact clone alternatives means the

voters are not really providing any additional information about their preferences
which

should
reasonably affect the outcome. *ICA* is nearly as easy to justify, differing from

*IECA* only in that voters need not be
indifferent between alternatives as long as they

do not rank other alternatives between them; this is a strong indicator
that these

"clone" alternatives are indeed similar to each other and thus the
voters' preference

intensities between clones are likely milder than between clone and
non-clone.

*ISA* is much broader than *ICA*, and
variants of * ISA* which cannot together be satisfied

could be plausibly defined. These considerations raise the
question whether * ISA* is

overly broad, which is not answered
here. However, even if * ISA* is deemed too

strong to require, voting procedures which satisfy *ISA* demonstrate
their satisfaction

of *ICA* is robust. In practice *ICA*'s premise would rarely strictly hold since with many

voters there could easily be a few
odd voters who rank dissimilar alternatives between

similar ones, and thus robust satisfaction of * ICA* is important when
evaluating the ease

of manipulability.

First some notational conventions. See the
document "Set
Operators and Binary Relations"

for an explanation of the mathematical symbols used below. (Note that some
symbols may

not display properly when viewed with a browser which does not
support HTML 4.0 or

if the
browser is not configured to display the "Symbol" font.)

Let

denote a finite non-empty set of voters {1V,2,3,...,n}.

Letdenote a non-empty set of potential alternatives.A

LetB, a finite non-empty subset of, denote the alternatives nominated to the ballot.A

The set of nominees *B* is determined endogenously under some unspecified
procedure.

For all non-empty

Z⊆, let Rankings(AZ) denote the set of all possible

non-strict rankings (also called weak orderings) of the alternatives inZ.

Each voter is assumed to have transitive asymmetric preferences regarding the alternatives

in * A*. Each voter casts a ballot by expressing a ranking of

the ballot cast by voter

voters express strict rankings (linear orderings) because, even if it is reasonable to assume

every voter sincerely has strict preferences, there may be strategic incentives to report

indifference, and there may be unsophisticated failure to report all sincere strict preferences

since a large set of nominees would make that tedious. Furthermore, it is not

desirable to prevent the voters from voting indifference strategically, since some strategies

involving insincere indifference may deter or thwart other voters' socially harmful strategies.

See the document discussing the

to be a strict ranking could deter voters from voting if the set of nominees is large.)

Let

denote the set of voters' ballots. For allRa,b∈B, let(Ra,b) denote the

ballots inwhich rankRaoverb. Thus #(Ra,b) is the number of voters who

rankedaoverb.For all finite non-empty

B⊆and allAC⊆B,Cis a set of exact clone

alternatives withinBgivenif and only if both of the following conditions hold:R(1) For all

c,c'∈C,(Rc,c') = φ and(Rc',c) = φ.

(2) For allc∈Cand allx∈B\C,(Rx,c) ≠ φ or(Rc,x) ≠ φ.

(Condition 1 says every voter
expresses indifference between exact clones. Condition 2 is

an innocuous technical condition which implies an exact clone
set is not contained in a larger

exact clone set. This avoids
a problem in some rare scenarios involving both pairwise ties

and massive indifference. It
refers to an alternative which, though technically might be

considered outside an exact
clone set, is itself an exact clone of those in the exact clone

set. Would-be manipulators would consider such an alternative an
exact clone too, and

we are only interested in ensuring their manipulation of the nominations of an exact clone

set cannot affect the election
of alternatives they would not consider exact clones. Thus

condition 2 is innocuous, and means that a strict subset of a set of exact
clones is not

called a set of exact clones.)

For all finite non-empty

B⊆and allAC⊆B,Cis a set of clone alternatives

withinBgivenif and only if both of the following conditions hold:R(1) For all

c,c'∈Cand allx∈B\C,(Rx,c) =(Rx,c') and(Rc,x) =(Rc',x).

(2) For allc∈Cand allx∈B\C,(Rx,c) ≠ φ or(Rc,x) ≠ φ.

(Condition 1 says every voter who
ranks a clone over a non-clone ranks every clone over

that non-clone, and every voter who ranks a non-clone over a clone ranks
that non-clone

over every clone. Condition 2 is
an innocuous technical condition which implies *C* is not

contained in a larger set of exact clones,
which permits condition 1 to be slightly relaxed

compared to Tideman's definition of clones.)

Since we are discussing the effect on outcomes when
the set of nominated alternatives *B*

is changed, the notation must be able to indicate deletion of alternatives from *B*
and * R*:

For all non-empty *Z* ⊆
* A* and all

In other words,

Thus

That is,

We are primarily interested in voting procedures
which leave little or nothing to chance.

(Completely eliminating chance
would require sacrificing * anonymity* or *neutrality*,

desirable
democratic properties which require no voters nor alternatives be
specially

privileged.) However, we use a framework general enough to encompass both

deterministic and probabilistic voting procedures.

A **lottery**
is a #* A*-tuple of real numbers such that each component corresponds to

an alternative in

components is 1. For all lotteries

of

all lotteries

(1) For all *x* ∈
* A*, 0 ≤

(2) Σ

*L _{x}* is interpreted as the probability

elected with certainty, and

A **voting scheme** is
a function *f* which maps a non-empty *Z* ⊆
** A** and a set of

voters' rankings

(1)

f_{x}(Z,) = 0 for allR, allA, all non-emptyRZ⊆and allAx∈\AZ.

(2)f_{x}(Z,) =R^{Z}f_{x}(Z,) for allR, allA, all non-emptyRZ⊆, and allAx∈.A

Just as *L _{x} * denotes the
component of lottery

certainty. If

fair random mechanism will determine the outcome in accordance with the probabilities.

A voting scheme

all non-empty

it is not deterministic.

Condition 1 of the definition of
voting scheme means no
alternative outside * Z* will be

elected. Since we are discussing the effect of attempts to
manipulate by adding or

removing alternatives, the notation needed to
encompass the concept of neglect of

alternatives so outcomes given any subsets
of * A*
can be compared. This is why the

definition of voting scheme includes as a parameter the subset of alternatives which can

be elected, which (after Kenneth Arrow) we call the

a mild restriction which simplifies the notation by requiring the lottery must not depend

on expressed preferences regarding alternatives outside the feasible subset. This

avoids potential complications which may otherwise arise if voters rank alternatives

which are not in the feasible subset and allows us to more easily model attempts to

manipulate outcomes by manipulating nominations.

** Independence from Exact Clone Alternatives
**(

A voting scheme

all

and all

*IECA* demands that the probability of
election of an alternative must
be unaffected by

addition or removal of exact clones, as long as the alternative is
not itself one of the exact

clones and at least one of the exact clones is nominated. Preferences
regarding additional

exact clones must be irrelevant to the outcome. This
can be viewed as a fundamental

consistency axiom. Note that since the sum of probabilities over all
alternatives must

total 1, satisfaction of * IECA* also implies Σ_{(c ∈
C)}*
f _{c}*(

** Independence from Clone Alternatives
**(

A voting scheme

all

and all

*ICA* demands that as long as at least one clone is nominated,
additional clones must be

irrelevant to the outcome, except
possibly to elect a "better" clone instead of a "worse"

clone. Note that since the sum of probabilities over all
alternatives must total 1,

satisfaction of * ICA* also implies Σ_{(c ∈
C)}*
f _{c}*(

Clearly any set of exact clone alternatives is also a set of clone
alternatives. Therefore,

satisfaction of * ICA* implies satisfaction of *IECA*, and failure of *
IECA* implies failure of *ICA*.

Turning now to the definition of "similar" (near-clone) alternatives, an intuitive way to

relax the
definition of clones is to only require that in every pairing of a similar
alternative

versus an alternative outside the similar set, the "majority
preference" relation must

remain invariant when any similar alternative is substituted
for the one in the pairing:

Let Pairs denote the set of
all possible ordered pairs of alternatives in ** A**. That
is,

Pairs = {

Let Majorities(* R*)
denote the subset of ordered pairs {

that #

for all

For all finite non-empty *B* ⊆
* A* and all

within

and all

(1) *(x,c)* ∈
Majorities(* R*) if and only if

(2)

Note the "only if" construction instead of the usual "if and
only if." Using "if and only if"

would produce such a broad definition that it would be impossible for any
reasonable

voting scheme to satisfy independence. Thus an additional restriction involving other

aggregate
properties needs to be imposed.

Given

,Aand finite non-emptyRZ⊆, and abbreviatingAk= #Z, call

the sequencez_{1},z_{2},...,za_{k}majority cyclic permutationofZgivenR

if and only ifZ= {z_{1},z_{2},...,z_{k}} and(z_{k},z_{1})∈ Majorities()R

and(z_{j},z_{j+1})∈ Majorities() for allRj∈ {1,2,...,k-1}.Given

,A, and finite non-emptyRZ⊆, let majoritycycles(AZ,) denoteR

the set of subsets of alternatives {MCsuch thatMCis a non-empty subset

ofZand there exists a majority cyclic permutation ofMCgiven}.R

Given

,A, and finite non-emptyRZ⊆, let majorities(AZ,) denote theR

set of ordered pairs of alternatives {(x,y)∈ Pairs such that there exists a

majority cyclic permutation ofZgivenin whichRximmediately precedesy}.Given

,A, and non-emptyRZ⊆, let min(AZ,R) denote the set of ordered

pairs of alternatives {(x,y)∈ Pairs such that(x,y)∈ majorities(Z,)R

and #(Rx,y)<#(Rz,w) for all(z,w)∈ majorities(Z,)}.R

When * R* is
clear from the context, we abbreviate majoritycycles(

and min(

Note that majorities(*Z*) and
min(*Z*) do not
include all "majorities" which are identifiable

in *Z*. Only those pairs of alternatives which are adjacent in a majority cyclic permutation

of * Z* are contained in majorities(*Z*) and
min(*Z*).
Two examples illustrate this:

(2.11.1) Given the relations

aMb,bMc, andc~a,majorities({a,b,c}) = Ø andmin({a,b,c}) = Ø because there are no majority cyclic permutations of {a,b,c}.(2.11.2) Given the relations

aMb,bMc,cMd,dMa,aMc, anddMb,majorities({a,b,c,d}) = {(a,b),(b,c),(c,d),(d,a)}. Without more information,min({a,b,c,d}) cannot be specified, but it is always the case thatmin(Z,R) ⊆majorities(Z,R). Note that (a,c) and (d,b) are not inmajorities({a,b,c,d}) and are not inmin({a,b,c,d}), even thoughaMcanddMb, because there are no majority cyclic permutations of {a,b,c,d} in whichaimmediately precedescor in whichdimmediately precedesb. For instance (trying to find a permutation in whichaimmediately precedesc),acdabcdis not a majority cyclic permutation of {a,b,c,d}because its alternatives are not all distinct, andacdis not a majority cyclic permutation of {a,b,c,d} because it does not include all four alternatives in {a,b,c,d}. However, even though (a,c) ∉majorities({a,b,c,d}), (a,c) ∈majorities({a,c,d}).

The following two definitions are not technically necessary for a definition
of an ISA criterion

which is stronger than ICA, but will be used to broaden
similarity in order to strengthen ISA

even further.

Definition (2.12): Given

A,Rand non-empty Z ⊆A, and abbreviating k = #Z, the sequence x_{1},x_{2},...,x_{k}is acyclic permutationof (Z,R) if and only if x_{1}, x_{2}, ..., x_{k}are distinct alternatives in Z and [x_{k}Mx_{1}or x_{k}~x_{1}] and [x_{j}Mx_{j+1}or x_{j}~x_{j+1}for all j ∈ {1,2,...k-1}]}. GivenA,R, and non-empty Z ⊆A, let(Z,cyclesR) denote the set of subsets of alternatives {C such that C is a non-empty subset of Z and there exists a cyclic permutation of (C,R)}.Definition (2.13): Let τ(Z,

R) denote thetop cycleof (Z,R). Formally, givenA,R, and non-empty Z ⊆A, τ(Z,R) is the set of alternatives {x ∈ Z such that [for all z ∈ Z such that zMx, there exists a C ∈cycles(Z,R) such that x,z ∈ C]}.

When *R* is
clear from the context, we abbreviate *cycles*(Z) and τ(Z).

Definition (2.14): For all x,y ∈

Aand any set S which is either a set of alternatives or a set of ordered pairs of alternatives such that y is nowhere in S, let(S,x,y) denote the set obtained by substituting y for x everywhere x appears in S.substituteDefinition (2.15): A set Y is a

similar setof (Z,R) if and only if the following three conditions hold:(2.15.1) Y ⊆ Z ⊆

Aand #Y > 1.(2.15.2) For all y,y' ∈ Y and all x ∈ τ(Z)\Y, [y

Mx if and only if y'Mx] and [xMy if and only if xMy'].(2.15.3) For all y,y' ∈ Y and all MC ∈

majoritycycles(τ(Z),R) such that MC∩Y={y},substitute(min(MC),y,y') =min(substitute(MC,y,y')).

Condition 2.15.1 restricts similar sets to sets
containing at least two of the alternatives in Z, an obvious requirement.
Condition 2.15.2 embodies our basic intuition for broadening of clone sets; it
restricts similar sets by requiring that for every alternative x outside a
similar set, the *M* and ~ aggregate relations between x and every similar
alternative are the same. (The restriction has been relaxed here by
ignoring relations outside the top cycle, since our purpose is to establish the
robustness of ICA by demonstrating the existence of voting procedures which
satisfy as strong an independence criterion as possible.) As
mentioned earlier, 2.15.2 does not restrict similarity enough to allow existence
of voting schemes which are independent from similar alternatives, which is why
condition 2.15.3 is imposed. Condition 2.15.3 restricts similar sets
further by requiring that additional aggregate properties of *R*, the
smallest majorities in every majority cycle containing exactly one of the
similar alternatives, are the same when any similar alternative is substituted
in those majority cycles. (Like 2.15.2, 2.15.3 has been relaxed by
ignoring cycles outside the top cycle in order to strengthen the independence
criterion as much as possible to establish the robustness of ICA.)

It is easy to see that every clone set of (Z,*R*) is a similar set of (Z,*R*).
The alternatives in a clone set remain similar under small perturbations of *R*,
since similarity is based on aggregate properties of *R* which are
insensitive to small perturbations.

The following statements hold for all non-empty Z ⊆ *A*:

(2.15.4) If #Z > 1, then Z is (trivially) a similar set of (Z,

R).(2.15.5) If #τ( Z,

R) > 1, then τ( Z,R) is a similar set of (Z,R).(2.15.6) If #(Z\τ( Z,

R)) > 1, then Z\τ( Z,R) is a similar set of (Z,R).

The following definition, which provides a measure
of the relative "clonishness" of two

subsets of alternatives, is
needed for a mild technical restriction in ISA, analogous to

the innocuous
technical restriction in ICA, to avoid a problem in some rare scenarios

involving indeterminism:

Definition (2.16): Given

A,R, Z ⊆A, Y ⊆ Z, and X ⊆ Z such that X\Y ≠ ∅, let(Y,X,clonescoreR) denote maximum_{(over x ∈ X\Y)}of #{i∈Nsuch that there exists y,y' ∈ Y such that [xP_{i}y and not xP_{i}y'] or [yP_{i}x and not y'P_{i}x]}. GivenA,R, X ⊆A, and Y ⊆Asuch that X\Y ≠ ∅ and Y\X ≠ ∅, X ismore clone-likethan Y with respect toRif and only ifclonescore(X,Y,R) <clonescore(Y,X,R).

Note that if Y is a clone set of (Z,*R*),
it follows immediately from condition 2.6.2 of the definition of clone set that *clonescore*(Y,X,*R*)
= 0 for all X ⊆ Z such that X\Y ≠
∅). Thus, no subset of alternatives is more clone-like than
a clone set.

We can now formally state the ISA criterion:

Criterion (2.17):

Independence from Similar Alternatives(ISA):

A voting schemefis independent from similar alternatives if and only if

f_{x}(Z,R) =f_{x}(Z\Y',R^{Z\Y'}) for allA, allR, all non-empty Z ⊆A, all Y such that Y is a similar set of (Z,R), all Y'⊂ Y, and all x ∈A\Y such that [for all X ⊆ Z\Y such that x ∈ X and all non-empty Y_{s}⊂ Y such that X∪Y_{s}is a similar set of (Z,R),Y is more clone-like than X∪Ywith respect to_{s}R].

Lemma: Satisfaction of ISA implies satisfaction of ICA.

Proof: Suppose Y is a clone
set of (Z,*R*) and *f* is a voting scheme which satisfies ISA.
Since every clone set of (Z,*R*) is a similar set of (Z,*R*),
satisfaction of ISA implies that *f*_{x}(Z,*R*) = *f*_{x}(Z\Y**',***R*^{Z\Y'})
for all Y**'** ⊂ Y
and all x ∈ *A*\Y such that [for all X ⊆
Z\Y such that x ∈ X and all non-empty Y_{s} ⊂
Y such that X∪Y_{s} is a similar set of (Z,*R*),
Y is more clone-like than X∪Y_{s} with
respect to *R*]. To demonstrate satisfaction of ICA, we need to show
that *f*_{x}(Z,*R*) = *f*_{x}(Z\Y**',***R*^{Z\Y'})
for all Y**'** ⊂ Y
and all x ∈ *A*\Y such that [there exists no y
∈ Y such that xI_{i}y for all *i* ∈
*N*]. Since for all x ∉ Z, *f*_{x}(Z,*R*)
= 0 and *f*_{x}(Z\Y**',***R*^{Z\Y'}) = 0, we
need only establish the following statement:

For all x ∈ Z\Y such that [there exists no y ∈ Y such that xI

_{i}y for alli∈N] and all X ⊆ Z\Y such that x ∈ X and all non-empty Y_{s}⊂ Y such that X∪Y_{s}is a similar set of (Z,R), Y is more clone-like than X∪Y_{s}with respect toR.

Assume x ∈
Z\Y and there exists no y ∈ Y such that xI_{i}y
for all *i* ∈ *N* and X ⊆
Z\Y and x ∈ X and Y_{s} is a non-empty
strict subset of Y and X∪Y_{s} is a similar
set of (Z,*R*). We need to establish that Y is more clone-like than X∪Y_{s}
with respect to *R*.

Since x ∈
Z\Y and x ∈ X, (X∪Y_{s})\Y
≠ ∅. Also, since X ⊆
Z\Y and Y_{s} ⊆ Z, X∪Y_{s}
⊆ Z. Also, since Y is a clone set of (Z,*R*),
Y ⊆ Z. Given the conclusions of the last
three statements, *clonescore*(Y,X∪Y_{s},*R*)
is defined, and since Y is a clone set, *clonescore*(Y,X∪Y_{s},*R*)
= 0.

There are two cases to consider:

Case 1: *clonescore*(X∪Y_{s},Y,*R*)
> 0. In this case, it is obvious that Y is more clone-like than X∪Y_{s}
with respect to *R*.

Case 2: *clonescore*(X∪Y_{s},Y,*R*)
= 0. We want to show that this case contradicts the assumptions.

So the only x ∈
*A*\Y for which *f*_{x}(Z,*R*) need not equal *f*_{x}(Z\Y**',***R*^{Z\Y'})
are those x for which there exists an X∪Y_{s}
containing x such that X∪Y_{s} is a similar
set and *clonescore*(X∪Y_{s},Y,*R*)
= 0.

Since the technical restriction in
ISA ("for all X ⊆ Z\Y such that x ∈
X and all non-empty Y_{s} ⊂ Y such that X∪Y_{s}
is a similar set of (Z,*R*), Y is more clone-like than X∪Y_{s}")
is not identical to the technical restriction in ICA ("there is no y ∈
Y such that {x,y} is an exact clone set"), it may not be obvious that ISA
is a stronger criterion than
ICA. But this is indeed the case, since when Y is a clone set, the
restriction condition in ICA holds if the restriction condition in ISA
holds. Suppose that Y is a clone set and x ∉ Y
and {x,y'} is an exact clone set for some y' ∈ Y;
then Y\{y'} is not more clone-like than {x,y'} because

maximum_{(over x ∈
X\Y)} of #{*i* ∈ *N* such that [xP_{i}y
for all y ∈ Y] or [yP_{i}x for all y ∈
Y]} is less than maximum_{(over y ∈ Y\X)} of
#{*i* ∈ *N* such that [yP_{i}x for
all x ∈ X] or [xP_{i}y for all x ∈
X]}

#{*i* ∈
*N* such that [xP_{i}y for all y ∈
Y\{y'}] or [yP_{i}x for all y ∈ Y\{y'}]} =
0. Therefore, since every clone set is also a similar set,
satisfaction of ISA implies satisfaction of ICA and IECA, and failure
of IECA or ICA implies failure of ISA.

There are other ways similar sets could have been
defined (e.g., by replacing x#y with x#y-y#x and replacing z#z' with z#z'-z'#z in the definition of *min*(MC,*R*))
which would make it possible to satisfy some variant of ISA but
not the ISA defined here. So it could be controversial to insist upon satisfaction of
the ISA defined here. But the
purpose of ISA is primarily to strengthen the argument for requiring satisfaction of
ICA by showing that manipulation resistance is robust.

The following properties of similar (clone, exact clone) sets and majority cycles will be useful when proving subsequent lemmas and theorems:

**Lemma (2.18):** (**Splittability** of
majority cycle) If Y is a similar set of (Z,*R*) and MC ∈
*majoritycycles*(Z,*R*)
and #(MC∩Y)__>__1 and (x,x') ∈
*min*(MC,*R*)
and Y∩{x,x'}≠{x,x'},
then there exists an MC_{1} ∈ *majoritycycles*(Z,*R*) such that
#(MC_{1}∩Y)=1 and (x,x') ∈
*min*(MC_{1},*R*). (Proof in
Appendix A1.)

Lemma 2.18 states that any majority which is not a pair of similar alternatives and which is smallest in a majority cycle containing at least one similar alternative is also smallest in a majority cycle containing exactly one similar alternative.

**Lemma (2.19):** (**Substitutability** of similar
alternative) If Y is a similar set of (Z,*R*) and y,y' ∈
Y and MC ∈ *majoritycycles*(Z,*R*) and MC∩Y={y}, then
*substitute*(MC,y,y') ∈ *majoritycycles*(Z,*R*).
(Proof in appendix A1.)

Lemma 2.19 states that for any set
of alternatives which is a majority cycle and contains exactly one alternative
of a similar set, the set obtained by substituting any similar alternative is
also a majority cycle. This is important in 2.15.3 of the definition of
similar set, which uses the expression *min*(*substitute*(MC,y,y')),
since the definition of *min*() requires that its argument is a majority
cycle.

**Lemma (2.20):** For any sets Y, Z, and Z_{s} such
that
Y is a similar (clone, exact clone) set of (Z,*R*) and Z_{s}∩τ( Z,*R*)
≠ Ø
and #(Y∩Z_{s})>1, Y∩Z_{s} is a similar (clone, exact clone)
set of (Z∩Z_{s},*R*). (Proof
in appendix A1.)

Lemma 2.20 essentially states that
when Y is a similar set of Z, Y∩Z_{s} is a
similar set of Z∩Z_{s}, assuming a couple of
obvious restrictions. The restriction about
the top cycle could be dropped and the lemma would still hold for
clone sets and exact clone sets. Also, without the restriction about the
top cycle, the lemma would hold for similar sets if the definition of similarity were narrowed by
replacing "τ(Z)" with "Z"
everywhere in the definition of similar set. But we prefer to define similar sets
broadly in order to make ISA stronger.

We seek voting schemes which satisfy ISA (and thus ICA and IECA). Such voting schemes are considered to be "completely" independent from similar alternatives. In particular, we seek such voting schemes which are Condorcet-consistent. It is useful to first describe related properties involving correspondences, and to define some notation denoting the breaking of ties of a correspondence by applying other correspondences and/or a voting scheme.

Definition (3.1): A

correspondenceis a functiong: 2\Ø x^{A}R^{n}→ 2\Ø which satisfies the following conditions:^{A}(3.1.1)

g(Z,R) ⊆ Z for allA, allR, and all non-empty Z ⊆A.(3.1.2)

g(Z,R') =g(Z,R) for allA, allR, all non-empty Z ⊆A, and allR'such thatR'=R.(3.1.3)

g(Z,R^{Z}) =g(Z,R) for allA, allR, and all non-empty Z ⊆A.

A correspondence takes as its arguments a non-empty subset of the alternatives and a profile of voters' rankings and returns a non-empty subset of the alternatives. Condition 3.1.1 means no alternative outside Z will be chosen. Condition 3.1.2 means the set of chosen alternatives depends only on the voters' rankings. One implication is that correspondences are deterministic, leaving nothing to chance. Condition 3.1.3 means that a correspondence neglects alternatives outside the feasible set Z; the set of chosen alternatives is independent of neglected alternatives.

A correspondence already mentioned is the top cycle
τ(Z,*R*).

Definition (3.2): A correspondence

gispartially independentfrom similar (clone, exact clone) alternatives if and only if the following conditions hold for allA, allR, all non-empty Z ⊆A, all Y such that Y is a similar (clone, exact clone) set of (Z,R), and all Y_{s}⊂ Y:(3.2.1)

g(Z,R) ∩A\Y =g(Z\Y_{s},R^{Z\Y}s) ∩A\Y(3.2.2)

g(Z,R) ∩ Y = Ø if and only ifg(Z\Y_{s},R^{Z\Y}s) ∩ Y = Ø

Condition 3.2.1 requires that for all non-similar (non-clone, non exact clone) alternatives x (i.e., x ∈ Z\Y), x is chosen when no alternatives in Y are neglected if and only if x is chosen when any strict subset of Y is neglected. Condition 3.2.2 requires that at least one alternative in Y is chosen when no alternatives in Y are neglected if and only if at least one alternative in Y is chosen when any strict subset of Y is neglected.

A correspondence which is partially independent and which usually selects a singleton in some applications, (e.g., large public elections) can be considered "practically independent" in those applications since a tie-breaker would rarely be required. However, to demonstrate complete independence we must consider those cases where the chosen set contains more than one alternative, where a tie-breaker would be needed.

Definition (3.3): Let

g//fdenote the function defined with respect to two functionsgandf, wheregis a correspondence andfis either a correspondence or a voting scheme, which first appliesgand then appliesfto the subset chosen byg. Formally,(

g//f)(Z,R) =f(g(Z,R),R).

Depending on whether *f* is a correspondence
or a voting scheme, *g*//*f* is a correspondence or a voting
scheme. The
notation can be extended to *g*_{1}//*g*_{2}//*g*_{3}//...//*f*
where *g*_{1}, *g*_{2}, *g*_{3}, ... are
correspondences and *f* is either a correspondence or a voting scheme.
Left-to-right precedence is implied; for instance *g*_{1}//*g*_{2}//*f*
= (*g*_{1}//*g*_{2})//*f*.

We also define the notation [*g*]
to indicate that a correspondence *g* is repeated until convergence; i.e.,
until further repetition would eliminate no more alternatives. To illustrate the meaning of [*g*] we could abuse
notation by writing
[*g*] = *g*//*g*//*g*//*g*//*g*//... Instead
we define [*g*] formally as follows:

Definition (3.4): Let [

g] denote the correspondence defined inductively with respect to a correspondencegby the following rules:(3.4.1) For all positive integers r, let

g_{r}be the correspondence defined inductively with respect to a correspondencegby the two rules:(3.4.1.1)

g_{1}=g.(3.4.1.2) For integer r>1,

g_{r}=g_{r-1}//g.(3.4.2) Let r'(

g,Z,R) denote the smallest positive integer r such thatg_{r}(Z,R) =g_{r+1}(Z,R).(3.4.3) Abbreviating r' = r'(

g,Z,R), [g] is the correspondence such that [g](Z,R) =g_{r'}(Z,R) for allA, allR, and all non-empty Z ⊆A.

**Lemma (3.5):** r'(*g*,Z,*R*)
__
<__ #Z for all correspondences *g*, all *A*, all *R*, and all
non-empty Z ⊆ *A*.
(Proof in appendix A1.)

The // and [] notation is credited to Bruce Anderson, whose definitions are slightly different in that they informally stipulate that preferences regarding eliminated alternatives are neglected. In our context, where voting schemes and correspondences are required to neglect alternatives not in their feasible subset of alternatives, it is not necessary to add that stipulation.

The Condorcet-consistent ISA-consistent voting scheme whose existence is established in the following sections takes the form Ψ//Dissimilar(Ψ), where Ψ is a correspondence which satisfies the top cycle criterion and is partially independent from similar alternatives and Dissimilar(Ψ) is a voting scheme which satisfies ISA and may involve some randomness.

Criterion (3.6):

Top Cycle(TC). A correspondencegsatisfies top cycle if and

only ifg(Z,R) ⊆ τ(Z,R) for allA, allR, and all non-empty Z ⊆A. A voting schemef

satisfies top cycle if and only iff_{x}(Z,R) = 0 for allA, allR, all non-empty Z ⊆A,

and all x ∉ τ(Z,R).

**Lemma (3.7):** If * g*_{1} and
*g*_{2} are correspondences which satisfy top cycle and are partially independent from similar alternatives,
then *g*_{1}//*g*_{2}
is a correspondence which satisfies top

cycle and is partially independent from similar
alternatives. (Proof
in appendix A1.)

**Lemma (3.8):** If * g* is a correspondence
which satisfies top cycle and is partially independent from similar alternatives, then [*g*] is a
correspondence which satisfies top cycle and is partially independent from similar
alternatives. (Proof in
appendix A1.)

**Lemma (3.9):** If *g* is a correspondence
which satisfies top cycle and is
partially independent from similar alternatives, and *f* is a voting scheme which satisfies ISA, then *g*//*f* and [*g*]//*f* are
voting schemes which satisfy top cycle and ISA. (Proof
in appendix A1.)

In this section we define a correspondence which satisfies top cycle, is partially independent from similar (clone, exact clone) alternatives, and which would rarely need a tie-breaker in large public elections. First we define a useful subset of the alternatives, obtained by ignoring the smallest majority (or majorities) of every majority cycle and selecting the alternatives which are unbeaten pairwise in the set of non-ignored majorities:

Definition (4.1): Given

A,R, and non-empty Z ⊆A, let ψ_{1}(Z,R) denote the set of alternatives {x ∈ Z | for all z ∈ Z such that zMx, there exists at least one MC ∈majoritycycles(Z,R) such that (z,x) ∈min(MC,R)}.

Note the similarity between the
definition of ψ_{1} and the definition
of τ. The clause beginning with "for
all z ∈ Z such that z*M*x" would simply
embody the majority rule heuristic if the

"there exists..." condition
were replaced by the *false* condition. Condorcet's paradox tells

us that
the majority rule heuristic alone would be
too strong since it could result in the

elimination of every
alternative. Relaxing the heuristic when there exists a majority cycle

MC
such that "(z,x) ∈ *min*(MC,*R*)" guarantees
ψ_{1} will
never be empty: Since due to cycles

it is not always possible to honor all
majority opinions,
a remedy
is to ignore the smallest

majority of every majority cycle.
The
non-ignored majorities will always be transitive

so ψ_{1}
cannot be empty. Appendix A2 provides an example
illustrating the calculation of ψ_{1}.

Definition (4.2):

Ψand <β>Ψ_{1}(4.2.1) Ψ

_{1}is the correspondence defined by the rule Ψ_{1}(Z,R) = ψ_{1}(Z,R) for allA, allR, and all non-empty Z ⊆A.(4.2.2) Ψ is the correspondence [Ψ

_{1}].

In 1785 the Marquis
de Condorcet of the French Academy of Sciences proposed a voting

correspondence that has been interpreted by H
Peyton Young as being similar to Ψ_{1}.

According to Young, when there is
no Condorcet winner "... *one successively deletes
from that opinion the
propositions that have the least plurality, and one adopts the
opinion from
those that remain.*" Or, as translated by Ian
McLean, "...

successively exclude from it the propositions with the lowest plurality.

this procedure is equivalent to a non-iterative minimax since it chooses the alternative

whose largest pairwise opposition is smallest. Unfortunately, Condorcet's writing was

terse and ambiguous. For one thing, it is not clear how he measured the size of each

proposition's plurality. The word "plurality" is often interpreted now-a-days as the margin

of difference between two counts, but French dictionaries of his time defined plurality as

the larger of the counts. (See the Dictionnaire de L'Académie Française, 1694: "plus grande

quantité, plus grand nombre.") On the other hand, Condorcet estimated the probability

that a jury reaches the correct decision as a function of the margin of difference between

two counts. McLean pointed out some of these ambiguities: Translating from p. lxvii

of Condorcet's "Essai": "

form one of the 2 contradictory systems

supporting coalition and not margin of difference. McLean later writes:

"Where does this leave Condorcet's choice rule? - still ambiguous, because

the choice rule consistent with the ordering rule ("select the candidate with the

maximum likelihood of being the correct one") is not the same as the choice rule

embodying theCondorcetcriterion ("select the Condorcet winner if there is one").

We aim to show that Condorcet never resolved the tension between probability

and social choice in his writings on elections during the last nine years of his life."

[McLean 1995, p.22]

Due to considerations of voting strategies and
equilibria, which Condorcet apparently did

not consider, we prefer to measure
size by using the supporting coalition (the larger of the

two counts) rather than
the margin of difference. (See the definition of min()
in section 2).

Condorcet explicitly assumed all votes
would be made in good faith, and assuming also

complete strict preferences, then, when
those assumptions hold, neglecting strategic effects,

both measures
would result in the choice of the same alternative(s).

It is unclear whether Condorcet
was aware that the wording of his proposal, taken literally,

could elect a
Condorcet loser (an alternatives that is less preferred by a majority in each
of

its pairings). His wording does not discriminate between cyclic
propositions, such as those

in the top cycle, from acyclic propositions, such as
the defeats of alternatives outside the

top cycle by the alternatives in the top
cycle. Since there is no need to discard acyclic

propositions when
resolving cycles, it is easy to imagine that Condorcet would have

been
comfortable with one or both of the following procedures:

"

Successively delete the smallest of the cyclic propositions"

until no cycles remain."

Successively delete the smallest of the cyclic propositions,"

recalculating cyclicity after each deletion, until no cycles remain.

Measuring the sizes of
propositions by their supporting coalitions, the first of these two is Ψ_{1}.

The latter, which we will call Ψ_{2}, elects
a subset of
ψ_{1}, is nearly as easy to calculate as Ψ_{1},

and satisfies ICA (and probably ISA too, though this has not been verified) when
accompanied

by a suitable tie-breaker. The difference between Ψ_{1}
and Ψ_{2} is that Ψ_{2}
recalculates cyclicity

but Ψ_{1} does
not. Ψ also recalculates cyclicity, in a sense,
but less often than Ψ_{2}. This

difference can occasionally result in different winners. An argument for
preferring Ψ over

[Ψ_{2}]
is that when they choose different winners, the winner
according to Ψ tends to beat

pairwise the winner
according to [Ψ_{2}] more often than vice
versa, according to computer

simulations using randomly generated
rankings. Since we are concerned here only with

establishing the existence
of a voting scheme which satisfies ISA, we do not consider Ψ_{2}

further in this document, apart from a brief comment below about its
decisiveness.

Voting procedures like Ψ_{1}
and Ψ which choose only alternatives in ψ_{1}
have significant

strategic implications not discussed in this
document. (See the document
describing the

*minimal defense* criterion.)

**Lemma (4.3):** Ψ_{1} and
Ψ
satisfy the top cycle criterion. (Proof
in appendix A1.)

**Theorem (4.4):** Ψ_{1}
and Ψ are partially
independent from similar (clone, exact clone)

alternatives. (The proof
is in appendix A1.)

Like the top cycle correspondence τ, Ψ_{1} is too indecisive to be
practical by itself. Even

with many
voters, its indecisiveness increases asymptotically with the
number of alternatives,

according to computer simulations
using randomly generated preference orders. However,

the decisiveness of Ψ is
comparable to other correspondences which are prominent in the

literature,
leaving little to chance, particularly in large public elections. Ψ_{2}
is more decisive

than Ψ_{1} and would be
reasonably decisive in large public elections. [Ψ_{2}]
is slightly more

decisive than Ψ_{2}, and its
decisiveness is comparable to other prominent correspondences.

To explore the issue of "practical"
independence, which requires both partial independence

and
"reasonable" decisiveness, computer simulations using randomly
generated orders of

preference were run to quantify the decisiveness of Ψ_{1}
and Ψ. A portion of the decisiveness

measurements are
summarized in appendix A3. The results show that the
decisiveness of Ψ_{1}

and Ψ
increases as the number of voters increases, and the decisiveness of Ψ is comparable

to the decisiveness of
Borda given many voters. The results suggest that Ψ would be

reasonably decisive in large public elections, meaning that a poor choice of
tie-breaker

(e.g., "random") for Ψ would not substantially affect its properties in those elections.

If we were merely interested in satisfaction of * ICA*
and *IECA*, not in *ISA*, a voting scheme

which is a variation of Random Dictator would be a suitable tie-breaker for
correspondences

which are partially independent from similar alternatives, clone
alternatives, and/or exact clone

alternatives. Random Dictator would
suffice if voters' rankings are required to be strict

orderings, but allowing
indifference adds a degree of complexity. Random Voter Hierarchy,

a generalization of Random Dictator, chooses one
alternative from a feasible subset by

randomly picking a ballot and eliminating
all but that ballot's top-ranked feasible alternative(s), repeating until either
one alternative remains or all ballots have been randomly
picked.

In the latter case, which can occur only if all voters report
indifference between the

remaining alternatives, one of the remaining alternatives is randomly chosen.

Let random(S) denote the function which, given any non-empty set S, randomly

chooses one element of S, giving an equal 1/#S chance to each element of S.

(When S is a singleton, random(S) selects the lone element of S with certainty.)For all

i∈N, all, allAand allRZ⊆, let top(Ai,Z,) denote the subset ofR

alternatives {x∈Zsuch that, for ally∈Z, [xPor_{i}yxI]}._{i}y

Random Voter HierarchyandRandomVoterHierarchyScheme:Let RandomVoterHierarchy(

Z,) denote the probabilistic functionR

defined for all, allAand all non-emptyRZ⊆by this procedure:AStep 1. Let W denote a variable subset of the alternatives, and initially

let W =Z. LetNdenote a variable subset of'N, and initially letN='N.Step 2. Repeat while #W > 1 and #

N> 0:'(2.1) Let

j=Random(N).'(2.2) Let

N='N\{'j}. (That is, delete voterjfrom the subset.)(2.3) Let W = W ∩ top(

j,W,).RStep 3. Let RandomVoterHierarchy(Z

,) = random(W).RRandomVoterHierarchyScheme denotes the voting scheme such that, for all

,A

all, all non-emptyRZ⊆, and allAx∈, RandomVoterHierarchySchemeA(_{x}Z,) equals the probability thatRx= RandomVoterHierarchy(Z,).R

It would be desirable to also have
a formulaic definition of RandomVoterHierarchyScheme,

but that would require
additional complicated notation and would probably not increase

its ease of
understanding.

Given a correspondence *g* which is partially
independent from similar (or clone) alternatives,

the voting scheme *g*//RandomVoterHierarchyScheme
satisfies * IECA* and *ICA*. (We do

not attempt to prove this here since we are
interested in *ISA*.) Satisfaction of * ISA* is more

demanding, however, and
requires a more sophisticated voting scheme as tie-breaker.

Dissimilar(*g*) is a voting scheme
defined with respect to a voting correspondence *g*.

Dissimilar(*g*)(*Z, R*)
eliminates all but one alternative from each identifiable
similar set

of (

We formally define Dissimilar(

Given a correspondence

g, Dissimilar(g)(Z,) is defined for allR, allAR

and all finite non-emptyZ⊆by this procedure:AStep 1. Let L be a #

-tuple of real numbers having one component for each alternative inA, and initally let LA_{x}= 1 for allx∈Zand let L_{x}= 0

for allx∈\AZ. LetRepresentbe a #-tuple of alternatives having one component for each alternative inA, and initially letARepresent(x) =x

for allx∈. LetADbe a subset of the alternatives, and initially letD=Z.Step 2. Repeat while #

D> 1:(2.1) Pick a set Y such that Y is a similar set of (D,

R)

and no strict subset of Y is a similar set of (D,R).(2.2) Let G =

g(Y,R).(2.3) Let x' =

Random(G).(2.4) For all x ∈ Z such that

Represent(x) ∈ Y\G, let L_{x}= 0.(2.5) For all x ∈ Z such that

Represent(x) ∈ G, let L_{x}= L_{x}/ #G and letRepresent(x) = x'.(2.6) Let D = {x'} ∪ (D\Y).

Step 3. Let Dissimilar(

g)(Z,R) = L.

Remarks:

In step 2.1, at least one such
similar set exists while #D>1 since D itself is trivially a similar set of (D,*R*).
An algorithm to identify such a similar set which is fast even when Z is large
is yet to be found, however, suggesting that Dissimilar is likely to be
practical only as a tie-breaker.

There is an
ambiguity in step 2.1 since there may be more than one similar set meeting the
specified constraint. If the similar sets meeting the constraint are
disjoint, the ambiguity is innocuous since the choice between them will not
ultimately make a difference. However, if two or more of them are not
disjoint, the choice between them can make a difference. Though this
problem does not affect partial independence or practical independence, a claim
of complete independence from similar alternatives cannot be sustained unless
this ambiguity is resolvable by finding a way to narrow the definition of
similarity or independence that does not sacrifice manipulation
resistance. Still under development, such a narrowing is expected to
involve the identification of the "most clone-like" of the
non-disjoint sets and rejecting the similarity of the "less
clone-like." Letting Y_{u} denote the union of the
non-disjoint "near-similar" sets, each set Y might be scored according
to the largest number of voters who ranked an alternative in Y_{u}\Y
strictly over or under every alternative in Y, and calling "similar"
only the set having the largest score (a maximaximax function).

Step 2.6 eliminates from D all of Y except an alternative which is "g-best" of Y. Since Y is not a singleton, step 2.6 must eliminate at least one alternative from D, so the number of times step 2 is performed must be less than #Z.)

In step 3, each component of L is a real number in
[0,1], the components of L sum to 1, L_{x}=0 for all x ∉
Z,
etc. So for any correspondence *g*, Dissimilar(*g*)
is a voting scheme:

Appendix A4 provides an example showing the operation of Dissimilar.

**Lemma (5.5):** If *g* is a
correspondence which satisfies top cycle,
then Dissimilar(*g*) satisfies top cycle. (Proof
in appendix A1.)

**Theorem (5.6):** If * g* is a correspondence which
satisfies top cycle and is
partially independent from similar alternatives, then Dissimilar(*g*) satisfies
top cycle, ISA, ICA, and IECA. (Proof
in appendix A1.)

**Lemma (5.7):** Dissimilar(Ψ)
satisfies top cycle, ISA, ICA, IECA. (Proof
in appendix A1.)

**Lemma (5.8):** Ψ//Dissimilar(Ψ)
satisfies top cycle, ISA, ICA, IECA. (Proof
in appendix A1.)

Ψ//Dissimilar(Ψ) is a single-winner voting function which satisfies ISA, ICA, IECA, top cycle, anonymity, neutrality, and other desirable criteria. Satisfaction of ISA suggests it is less manipulable than many voting procedures (a conclusion which will be bolstered by a consideration of certain strategy criteria not discussed here).

Dissimilar(Ψ) is also a single-winner voting function which satisfies ISA, ICA, IECA, top cycle, etc. In a sense, Dissimilar(Ψ) is simpler than Ψ//Dissimilar(Ψ), but Ψ is reasonably decisive so in practice Ψ//Dissimilar(Ψ) would be much simpler to tally. If voting procedures need to be defined as simply as possible in order to gain public acceptance, it would be reasonable to simply propose Ψ and not specify the tie-breaker, since Ψ is "practically" independent from similar alternatives in public elections

**Lemma (2.14):** (**Rotations** of majority cycle) If *mc* = {z_{1},z_{2},...,z_{k}}
(k>2) is a majority cycle of (Z,*R*), then *mc*' = {z_{2},...,z_{k},z_{1}}
is a majority cycle of (Z,*R*), and the majority sequence associated with *mc*
is identical to the majority sequence associated with *mc*'.

**Proof**: By inspection
of the definition of majority cycle
and the definition of majority
sequence.

**Lemma (2.15):** (**Splittability** of
majority cycle) If Y is a similar set of (Z,*R*), and z and z' are
two alternatives in Z such that z*M*z' and at least one of z and z' is in
Z\Y, and *mc* is a majority cycle of (Z,*R*)
such that z and z' are either adjacent in *mc* or last and first in *mc*,
z#z' is last in the majority sequence associated with *mc*, and at least
two distinct alternatives in *mc* are in Y, then there exists a majority
cycle of (Z,*R*) (call it *mc*_{1} without loss of generality) such that
z and z' are adjacent in *mc*_{1}, z#z' is last in the majority
sequence associated with *mc*_{1}, and exactly one alternative in *mc*_{1}
is in Y.

**Proof**: Assume the
premise holds. By induction on lemma 2.14 (rotatability), there must be a
majority cycle *mc*' = {z_{1},z_{2},...,z_{k}}
obtained by rotation of *mc* such that z_{1}=z and z_{2}=z' and z#z' is last in the majority sequence associated with *mc*'.
Since *mc*' contains at least two distinct alternatives in Y and at least
one alternative in Z\Y, *mc* and *mc*' must contain at least two
distinct alternatives in Z\Y, else 2.12.2 of the definition
of similar set would be contradicted. So k __>__ 4. Again
by 2.12.2, at least two distinct alternatives in Z\Y must be either adjacent in *mc*
or last and first in *mc* and either adjacent in *mc*' or last and
first in *mc*'. (In other words, by 2.12.2, in no majority cycle can
two alternatives in Y be separated by exactly one alternative not in Y).

Of all the alternatives which are
in both *mc*' and Y, let *l* be the position in *mc*' of the one
positioned lowest in *mc*', let *s* be the position in *mc*' of
the one positioned second lowest in *mc*', and let *h* be the position
in *mc*' of the one positioned highest in *mc*'. (Possibly *h* = *s*
since there may be as few as two alternatives which are in both *mc*' and
Y.)
Thus z_{l}, z* _{s}*, z

(2.15.1) If

l> 2, then z_{l}_{-1}Mz_{h}_{.}(2.15.2) If

h< k, then z_{l}Mz_{h+1.}(2.15.3) If

l= 2 andh= k, then z_{l}Mz_{1.}(2.15.4) If

l= 1, then z_{s-1}Mz_{l}.

There are three cases to consider:

Case 1:

l> 2. By 2.15.1, the ordered setmc_{1}= {z_{1},z_{2},...,z_{l-2},z_{l-1},z_{h},z_{h+1},...,z_{k}}is a majority cycle of (Z,R). Since z_{1}=z and z_{2}=z', z and z' are adjacent inmc_{1}. Exactly one alternative (z_{h}) in Y is inmc_{1}. By the definition of majority sequence, z#z' is last in the majority sequence associated withmc_{1}.Case 2:

l= 2. By 2.15.2 and 2.15.3, the ordered setmc_{1}= {z_{1},z_{2},z_{h+1},...,z_{k}} is a majority cycle of (Z,R). Since z_{1}=z and z_{2}=z', z and z' are adjacent inmc_{1}. Exactly one alternative (z_{2}) in Y is inmc_{1}. By the definition of majority sequence, z#z' is last in the majority sequence associated withmc_{1}.Case 3:

l= 1. By 2.15.4, the ordered setmc_{1}= {z_{1},z_{2},...z_{s}_{-1}}is a majority cycle of (Z,R). Since z_{1}=z and z_{2}=z', z and z' are adjacent inmc_{1}. Exactly one alternative (z_{1}) in Y is inmc_{1}. By the definition of majority sequence, z#z' is last in the majority sequence associated withmc_{1}.

In all cases there exists a majority cycle meeting the desired conditions, so the lemma is proved.

**Lemma
(2.16):** (**Substitutability** of similar alternative) If Y is a similar set of
(Z,*R*) and *mc* = {z_{1},z_{2},...z_{k})
(k>2) is a majority cycle of (Z,*R*) such that z_{1} ∈ Y and
z_{1} is the only alternative in *mc* which is in Y, then for all y∈Y {y,z_{2},...,z_{k}} is a majority cycle of (Z,*R*).

**Proof**: By 2.12.2 of
the definition of similar set, for all y∈ Y, z_{1}*M*z_{2}
implies y*M*z_{2} and z_{k}*M*z_{1}
implies z_{k}*M*y. By the definition of
majority cycle, {y,z_{2},...,z_{k}} must be a majority
cycle of (Z,*R*).

**Lemma
(2.17):** For any sets Y, Z, and Z_{s} such that Y is a similar
(clone, exact clone) set of (Z,*R*) and Z_{s} ⊆
Z
and at least one alternative in Z_{s} is in the top cycle of (Z,*R*)
and Y∩Z_{s} ≠ Ø,
Y∩Z_{s} is a similar (clone, exact
clone) set of (Z_{s},*R*).

**Proof**: Abbreviate Y_{s}
= Y∩Z_{s} and assume the premise, considering first the case where Y is
a similar set of (Z,*R*). We show that all the
similarity conditions of 2.12 hold for Y_{s} with respect to (Z_{s},*R*):

Since Y_{s} ⊆
Z_{s} and Y_{s} ≠ Ø, 2.12.1 holds for Y_{s} with
respect to (Z_{s},*R*).

Since Y_{s} ⊆
Y and *Z*_{s}\Y_{s} ⊆
Z\Y and 2.12.2 holds for Y with respect to (Z,*R*), it must be the case
that for all y,y' ∈ Y_{s} and all x ∈
*Z*_{s}\Y_{s},
y*M*x if and only if y'*M*x, and x*M*y
if and only if x*M*y'. So 2.12.2 holds for Y_{s}
with respect to (Z_{s},*R*).

Since Z_{s} ⊆
Z and Z_{s} ≠ Ø, every majority cycle
of (Z_{s},*R*) is a majority cycle of (Z,*R*), and their
associated majority sequences
are invariant since *R* is held fixed. Since at least one
alternative in Z_{s} is in τ(Z,R), τ(Z_{s},R)
is a non-empty subset of τ(Z,R), and every X = {x_{1},x_{2},...,x_{k}}
which is a subset of τ(Z_{s},*R*)\Y_{s}
is also a subset of τ(Z,*R*)\Y. Given
these facts, and since all four conditions of 2.12.3 hold for Y with respect to
(Z,*R*), it must be the case that for all y,y' ∈
Y_{s}
and all X = {x_{1},x_{2},...,x_{k}} such that X ⊆
τ(Z_{s},*R*)\Y_{s} and both *mc*_{1}={y_{1},x_{1},x_{2},...,x_{k}}
and
*mc*_{2}={y_{2},x_{1},x_{2},...,x_{k}}
are majority cycles of (Z_{s},*R*), all four conditions of 2.12.3
hold for Y_{s} with respect to (Z_{s},*R*).

Since all conditions of 2.12 hold
for Y_{s} with respect to (Z_{s},*R*), the lemma is proved
for when Y is a similar set of (Z,*R*). Since every clone set of (Z,*R*)
is a similar set of (Z,*R*) and every exact clone set of (Z,*R*) is a
clone set of (Z,*R*), the lemma also holds for when Y is a clone set of (Z,*R*)
and for when Y is an exact clone set of (Z,*R*).

**Lemma
(2.18):** (**Disjointness** of
similar sets) If Y and Y' are similar sets of (Z,*R*) and neither is
a subset of the other, then Y∩Y' = Ø. **FALSE!!**

**Proof**: Suppose
not. Then there is at least one alternative y in Y but not in Y', and
there is at least one alternative y' in Y' but not in Y. By the definition
of similar set, the following statements...

**Lemma (3.5):**
r'(*g*,Z,*R*)
__
<__ #Z for all correspondences *g*, all *A*, all *R*, and any
non-empty Z ⊆ *A*.

**Proof**: Since Z
and *R* are held fixed, abuse notation by abbreviating. Also
abbreviate #g = #(g(Z,*R*)). Since *g*_{r}
is a correspondence, for all r∈{1,2,...} 0 < #*g*_{r}
__
<__ #Z. Since r' is the smallest integer r__>__1 such that *g*_{r}
= *g*_{r+1}, r' is also the smallest integer r__>__1 such that #*g*_{r}
= #*g*_{r+1}. So #*g*_{r} > #*g*_{r+1}
for all r∈{1,2,..,r'-1}, and since #*g*_{r' }> 0,
by induction #*g*_{r'-k }>
*k* for all *k*∈{0,1,...,r'-1}.

Suppose to the contrary that r' > #Z. Then #Z
∈ {1,2,...,r'-1} and when *k *= #Z, #*g*_{r'-k }>
#Z. But this would contradict #*g*_{r} __ <__ #Z for
all r in {1,2,...}, so r' > #Z must be false. Thus r' __
<__ #Z and the lemma is proved.

**Lemma
(3.7):** If * g*_{1} and
*g*_{2} are correspondences which satisfy top cycle and are partially
independent from similar
alternatives,
then *g*_{1}//*g*_{2}
is a correspondence which satisfies top cycle and is partially independent from similar
alternatives.

**Proof**: Since *R* is
fixed, abbreviate *g*(...) for *g*(...,*R*). Assume the
premise of the
lemma. Let Z be a non-empty subset of *A* and let Y be a similar set of (Z,*R*) and let Y_{s} be
a strict subset of Y. We first establish that *g*_{1}//*g*_{2}
is partially independent from
similar alternatives by showing that conditions 3.2.1 and 3.2.2 hold for *g* = *g*_{1}//*g*_{2}.

Since *g*_{1} is partially independent from similar alternatives,
the following two statements must hold:

(3.7.1)

g_{1}(Z) ∩A\Y =g_{1}(Z\Y_{s}) ∩A\Y

(3.7.2)

g_{1}(Z) ∩ Y = Ø if and only ifg_{1}(Z\Y_{s}) ∩ Y = Ø

By properties of set intersection and union, the following two statements must hold:

(3.7.3)

g_{1}(Z) = (g_{1}(Z)∩Y) ∪ (g_{1}(Z) ∩A\Y)(3.7.4)

g_{1}(Z\Y_{s}) = (g_{1}(Z\Y_{s})∩Y) ∪ (g_{1}(Z\Y_{s}) ∩A\Y)

Three cases encompass all possibilities:

Case 1:

g_{1}(Z)∩Y = Ø. By 3.7.3,g_{1}(Z) =g_{1}(Z) ∩A\Y. By 3.7.2,g_{1}(Z\Y_{s})∩Y = Ø. By 3.7.4,g_{1}(Z\Y_{s}) =g_{1}(Z\Y_{s}) ∩A\Y. By 3.7.1,g_{1}(Z) =g_{1}(Z\Y_{s}), so g2(g_{1}(Z)) = g2(g_{1}(Z\Y_{s})), which means both conditions 3.2.1 and 3.2.2 hold forg_{1}//g_{2}in case 1.Case 2:

g_{1}(Z) ∩A\Y = Ø. By 3.7.3,g_{1}(Z) =g_{1}(Z)∩Y. By 3.7.1,g_{1}(Z\Y_{s}) ∩A\Y = Ø. By 3.7.4,g_{1}(Z\Y_{s}) =g_{1}(Z\Y_{s})∩Y. Sinceg_{1}is a correspondence,g_{1}cannot choose the empty set, sog_{1}(Z)∩Y ≠ Ø andg_{1}(Z\Y_{s})∩Y ≠ Ø. Sinceg_{2}is a correspondence, (g_{1}//g_{2})(Z) must choose a non-empty subset ofg_{1}(Z), sog_{2}(g_{1}(Z)) ∩A\Y = Ø andg_{2}(g_{1}(Z\Y_{s})) ∩A\Y = Ø andg_{2}(g_{1}(Z))∩Y ≠ Ø andg_{2}(g_{1}(Z\Y_{s}))∩Y ≠ Ø. So both conditions 3.2.1 and 3.2.2 hold forg_{1}//g_{2}in case 2.Case 3:

g_{1}(Z)∩Y ≠ Ø andg_{1}(Z) ∩A\Y ≠ Ø. Sinceg_{1}satisfies top cycle,g_{1}(Z) is a non-empty subset of τ(Z,R). By lemma 2.17 (letting Z_{s}beg_{1}(Z)∪Y), Y is a similar set of (g_{1}(Z)∪Y,R). Letting Y_{s1}= Y \ (g_{1}(Z)∩Y) implies Y_{s1}⊂ Y. Sinceg_{2}is partially independent from similar alternatives, and since (by properties of intersection and union)g_{1}(Z) = (g_{1}(Z) ∪Y)\Y_{s1}, by 3.2.1 and 3.2.2 the following two statements must hold in case 3:(3.7.5)

g_{2}(g_{1}(Z) ∪Y) ∩A\Y =g_{2}(g_{1}(Z)) ∩A\Y(3.7.6)

g_{2}(g_{1}(Z) ∪Y) ∩ Y = Ø if and only ifg_{2}(g_{1}(Z)) ∩ Y = ØLetting Y

_{s2}= Y \ (g_{1}(Z\Y_{s})∩Y) implies Y_{s2}⊂ Y. By properties of intersection and union, (g_{1}(Z\Y_{s})∪Y)\Y_{s2}=g_{1}(Z\Y_{s}). By 3.7.1,g_{1}(Z\Y_{s}) ∪Y =g_{1}(Z) ∪Y. Combining the last two equations gives (g_{1}(Z) ∪Y)\Y_{s2}=g_{1}(Z\Y_{s}). Sinceg_{2}is partially independent from similar alternatives, by 3.2.1 and 3.2.2 the following two statements must hold in case 3:(3.7.7)

g_{2}(g_{1}(Z) ∪Y) ∩A\Y =g_{2}(g_{1}(Z\Y_{s})) ∩A\Y(3.7.8)

g_{2}(g_{1}(Z) ∪Y) ∩ Y = Ø if and only ifg_{2}(g_{1}(Z\Y_{s})) ∩ Y = ØThe left side of 3.7.5 is identical to the left side of 3.7.7, and the left side of 3.7.6 is identical to the left side of 3.7.8. So both conditions 3.2.1 and 3.2.2 hold for

g_{1}//g_{2}in case 3.

The similarity conditions hold in all three cases, establishing
that *g*_{1}//*g*_{2} is partially independent from
similar alternatives.

Since *g*_{1}
satisfies top cycle, *g*_{1} must choose a non-empty subset of the
top cycle, and *g*_{1}//*g*_{2} must choose a
non-empty subset of what *g*_{1} chooses. So *g*_{1}//*g*_{2}
must choose a non-empty subset of the top cycle, which establishes that *g*_{1}//*g*_{2}
satisfies top cycle.

**Lemma
(3.8):** If * g* is a correspondence
which satisfies top cycle and is partially independent from similar alternatives, then [*g*] is a
correspondence which satisfies top cycle and is
partially independent from similar
alternatives.

**Proof**: The proof follows from the
definition
of [*g*] and induction using lemma 3.7.

**Lemma
(3.9):** If *g* is a correspondence
which satisfies top cycle and is
partially independent from similar alternatives and *f* is a single-winner voting function which satisfies ISA, then *g*//*f* and [*g*]//*f* are
single-winner voting functions which satisfy top cycle and ISA.

**Proof**: The proof for *g*//*f*
closely resembles the proof of lemma 3.7. Then by lemma 3.8, the proof for [*g*]//*f*
follows immediately.

**Lemma (4.3):**
Ψ_{1} and Ψ
satisfy the top cycle criterion.

**Proof**: By the definition
of the top cycle, y*M*x for all y ∈ τ(Z,*R*)
and all x ∉ τ(Z,*R*). So condition 4.1.1
of the definition of ψ_{1}
holds for all y ∈ τ(Z,*R*) and all x
∉ τ(Z,*R*).
By the definition of majority cycle,
there are no majority cycles of (Z,R) containing both x and y, for any y ∈
τ(Z,*R*)
and any x ∉ τ(Z,*R*). So condition 4.1.2 holds for all
y ∈ τ(Z,*R*) and all x
∉ τ(Z,*R*).
Since τ(Z,*R*) is a non-empty subset of Z, for all x
∉ τ(Z,*R*) there exists at least one y
∈ τ(Z,*R*)
for which both 4.1.1 and 4.1.2 hold. Therefore the ψ_{1}(Z,*R*)
set includes no alternatives which are not in τ(Z,*R*). By the
definition of Ψ_{1}, Ψ_{1}(Z,*R*)
= ψ_{1}(Z,*R*) so Ψ_{1} satisfies top
cycle. By induction and the same reasoning in lemma 3.7 which showed that *g*_{1}//*g*_{2}
satisfies top cycle if *g*_{1} satisfies top cycle, Ψ
satisfies top cycle because Ψ = [Ψ_{1}].

**Theorem (4.4):**
Ψ_{1}
and Ψ are partially
independent from similar (clone, exact clone) alternatives.

**Proof**: Since *R*
is held fixed, we abuse notation by abbreviating (...,*R*) as (...).
First we show that Ψ_{1}
is partially independent from similar alternatives: Assume Z is a
non-empty subset of *A*, Y is a similar
set of (Z,*R*) and Y_{s} is a strict subset of
Y. By the definition of Ψ_{1}, Ψ_{1}(Z)
= ψ_{1}(Z) and Ψ_{1}(Z\Y_{s})
= ψ_{1}(Z\Y_{s}), so we need to
establish the following two statements:

(4.4.1) ψ_{1}(Z)
∩ *A*\Y = ψ_{1}(Z\Y_{s})
∩ *A*\Y

(4.4.2) ψ_{1}(Z)
∩ Y = Ø if and only if ψ_{1}(Z\Y_{s})
∩ Y = Ø

By the definition of ψ_{1},
x ∈ ψ_{1}(Z) if and only if x∈Z and there is no z∈Z for which both of the
following conditions hold:

(4.4.3) z

Mx.(4.4.4) For all

mcsuch thatmcis a majority cycle of (Z,R) andmccontains both z and x, z#x is not last in ms(mc).

By the definition of ψ_{1},
x ∈ ψ_{1}(Z\Y_{s}) if and only if
x ∈ Z\Y_{s} and there is no z' ∈
Z\Y_{s} for which both of the
following conditions hold:

(4.4.5) z'

Mx.(4.4.6) For all

mc' such thatmc' is a majority cycle of (Z\Y_{s},R) andmc' contains both z' and x, z'#x is not last in ms(mc').

To establish 4.4.1 there are four cases to consider:

Case 4.4.1.1: x ∈

A\Y and x ∈ ψ_{1}(Z). We must show that x ∈ ψ_{1}(Z\Y_{s}). By the definition of ψ_{1}, x∈Z, and since x ∈A\Y, x ∈ Z\Y and x ∈ Z\Y_{s}. By the definition of ψ_{1}there is no z∈Z for which both 4.4.3 and 4.4.4 hold. By the definition of majority cycle, every majority cycle of (Z\Y_{s},R) is a majority cycle of (Z,R), so there cannot be any z' ∈ Z\Y_{s}such that 4.4.5 and 4.4.6 both hold. Therefore, by the definition of ψ_{1}, x ∈ ψ_{1}(Z\Y_{s}).Case 4.4.1.2: x ∈

A\Y and x ∈ ψ_{1}(Z\Y_{s}). We must show that x ∈ ψ_{1}(Z). This follows by reasoning similar to that in case 4.4.1.1, plus the use 2.12.2 of the definition of similarity, plus lemma 2.15 (splittability) and lemma 2.16 (substitutability) and 2.12.2 and 2.12.3 of the definition of similarity to show that the majority cycles of (Z,R) which are not majority cycles of (Z\Y_{s},R) are either redundant or irrelevant for determination of whether x ∈ ψ_{1}(Z).Case 4.4.1.3: x ∈

A\Y and x ∉ ψ_{1}(Z). We must show that x ∉ ψ_{1}(Z\Y_{s}). By the definition of ψ_{1}, x∈ Z, so x ∈ Z\Y, and x ∈ Z\Y_{s}. By the definition of ψ_{1}there is a z∈Z for which both 4.4.3 and 4.4.4 hold. There are two subcases to consider:Case 4.4.1.3.1: z ∈ Z\Y. Since Y

_{s}⊂ Y, z ∈ Z\Y_{s}. By the definition of majority cycle, every majority cycle of (Z\Y_{s},R) is a majority cycle of (Z,R), and since z#x is not last in the majority sequence associated with any majority cycle of (Z,R) which contains z and x, z#x is not last in the majority sequence associated with any majority cycle of (Z\Y_{s},R) which contains z and x. Therefore, by the definition of ψ_{1}, x ∉ ψ_{1}(Z\Y_{s}).Case 4.4.1.3.2: z ∈ Y. By 4.4.3 and similarity, y

Mx for all y∈ Y. By 4.4.4 and similarity, for all y∈Y there is no majority cyclemcof (Z,R) such thatmccontains both y and x and y#x is last in ms(mc). Since Y_{s}⊂ Y, yMx for all y ∈ Y\Y_{s}. Since all majority cycles of (Z\Y_{s},R) are majority cycles of (Z,R), for all y ∈ Y\Y_{s}there is no majority cyclemc' of (Z\Y_{s},R) such thatmc' contains both y and x and y#x is last in ms(mc'). Therefore, by the definition of ψ_{1}, x ∉ ψ_{1}(Z\Y_{s}).Case 4.4.1.4: x ∈

A\Y and x ∉ ψ_{1}(Z\Y_{s}). We must show that x ∉ ψ_{1}(Z). There are two subcases to consider:Case 4.4.1.4.1: z ∈ Z\Y. The reasoning in this case is to case 4.4.1.3.1 as the reasoning in case 4.4.1.2 is to case 4.4.1.1.

Case 4.4.1.4.2: z ∈ Y. The reasoning in this case is to case 4.4.1.3.2 as the reasoning in case 4.4.1.2 is to case 4.4.1.1.

So 4.4.1 has been established in all cases. To establish 4.4.2 there are four cases to consider:

Case 4.4.2.1: ψ

_{1}(Z)∩Y ≠ Ø. We must show that ψ_{1}(Z\Y_{s})∩Y ≠ Ø. There exists an alternative in Y, call it y_{0}with no loss of generality, such that y_{0}∈ ψ_{1}(Z)∩Y. By the definition of ψ_{1}, for all z∈Z such that zMy_{0}, there exists a majority cyclemcof (Z,R) such that z#y_{0}is last in ms(mc). There are four cases to consider:Case 4.4.2.1.1: z ∈ Z\Y. By lemma 2.15 (splittability) and lemma 2.14 (rotatability), for all z ∈ Z\Y such that z

My_{0}there exists a majority cyclemc' of (Z,R) such thatmc' = {z,y_{0},...,z_{k}} and y_{0}is the only alternative in Y which is inmc' and z#y_{0}is last in ms(mc'). By lemma 2.16 (substitutability), for all y∈Y and for all z ∈ Z\Y such that zMy_{0}, there is a majority cyclemc" of (Z,R) such thatmc" = {z,y,...,z_{k}} and y is the only alternative in Y which is inmc" and z#y is last in ms(mc"). Furthermore,mc" is also a majority cycle of (Z\Y_{s},R). Therefore, for all y ∈ Y\Y_{s}and all z ∈ Z\Y such that zMy, there exists a majority cycle of (Z\Y_{s},R) containing z and y such that z#y is last in its associated majority sequence.NEED TO SHOW THAT NOT ALL Ys ARE KNOCKED OUT BY Ys.Case 4.4.2.1.2: z ∈ Y\Y

_{s}and #(Y\Y_{s}) > 1. y_{0}is in Y\Y_{s}?Case 4.4.2.1.3: z ∈ Y\Y

_{s}and #(Y\Y_{s}) = 1. y_{0}is in Y\Y_{s}?Case 4.4.2.1.4: z ∈ Y

_{s}. y_{0}∈ Y\Y_{s}?Case 4.4.2.2: ψ

_{1}(Z\Y_{s})∩Y ≠ Ø. We must show that ψ_{1}(Z)∩Y ≠ Ø.Case 4.4.2.3: ψ

_{1}(Z)∩Y = Ø. We must show that ψ_{1}(Z\Y_{s})∩Y = Ø.Case 4.4.2.4: ψ

_{1}(Z\Y_{s})∩Y = Ø. We must show that ψ_{1}(Z)∩Y = Ø.

Having established 4.4.1 and 4.4.2 in all cases, Ψ_{1}
is partially independent from similar alternatives. Since every clone set
of (Z,*R*) is a similar set of (Z,*R*) and since every exact clone set
of (Z,*R*) is a clone set of (Z,*R*), Ψ_{1}
is partially independent from clone alternatives and Ψ_{1}
is partially independent from exact clone alternatives. By lemma 3.8 and
by induction on lemma 4.3, Ψ is partially independent
from similar alternatives. Since every clone set of (Z,*R*) is a
similar set of (Z,*R*) and since every exact clone set of (Z,*R*) is a
clone set of (Z,*R*), Ψ is partially independent
from clone alternatives and Ψ is partially
independent from exact clone alternatives.

**Lemma (5.3):** If *g* is a
correspondence which satisfies top cycle,
then Dissimilar(*g*) satisfies top cycle.

**Proof**:

**Theorem (5.4):** If * g* is a correspondence which
satisfies top cycle and is
partially independent from similar alternatives, then Dissimilar(*g*) satisfies
top cycle, ISA, ICA, and IECA.

**Proof**:

**Lemma (5.5):**
Dissimilar(Ψ)
satisfies top cycle, ISA, ICA, and IECA.

**Proof**: The proof follows from lemma
4.3,
theorem 4.4, and theorem 5.4.

**Lemma (5.6):**
Ψ//Dissimilar(Ψ)
satisfies top cycle, ISA, ICA, and IECA.

**Proof**: The proof follows from lemma
4.3, theorem 4.4, lemma
5.5, and lemma 3.10.

## Appendix A2: Example Calculation of Ψ

_{1}and Ψ

__Example A2.1: Calculating Ψ _{1}
and Ψ given a cycle of three alternatives__

Suppose 12 voters
rank alternatives *a*, *b*, and *c* as follows:

5:

a>b>c4:

b>c>a2:

c>a>b1:

c>a~b

The following aggregate properties relations and properties are tallied:

aMbsincea#b>b#a. (7 = 5+2 > 4)

bMcsinceb#c>c#b. (9 = 5+4 > 3)

cMasincec#a>a#c. (7 = 4+3 > 5){

a,b,c} is the only set of alternatives for which there exists a majority cyclic permutation, somajoritycycles(A) = {{a,b,c}}.

majorities({a,b,c}) = {(a,b), (b,c), (c,a)}.

min({a,b,c}) = {(a,b), (c,a)} sincea#b=c#a= 7 < 9 =b#c.

*a* ∈ ψ_{1}:
Letting x=*a*, condition 4.1.1 holds for
z=*b* and condition
4.1.2 holds for z=*c* since (*c*,*a*)∈*min*({*a*,*b*,*c*}).

*b* ∈ ψ_{1}: Letting x=*b*, condition 4.1.1 holds
only z=*c* and condition 4.1.2 holds for z=*a* since (*a*,*b*)∈*min*({*a*,*b*,*c*}).

*c* ∉ ψ_{1}: Letting x=*c*, condition 4.1.1
does not hold for
z=*b* and
condition 4.1.2 does not hold for z=*b* since (*b*,*c*)∉*min*({*a*,*b*,*c*}).

Therefore, ψ_{1}
= {*a*,*b*}, and thus Ψ_{1}({*a*,*b*,*c*},*R*)
= {*a*,*b*}.

To calculate Ψ,
repeat Ψ_{1} until convergence: (Ψ_{1}//Ψ_{1})({*a*,*b*,*c*},*R*))
=* *Ψ_{1}({*a*,*b*},*R*)
= {*a*} (since *aMb* and *c* is neglected). So in this
example, a repetition of Ψ_{1}
suffices to eliminate all but one alternative, and Ψ({*a*,*b*,*c*},*R*)
= {*a*}.

Computer simulations using randomly
generated orders of preference were run in an attempt to quantify the decisiveness of
Ψ_{1}
and Ψ. For comparison the decisiveness of Borda was also
tallied. The number of voters and the number of alternatives were varied,
and for each set of parameters the computer generated 1,000 scenarios of random
preference orders and tallied each scenario by all three procedures. The
three columns in the middle of the tables show the decisiveness of the
procedures.

The two columns at the right of the tables
provide an additional comparison showing the overall majority preferences
regarding the Ψ winner and the Borda winner: The "Ψ * M*
Borda" column shows the percentage of scenarios where both procedures were
decisive and more voters ranked the Ψ winner over the Borda winner than
vice versa. The "Borda * M* Ψ" column shows the percentage
of scenarios where both procedures were decisive and more voters ranked the
Borda winner over the Ψ winner than vice versa. (The two numbers in
each row don't total 100% because sometimes both procedures chose the same
alternative and sometimes one or both procedures were indecisive.)

All the scenarios in table A-3.1 involved strict preferences only. In all scenarios in table A-3.2, the preference relation between every adjacent pair of alternatives in every voter's ranking had a 0.3 probability of being indifference instead of strict preference.

Table A-3.1

Decisiveness given strict preferences

__Voters
Alternatives Ψ _{1}
Ψ
Borda Ψ M Borda
Borda M Ψ__

100 3 89.7% 90.8% 96.9% 7.5% 0.0%

100 6 81.7% 88.8% 97.8% 16.6% 1.4%

100 12 65.2% 86.6% 97.2% 24.2% 3.8%

1000 3 99.2% 99.4% 99.9% 11.0% 0.0%

1000 6 93.4% 99.4% 99.1% 20.2% 2.8%

1000 12 80.3% 98.8% 99.5% 28.3% 5.6%

Table A-3.2

Decisiveness given non-strict preferences

__Voters
Alternatives Ψ _{1}
Ψ
Borda Ψ M
Borda
Borda M
Ψ__

100 3 93.0% 94.3% 97.0% 6.8% 0.5%

100 6 85.7% 92.2% 98.5% 16.6% 3.1%

100 12 71.3% 91.6% 98.9% 23.4% 5.6%

1000 3 99.1% 99.3% 99.7% 9.5% 0.8%

1000 6 94.1% 99.4% 99.6% 20.3% 3.4%

1000 12 79.5% 98.9% 100.0%* 27.8% 6.8%

* A 100% decisiveness value does not imply absolute decisiveness. A more accurate test involving many thousands of scenarios would produce a value below 100%.

The tables show that the decisiveness of all three procedures increased as the number of voters increased, and the decisiveness of Ψ is comparable to the decisiveness of Borda given 1,000 voters. The tables suggest that Ψ would be reasonably decisive in large public elections, meaning that a poor choice of tie-breaker for Ψ would not substantially affect its properties in those elections. The assumption regarding non-strictness of reported preferences does not appear to significantly affect decisiveness.

**Appendix
A4: Example calculation of Dissimilar**

This example involves three
alternatives {*a*,*b*,c} such that {*b*,*c*} is a similar
set and is nearly a clone set.
All three alternatives tie pairwise, so a tie-breaker is needed to break a
three-way tie if a pairwise correspondence is employed. We assume the
voting procedure satisfies anonymity and neutrality, so *a* would have a ½
chance of being elected if *a* has only one opponent. To satisfy
independence from similar alternatives, *a* must still have a ½ chance of
being elected when both *b* and *c* compete.

Suppose 100 voters rank the alternatives as follows:

1:

b>a>c

24:a>b>c

25:a>c>b

25:b>c>a

24:c>b>a

1:c>a>b

All three pairings of
the alternatives are 50:50 ties. Alternatives *b* and *c* are
nearly clones: by slightly changing two ballots to produce the 25,25,25,25
scenario, *b* and *c* would technically be clones since every voter
would rank *a* either over both *b* and *c* or under both *b*
and *c*. As is, the RandomHierarchyScheme
tie-breaker (or RandomDictator) gives *a* a 49/100 chance of being elected
since 49 voters rank *a* best and 51 voters rank *a* worse than
best. We show here that Dissimilar(*g*)
gives *a* a ½ chance, assuming *g* is a pairwise correspondence
satisfying anonymity and neutrality (meaning that, given a feasible set of two
tied alternatives, *g* chooses both alternatives).

In step 1, Dissimilar
initializes D={*a*,*b*,*c*}, L=(1,1,1), and *Represent*=(*a*,*b*,*c*).

Since #D=3 > 1, step 2 is performed:

In step 2.1, Dissimilar finds {

b,c} is (OopsNOT!) the only similar set meeting the requirements. (Though {a,b,c}is a similar set, so is a strict subset of {a,b,c}.) So Y={b,c}.In step 2.2,

g({b,c})={b,c} by assumption, so G={b,c}. Then x' is set to eitherborc, at random. Here we assume x'=b. (The reader may verify that the lottery will be the same if x'=c.)In step 2.3, nothing happens since Y\G is empty.

In step 2.4, L

and L_{b}_{c}are divided by #G=2, so L=(1,½,½). Also,Representis set to_{c}bsoRepresent=(a,b,b).In step 2.5,

cis eliminated from D so D={a,b}.

Since #D=2 > 1, step 2 is repeated:

In step 2.1, Dissimilar finds {

a,b} is the only similar set meeting the requirements. So Y={a,b}.In step 2.2,

g({a,b})={a,b} by assumption, so G={a,b}. Then x' is set to eitheraorb, at random. Here we assume x'=a. (The reader may verify that the lottery will be the same if x'=b.)In step 2.3, nothing happens since Y\G is empty.

In step 2.4, L

, L_{a}and L_{b}are divided by #G=2, so L=(½,¼,¼). Also,_{c}Representand_{b}Representare set to_{c}asoRepresent=(a,a,a).In step 2.5,

bis eliminated from D so D={a}.

Since #D=1, step 2 does not repeat again.

In step 3, Dissimilar returns the lottery (½,¼,¼). This means that independence from clone alternatives is robust over small perturbations of the ballots which make the clones premise not strictly hold.

**REFERENCES**

Anderson, L. B. (1996), "Brief Descriptions of Voting Methods, Part 3," maillist:election-methods-list@eskimo.com.

Arrow, K. (1951), Social Choice and Individual Values. New York: Wiley (second edition, 1963).

Borda, J-C de (1784), "Memoire sur les elections per scrutin," Memoires de l'Academie Royale des Sciences annee, pp. 657-65.

Condorcet, M. J. A. N., marquis de ([1785] 1972), "Essai sur l'application de l'analyse a la probabilite des decisions rendues a la pluralitie dex voix" (Essay on the Application of Analysis to the Probability of Majority Decisions), New York: Chelsea (orig. Paris: Imprimerie Royale).

McLean I. (1995), "Historical Aspects of Social Choice," Social Choice, Welfare, and Ethics, Proceedings of the Eighth International Symposium in Economic Theory and Econometrics (editors: Barrett, Moulin, Salles, Schofield), Cambridge University Press, pp. 13-33.

Moulin, H. (1988), Axioms of Cooperative Decision Making. Cambridge University Press

Saari, D. G. (1995), "Inner Consistency or Not Inner Consistency: A Reformulation is the Answer," Social Choice, Welfare, and Ethics, Proceedings of the Eighth International Symposium in Economic Theory and Econometrics (editors: Barrett, Moulin, Salles, Schofield), Cambridge University Press, pp. 187-212.

Tideman, T. N. (1987), "Independence of Clones as a Criterion for Voting Rules," Social Choice and Welfare, vol. 4, pp. 185-206.

Zavist, T.M., Tideman, T. N. (1989), "Complete Independence of Clones in the Ranked Pairs Rule," Social Choice and Welfare, vol. 6, pp. 167-173.

Young, H.P. (1974), (re: Reinforcement)

Young, H. P. (1988), "Condorcet's Theory of Voting," 82nd American Political Science Review, pp. 1231- .