Independence from Similar Alternatives in Social Choice Procedures

Stephen Eppley <seppley@alumni.caltech.edu>

Revised:  January 29, 2003

Abstract

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.

1.  Introduction

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 alternatives w, x, y, z as follows:

7	4
w	x,y
x,y	z
z	w

 

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 alternatives w, x, y, z as follows:

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 alternatives x, y, y' as follows:

3	2
x	y
y	y'
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.

2.  The Framework

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 V denote a finite non-empty set of voters {1,2,3,...,n}.  
Let A denote a non-empty set of potential alternatives.  
Let B, a finite non-empty subset of A, denote the alternatives nominated to the ballot. 

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

For all non-empty Z Í A, let Rankings(Z) denote the set of all possible 
non-strict rankings (also called weak orderings) of the alternatives in Z.  

Each voter is assumed to have transitive asymmetric preferences regarding the alternatives 
in A.  Each voter casts a ballot by expressing a ranking of B.  For all i Î V, let R_i denote 
the ballot cast by voter i.  Thus R_i Î Rankings(B) for all i Î V. (We have not assumed 
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 a priori  
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 minimal defense criterion.  Also, requiring each vote 
to be a strict ranking could deter voters from voting if the set of nominees is large.) 

Let R denote the set of voters' ballots.  For all a,b Î B, let R(a,b) denote the 
ballots in R which rank a over b.  Thus #R(a,b) is the number of voters who 
ranked a over b.

For all finite non-empty B Í A and all C Í B, C is a set of exact clone 
alternatives within B given R if and only if both of the following conditions hold: 

