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 cancellationReinforcement 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:

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 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 ZA, 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 iV, let Ri denote 
the ballot cast by voter i.  Thus RiRankings(B) for all iV. (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,bB, 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 BA and all CB, 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') = φ and R(c',c) = φ. 
(2)  For all cC and all xB\C, R(x,c) ≠ φ or R(c,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 BA and all CB, 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 xB\C, R(x,c) = R(x,c') and R(c,x) = R(c',x).
(2)  For all cC and all xB\C, R(x,c) ≠ φ or R(c,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 ZA and all iV, let RiZ denote the restriction of Ri to Z.  
In other words, RiZ is the same as Ri except all alternatives not in Z are deleted.  
Thus RiZRankings(Z) for iV.  Let RZ denote the restriction of R to Z.  
That is, RZ = {R1Z,R2Z,...,RnZ}.

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 xA, let Lx denote the component 
of L which corresponds to x.  Thus, both of the following conditions hold for 
all lotteries L

(1)  For all xA, 0 ≤ Lx ≤ 1.  (Each component represents a probability.)
(2)  Σ(xA)Lx = 1.  (The probabilities sum to 1.)

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

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

(1)  fx(Z,R) = 0 for all A, all R, all non-empty ZA and all xA\Z.  
(2)  fx(Z,RZ) = fx(Z,R) for all A, all R, all non-empty ZA, and all xA.

Just as Lx denotes the component of lottery L which corresponds to alternative x
fx denotes the component of f which corresponds to x.  If fx = 1, x will be elected with 
certainty.  If fx = 0, x will be defeated with certainty.  If 0 < fx < 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 fx(Z,R) is 1 or 0 for all A, all R
all non-empty ZA and all xA.  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 
fx(Z,R) = fx(Z\C0,RZ\C0) for all A, all R, all finite non-empty ZA
all C which is a set of exact clone alternatives within Z given R, all xZ\C  
and all C0 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 Σ(cC) fc(Z,R) = Σ(cC) fc(Z\C0,RZ\C0).  

Independence from Clone Alternatives (ICA):  
A voting scheme f is independent from clone alternatives if and only if 
fx(Z,R) = fx(Z\C0,RZ\C0) for all A, all R, all finite non-empty ZA
all C which is a set of clone alternatives within Z given R, all xZ\C  
and all C0 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 Σ(cC) fc(Z,R) = Σ(cC) fc(Z\C0,RZ\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,bA}. (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,bA, aMb if and only if (a,b)Majorities(R).

For all finite non-empty BA and all CB, 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 xB\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 ZA, and abbreviating k = #Z, call 
the sequence z1,z2,...,zk a majority cyclic permutation of Z given R 
if and only if Z = {z1,z2,...,zk} and (zk,z1)Majorities(R
and (zj,zj+1)Majorities(R) for all j ∈ {1,2,...,k-1}.

Given A, R, and finite non-empty ZA, 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 ZA, 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 ZA, 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 x1,x2,...,xk is a cyclic permutation of (Z,R) if and only if x1, x2, ..., xk are distinct alternatives in Z and [xkMx1 or xk~x1] and [xjMxj+1 or xj~xj+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 τ(Z,R) denote the top cycle of (Z,R).  Formally, given A, 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 ∈ 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 ∈ τ(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(τ(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 clonescore(Y,X,R) denote maximum(over x ∈ X\Y) of #{iN such that there exists y,y' ∈ Y such that [xPiy and not xPiy'] or [yPix and not y'Pix]}.  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) = fx(Z\Y',RZ\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 Ys ⊂ Y such that X∪Ys is a similar set of (Z,R), Y is more clone-like than X∪Ys 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  fx(Z,R) = fx(Z\Y',RZ\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 Ys ⊂ Y such that X∪Ys is a similar set of (Z,R), Y is more clone-like than X∪Ys with respect to R].  To demonstrate satisfaction of ICA, we need to show that fx(Z,R) = fx(Z\Y',RZ\Y') for all Y' ⊂ Y and all x ∈ A\Y such that [there exists no y ∈ Y such that xIiy for all iN].  Since for all x ∉ Z,  fx(Z,R) = 0 and fx(Z\Y',RZ\Y') = 0, we need only establish the following statement:

For all x ∈ Z\Y such that [there exists no y ∈ Y such that xIiy for all iN] and all X ⊆ Z\Y such that x ∈ X and all non-empty Ys ⊂ Y such that X∪Ys is a similar set of (Z,R), Y is more clone-like than X∪Ys with respect to R

Assume x ∈ Z\Y and there exists no y ∈ Y such that xIiy for all iN and X ⊆ Z\Y and x ∈ X and Ys is a non-empty strict subset of Y and X∪Ys is a similar set of (Z,R).  We need to establish that Y is more clone-like than X∪Ys with respect to R

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

There are two cases to consider:

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

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

So the only x ∈ A\Y for which fx(Z,R) need not equal fx(Z\Y',RZ\Y') are those x for which there exists an X∪Ys containing x such that X∪Ys is a similar set and clonescore(X∪Ys,Y,R) = 0.

 

Since the technical restriction in ISA ("for all X ⊆ Z\Y such that x ∈ X and all non-empty Ys ⊂ Y such that X∪Ys is a similar set of (Z,R), Y is more clone-like than X∪Ys") 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 #{iN such that [xPiy for all y ∈ Y] or [yPix for all y ∈ Y]} is less than maximum(over y ∈ Y\X) of #{iN such that [yPix for all x ∈ X] or [xPiy for all x ∈ X]}

 #{iN such that [xPiy for all y ∈ Y\{y'}] or [yPix 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 MC1majoritycycles(Z,R) such that #(MC1∩Y)=1 and (x,x') ∈ min(MC1,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 Zs such that Y is a similar (clone, exact clone) set of (Z,R) and Zs∩τ( Z,R) ≠ and #(Y∩Zs)>1, Y∩Zs is a similar (clone, exact clone) set of (Z∩Zs,R).  (Proof in appendix A1.)

Lemma 2.20 essentially states that when Y is a similar set of Z, Y∩Zs is a similar set of Z∩Zs, 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.

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 :  2Ax  Rn  →  2A\ 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,RZ) = 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 τ(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 Ys ⊂ Y:

(3.2.1)  g(Z,R) ∩ A\Y = g(Z\Ys,RZ\Ys) ∩ A\Y

(3.2.2)  g(Z,R) ∩ Y = if and only if g(Z\Ys,RZ\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 g1//g2//g3//...//f where g1, g2, g3, ... are correspondences and f is either a correspondence or a voting scheme.   Left-to-right precedence is implied; for instance g1//g2//f = (g1//g2)//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 gr be the correspondence defined inductively with respect to a correspondence g by the two rules:

(3.4.1.1)  g1 = g.

(3.4.1.2)  For integer r>1,  gr = gr-1//g.

(3.4.2)  Let r'(g,Z,R) denote the smallest positive integer r such that gr(Z,R) = gr+1(Z,R).

(3.4.3)  Abbreviating r' = r'(g,Z,R), [g] is the correspondence such that [g](Z,R) = gr'(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 Ψ//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 correspondence g satisfies top cycle if and 
only if g(Z,R) ⊆ τ(Z,R) for all A, all R, and all non-empty Z ⊆ A.  A voting scheme f 
satisfies top cycle if and only if fx(Z,R) = 0 for all A, all R, all non-empty Z ⊆ A
and all x ∉ τ(Z,R).

Lemma (3.7):  If g1 and g2 are correspondences which satisfy top cycle and are partially independent from similar alternatives, then g1//g2 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 <β>Ψ1 and <β>Ψ 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 ψ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 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 ψ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):  Ψ1 and <β>Ψ

(4.2.1)  Ψ1 is the correspondence defined by the rule Ψ1(Z,R) = ψ1(Z,R) for all A, all R, 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, "... 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'Acadmie Franaise, 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 Ψ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.

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

Random Voter Hierarchy and RandomVoterHierarchyScheme:

Let RandomVoterHierarchy(Z,R) denote the probabilistic function 
defined for all A, all R and all non-empty ZA 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 ZA, and all xA, RandomVoterHierarchySchemex(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 ZA 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 Lx = 1 for all x Z and let Lx = 0 
for all xA\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 xA.  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 Lx = 0.

(2.5)  For all x ∈ Z such that Represent(x) ∈ G, let Lx = Lx / #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 Yu 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 Yu\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, Lx=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.)

6.  Conclusions

Ψ//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

Appendix A1:  Proofs of Lemmas and Theorems

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

Proof:  Assume the premise holds.  By induction on lemma 2.14 (rotatability), there must be a majority cycle mc' = {z1,z2,...,zk} obtained by rotation of mc such that z1=z and z2=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 zl, zs, zh ∈ Y.  Since at least one of z1 and z2 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 zl-1 M zh.

(2.15.2)  If h < k, then zl M zh+1.

(2.15.3)  If l = 2 and h = k, then zl M z1.

(2.15.4)  If l = 1, then zs-1 M zl.

There are three cases to consider:

Case 1:  l > 2.  By 2.15.1, the ordered set mc1 = {z1,z2,...,zl-2,zl-1,zh,zh+1,...,zk}is a majority cycle of (Z,R).  Since z1=z and z2=z', z and z' are adjacent in mc1.  Exactly one alternative (zh) in Y is in mc1.  By the definition of majority sequence, z#z' is last in the majority sequence associated with mc1.

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

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

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 = {z1,z2,...zk) (k>2) is a majority cycle of (Z,R) such that z1 ∈ Y and z1 is the only alternative in mc which is in Y, then for all y∈Y {y,z2,...,zk} is a majority cycle of (Z,R).

Proof:  By 2.12.2 of the definition of similar set, for all y∈ Y, z1Mz2 implies yMz2 and zkMz1 implies zkMy.  By the definition of majority cycle, {y,z2,...,zk} must be a majority cycle of (Z,R).

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

Proof:  Abbreviate Ys = Y∩Zs 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 Ys with respect to (Zs,R):

Since Ys ⊆ Zs and Ys ≠ , 2.12.1 holds for Ys with respect to (Zs,R).

Since Ys ⊆ Y and Zs\Ys ⊆ Z\Y and 2.12.2 holds for Y with respect to (Z,R), it must be the case that for all y,y' ∈ Ys and all x ∈ Zs\Ys, yMx if and only if y'Mx, and xMy if and only if xMy'.  So 2.12.2 holds for Ys with respect to (Zs,R).

Since Zs ⊆ Z and Zs ≠ , every majority cycle of (Zs,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 Zs is in τ(Z,R), τ(Zs,R) is a non-empty subset of τ(Z,R), and every X = {x1,x2,...,xk} which is a subset of τ(Zs,R)\Ys 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' ∈ Ys and all X = {x1,x2,...,xk} such that X ⊆ τ(Zs,R)\Ys and both mc1={y1,x1,x2,...,xk} and mc2={y2,x1,x2,...,xk} are majority cycles of (Zs,R), all four conditions of 2.12.3 hold for Ys with respect to (Zs,R).

Since all conditions of 2.12 hold for Ys with respect to (Zs,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 gr is a correspondence, for all r∈{1,2,...} 0 < #gr < #Z.  Since r' is the smallest integer r>1 such that gr = gr+1, r' is also the smallest integer r>1 such that #gr = #gr+1.  So #gr > #gr+1 for all r∈{1,2,..,r'-1}, and since #gr' > 0, by induction #gr'-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, #gr'-k > #Z.  But this would contradict #gr < #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 g1 and g2 are correspondences which satisfy top cycle and are partially independent from similar alternatives, then g1//g2 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 Ys be a strict subset of Y.  We first establish that g1//g2 is partially independent from similar alternatives by showing that conditions 3.2.1 and 3.2.2 hold for g = g1//g2.

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

(3.7.1)   g1(Z) ∩ A\Y = g1(Z\Ys) ∩ A\Y

(3.7.2)   g1(Z) ∩ Y = if and only if g1(Z\Ys) ∩ Y =

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

(3.7.3)   g1(Z) = (g1(Z)∩Y) ∪ (g1(Z) ∩ A\Y)

(3.7.4)   g1(Z\Ys) = (g1(Z\Ys)∩Y) ∪ (g1(Z\Ys) ∩ A\Y)

Three cases encompass all possibilities:

Case 1:  g1(Z)∩Y = .  By 3.7.3, g1(Z) = g1(Z) ∩ A\Y.  By 3.7.2, g1(Z\Ys)∩Y = .  By 3.7.4, g1(Z\Ys) = g1(Z\Ys) ∩ A\Y.  By 3.7.1, g1(Z) = g1(Z\Ys), so g2(g1(Z)) = g2(g1(Z\Ys)), which means both conditions 3.2.1 and 3.2.2 hold for g1//g2 in case 1.

Case 2:  g1(Z) ∩ A\Y = .  By 3.7.3, g1(Z) = g1(Z)∩Y.  By 3.7.1, g1(Z\Ys) ∩ A\Y = .  By 3.7.4, g1(Z\Ys) = g1(Z\Ys)∩Y.  Since g1 is a correspondence, g1 cannot choose the empty set, so g1(Z)∩Y ≠ and g1(Z\Ys)∩Y ≠ .  Since g2 is a correspondence, (g1//g2)(Z) must choose a non-empty subset of g1(Z), so g2(g1(Z)) ∩ A\Y = and g2(g1(Z\Ys)) ∩ A\Y = and g2(g1(Z))∩Y ≠ and g2(g1(Z\Ys))∩Y ≠ .  So both conditions 3.2.1 and 3.2.2 hold for g1//g2 in case 2.

Case 3:  g1(Z)∩Y ≠ and g1(Z) ∩ A\Y ≠ .  Since g1 satisfies top cycle, g1(Z) is a non-empty subset of τ(Z,R).  By lemma 2.17 (letting Zs be g1(Z)∪Y), Y is a similar set of (g1(Z)∪Y,R).  Letting Ys1 =  Y \ (g1(Z)∩Y) implies Ys1 ⊂ Y.  Since g2 is partially independent from similar alternatives, and since (by properties of intersection and union) g1(Z) = (g1(Z) ∪Y)\Ys1, by 3.2.1 and 3.2.2 the following two statements must hold in case 3:

(3.7.5)   g2(g1(Z) ∪Y) ∩ A\Y = g2(g1(Z)) ∩ A\Y

(3.7.6)   g2(g1(Z) ∪Y) ∩ Y = if and only if g2(g1(Z)) ∩ Y =

Letting Ys2 =  Y \ (g1(Z\Ys)∩Y) implies Ys2 ⊂ Y.  By properties of intersection and union, (g1(Z\Ys)∪Y)\Ys2 = g1(Z\Ys).  By 3.7.1, g1(Z\Ys) ∪Y = g1(Z) ∪Y.  Combining the last two equations gives (g1(Z) ∪Y)\Ys2 = g1(Z\Ys).  Since g2 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)   g2(g1(Z) ∪Y) ∩ A\Y = g2(g1(Z\Ys)) ∩ A\Y

(3.7.8)   g2(g1(Z) ∪Y) ∩ Y = if and only if g2(g1(Z\Ys)) ∩ 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 g1//g2 in case 3.

The similarity conditions hold in all three cases, establishing that g1//g2 is partially independent from similar alternatives.

Since g1 satisfies top cycle, g1 must choose a non-empty subset of the top cycle, and g1//g2 must choose a non-empty subset of what g1 chooses.  So g1//g2 must choose a non-empty subset of the top cycle, which establishes that g1//g2 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, yMx 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 g1//g2 satisfies top cycle if g1 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 Ys is a strict subset of Y.  By the definition of Ψ1, Ψ1(Z) = ψ1(Z) and Ψ1(Z\Ys) = ψ1(Z\Ys), so we need to establish the following two statements:

(4.4.1)  ψ1(Z) ∩ A\Y = ψ1(Z\Ys) ∩ A\Y

(4.4.2)  ψ1(Z) ∩ Y = if and only if ψ1(Z\Ys) ∩ 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)  zMx.

(4.4.4)  For all mc such that mc is a majority cycle of (Z,R) and mc contains both z and x, z#x is not last in ms(mc).

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

(4.4.5)  z'Mx.

(4.4.6)  For all mc' such that mc' is a majority cycle of (Z\Ys,R) and mc' 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\Ys).  By the definition of ψ1, x∈Z, and since x ∈ A\Y, x ∈ Z\Y and x ∈ Z\Ys.  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\Ys,R) is a majority cycle of (Z,R), so there cannot be any z' ∈ Z\Ys such that 4.4.5 and 4.4.6 both hold.  Therefore, by the definition of ψ1, x ∈ ψ1(Z\Ys). 

Case 4.4.1.2:  x ∈ A\Y and x ∈ ψ1(Z\Ys).  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\Ys,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\Ys).  By the definition of ψ1, x∈ Z, so x ∈ Z\Y, and x ∈ Z\Ys.  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 Ys ⊂ Y, z ∈ Z\Ys.  By the definition of majority cycle, every majority cycle of (Z\Ys,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\Ys,R) which contains z and x.  Therefore, by the definition of ψ1, x ∉ ψ1(Z\Ys). 

Case 4.4.1.3.2:  z ∈ Y.  By 4.4.3 and similarity, yMx for all y∈ Y.  By 4.4.4 and similarity, for all y∈Y there is no majority cycle mc of (Z,R) such that mc contains both y and x and y#x is last in ms(mc).  Since Ys ⊂ Y, yMx for all y ∈ Y\Ys.  Since all majority cycles of (Z\Ys,R) are majority cycles of (Z,R), for all y ∈ Y\Ys there is no majority cycle mc' of (Z\Ys,R) such that mc' contains both y and x and y#x is last in ms(mc').  Therefore, by the definition of ψ1, x ∉ ψ1(Z\Ys).  

Case 4.4.1.4:  x ∈ A\Y and x ∉ ψ1(Z\Ys).  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\Ys)∩Y ≠ .  There exists an alternative in Y, call it y0 with no loss of generality, such that y0 ∈ ψ1(Z)∩Y.  By the definition of ψ1, for all z∈Z such that zMy0, there exists a majority cycle mc of (Z,R) such that z#y0 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 zMy0 there exists a majority cycle mc' of (Z,R) such that mc' = {z,y0,...,zk} and y0 is the only alternative in Y which is in mc' and z#y0 is last in ms(mc').  By lemma 2.16 (substitutability), for all y∈Y and for all z ∈ Z\Y such that zMy0, there is a majority cycle mc" of (Z,R) such that mc" = {z,y,...,zk} and y is the only alternative in Y which is in mc" and z#y is last in ms(mc").  Furthermore, mc" is also a majority cycle of (Z\Ys,R).  Therefore, for all y ∈ Y\Ys and all z ∈ Z\Y such that zMy, there exists a majority cycle of (Z\Ys,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\Ys and #(Y\Ys) > 1.  y0 is in Y\Ys?

Case 4.4.2.1.3:  z ∈ Y\Ys and #(Y\Ys) = 1.  y0 is in Y\Ys?

Case 4.4.2.1.4:  z ∈ Ys.  y0 ∈ Y\Ys?

Case 4.4.2.2:  ψ1(Z\Ys)∩Y ≠ .  We must show that ψ1(Z)∩Y ≠ .

Case 4.4.2.3:  ψ1(Z)∩Y = .  We must show that ψ1(Z\Ys)∩Y = .

Case 4.4.2.4:  ψ1(Z\Ys)∩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 > c

4:  b > c > a

2:  c > a > b

1:  c > a ~ b

The following aggregate properties relations and properties are tallied:

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

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

cMa since c#a > a#c.    (7 = 4+3 > 5)

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

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

min({a,b,c}) = {(a,b), (c,a)} since a#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}.

Appendix A3:  Decisiveness of Ψ1 and Ψ

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 (Oops NOT!) 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 either b or c, 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, Lb and Lc are divided by #G=2, so L=(1,,).  Also, Representc is set to b so Represent=(a,b,b).

In step 2.5, c is 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 either a or b, 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, La, Lb and Lc are divided by #G=2, so L=(,,).  Also, Representb and Representc are set to a so Represent=(a,a,a).

In step 2.5, b is 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- .