"Maximize Affirmed Majorities" (MAM) is Independent of Clone Alternatives.

Revised:  December 19, 2003

The criterion independence of clone alternatives was first promoted by TN Tideman.  
For more information, including the rationale that justifies the criterion, see the document 
"Independence from Similar Alternatives."

Call a subset of alternatives BA a set of exact clones within A given 
a collection of votes R if and only if, for all pairs of alternatives x,yB
every vote in R expresses indifference between x and y.

Call a subset of alternatives BA a set of clones within A given a 
collection of votes R if and only if both of the following conditions hold: 
    (1)  For all x,yB and all zA\B, every vote in R that ranks z over x also 
          ranks z over y, and every vote in R that ranks x over z also ranks y over z.
    (2)  For all zA\B, B ∪ {z} is not a set of exact clones within A given R

(Condition 2 is an innocuous technical condition which allows us to relax condition 1, 
thereby allowing some voters, but not all, to be indifferent between clones and some 
non-clones.  Thus our definition of clone alternatives is slightly broader than Tideman's.  
This makes our independence of clones criterion slightly stronger than his; however 
the proof of its satisfaction becomes slightly more complicated.)

For all non-empty BA and all collections of votes R, let R|B denote 
the restriction of R to the alternatives in B.  That is, R|B is the same as R  
except all preferences regarding alternatives not in B are deleted.

Call a function f a decision scheme if and only if, for all finite non-empty BA 
and all collections of votes R, the following three conditions hold: 
    (1)  For all xB, f(x,B,R) = 0. 
    (2)  For all xA, 0 ≤ f(x,B,R) ≤ 1. 
    (3)  Σ(x B)f(x,B,R) = 1. 
    (4)  For all xA and all CA, if BC then f(x,B,R) = f(x,B,R|C). 

The interpretation of f(x,B,R) is the probability that alternative x will be elected from 
a subset of "nominees" B given votes R.  Condition 1 implies only an alternative in B
a nominee, will be elected.  Condition 2 reflects the fact that any probability is always a 
real number between 0 and 1.  Condition 3 reflects the fact that the sum of probabilities 
over an exhaustive set of mutually exclusive events is always 1, so a decision scheme 
often called a "lottery") corresponds is a voting procedure that always elects exactly one 
alternative. (In other words, a resolute procedure.)  The procedure is not necessarily 
always deterministic.  Note that this framework encompasses both deterministic and 
non-deterministic voting procedures (including those that are "usually" deterministic 
such as MAM).  Condition 4 implies the outcome will depend only on the restriction 
of the votes to the nominees, a mild condition which simplifies the notation in the 
current context where we are exploring the effect of changing the set of nominees.)

Call a decision scheme f independent of clone alternatives if and only if both of 
the following conditions hold for all finite A, all R, all finite non-empty CA 
that is a set of clones within A given R, and all D which is a strict subset of C
    (1)  For all xA\C, f(x,A,R) = f(x,A\D,R|A\D).
    (2)  Σ(x C)f(x,A,R) = Σ(x C)f(x,A\D,R|A\D).  

(Condition 1 means the probability any particular "non-clone" will be elected must be 
unaffected by deletion of a strict subset of the clones.  Condition 2 means the probability 
that the elected alternative will be within the set of clones must be unaffected by deletion 
of a strict subset of the clones.  Note that condition 2 automatically holds if condition 1 
holds since, by condition 3 of the definition of a decision scheme, the sum of the clones' 
probabilities of being elected is 1 minus the sum of the non-clones' probabilities of being 
elected, which is unaffected by deletion of a strict subset of clones if condition 1 holds.)

Satisfaction of independence of clone alternatives (ICA) implies manipulation-minded 
people cannot expect to affect the outcome by nominating alternatives which are nearly 
identical to those already on the ballot.  ICA is a stronger criterion than independence 
of exact clone alternatives
(IECA, which would be defined in an analogous manner).  

For more information about these criteria and some examples showing how some voting 
procedures fail to satisfy them, see the draft "Independence from Similar Alternatives." 

Example 1:  Independence of clone alternatives.

Suppose there are 3 alternatives x, y and z.  
Suppose the voters vote the following rankings:

65% 35%
x y
y z
z x

Clearly {y,z} is a set of clones since every voter either ranks x over both y and z  
or both y and z over xICA requires that the probability that x is elected must not 
change if z is deleted.  Note that every voting procedure that reduces to majority rule 
when there are only two nominees (that is, nearly every voting procedure) will elect x  
if {x,y} is the set of nominees.  Thus any voting procedure that reduces to majority 
rule when there are only two nominees and is independent of clones must elect x  
if {x,y,z} is the set of nominees.  Otherwise, would-be manipulators will nominate 
alternatives like z that are obviously inferior (to y).  The Borda procedure, for instance,  
elects x from {x,y} but elects y from {x,y,z}.  Thus the faction that nominates the 
most alternatives has an unfair advantage under Borda, creating an incentive to 
nominate many inferior alternatives, thereby making farces of elections. (It can be 
seen from this example that ICA is closely related to the criterion independence 
from Pareto-dominated alternatives
.)  

Example 2:  Complete independence of clone alternatives in a "tied" scenario.

Suppose there are 3 alternatives x, y and z.  
Suppose the voters vote the following rankings:

50% 50%
x z
y y
z x

It can be seen that {y,z} is a set of clones since every voter either ranked x  
over both y and z or both y and z over xICA requires that the probability 
that x is elected must not change if z is deleted from the set of alternatives 
and from the votes.  Clearly, any voting procedure which is anonymous  
and neutral will give x a chance of being elected if {x,y} is the set of 
nominated alternatives.  Thus any voting procedure which is anonymous
neutral and independent of clones must give x a chance of being elected 
if {x,y,z} is the set of nominees. (By similar reasoning, since {x,y} is also 
a set of clones, any voting procedure which is anonymousneutral and 
independent of clones must give z a chance of being elected.  Thus, 
since the sum of all alternatives' probabilities of being elected must be 1, 
such a procedure must give y zero chance of being elected.)


Theorem "MAM is Independent of Clones."  

Proof:  Refer to the definitions in the document "A formal definition of MAM".  
Pick any set of alternatives A and any collection of votes R.  Assume CA is a 
finite non-empty set of clones within A given R and assume D is a strict subset of C.  
Abbreviate A' = A\D and R' = R|A' ( the restriction of R to A').  Pick any xA\C.  
Let MAMx denote the probability that MAM elects x from A given R.  Let MAM'x 
denote the probability that MAM elects x from A' given R'.  To show that MAM 
satisfies ICA, we must show MAMx = MAM'x. (In other words, that MAM satisfies 
condition 1 of the definition of ICA.  As noted above, satisfaction of condition 2 
follows immediately if condition 1 is satisfied.)  Let Wx = {σ ∈ L(R,A) such that 
MAM(A,R,σ) = x}.  Thus MAMx = #Wx/#L(R,A).  Let W'x = {σ'L(R',A'
such that MAM(A',R',σ') = x}.  Thus MAM'x = #W'x/#L(R',A').  We must 
establish the following proposition: 

        Proposition (1)  #Wx/#L(R,A) = #W'x/#L(R',A').

Proof of 1:  By inspection of the definition of L(.,.), #L(R,A) = (#R)! × (#A)! 
and #L(R',A') = (#R')! × (#A')!.  Since #R' = #R, the following statement holds:

(1.2)  #L(R,A)/#L(R',A') = ((#A)!)/((#A')!) 

Thus proposition 1 will follow immediately if we establish the following proposition:

Proposition (1.3):  #Wx = #W'x × ((#A)!)/((#A')!). 

For all σ ∈ L(R,A), let σ|A' denote the restriction of σ to A'.  In other words, 
σ|A' = (σR,σA)|A' = (σR|A',σA|A') where σR|A' is the same as σR except that 
all alternatives in D are deleted, and σA|A' is the same as σA except all alternatives 
in D are deleted. (Thus σ|A'L(R',A').)  By 1.2, the following statement holds: 

(1.4)  For all σ'L(R',A'), #{σ ∈ L(R,A) such that σ|A' = σ'} = ((#A)!)/((#A')!) 