(1)  For all c,c' Î C, R(c,c') = f and R(c',c) = f. 
(2)  For all c Î C and all x Î B\C, R(x,c) ¹ f or R(c,x) ¹ f. 

(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 Í A and all C Í B, C is a set of clone alternatives  
within B given R if and only if both of the following conditions hold: 

(1)  For all c,c' Î C and all x Î B\C, R(x,c) = R(x,c') and R(c,x) = R(c',x).
(2)  For all c Î C and all x Î B\C, R(x,c) ¹ f or R(c,x) ¹ f. 

(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 i Î V, let R_i^Z denote the restriction of R_i to Z.  
In other words, R_i^Z is the same as R_i except all alternatives not in Z are deleted.  
Thus R_i^Z Î Rankings(Z) for i Î V.  Let R^Z denote the restriction of R to Z.  
That is, R^Z = {R₁^Z,R₂^Z,...,R_n^Z}.

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 A, each component is a real number in [0,1] and the sum of the 
components is 1.  For all lotteries L and all x Î A, let L_x denote the component 
of L which corresponds to x.  Thus, both of the following conditions hold for 
all lotteries L: 

(1)  For all x Î A, 0 £ L_x £ 1.  (Each component represents a probability.)
(2)  S_{(x Î A)}L_x = 1.  (The probabilities sum to 1.)

L_x is interpreted as the probability x will be elected.  Thus, L_x = 1 implies x will be 
elected with certainty, and L_x = 0 implies x will be defeated with certainty.

A voting scheme is a function f which maps a non-empty Z Í A and a set of 
voters' rankings R into a lottery and satisfies the following conditions: 

(1)  f_x(Z,R) = 0 for all A, all R, all non-empty Z Í A and all x Î A\Z.  
(2)  f_x(Z,R^Z) = f_x(Z,R) for all A, all R, all non-empty Z Í A, and all x Î A.

Just as L_x denotes the component of lottery L which corresponds to alternative x, 
f_x denotes the component of f which corresponds to x.  If f_x = 1, x will be elected with 
certainty.  If f_x = 0, x will be defeated with certainty.  If 0 < f_x < 1, it is presumed some 
fair random mechanism will determine the outcome in accordance with the probabilities.  
A voting scheme f is deterministic if and only if f_x(Z,R) is 1 or 0 for all A, all R, 
all non-empty Z Í A and all x Î A.  A voting scheme is probabilistic if and only if 
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 feasible subset.  Condition 2 is 
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 (IECA):  
A voting scheme f is independent from exact clone alternatives if and only if 
f_x(Z,R) = f_x(Z\C₀,R^Z\C0) for all A, all R, all finite non-empty Z Í A, 
all C which is a set of exact clone alternatives within Z given R, all x Î Z\C  
and all C₀ which is a strict subset of C. 

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 S_{(c Î C)} f_c(Z,R) = S_{(c Î C)} f_c(Z\C₀,R^Z\C0).  

Independence from Clone Alternatives (ICA):  
A voting scheme f is independent from clone alternatives if and only if 
f_x(Z,R) = f_x(Z\C₀,R^Z\C0) for all A, all R, all finite non-empty Z Í A, 
all C which is a set of clone alternatives within Z given R, all x Î Z\C  
and all C₀ which is a strict subset of C. 

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 S_{(c Î C)} f_c(Z,R) = S_{(c Î C)} f_c(Z\C₀,R^Z\C0).  

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 = {(a,b) such that a,b Î A}. (Note that (a,b) and (b,a) are distinct pairs.)

Let Majorities(R) denote the subset of ordered pairs {(a,b) Î Pairs such 
that #R(a,b) > #R(b,a)}.  Let M denote the binary relation on A such that, 
for all a,b Î A, aMb if and only if (a,b) Î Majorities(R).

For all finite non-empty B Í A and all C Í B, C is a set of similar alternatives  
within B given R only if both of the following conditions hold for all c,c' Î C  
and all x Î B\C:

(1)  (x,c) Î Majorities(R) if and only if (x,c') Î Majorities(R).  
(2)  (c,x) Î Majorities(R) if and only if (c',x) Î Majorities(R).

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 A, R and finite non-empty Z Í A, and abbreviating k = #Z, call 
the sequence z₁,z₂,...,z_k a majority cyclic permutation of Z given R 
if and only if Z = {z₁,z₂,...,z_k} and (z_k,z₁) Î Majorities(R) 
and (z_j,z_j+1) Î Majorities(R) for all j Î {1,2,...,k-1}.

Given A, R, and finite non-empty Z Í A, let majoritycycles(Z,R) denote 
the set of subsets of alternatives {MC such that MC is a non-empty subset 
of Z and there exists a majority cyclic permutation of MC given R}.

Given A, R, and finite non-empty Z Í A, let majorities(Z,R) denote the 
set of ordered pairs of alternatives {(x,y) Î Pairs such that there exists a 
majority cyclic permutation of Z given R in which x immediately precedes y}.

Given A, R, and non-empty Z Í A, let min(Z,R) denote the set of ordered 
pairs of alternatives {(x,y) Î Pairs such that (x,y) Î majorities(Z,R) 
and #R(x,y) < #R(z,w) for all (z,w) Î majorities(Z,R)}.

When R is clear from the context, we abbreviate majoritycycles(Z), majorities(Z) 
and min(Z).

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, and c~a, majorities({a,b,c}) = Ø and min({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, and dMb, 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 that min(Z,R) Í majorities(Z,R).  Note that (a,c) and (d,b) are not in majorities({a,b,c,d}) and are not in min({a,b,c,d}), even though aMc and dMb, because there are no majority cyclic permutations of {a,b,c,d} in which a immediately precedes c or in which d immediately precedes b.  For instance (trying to find a permutation in which a immediately precedes c), acdabcd is not a majority cyclic permutation of {a,b,c,d}because its alternatives are not all distinct, and acd is 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, R and non-empty Z Í A, and abbreviating k = #Z, the sequence x₁,x₂,...,x_k is a cyclic permutation of (Z,R) if and only if x₁, x₂, ..., x_k are distinct alternatives in Z and [x_kMx₁ or x_k~x₁] and [x_jMx_j+1 or x_j~x_j+1 for all j Î {1,2,...k-1}]}.  Given A, R, and non-empty Z Í A, let cycles(Z,R) 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 t(Z,R) denote the top cycle of (Z,R).  Formally, given A, R, and non-empty Z Í A, t(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 t(Z).

Definition (2.14):  For all x,y Î A and 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 substitute(S,x,y) denote the set obtained by substituting y for x everywhere x appears in S.

Definition (2.15):  A set Y is a similar set of (Z,R) if and only if the following three conditions hold:

(2.15.1)  Y Í Z Í A and #Y > 1.

(2.15.2)  For all y,y' Î Y and all x Î t(Z)\Y, [yMx 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(t(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 #t( Z,R) > 1, then t( Z,R) is a similar set of (Z,R).

(2.15.6)  If #(Z\t( Z,R)) > 1, then Z\t( 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 clonescore(Y,X,R) denote maximum_{(over x Î X\Y)} of #{i Î N such that there exists y,y' Î Y such that [xP_iy and not xP_iy'] or [yP_ix and not y'P_ix]}.  Given A, R, X Í A, and Y Í A such that X\Y ¹ Æ and Y\X ¹ Æ, X is more clone-like than Y with respect to R if and only if clonescore(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 scheme f is independent from similar alternatives if and only if 
f_x(Z,R) = f_x(Z\Y',R^Z\Y') for all A, all R, 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ÈY_s with respect to 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_iy 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_iy for all i Î 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 to R. 

Assume x Î Z\Y and there exists no y Î Y such that xI_iy 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_iy for all y Î Y] or [yP_ix for all y Î Y]} is less than maximum_{(over y Î Y\X)} of #{i Î N such that [yP_ix for all x Î X] or [xP_iy for all x Î X]}

 #{i Î N such that [xP_iy for all y Î Y\{y'}] or [yP_ix 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₁ Î majoritycycles(Z,R) such that #(MC₁ÇY)=1 and (x,x') Î min(MC₁,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Çt( 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 "t(Z)" with "Z" everywhere in the definition of similar set.  But we prefer to define similar sets broadly in order to make ISA stronger.

3.  Correspondences and Tie-breaking

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 correspondence is a function g :  2^A\Ø  x  Rⁿ  ®  2^A\Ø which satisfies the following conditions:

(3.1.1)  g(Z,R) Í Z for all A, all R, and all non-empty Z Í A.

(3.1.2)  g(Z,R') = g(Z,R) for all A, all R, all non-empty Z Í A, and all R' such that R' = R.

(3.1.3)  g(Z,R^Z) = g(Z,R) for all A, all R, 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 t(Z,R).

Definition (3.2):  A correspondence g is partially independent from similar (clone, exact clone) alternatives if and only if the following conditions hold for all A, all R, 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\Ys) Ç A\Y

(3.2.2)  g(Z,R) Ç Y = Ø if and only if g(Z\Y_s,R^Z\Ys) Ç 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//f denote the function defined with respect to two functions g and f, where g is a correspondence and f is either a correspondence or a voting scheme, which first applies g and then applies f to the subset chosen by g.  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₁//g₂//g₃//...//f where g₁, g₂, g₃, ... are correspondences and f is either a correspondence or a voting scheme.   Left-to-right precedence is implied; for instance g₁//g₂//f = (g₁//g₂)//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 correspondence g by the following rules:

(3.4.1)  For all positive integers r, let g_r be the correspondence defined inductively with respect to a correspondence g by the two rules:

(3.4.1.1)  g₁ = 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 that g_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 all A, all R, 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 Y//Dissimilar(Y), where Y is a correspondence which satisfies the top cycle criterion and is partially independent from similar alternatives and Dissimilar(Y) is a voting scheme which satisfies ISA and may involve some randomness.

Criterion (3.6):  Top Cycle (TC).  A correspondence g satisfies top cycle if and 
only if g(Z,R) Í t(Z,R) for all A, all R, and all non-empty Z Í A.  A voting scheme f 
satisfies top cycle if and only if f_x(Z,R) = 0 for all A, all R, all non-empty Z Í A, 
and all x Ï t(Z,R).

Lemma (3.7):  If g₁ and g₂ are correspondences which satisfy top cycle and are partially independent from similar alternatives, then g₁//g₂ 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.)

4.  The Y₁ and Y correspondences

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 y₁(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 y₁ and the definition of t.  The clause beginning with "for all z Î Z such that zMx" 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 y₁ 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 y₁ cannot be empty.  Appendix A2 provides an example illustrating the calculation of y₁.

Definition (4.2):  Y₁ and Y

(4.2.1)  Y₁ is the correspondence defined by the rule Y₁(Z,R) = y₁(Z,R) for all A, all R, and all non-empty Z Í A.

(4.2.2)  Y is the correspondence [Y₁].

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 Y₁.  
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, "... then we shall 
successively exclude from it the propositions with the lowest plurality."  Taken literally, 
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": "Now imagine that the 3 propositions with plurality support  
form one of the 2 contradictory systems..." which suggests Condorcet intended 
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 the Condorcet criterion ("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 Y₁.  
The latter, which we will call Y₂, elects a subset of y₁, is nearly as easy to calculate as Y₁, 
and satisfies ICA (and probably ISA too, though this has not been verified) when accompanied 
by a suitable tie-breaker.  The difference between Y₁ and Y₂ is that Y₂ recalculates cyclicity 
but Y₁ does not.  Y also recalculates cyclicity, in a sense, but less often than Y₂.  This 
difference can occasionally result in different winners.  An argument for preferring Y over 
[Y₂] is that when they choose different winners, the winner according to Y tends to beat 
pairwise the winner according to [Y₂] 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 Y₂  
further in this document, apart from a brief comment below about its decisiveness.

Voting procedures like Y₁ and Y which choose only alternatives in y₁ have significant 
strategic implications not discussed in this document. (See the document describing the 
minimal defense criterion.) 

Lemma (4.3):  Y₁ and Y satisfy the top cycle criterion.  (Proof in appendix A1.)

Theorem (4.4):  Y₁ and Y are partially independent from similar (clone, exact clone) 
alternatives. (The proof is in appendix A1.)

Like the top cycle correspondence t, Y₁ 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 Y is comparable to other correspondences which are prominent in the 
literature, leaving little to chance, particularly in large public elections.  Y₂ is more decisive 
than Y₁ and would be reasonably decisive in large public elections.  [Y₂] is slightly more 
decisive than Y₂, 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 Y₁ and Y.  A portion of the decisiveness 
measurements are summarized in appendix A3.  The results show that the decisiveness of Y₁  
and Y increases as the number of voters increases, and the decisiveness of Y is comparable 
to the decisiveness of Borda given many voters.  The results suggest that Y would be 
reasonably decisive in large public elections, meaning that a poor choice of tie-breaker 
(e.g., "random") for Y would not substantially affect its properties in those elections.

5.  The Dissimilar(g) voting scheme

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 A, all R and all Z Í A, let top(i,Z,R) denote the subset of 
alternatives {x Î Z such that, for all y Î Z, [xP_iy or xI_iy]}.

Random Voter Hierarchy and RandomVoterHierarchyScheme:

Let RandomVoterHierarchy(Z,R) denote the probabilistic function 
defined for all A, all R and all non-empty Z Í A by this procedure:

Step 1.  Let W denote a variable subset of the alternatives, and initially 
let W = Z.  Let N' denote a variable subset of N, and initially let N' = 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 voter j from the subset.)

(2.3)  Let W = W Ç top(j,W,R).

Step 3.  Let RandomVoterHierarchy(Z,R) = random(W).

RandomVoterHierarchyScheme denotes the voting scheme such that, for all A, 
all R, all non-empty Z Í A, and all x Î A, RandomVoterHierarchyScheme_x(Z,R) equals the probability that x = 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 (Z,R) by iteratively applying g, and if necessary random(), to each such set.  
We formally define Dissimilar(g) and describe its properties:

Given a correspondence g, Dissimilar(g)(Z,R) is defined for all A, all R 
and all finite non-empty Z Í A by this procedure:

Step 1.  Let L be a #A-tuple of real numbers having one component for each alternative in A, and initally let L_x = 1 for all x Î Z and let L_x = 0 
for all x Î A\Z.  Let Represent be a #A-tuple of alternatives having one component for each alternative in A, and initially let Represent(x) = x 
for all x Î A.  Let D be a subset of the alternatives, and initially let D = 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 let Represent(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(Y) satisfies top cycle, ISA, ICA, IECA.  (Proof in appendix A1.)

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

6.  Conclusions

Y//Dissimilar(Y) 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(Y) is also a single-winner voting function which satisfies ISA, ICA, IECA, top cycle, etc.  In a sense, Dissimilar(Y) is simpler than Y//Dissimilar(Y), but Y is reasonably decisive so in practice Y//Dissimilar(Y) 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 Y and not specify the tie-breaker, since Y is "practically" independent from similar alternatives in public elections

Appendix A1:  Proofs of Lemmas and Theorems

Lemma (2.14):  (Rotations of majority cycle)  If mc = {z₁,z₂,...,z_k} (k>2) is a majority cycle of (Z,R), then mc' = {z₂,...,z_k,z₁} 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 zMz' 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₁ without loss of generality) such that z and z' are adjacent in mc₁, z#z' is last in the majority sequence associated with mc₁, and exactly one alternative in mc₁ is in Y.

Proof:  Assume the premise holds.  By induction on lemma 2.14 (rotatability), there must be a majority cycle mc' = {z₁,z₂,...,z_k} obtained by rotation of mc such that z₁=z and z₂=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_h Î Y.  Since at least one of z₁ and z₂ are in Z\Y, 3<s<h<k.  Since there are at least two alternatives in mc' which are in Y, l<s and l<h.  By 2.12.2 of the definition of similar set and by the definition of majority cycle, the following statements hold:

(2.15.1)  If l > 2, then z_l-1 M z_h.

(2.15.2)  If h < k, then z_l M z_h+1.

(2.15.3)  If l = 2 and h = k, then z_l M z_1.

(2.15.4)  If l = 1, then z_s-1 M z_l.

There are three cases to consider:

Case 1:  l > 2.  By 2.15.1, the ordered set mc₁ = {z₁,z₂,...,z_l-2,z_l-1,z_h,z_h+1,...,z_k}is a majority cycle of (Z,R).  Since z₁=z and z₂=z', z and z' are adjacent in mc₁.  Exactly one alternative (z_h) in Y is in mc₁.  By the definition of majority sequence, z#z' is last in the majority sequence associated with mc₁.

Case 2:  l = 2.  By 2.15.2 and 2.15.3, the ordered set mc₁ = {z₁,z₂,z_h+1,...,z_k} is a majority cycle of (Z,R).  Since z₁=z and z₂=z', z and z' are adjacent in mc₁.  Exactly one alternative (z₂) in Y is in mc₁.  By the definition of majority sequence, z#z' is last in the majority sequence associated with mc₁.

Case 3:  l = 1.  By 2.15.4, the ordered set mc₁ = {z₁,z₂,...z_s-1}is a majority cycle of (Z,R).  Since z₁=z and z₂=z', z and z' are adjacent in mc₁.  Exactly one alternative (z₁) in Y is in mc₁.  By the definition of majority sequence, z#z' is last in the majority sequence associated with mc₁.

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₁,z₂,...z_k) (k>2) is a majority cycle of (Z,R) such that z₁ Î Y and z₁ is the only alternative in mc which is in Y, then for all yÎY {y,z₂,...,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₁Mz₂ implies yMz₂ and z_kMz₁ implies z_kMy.  By the definition of majority cycle, {y,z₂,...,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, yMx if and only if y'Mx, and xMy if and only if xMy'.  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 t(Z,R), t(Z_s,R) is a non-empty subset of t(Z,R), and every X = {x₁,x₂,...,x_k} which is a subset of t(Z_s,R)\Y_s is also a subset of t(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₁,x₂,...,x_k} such that X Í t(Z_s,R)\Y_s and both mc₁={y₁,x₁,x₂,...,x_k} and mc₂={y₂,x₁,x₂,...,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₁ and g₂ are correspondences which satisfy top cycle and are partially independent from similar alternatives, then g₁//g₂ 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₁//g₂ is partially independent from similar alternatives by showing that conditions 3.2.1 and 3.2.2 hold for g = g₁//g₂.

Since g₁ is partially independent from similar alternatives, the following two statements must hold:

(3.7.1)   g₁(Z) Ç A\Y = g₁(Z\Y_s) Ç A\Y

(3.7.2)   g₁(Z) Ç Y = Ø if and only if g₁(Z\Y_s) Ç Y = Ø

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

(3.7.3)   g₁(Z) = (g₁(Z)ÇY) È (g₁(Z) Ç A\Y)

(3.7.4)   g₁(Z\Y_s) = (g₁(Z\Y_s)ÇY) È (g₁(Z\Y_s) Ç A\Y)

Three cases encompass all possibilities:

Case 1:  g₁(Z)ÇY = Ø.  By 3.7.3, g₁(Z) = g₁(Z) Ç A\Y.  By 3.7.2, g₁(Z\Y_s)ÇY = Ø.  By 3.7.4, g₁(Z\Y_s) = g₁(Z\Y_s) Ç A\Y.  By 3.7.1, g₁(Z) = g₁(Z\Y_s), so g2(g₁(Z)) = g2(g₁(Z\Y_s)), which means both conditions 3.2.1 and 3.2.2 hold for g₁//g₂ in case 1.

Case 2:  g₁(Z) Ç A\Y = Ø.  By 3.7.3, g₁(Z) = g₁(Z)ÇY.  By 3.7.1, g₁(Z\Y_s) Ç A\Y = Ø.  By 3.7.4, g₁(Z\Y_s) = g₁(Z\Y_s)ÇY.  Since g₁ is a correspondence, g₁ cannot choose the empty set, so g₁(Z)ÇY ¹ Ø and g₁(Z\Y_s)ÇY ¹ Ø.  Since g₂ is a correspondence, (g₁//g₂)(Z) must choose a non-empty subset of g₁(Z), so g₂(g₁(Z)) Ç A\Y = Ø and g₂(g₁(Z\Y_s)) Ç A\Y = Ø and g₂(g₁(Z))ÇY ¹ Ø and g₂(g₁(Z\Y_s))ÇY ¹ Ø.  So both conditions 3.2.1 and 3.2.2 hold for g₁//g₂ in case 2.

Case 3:  g₁(Z)ÇY ¹ Ø and g₁(Z) Ç A\Y ¹ Ø.  Since g₁ satisfies top cycle, g₁(Z) is a non-empty subset of t(Z,R).  By lemma 2.17 (letting Z_s be g₁(Z)ÈY), Y is a similar set of (g₁(Z)ÈY,R).  Letting Y_s1 =  Y \ (g₁(Z)ÇY) implies Y_s1 Ì Y.  Since g₂ is partially independent from similar alternatives, and since (by properties of intersection and union) g₁(Z) = (g₁(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₂(g₁(Z) ÈY) Ç A\Y = g₂(g₁(Z)) Ç A\Y

(3.7.6)   g₂(g₁(Z) ÈY) Ç Y = Ø if and only if g₂(g₁(Z)) Ç Y = Ø

Letting Y_s2 =  Y \ (g₁(Z\Y_s)ÇY) implies Y_s2 Ì Y.  By properties of intersection and union, (g₁(Z\Y_s)ÈY)\Y_s2 = g₁(Z\Y_s).  By 3.7.1, g₁(Z\Y_s) ÈY = g₁(Z) ÈY.  Combining the last two equations gives (g₁(Z) ÈY)\Y_s2 = g₁(Z\Y_s).  Since g₂ 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₂(g₁(Z) ÈY) Ç A\Y = g₂(g₁(Z\Y_s)) Ç A\Y

(3.7.8)   g₂(g₁(Z) ÈY) Ç Y = Ø if and only if g₂(g₁(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₁//g₂ in case 3.

The similarity conditions hold in all three cases, establishing that g₁//g₂ is partially independent from similar alternatives.

Since g₁ satisfies top cycle, g₁ must choose a non-empty subset of the top cycle, and g₁//g₂ must choose a non-empty subset of what g₁ chooses.  So g₁//g₂ must choose a non-empty subset of the top cycle, which establishes that g₁//g₂ 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 corres