Pick any σ ∈ L(R,A).  By 1.4, proposition 1.3 will follow immediately if we 
establish the following proposition:

Proposition (1.5)  σ ∈ Wx if and only if σ|A'W'x.

Let XPairs denote Pairs(A)\Pairs(C). (In other words, XPairs is the ordered pairs of 
alternatives involving at least one non-clone.)  Let XPairs' denote Pairs(A')\Pairs(C). 
(The ordered pairs of alternatives in A' involving at least one non-clone.)  Make the 
following abbreviations:  

Maj = Majorities(A,R). 
RVH = RVH(A,R,σ). 
Precede(a,b) = Precede(a,b,A,R,σ) for all a,bA.
Aff = Affirmed(A,R,σ). 
Top = Top(A,R,σ). 
MAM = MAM(A,R,σ). 

σ' = σ|A'.  
Maj' = Majorities(A',R'). 
RVH' = RVH(A',R',σ'). 
Precede'(a,b) = Precede(a,b,A',R',σ') for all a,bA'.
Aff' = Affirmed(A',R',σ'). 
Top' = Top(A',R',σ'). 
MAM' = MAM(A',R',σ'). 

The following propositions, 1.6 through 1.18, will facilitate the proof of 1.5:

Proposition (1.6): "Random Voter Hierarchy ranks clones together."  
That is, for all yA\C, RVH either ranks y over every alternative in C 
or ranks every alternative in C over y

Proof of 1.6:  Pick any yA\C and any c,c'C.  By condition 2 of 
the definition of clones, at least one vote ranks y over c or c over y.  
This means R(yc) is not empty.  Thus, by condition 1 of the definition 
of clones, R(yc') is not empty.  Furthermore, condition 1 of the definition 
of clones implies Rσyc = Rσyc'. (That is, the vote in R(yc) ranked highest 
by σR is the same as the vote in R(yc') ranked highest by σR.)  Furthermore, 
condition 1 of the definition of clones implies Rσyc ranks y relative to c 
the same as Rσyc' ranks y relative to c'.  It follows by the definition of 
Random Voter Hierarchy
that RVH either ranks y over both c and c' 
or ranks both c and c'  over y.  Since y, c and c' were picked arbitrarily, 
1.6 is established.         QED 

Proposition (1.7):  For all a,bA', R(a,b)|A' = R'(a,b). (That is, 
the restriction to A' of the votes in R that rank a over b is the same 
as the votes in R' that rank a over b.) 

Proof of 1.7:  This follows by inspection of the definitions of A' and R'.   QED 

Proposition (1.8):  Maj ∩ Pairs(A') = Maj'

Proof of 1.8:  This follows by 1.7 and the definition of Majorities().      QED 

Proposition (1.9):  For all a,bA', RVH ranks a over b 
if and only if RVH' ranks a over b

Proof of 1.9:  This follows immediately from theorem "Random Voter 
Hierarchy is Independent of Irrelevant Alternatives (1)"
.           QED 

Proposition (1.10):  For all a,bA', Precede(a,b) ∩ Pairs(A') = Precede'(a,b). 

Proof of 1.10:  This follows immediately from theorem "Precedence is 
Independent of Irrelevant Alternatives."
    QED 

Proposition (1.11):  For all yA\C and all c,c'C
the following four statements hold: 
       (1.11.1)  R(y,c) = R(y,c'). 
       (1.11.2)  R(c,y) = R(c',y).  
       (1.11.3)  (y,c) ∈ Maj if and only if (y,c') ∈ Maj. 
       (1.11.4)  (c,y) ∈ Maj if and only if (c',y) ∈ Maj. 

Proof of 1.11:  Statements 1.11.1 and 1.11.2 are implied by condition 1 of 
the definition of clones.  Statements 1.11.3 and 1.11.4 follow from 1.11.1 
and 1.11.2 and inspection of the definition of Majorities().     QED 

Proposition (1.12):  For all aA, all y,zA\C and all c,c'C
all four of the following statements hold: 
       (1.12.1)  (c,y) ∈ Precede(z,a) if and only if (c',y) ∈ Precede(z,a).  
       (1.12.2)  (y,c) ∈ Precede(a,z) if and only if (y,c') ∈ Precede(a,z).  
       (1.12.3)  (y,a) ∈ Precede(c,z) if and only if (y,a) ∈ Precede(c',z).  
       (1.12.4)  (a,y) ∈ Precede(z,c) if and only if (a,y) ∈ Precede(z,c'). 

Proof of 1.12:  By symmetry, we need only establish the "only if" clauses.  
First we establish 1.12.1:  Pick any aA, any y,zA\C and any c,c'C.  
Assume (c,y) ∈ Precede(z,a).  We must show (c',y) ∈ Precede(z,a).  
Since (c,y) ∈ Precede(z,a), one of the following four conditions must hold:

(1.12.1.1)  #R(c,y) > #R(z,a). 
(1.12.1.2)  #R(c,y) = #R(z,a) and #R(y,c) < #R(a,z). 
(1.12.1.3)  #R(c,y) = #R(z,a) and #R(y,c) = #R(a,z
                 and RVH ranks a over y
(1.12.1.4)  #R(c,y) = #R(z,a) and #R(y,c) = #R(a,z
                 and a = y and RVH ranks c over z.

By 1.11.1, #R(c,y) = #R(c',y).  By 1.11.2, #R(y,c) = #R(y,c').  
By 1.6, RVH ranks c' over z if and only if RVH ranks c over z.  
Therefore one of the following four conditions must hold:

(1.12.1.5)  #R(c',y) > #R(z,a). 
(1.12.1.6)  #R(c',y) = #R(z,a) and #R(y,c') < #R(a,z). 
(1.12.1.7)  #R(c',y) = #R(z,a) and #R(y,c') = #R(a,z
                 and RVH ranks a over y
(1.12.1.8)  #R(c',y) = #R(z,a) and #R(y,c') = #R(a,z
                 and a = y and RVH ranks c' over z.

By the definition of precedence, (c',y) ∈ Precede(z,a), establishing the 
"only if" clause of 1.12.1.  By symmetry, the "if" clause must also hold.  
Thus 1.12.1 has been established.  By similar reasoning, 1.12.2, 
1.12.3 and 1.12.4 can be established.       QED  

Proposition (1.13):  All four of the following statements hold: 
        (1.13.1)  For all yA\C and all c,c'C
                       (y,c) ∈ Aff if and only if (y,c') ∈ Aff. 
        (1.13.2)  For all yA\C and all c,c'C
                      (c,y) ∈ Aff if and only if (c',y) ∈ Aff.  
        (1.13.3)  For all yA\C and all c,c'C\D
                       (y,c) ∈ Aff' if and only if (y,c') ∈ Aff'
        (1.13.4)  For all yA\C and all c,c'C\D
                       (c,y) ∈ Aff' if and only if (c',y) ∈ Aff'.  

Proof of 1.13:  First we prove 1.13.1 and 1.13.2:  For all a,bA
abbreviate Affab = Aff ∩ Precede(a,b).  Let Q denote the union of 
the following four sets:   
        Q1 = {(y,c) ∈ Aff such that yA\C and cC  
                  and there exists c'C such that (y,c') ∉ Aff}. 
        Q2 = {(y,c)Pairs(A)\Aff such that yA\C and cC  
                  and there exists c'C such that (y,c') ∈ Aff}. 
        Q3 = {(c,y) ∈ Aff such that yA\C and cC  
                  and there exists c'C such that (c',y) ∉ Aff}. 
        Q4 = {(c,y)Pairs(A)\Aff such that yA\C and cC  
                  and there exists c'C such that (c',y) ∈ Aff}.  
To establish 1.13.1 and 1.13.2, we must show Q is empty.  Suppose the contrary.  
By theorem "Precedence is a Strict Ordering" we can pick (a,b)Q such that 
Q ∩ Precede(a,b) is empty. (That is, (a,b) is the pair in Q preceded by no other 
pair in Q.)  There are four cases to consider:  

Case 1.13.5:  (a,b) ∈ Q1.  This means aA\C and bC and (a,b) ∈ Aff 
and there exists cC such that (a,c) ∉ Aff.  By the definition of Affirmed()
Aff ⊆ Maj, so (a,b) ∈ Maj.  By 1.11.3, (a,c) ∈ Maj.  Since (a,c) ∈ Maj\Aff, 
by the definition of Affirmed() (a,c) must be inconsistent with Affac.  This 
means there exist alternatives z1,z2,...,zkA such that z1 = c and zk = a 
and {(z1,z2),(z2,z3),...,(zk-1,zk)} ⊆ Affac.  Since z1C, we can let i denote 
the largest integer in {1,2,...,k} such that ziC.  Since zk = aA\C, i < k.  
Since (zk,c) ∈ Maj, (c,zk) ∉ Maj.  By 1.11.4, (c',zk) ∉ Maj for all c'C.  
Since (zk-1,zk) ∈ Maj, this means zk-1C, so i < k-1.  Thus zi+1A\C and 
zi+2A\C.  Thus we can let P denote {(zi+1,zi+2),...,(zk-1,zk)} ∪ {(zk,b)}.  
Since P ⊆ Aff, (b,zi+1) is inconsistent with Aff.  By theorem "Consistency 
Maintained"
, Aff is internally consistent, so (b,zi+1) ∉ Aff.  Since (zi,zi+1) ∈ Aff 
and (b,zi+1) ∉ Aff, (zi,zi+1)Q3.  Since (zi,zi+1) ∈ Precede(a,c), by 1.12.4 
(zi,zi+1) ∈ Precede(a,b).  Thus (zi,zi+1)Q ∩ Precede(a,b).  But this is a 
contradiction since Q ∩ Precede(a,b) is empty, so this case is impossible.  

Case 1.13.6:  (a,b) ∈ Q2.  This means aA\C and bC and (a,b) ∉ Aff 
and there exists cC such that (a,c) ∈ Aff.  By the definition of Affirmed()
Aff ⊆ Maj, so (a,c) ∈ Maj.  By 1.11.3, (a,b) ∈ Maj.  Since (a,b) ∈ Maj\Aff, 
by the definition of Affirmed() (a,b) must be inconsistent with Affab.  This 
means there exist alternatives z1,z2,...,zkA such that z1 = b and zk = a and 
{(z1,z2),(z2,z3),...,(zk-1,zk)} ⊆ Affab.  Since z1C, we can let i denote the 
largest integer in {1,2,...,k} such that ziC.  Since zk = aA\C, i < k.  
Since (zk,c) ∈ Maj, (c,zk) ∉ Maj.  By 1.11.4, (c',zk) ∉ Maj for all c'C.  
Since (zk-1,zk) ∈ Maj, this means zk-1C, so i < k-1.  Thus zi+1A\C and 
zi+2A\C.  Thus we can let P denote {(zi+1,zi+2),...,(zk-1,zk)} ∪ {(zk,c)}.  
Since P ⊆ Aff, (c,zi+1) is inconsistent with Aff.  By theorem "Consistency 
Maintained"
, Aff is internally consistent, so (c,zi+1) ∉ Aff.  Since (zi,zi+1) ∈ Aff 
and (c,zi+1) ∉ Aff, (zi,zi+1)Q3.  Thus (zi,zi+1)Q ∩ Precede(a,b).  
But this is a contradiction since Q ∩ Precede(a,b) is empty, so this case 
is impossible.  

Case 1.13.7:  (a,b) ∈ Q3.  This means aC and bA\C and (a,b) ∈ Aff 
and there exists cC such that (c,b) ∉ Aff.  By the definition of Affirmed()
Aff ⊆ Maj, so (a,b) ∈ Maj.  By 1.11.4, (c,b) ∈ Maj.  Since (c,b) ∈ Maj\Aff, 
by the definition of Affirmed() (c,b) must be inconsistent with Affcb.  This 
means there exist alternatives z1,z2,...,zkA such that z1 = b and zk = c and 
{(z1,z2),(z2,z3),...,(zk-1,zk)} ⊆ Affcb.  Since zkC, we can let i denote the 
smallest integer in {1,2,...,k} such that ziC.  Since z1 = bC, i > 1.  
Since (c,z1) ∈ Maj, (z1,c) ∉ Maj.  By 1.11.3, (z1,c') ∉ Maj for all c'C.  
Since (z1,z2) ∈ Maj, this means z2C, so i > 2.  Thus zi-1A\C and 
zi-2A\C.  Thus we can let P denote {(a,z1)} ∪ {(z1,z2),...,(zi-2,zi-1)}.  
Since P ⊆ Aff, (zi-1,a) is inconsistent with Aff.  By theorem "Consistency 
Maintained"
, Aff is internally consistent, so (zi-1,a) ∉ Aff.  Since (zi-1,zi) ∈ Aff 
and (zi-1,a) ∉ Aff, (zi-1,zi)Q1.  Since (zi-1,zi) ∈ Precede(c,b), by 1.12.3 
(zi-1,zi) ∈ Precede(a,b).  Thus (zi-1,zi)Q ∩ Precede(a,b).  But this is a 
contradiction since Q ∩ Precede(a,b) is empty, so this case is impossible.  

Case 1.13.8:  (a,b) ∈ Q4.  This means aC and bA\C and (a,b) ∉ Aff 
and there exists cC such that (c,b) ∈ Aff.  By the definition of Affirmed()
Aff ⊆ Maj, so (c,b) ∈ Maj.  By 1.11.4, (a,b) ∈ Maj.  Since (a,b) ∈ Maj\Aff, 
by the definition of Affirmed() (a,b) must be inconsistent with Affab.  This 
means there exist alternatives z1,z2,...,zkA such that z1 = b and zk = a and 
{(z1,z2),(z2,z3),...,(zk-1,zk)} ⊆ Affab.  Since zkC, we can let i denote the 
smallest integer in {1,2,...,k} such that ziC.  Since z1 = bC, i > 1.  
Since (c,z1) ∈ Maj, (z1,c) ∉ Maj.  By 1.11.3, (z1,c') ∉ Maj for all c'C.  
Since (z1,z2) ∈ Maj, this means z2C, so i > 2.  Thus zi-1A\C and 
zi-2A\C.  Thus we can let P denote {(c,z1)} ∪ {(z1,z2),...,(zi-2,zi-1)}.  
Since P ⊆ Aff, (zi-1,c) is inconsistent with Aff.  By theorem "Consistency 
Maintained"
, Aff is internally consistent, so (zi-1,c) ∉ Aff.  Since (zi-1,zi) ∈ Aff 
and (zi-1,c) ∉ Aff, (zi-1,zi)Q1.  Thus (zi-1,zi)Q ∩ Precede(a,b).  But this 
is a contradiction since Q ∩ Precede(a,b) is empty, so this case is impossible.  

Since all four cases are impossible, the contrary assumption that Q is not empty 
cannot hold.  Thus 1.13.1 and 1.13.2 are established.

Next we prove 1.13.3 and 1.13.4:  Note that C\D is a set of clones within A'  
given R'.  Since 1.13.1 and 1.13.2 hold for any A, any R, and any C which is 
a set of clones within A given R, 1.13.3 and 1.13.4 can be established by 
substituting A' for AR' for R, and C\D for C within 1.13.1 and 1.13.2.     QED

Proposition (1.14):  For all (a,b) ∈ XPairs and all P ⊆ Aff ∩ Precede(a,b), 
if (a,b) is inconsistent with P and (a,b) is consistent with all subsets of 
Aff ∩ Precede(a,b) smaller than P, then at most one alternative in C is 
involved in any pairs in P.  

Proof of 1.14:  For all a,bA, abbreviate Affab = Aff ∩ Precede(a,b).  
Pick any (a,b) ∈ XPairs and any P ⊆ Affab.  Assume (a,b) is inconsistent 
with P and consistent with all  subsets of Affab smaller than P.  This means 
there exist alternatives z1,z2,...,zkA such that z1 = b and zk = a and 
P = {(z1,z2),(z2,z3),...,(zk-1,zk)}.  We must show that at most one alternative 
in C is in {z1,z2,...,zk}.  Suppose the contrary.  This implies means we can 
let s denote the smallest integer in {1,2,...,k} such that ziC and we can 
let l denote the largest integer in {1,2,...,k} such that ziC.  Clearly s < l.  
There are three cases to consider:  

Case 1.14.1:  aC.  This means l = k.  Also, since (a,b) ∈ XPairs, bC.  
Thus s > 1.  Since (zs-1,zs) ∈ Affab, it follows by 1.12.2 and  1.13.1 that 
(zs-1,a) ∈ Affab.  But since {(zi,zi+1)P such that 1 ≤ i < s - 1} ∪ {(zs-1,a)
is a subset of Affab smaller than P and (a,b) is inconsistent with it, this is 
a contradiction, which means this case is impossible.   

Case 1.14.2:  bC.  This means s = 1.  Also, since (a,b) ∈ XPairs, aC.  
Thus l < k.  Since (zl,zl+1) ∈ Affab, it follows by 1.12.1 and 1.13.2 that 
(b,zl+1) ∈ Affab.  But since {(b,zl+1)} ∪ {(zi,zi+1)P such that l + 1 ≤ i < k
is a subset of Affab smaller than P and (a,b) is inconsistent with it, this is 
a contradiction, which means this case is impossible.   

Case 1.14.3:  aC and bC.  Thus 1 < s < l < k.  Since (zs-1,zs) ∈ Affab
it follows by 1.12.2 and  1.13.1 that (zs-1,zl) ∈ Affab.  But since {(zi,zi+1)P 
such that 1 ≤ i < s - 1} ∪ {(zs-1,zl)}  ∪ {(zi,zi+1)P such that l + 1 ≤ i < k
is a subset of Affab smaller than P and (a,b) is inconsistent with it, this is 
a contradiction, which means this case is impossible.   

Since all three cases are impossible, the contrary assumption cannot hold.  
Thus 1.14 is established.                                                                      QED

Proposition (1.15):  For all (a,b) ∈ XPairs' ∩ Maj, (a,b) ∉ Aff if and only if 
there exists P ⊆ Aff ∩ Precede(a,b) such that both of the following hold:

(1.15.1)  (a,b) is inconsistent with P
(1.15.2)  P ⊆ XPairs'.

Proof of 1.15:  The "if" clause follows immediately from condition 1.15.1 
and the definition of Affirmed().  We next prove the "only if" clause:  
Assume (a,b) ∈ XPairs' ∩ Maj and (a,b) ∉ Aff.  We must show there exists 
P ⊆ Aff ∩ Precede(a,b) ∩ XPairs' such that (a,b) is inconsistent with P.  
Since (a,b) ∈ Maj\Aff, (a,b) must be inconsistent with Aff ∩ Precede(a,b).  
By induction, there must exist P0 ⊆ Aff ∩ Precede(a,b) such that (a,b) is 
inconsistent with P0 and consistent with all subsets of Aff ∩ Precede(a,b
smaller than P0.  By the definition of Affirmed(), Aff ⊆ Maj.  Thus P0 ⊆ Maj.  
By 1.14, at most one alternative in C is involved in any pairs in P0.  
Since (z,z) ∉ Maj for all zA, this implies P0 ⊆ XPairs.  
There are two cases to consider: 

Case 1.15.3:  No alternative in C is involved in any pair in P0.  This  
means P0Pairs(A\C).  Since Pairs(A\C) ⊆ XPairs', P0 ⊆ XPairs'.  
Relabel P = P0.  Clearly P ⊆ Aff ∩ Precede(a,b) ∩ XPairs'  
and (a,b) is inconsistent with P, the desired conclusion.

Case 1.15.4:  Exactly one alternative in C is involved in any pairs in P0.  
Let c denote this alternative.  There are two subcases to consider:

Case 1.15.4.1:  cD.  This implies P0 ⊆ XPairs'.  Relabel P = P0.  
Clearly P ⊆ Aff ∩ Precede(a,b) ∩ XPairs' and (a,b) is inconsistent 
with P, the desired conclusion.

Case 1.15.4.2:  cD.  Represent P0 as {(a1,a2),(a2,a3),...,(ak-1,ak)
where a1 = b and ak = a and there exists at least one j ∈ {1,2,...,k} such 
that aj = c.  Since (a,b) ∈ XPairs', a1D and akD.  Thus we can 
let i denote the smallest integer in {2,3,...,k-1} such that ai = c and 
we can let j denote the largest integer in {2,3,...,k-1} such that aj = c.   
Clearly 1 < ij < k.  By construction, ai-1A\C and aj+1A\C.  
Pick any c'C\D.  Since (ai-1,ai) ∈ Aff, by 1.13.1 (ai-1,c') ∈ Aff.  Since 
(aj,aj+1) ∈ Aff, by 1.13.2 (c',aj+1) ∈ Aff.  Since (ai-1,ai) ∈ Precede(a,b), 
by 1.12.2 (ai-1,c') ∈ Precede(a,b).  Since (aj,aj+1) ∈ Precede(a,b), 
by 1.12.1 (c',aj+1) ∈ Precede(a,b).  Let P denote the following set: 
       {(a1,a2),(a2,a3),...,(ai-1,c'),(c',aj+1),(aj+1,aj+2),...,(ak-1,ak)
Clearly P ⊆ Aff ∩ Precede(a,b) ∩ XPairs' and (a,b) is inconsistent 
with P, the desired conclusion.

Thus in all cases there exists P ⊆ Aff ∩ Precede(a,b) ∩ XPairs' such that (a,b) is 
inconsistent with P, establishing the "only if" clause of 1.15.  Since both the "if" 
and "only if" clauses of 1.15 have been established, 1.15 is established.    QED

Proposition (1.16):  Aff ∩ XPairs' = Aff' ∩ XPairs'.

Proof of 1.16:  Let P denote {(a,b) ∈ XPairs' such that (a,b) ∈ Aff\Aff'  
or (a,b) ∈ Aff'\Aff}.  We must show P is empty.  Suppose the contrary.  
By theorem "Precedence is a Strict Ordering" we can pick (a,b)P  
such that the following condition holds:

(1.16.1)  P ∩ Precede'(a,b) is empty.  

There are two cases to consider:

Case 1.16.2:  (a,b) ∈ Aff.  This implies (a,b) ∉ Aff'.  By the definition 
of Affirmed(), Aff ⊆ Maj.  Thus (a,b) ∈ Maj.  By 1.8, (a,b) ∈ Maj'.  
Since (a,b) ∈ Maj'\Aff', (a,b) must be inconsistent with Aff' ∩ Precede'(a,b).  
By 1.16.1, Precede'(a,b) ∩ P is empty.  Thus Aff' ∩ Precede'(a,b) ⊆ Aff.  
By 1.10, Precede'(a,b) ⊆ Precede(a,b).  Combining the last two statements, 
Aff' ∩ Precede'(a,b) ⊆ Aff ∩ Precede(a,b).  This implies (a,b) is inconsistent 
with Aff ∩ Precede(a,b), which implies (a,b) ∉ Aff.  But (a,b) ∈ Aff in 
case 1.16.2, a contradiction.  Thus case 1.16.2 is impossible.

Case 1.16.3:  (a,b) ∉ Aff.  This implies (a,b) ∈ Aff'.  By the definition 
of Affirmed(), Aff' ⊆ Maj'.  Thus (a,b) ∈ Maj'.  By 1.8, (a,b) ∈ Maj.  
By 1.15, there must exist P2 ⊆ Aff ∩ Precede(a,b) ∩ XPairs' such that (a,b)  
is inconsistent with P2.  By 1.10, P2 ⊆ Precede'(a,b).  By 1.16.1, this implies 
no pair in P2 is in P.  This implies P2 ⊆ Aff'.  Thus P2 ⊆ Aff' ∩ Precede'(a,b), 
which implies (a,b) is inconsistent with Aff' ∩ Precede'(a,b).  This implies 
(a,b) ∉ Aff'.  But (a,b) ∈ Aff' in case 1.16.3,  a contradiction.  
Thus case 1.16.3 is impossible.

Since both cases are impossible, the contrary assumption that P is not empty 
cannot hold.  Thus P must be empty, and 1.16 follows immediately.        QED 

Proposition (1.17):  A\C ∩ Top = A\C ∩ Top'.

Proof of 1.17:  First we show A\C ∩ Top ⊆ A\C ∩ Top'.  
Pick any yA\C ∩ Top.  We must show y ∈ Top'.  Suppose the contrary.  
By the definition of Top(), y is not second in any pair in Aff, and y is second 
in at least one pair in Aff'.  This means there exists zA'\{y} such that 
(z,y) ∈ Aff'.  Clearly (z,y) ∈ XPairs'.  By 1.16, (z,y) ∈ Aff, which implies 
y ∉ Top.  But this is a contradiction, which implies the contrary assumption 
cannot hold, establishing A\C ∩ Top ⊆ A\C ∩ Top'.  
Next we show A\C ∩ Top'A\C ∩ Top.  Pick any yA\C ∩ Top'.  
We must show y ∈ Top.  Suppose the contrary.  By the definition of Top(), 
y is not second  in any pair in Aff', and y is second  in at least one pair 
in Aff.  This means there exists zA\{y} such that (z,y) ∈ Aff.  
There are two cases to consider:

Case 1.17.1:  zD.  Since D is a strict subset of C, by 1.13.2 there 
must exist cC\D such that (c,y) ∈ Aff.  Clearly (c,y) ∈ XPairs'.  
By 1.16, (c,y) ∈ Aff'.  This implies y ∉ Top', a contradiction.  
Thus case 1.17.1 is impossible.  

Case 1.17.2:  zD.  Clearly (z,y) ∈ XPairs'.  By 1.16, (z,y) ∈ Aff'.  
This implies y ∉ Top', a contradiction.  Thus case 1.17.2 is impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
which means y ∈ Top.  Thus A\C ∩ Top'A\C ∩ Top.  
Thus A\C ∩ Top = A\C ∩ Top', establishing 1.17.                     QED 

Proposition (1.18):  C ∩ Top is empty if and only if C ∩ Top' is empty.

Proof of 1.18:   First we prove the "only if" clause:  Assume C ∩ Top is empty.  
We must show C ∩ Top' is empty.  By theorem "Consistency Maintained (2)," 
Aff is internally consistent.  Since Pairs(C) ∩ Aff ⊆ Aff, Pairs(C) ∩ Aff must 
also be internally consistent.  By theorem "At Least One Top (1)" there must 
exist cC that is not second in any pair in Pairs(C) ∩ Aff.  Since c ∉ Top, 
c must be second in at least one pair in Aff\Pairs(C).  This means there exists 
yA\C such that (y,c) ∈ Aff.  By 1.13.1, (y,c') ∈ Aff for all c'C.  By 1.16, 
(y,c') ∈ Aff' for all c'C\D.  Thus C ∩ Top' must be empty, establishing the 
"only if" clause.  Next we prove the "if" clause:  Assume C ∩ Top is not empty.  
We must show C ∩ Top' is not empty.  Since C ∩ Top is not empty, there must 
exist cC that is not second in any pair in Aff.  This means (y,c) ∉ Aff for all 
yA\{c}.  Thus (y,c) ∉ Aff for all yA\C.  By 1.13.1, (y,c') ∉ Aff for all  
yA\C and all c'C.  By 1.16, (y,c') ∉ Aff' for all yA\C and all c'C\D.  
By theorem "Consistency Maintained (2)" (temporarily relabeling A = A', R = R'
etc.), Aff' must be internally consistent.  Thus Pairs(C\D) ∩ Aff' must also 
be internally consistent.  By theorem "At Least One Top (1)" there must exist 
c'C\D that is not second in any pair in Pairs(C\D) ∩ Aff'.  Since (y,c') ∉ Aff'  
for all yA\C and c' is not second in any pair in Pairs(C\D) ∩ Aff', it follows 
that c' is not second in any pair in Aff'.  This means c' ∈ Top', which means 
C ∩ Top' is not empty.  Thus the "if" clause has been established.  Since both 
the "if" and "only if" clauses have been established, 1.18 is established.          QED 

Resuming the proof of proposition 1.5...  First we establish the "only if" clause of 1.5.  
Assume σ ∈ Wx. (This means MAM = x.)  We aim to show MAM' = x.  
Since MAM = x, this implies x ∈ Top.  By 1.17, x ∈ Top'.  Since MAM = x
by the definition of MAM() the following condition must hold: 

(1.5.1)  RVH ranks x over all a ∈ Top\{x}. 

By 1.9, 1.17 and 1.5.1, the following condition must hold: 

(1.5.2)  RVH' ranks x over all x' ∈ (A\C)\{x} ∩ Top'.

There are two cases to consider: 

Case 1.5.3:  C ∩ Top is empty.  By 1.18, C ∩ Top' must also be empty.  
Thus, by 1.5.2 RVH' ranks x over all a ∈ Top'\{x}.  Thus MAM' = x.

Case 1.5.4:  C ∩ Top is not empty.  By 1.5.1, RVH ranks x over 
all cC ∩ Top.  By 1.6, RVH ranks x over all cC.  By 1.9, 
RVH' ranks x over all cC\D.  Thus, by 1.5.2 RVH' ranks x  
over all a ∈ Top'\{x}.  Thus MAM' = x.

Since MAM' = x in both cases, σ'W'x, establishing the "only if" clause of 1.5.  
Next we establish the "if" clause.  Assume σ'W'x.  This means MAM' = x.  
We must show MAM = x.  Since MAM' = x, this implies x ∈ Top'.  By 1.17, 
x ∈ Top.  Since MAM' = x, by the definition of MAM() the following must hold: 

(1.5.5)  RVH' ranks x over all a ∈ Top'\{x}. 

By 1.9, 1.17 and 1.5.5, the following condition must hold: 

(1.5.6)  RVH ranks x over all x' ∈ (A\C)\{x} ∩ Top.

There are two cases to consider: 

Case 1.5.7:  C ∩ Top' is empty.  By 1.18, C ∩ Top must also be empty.  
Thus, by 1.5.6 RVH must rank x over all a ∈ Top\{x}.  Thus MAM = x.

Case 1.5.8:  C ∩ Top' is not empty.  By 1.5.5, RVH' ranks x over 
all cC ∩ Top'.  By 1.9, RVH ranks x over all cC ∩ Top'.  
By 1.6, RVH ranks x over all cC.  Thus, by 1.5.6 RVH ranks x  
over all a ∈ Top\{x}.  It follows that MAM = x.

Since MAM = x in both cases, σ ∈ Wx, establishing the "if" clause of 1.5.  
Since both the "if" and "only if" of 1.5 clauses have been established, 1.5 is 
established.  It follows that proposition 1.3 holds, and thus that proposition 1 holds.  
Thus MAM is completely independent of clone alternatives.        QED


 

It is instructive to provide a second proof that MAM satisfies ICA.  
Relying on theorem "MAM2 = MAM", we prove the following proposition:

Proposition (2):  MAM2 satisfies ICA.  

Assume CA is a finite non-empty set of clones within A given R.  Assume D is 
a strict subset of C.  Abbreviate A' = A\D.  Let R' denote the restriction of R to A'.  
For all σ ∈ L(R,A), let σ' denote the restriction of σ to A'. (Thus σ'L(R',A')).  
By 1.2 and 1.4, proposition 2 will follow immediately if we establish the following: 

Proposition (2.1):  For all xA\C and all σ ∈ L(R,A), 
                             MAM2(A,R,σ) = x if and only if MAM2(A',R',σ') = x

Pick any σ ∈ L(R,A).  Refer to the definitions comprising MAM2.  
Make the following abbreviations: 

Maj = Majorities(A,R).
For all rL(A), Agr(r) = Agreed(r,A,R). 
For all r,r'L(A), Dist(r,r') = DistinctAgreed(r,r',A,R).  
For all x,yA, Precede(x,y) = Precede(x,y,A,R,σ).
For all r,r'L(A) such that Dist(r,r') is not empty, 
        LDA(r,r') = LargestDistinctAgreed(r,r',A,R,σ). 
Undom = UndominatedRankings(A,R,σ). 
Top2 = Top2(A,R,σ). 
Maj' = Majorities(A',R').
For all rL(A'), Agr'(r) = Agreed(r,A',R'). 
For all r,r'L(A'), Dist'(r,r') = DistinctAgreed(r,r',A',R').  
For all x,yA', Precede'(x,y) = Precede(x,y,A',R',σ').
For all r,r'L(A') such that Dist'(r,r') is not empty, 
        LDA'(r,r') = LargestDistinctAgreed(r,r',A',R',σ'). 
Undom' = UndominatedRankings(A',R',σ'). 
Top2' = Top2(A',R',σ').  

The following four propositions will facilitate the proof of proposition 2.1: 

Proposition (2.2):  For all r ∈ Undom, #R(x,c) = #R(c,x) for all cC  
and all xA\C such that r ranks x over at least one alternative in C and 
below at least one alternative in C. (In other words, the number of votes 
that rank x over c equals the number of votes that rank c over x.)

Proposition (2.3):  For all r ∈ Undom, there exists r' ∈ Undom such that 
both of the following conditions hold: 
        (2.3.1)  The alternative that tops r also tops r'
        (2.3.2)  For all xA\C, either r' ranks x over every alternative in C 
                    or r' ranks every alternative in C over x. (That is, r' ranks 
                    the clones together, no non-clones between clones.) 

Proposition (2.4):  A\C ∩ Top2 = A\C ∩ Top2'

Proposition (2.5):  C ∩ Top2 is empty if and only if C ∩ Top2' is empty.

Proof of 2.2:  Pick any r ∈ Undom.  By inspection of the definition of 
UndominatedRankings()
, r must be a strict ordering of A, so we can 
let c0 denote the alternative in C that r ranks over all other alternatives in C
and we can let c1 denote the alternative in C that r ranks below all other 
alternatives in C.  Let B denote {xA\C such that r ranks c0 over x 
and x over c1}. (That is, the "non-clones" ranked between clones by r.)  
Let B' denote {xB such that #R(x,c) ≠ #R(c,x) for some cC}.  
We aim to show B' is empty.  Suppose the contrary.  By condition 1 
of the definition of clones, R(b,c) = R(b,c') and R(c,b) = R(c',b) for 
all bB and all c,c'C.  Thus, by the definition of Majorities()
the following two statements hold: 

(2.2.1)  For all bB and all c,c'C, (b,c) ∈ Maj if and only if (b,c') ∈ Maj. 
(2.2.2)  For all bB and all c,c'C, (c,b) ∈ Maj if and only if (c',b) ∈ Maj. 

Furthermore, by the definition of B', the following two statements hold: 

(2.2.3)  For all bB' and all cC, (b,c) ∈ Maj if and only if (c,b) ∉ Maj. 
(2.2.4)  For all bB\B' and all cC, (b,c) ∉ Maj and (c,b) ∉ Maj. 

Let r' denote the strict ordering of A that is the same as r except the alternatives 
in B are raised just over c0, and let r" denote the strict ordering of A that is the 
same as r except the alternatives in B are lowered just below c1.  By construction 
and by 2.2.3 and 2.2.4, all six of the following statements must hold:

(2.2.5)  For all (x,y) ∈ Dist(r,r') ∩ Agr(r), xC and yB'
(2.2.6)  For all (x,y) ∈ Dist(r,r') ∩ Agr(r'), xB' and yC
(2.2.7)  For all (x,y) ∈ Dist(r,r") ∩ Agr(r), xB' and yC
(2.2.8)  For all (x,y) ∈ Dist(r,r") ∩ Agr(r"), xC and yB'.  
(2.2.9)  For all bB', (c0,b) ∈ Dist(r,r') ∩ Agr(r
             if and only if (c1,b) ∈ Dist(r,r") ∩ Agr(r").  
(2.2.10)  For all bB', (b,c0) ∈ Dist(r,r') ∩ Agr(r'
              if and only if (b,c1) ∈ Dist(r,r") ∩ Agr(r).  

Since r ∈ Undom, r' does not dominate r given (R,σ).  Since B' is not empty, 
Dist(r,r') is not empty.  By theorem "Precedence is a Strict Ordering" and 
the definition of LargestDistinctAgreed(), we can let (z,z') denote the 
unique ordered pair LDA(r,r').  Since r' does not dominate r, this implies 
(z,z') ∉ Agr(r'), which implies (z,z') ∈ Agr(r).  Thus r dominates r' given (R,σ).  
By 2.2.5, zC and z'B'.  For greater clarity, let cL denote z and let bL 
denote z'. (Thus (cL,bL) = LDA(r,r').)  By theorem "Precedence is a Strict 
Ordering"
and the definition of LargestDistinctAgreed(), the following 
statement must hold: 

(2.2.11)  (cL,bL) ∈ Precede(x,y) for all (x,y) ∈ Dist(r,r') ∩ Agr(r').  

By 1.12.1, 2.2.6 and 2.2.11, the following statement must hold: 

(2.2.12)  (c,bL) ∈ Precede(x,y) for all cC and all (x,y) ∈ Dist(r,r') ∩ Agr(r').  

By 2.2.9, (c1,bL) ∈ Dist(r,r") ∩ Agr(r").  Therefore, by 1.12.1, 2.2.12, 
2.2.6 and 2.2.10 (c1,bL) ∈ Precede(x,y) for all (x,y) ∈ Dist(r,r") ∩ Agr(r).  
This implies LDA(r,r") ∉ Agr(r), which implies LDA(r,r") ∈ Agr(r").  
Thus r" dominates r given (R,σ).  But this contradicts r ∈ Undom.  
Thus the contrary assumption that B' is not empty cannot hold.  
Since B' is empty, proposition 2.2 follows immediately.         QED

Proof of 2.3:  Pick any r ∈ Undom.  There are two cases to consider:

Case 2.3.3:  For all xA\C, either r ranks x over every alternative in C 
or r ranks every alternative in C over x.  In this case we can simply 
let r' = r and clearly both conditions 2.3.1 and 2.3.2 hold.

Case 2.3.4:  There exists xA\C such that r ranks x over at least one 
alternative in C and below at least one alternative in C.  Define c1, B and B' 
the same as in the proof of proposition 2.2.  Clearly B is not empty in this 
case.  By 2.3, B' must be empty.  Let r' denote the strict ordering of A 
that is the same as r except all alternatives in B are lowered below c1.  
Since B' is empty, Dist(r,r') must be empty.  This implies r does not 
dominate r' given (R,σ).  By theorem "Dominance is an Ordering"
r' must also be undominated given (R,σ), so r' ∈ Undom.  
Clearly both conditions 2.3.1 and 2.3.2 hold. 

Since in both cases there exists r' ∈ Undom such that conditions 2.3.1 and 2.3.2 
hold, and since r was picked arbitrarily, proposition 2.3 is established.   QED 

Proof of 2.4:  Make the following additional abbreviations:

UndomC = UndominatedRankings(C,R|C,σ|C). 
Undom'C = UndominatedRankings(C\D,R|C\D,σ|C\D).  

By theorem "Dominance is an Ordering", Undom cannot be empty, Undom' cannot 
be empty, UndomC cannot be empty, and Undom'C cannot be empty.  Thus we can 
pick rC ∈ UndomC and r'C ∈ Undom'C. (In words, rC is some "best" ranking of the 
clones, and r'C is some "best" ranking of the clones that remain when D is deleted.)  

First we show (A\C ∩ Top2) ⊆ (A\C ∩ Top2'):  Pick any xA\C.  Assume x ∈ Top2.  
We must show x ∈ Top2'.  Since x ∈ Top2, by the definition of Top2() there must 
exist r0 ∈ Undom topped by x.  By 2.3, there must exist r1 ∈ Undom topped 
by x such that, for all yA\C, either r1 ranks y over every alternative in C 
or r1 ranks every alternative in C over y.  Let r2 denote the strict ordering of A 
that is the same as r1 except the alternatives in C are deleted and replaced with rC.  
Since r1 ∈ Undom and rC ∈ UndomC, it follows that r2 ∈ Undom.  Let r3 denote 
the strict ordering of A' that is the same as r2 except the alternatives in C are deleted 
and replaced with r'C.  We aim to show r3 ∈ Undom' (after which x ∈ Top2' will follow).  
Suppose to the contrary r3 ∉ Undom'.  This implies there exists r4 ∈ Undom' such 
that r4 dominates r3 given (R',σ').  Since C\D is a set of clones within A' given R'
by 2.3 there must exist r5 ∈ Undom' such that, for all yA\C, either r5 ranks y over 
every alternative in C\D or r5 ranks every alternative in C\D over y.  Let r6 denote 
the strict ordering of A' that is the same as r5 except the alternatives in C\D are 
deleted and replaced with r'C.  Since r5 ∈ Undom' and r'C ∈ Undom'C, it follows 
that r6 ∈ Undom'.  By theorem "Dominance is an Ordering"r6 must also dominate r3  
given (R',σ').  Let r7 denote the strict ordering of A that is the same as r6 except 
the alternatives in C\D are deleted and replaced with rC.  By construction, 
Dist(r7,r2) = Dist'(r6,r3).  Therefore, since r6 dominates r3 given (R',σ'), it follows by 
1.10 (that is, precedence is independent of irrelevant alternatives) that r7 dominates r2  
given (R,σ).  But this contradicts r2 ∈ Undom established above.  Thus the contrary 
assumption r3 ∉ Undom' cannot hold, implying r3 ∈ Undom'.  Since x tops r3 and 
r3 ∈ Undom', x ∈ Top2'.  Thus (A\C ∩ Top2) ⊆ (A\C ∩ Top2'). 

Next we show (A\C ∩ Top2') ⊆ (A\C ∩ Top2):  Pick any xA\C.  Assume x ∈ Top2'.  
We must show x ∈ Top2.  Since x ∈ Top2', by the definition of Top2() there must 
exist r0 ∈ Undom' topped by x.  Since C\D is a set of clones within A' given R'
by 2.3 there must exist r1 ∈ Undom' topped by x such that, for all yA\C
either r1 ranks y over every alternative in C\D or r1 ranks every alternative in C\D 
over y.  Let r2 denote the strict ordering of A' that is the same as r1 except the 
alternatives in C\D are deleted and replaced with r'C.  Since r1 ∈ Undom' and 
r'C ∈ Undom'C, it follows that r2 ∈ Undom'.  Let r3 denote the strict ordering 
of A that is the same as r2 except the alternatives in C\D are deleted and replaced 
with rC.  We aim to show r3 ∈ Undom (after which x ∈ Top2 will follow).  
Suppose to the contrary r3 ∉ Undom.  This implies there exists r4 ∈ Undom such 
that r4 dominates r3 given (R,σ).  By 2.3, there must exist r5 ∈ Undom such that, 
for all yA\C, either r5 ranks y over every alternative in C or r5 ranks every 
alternative in C over y.  Let r6 denote the strict ordering of A that is the same as r5  
except the alternatives in C are deleted and replaced with rC.  Since r5 ∈ Undom 
and rC ∈ UndomC, it follows that r6 ∈ Undom.  By theorem "Dominance is an 
Ordering"
, r6 must also dominate r3 given (R,σ).  Let r7 denote the strict ordering 
of A' that is the same as r6 except the alternatives in C are deleted and replaced 
with r'C.  By construction, Dist(r7,r2) = Dist'(r6,r3).  Therefore, since r6 dominates r3  
given (R,σ), it follows by 1.10 that r7 dominates r2 given (R',σ').  But this contradicts 
r2 ∈ Undom' established above.  Thus the contrary assumption r3 ∉ Undom cannot 
hold, implying r3 ∈ Undom.  Since x tops r3 and r3 ∈ Undom, x ∈ Top2.  
Thus (A\C ∩ Top2') ⊆ (A\C ∩ Top2).  Since (A\C ∩ Top2) ⊆ (A\C ∩ Top2'
and (A\C ∩ Top2') ⊆ (A\C ∩ Top2), proposition 2.2 is established.        QED 

Proof of 2.5:  Make the same abbreviations as in the proof of 2.4.  First we establish 
the "if" clause of 2.5:  Assume there exists cC such that c ∈ Top2.  We must show 
there exists c'C\D such that c' ∈ Top2'.  Since c ∈ Top2, by the definition of Top2() 
there must exist r0 ∈ Undom topped by c.  By 2.3, there must exist r1 ∈ Undom 
topped by c such that r1 ranks every alternative in C over every alternative in A\C.  
Let r2 denote the strict ordering of A that is the same as r1 except the alternatives 
in C are deleted and replaced with rC.  Since r1 ∈ Undom and rC ∈ UndomC
it follows that r2 ∈ Undom.  Let r3 denote the strict ordering of A' that is the same 
as r2 except the alternatives in C are deleted and replaced with r'C.  We aim to 
show r3 ∈ Undom' (after which it will follow that the alternative atop r'C is in Top2').  
Suppose to the contrary r3 ∉ Undom'.  This implies there exists r4 ∈ Undom' such 
that r4 dominates r3 given (R',σ').  Since C\D is a set of clones within A' given R'
by 2.3 there exists r5 ∈ Undom' such that, for all xA\C, either r5 ranks x over 
every alternative in C\D or r5 ranks every alternative in C\D over x.  Let r6 denote 
the strict ordering of A' that is the same as r5 except the alternatives in C\D are 
deleted and replaced with r'C.  Since r5 ∈ Undom' and r'C ∈ Undom'C, it follows 
that r6 ∈ Undom'.  By theorem "Dominance is an Ordering", r6 must also dominate r3  
given (R',σ').  Let r7 denote the strict ordering of A that is the same as r6 except 
the alternatives in C\D are deleted and replaced with rC.  By construction, 
Dist(r7,r2) = Dist'(r6,r3).  Therefore, since r6 dominates r3 given (R',σ'), it follows 
by 1.10 that r7 dominates r2 given (R,σ).  But this contradicts r2 ∈ Undom.  
Thus the contrary assumption r3 ∉ Undom' cannot hold, implying r3 ∈ Undom'.  
Since r'C is a strict ordering of C\D, we can let c' denote the alternative in C\D that 
tops r'C.  Since r3 ∈ Undom' and r3 is topped by c', this implies c' ∈ Top2'.  
Thus the "if" clause of 2.5 has been established.  

Next we establish the "only if" clause of 2.5:  Assume C ∩ Top2' is not empty.  
We must show C ∩ Top2 is not empty.  Since C ∩ Top2' is not empty, there must 
exist c'C\D such that c' ∈ Top2'.  By the definition of Top2(), there must exist 
r0 ∈ Undom' topped by c'.  Since C\D is a set of clones within A' given R'
by 2.3 there exists r1 ∈ Undom' topped by c' such that r1 ranks every alternative 
in C\D over every alternative in A\C.  Let r2 denote the strict ordering of A' that 
is the same as r1 except the alternatives in C\D are deleted and replaced with r'C.  
Since r1 ∈ Undom' and r'C ∈ Undom'C, it follows that r2 ∈ Undom'.  Let r3 denote 
the strict ordering of A that is the same as r2 except the alternatives in C\D are deleted 
and replaced with rC.  We aim to show r3 ∈ Undom (after which it will follow that 
the alternative atop rC is in Top2).  Suppose to the contrary r3 ∉ Undom.  This implies 
there exists r4 ∈ Undom such that r4 dominates r3 given (R,σ).  By 2.3, there must 
exist r5 ∈ Undom such that, for all xA\C, either r5 ranks x over every alternative 
in C or r5 ranks every alternative in C over x.  Let r6 denote the strict ordering of A  
that is the same as r5 except the alternatives in C are deleted and replaced with rC.  
Since r5 ∈ Undom and rC ∈ UndomC, it follows that r6 ∈ Undom.  By theorem 
"Dominance is an Ordering"
, r6 must also dominate r3 given (R,σ).  Let r7 denote 
the strict ordering of A' that is the same as r6 except the alternatives in C are deleted 
and replaced with r'C.  By construction, Dist(r7,r2) = Dist'(r6,r3).  Therefore, since 
r6 dominates r3 given (R,σ), it follows by 1.10 that r7 dominates r2 given (R',σ').  
But this contradicts r2 ∈ Undom'.  Thus the contrary assumption r3 ∉ Undom cannot 
hold, implying r3 ∈ Undom.  Since rC is a strict ordering of C, we can let c denote 
the alternative in C atop rC.  Since r3 ∈ Undom and r3 is topped by c, c ∈ Top2.  
Thus C ∩ Top2 is not empty, establishing the "only if" clause of 2.5.  Since both 
the "if" and "only if" clauses have been established, 2.5 is established.          QED 

Resuming the proof of 2.1...  There are three cases to consider:  

Case 2.1.1:  MAM2(A,R,σ) ∈ C.  This implies there exists c ∈ Top2 that is 
ranked by RVH over all other alternatives in Top2.  By 1.6 ("Random Voter 
Hierarchy ranks clones together"), RVH ranks all of C over all alternatives 
in A\C ∩ Top2.  By 2.4, A\C ∩ Top2 = A\C ∩ Top2'.  Thus, by 1.9 
("Random Voter Hierarchy is independent of irrelevant alternatives") 
RVH' ranks all of C\D over all alternatives in A\C ∩ Top2'.  By 2.5, 
C ∩ Top2' is not empty.  Thus RVH' ranks some c' ∈ Top2' over 
all other alternatives in Top2'.  Thus MAM2(A',R',σ') = c'
which means MAM2(A',R',σ') ∈ C.  

Case 2.1.2:  MAM2(A,R,σ) ∉ C and C ∩ Top2 is not empty.  This implies 
the alternative in Top2 ranked highest by RVH is not in C.  Let x denote 
this alternative.  It follows that MAM2(A,R,σ) = x.  By 1.6 ("Random 
Voter Hierarchy ranks clones together"), RVH ranks x over all of C.  
By 2.4, A\C ∩ Top2 = A\C ∩ Top2'.  Thus x ∈ Top2', and by 1.9 
("Random Voter Hierarchy is independent of irrelevant alternatives") 
RVH' ranks x over all of Top2'\{x}.  Thus MAM2(A',R',σ') = x
which means MAM2(A,R,σ) = MAM2(A',R',σ').  

Case 2.1.3:  MAM2(A,R,σ) ∉ C and C ∩ Top2 is empty.  By 2.5, 
C ∩ Top2' is empty.  By 2.4, Top2 = Top2'.  Thus, by 1.9 ("Random 
Voter Hierarchy is independent of irrelevant alternatives") the alternative 
in Top2 ranked highest by RVH is the same as the alternative in Top2' 
ranked highest by RVH'.  Thus MAM2(A,R,σ) = MAM2(A',R',σ'). 

By inspection of the three cases, proposition 2.1 follows immediately.  
Thus proposition 2 is also established, which means MAM2 satisfies ICA.  
By theorem "MAM2 = MAM", this implies MAM satisfies ICA.         QED