The "Maximize Affirmed Majorities" (MAM) voting method is monotonic.

Revised:  December 31, 2002

Monotonicity:  If some voters uprank an alternative, the probability that
that alternative is elected must not decrease.

Refer to the definitions in the document defining MAM.  An additional definition:

For all sets of alternatives A, all collections of voters' rankings R and 
all a Î A, let Wa(R,A) denote {s Î L(R,A) such that MAM(A,R,s) = a}. 
(Note: When Wa(R,A) is empty, MAM defeats a with certainty, 
and when Wa(R,A) = L(R,A), MAM chooses a with certainty.)

We provide two proofs that MAM is monotonic.  The second proof shows MAM2 is 
monotonic and relies on the equivalence of MAM2 and MAM.

Theorem 1:  "MAM is monotonic."

Proof #1:  Suppose R and R' are two collections of votes such that #R = #R'.  
For all i Î {1,2,...,#R}, let Ri denote the ith ballot in R and let R'i denote the ith  
ballot in R'.  Suppose that for some x Î A and all i Î {1,2,...,#R}, both of 
the following conditions hold: 

(1.1)  For all y Î A, if Ri ranks x over y then R'i ranks x over y
          and if R'i ranks y over x then Ri ranks y over x.

(1.2)  For all y,z Î A distinct from x, R'i ranks y over z  
          if and only if Ri ranks y over z

Abbreviate Wx = Wx(R,A) and W'x = Wx(R',A).  By the definition of MAM, the 
probability that MAM elects given R is #Wx/#L(R,A), and the probability that 
MAM elects x given R' is #W'x/#L(R',A).  Since #R = #R', #L(R,A) = #L(R',A).  
Thus monotonicity will be established by showing #W'x ³ #Wx.  Pick any s Î Wx.  
Let s' denote the ordered pair (s'R,sA) Î L(R',A) such that s'R is the strict 
ordering of the votes in R' such that, for all i,j Î (1,2,...,#R}, s'R orders R'i  
over R'j if and only if sR orders Ri over Rj.  Make the following abbreviations: 

Maj = Majorities(A,R). 
Maj' = Majorities(A,R').  
RVH = RVH(A,R,s
RVH' = RVH(A,R',s').  
Precede(a,b) = Precede(a,b,A,R,s) for all (a,b) Î Pairs.
Precede'(a,b) = Precede(a,b,A,R',s') for all (a,b) Î Pairs.
Aff = Affirmed(A,R,s). 
Aff' = Affirmed(A,R',s'). 
For all a Î A, let La denote the pairs in Aff in which a is second 
and let L'a denote the pairs in Aff' in which a is second.  That is, 
        La = {(b,a) Î Aff}. 
        L'a = {(b,a) Î Aff'}.
Top = Top(A,R,s).  
Top' = Top(A,R',s').  
MAM = MAM(A,R,s).  
MAM' = MAM(A,R',s'). 

The following propositions will facilitate the proof that MAM is monotonic:

Proposition 2: "Majorities are monotonic":  That is, 
the following five statements hold:  
        (2.1)  For all y Î A, #R'(x,y) ³ #R(x,y) and #R'(y,x) £ #R(y,x).
        (2.2)  For all y,z Î A\{x}, #R'(y,z) = #R(y,z).  
        (2.3)  For all y Î A, if (x,y) Î Maj then (x,y) Î Maj'.  
        (2.4)  For all y Î A, if (y,x) Î Maj' then (y,x) Î Maj.  
        (2.5)  For all y,z Î A\{x}, (y,z) Î Maj if and only if (y,z) Î Maj'.

Proposition 3: "Random Voter Hierarchy is monotonic":  That is, 
the following three statements hold: 
        (3.1)  For all y Î A, if RVH ranks x over y then RVH' ranks x over y
        (3.2)  For all y Î A, if RVH' ranks y over x then RVH ranks y over x
        (3.3)  For all s Î L(R,A) and all y,z Î A distinct from x
                  RVH' ranks y over z if and only if RVH ranks y over z

Proposition 4: "Precedence is monotonic":  That is, both of the following hold: 
        (4.1)  For all p,p' Î Pairs, if p precedes p' given (R,s) and x is neither 
                  second in p nor first in p' then p precedes p' given (R',s')
        (4.2)  For all p,p' Î Pairs, if p precedes p' given (R',s') and x is neither 
                  first in p nor second in p', then p precedes p' given (R,s).

Proposition 5: "Top is monotonic":  That is, x Î Top'.

Proposition 6: "Top' Í Top".

Proof of 2:  Statements 2.1 and 2.2 follow by inspection of the 
definitions above.  Statements 2.3-5 follow from 2.1, 2.2 and 
the definition of Majorities().     QED 

Proof of 3:  By inspection of the definitions above 
and the definition of RVH().       QED 

Proof of 4:  This follows immediately from 2, 3 and 
the definition  of precedence.       QED 

Proof of 5:  Since s Î Wx, MAM = x, which implies x Î Top.  Suppose to the 
contrary x Ï Top'.  This implies L'x ¹ f.  By theorem  "Precedence is a Strict 
Ordering"
we can let mx denote a majority in L'x that is not preceded by any 
other majority in L'x given (R',s').  Let Aff'mx+ denote Aff' Ç Precede'(mx). 
(Perhaps Aff'+ is empty.)  It follows from the definitions of mx and Aff'
that x is not second in any majority in Aff'mx+.  Since x Î Top, Lx is empty, 
implying mx Ï Aff.  By 1.1, mx Î Maj.  Thus mx must be inconsistent with 
Aff Ç Precede(mx).  Let Affmx+ denote Aff Ç Precede(mx).  By theorem 
"Minimal Inconsistent Set (1)"
, there must exist Aff0mx+ Í Affmx+ such that 
Aff0mx+ is a minimal set with which mx is inconsistent.  By theorem "Minimal 
Inconsistent Set (2)"
, x is not second in any majority in Aff0mx+.  By 2, 
Aff0mx+ Í Maj'.  Since Aff0mx+ Í Precede(mx), by 4 Aff0mx+ Í Precede'(mx).  
Since mx Î Aff' and Aff0mx+ Í Precede'(mx), by theorem "Consistency 
Maintained (2)"
at least one majority in Aff0mx+ is not in Aff'.  Thus we can 
let m1 denote a majority in Aff0mx+\Aff'.  It has been established that m1 Î Maj 
and m1 Î Maj' and m1 Î Aff0mx+ and m1 Ï Aff' and m1 Î Precede(mx
and m1 Î Precede'(mx) and x is not second in m1

Let M- denote the majorities (like m1) in which x is not second and which are in 
Maj and in Maj' and in Aff and in Precede(mx) and in Precede'(mx) but not in Aff'.  
Clearly m1 Î M-, so M- is not empty.  Thus, by theorem "Precedence is a 
Strict Ordering"
there exists m2 Î M- that precedes all other majorities in M-  
given (R,s). (Perhaps m2 = m1.)  Since m2 Î Maj'\Aff'm2 must be inconsistent 
with Aff' Ç Precede'(m2).  Let Aff'm2+ denote Aff' Ç Precede'(m2).  By theorem 
"Minimal Inconsistent Set (1)"
, there must exist Aff'0m2+ Í Aff'm2+ that is a minimal 
set with which m2 is inconsistent.  By theorem  "Precedence is a Strict Ordering"
Aff'0m2+ Í Aff'mx+.  Since x is not second in any majority in Aff'mx+ nor second 
in m2, by theorem "Minimal Inconsistent Set (3)" no majority in Aff'0m2+ involves x.  
By 2, Aff'0m2+ Í Maj.  Since Aff'0m2+ Í Precede'(m2), by 4 Aff'0m2+ Í Precede(m2).  Since m2 Î Aff and Aff'0m2+ Í Precede(m2), by theorem "Consistency Maintained 
(2)"
at least one majority in Aff'0m2+ is not in Aff.  Thus we can let m3 denote a 
majority in Aff'0m2+\Aff.  It has been established that m3 does not involve x and 
m3 Î Maj and m3 Î Maj' and m3 Î Aff'0m2+ and m3 Ï Aff and m3 Î Precede(m2
and m3 Î Precede'(m2).

Since m3 Î Maj and m3 Ï Aff, m3 must be inconsistent with Aff Ç Precede(m3).  
Let Affm3+ denote Aff Ç Precede(m3).  By theorem "Minimal Inconsistent Set (1)"
there exists Aff0m3+ Í Affm3+ that is a minimal set with which m3 is inconsistent.  
Since x Î Top, x is not second in any majority in Aff, and since m3 does not 
involve x it follows by theorem "Minimal Inconsistent Set (3)" that  no majority 
in Aff0m3+ involves x.  By 2, Aff0m3+ Í Maj', and by 4 Aff0m3+ Í Precede'(m3).  
Since m3 Î Aff', by theorem "Consistency Maintained (2)" at least one majority 
in Aff0m3+ is not in Aff'.  Thus we can let m4 denote a majority in Aff0m3+\Aff'.

By the definition of M-, m4 Î M-.  Since m4 Î Precede(m3) and m3 Î Precede(m2), 
by theorem  "Precedence is a Strict Ordering" m4 Î Precede(m2).  But this 
contradicts the definition of m2.  The contradiction implies the contrary 
assumption cannot hold, so x Î Top', establishing 5.     QED 

Proof of 6:  Assume MAM(A,R,s) = x.  Suppose to the contrary Top' is not a 
subset of Top.  This means there exists y Î Top'\Top.  Clearly x Î Top, so y ¹ x.  
Let M- denote the majorities in Aff\Aff' in which x is not second.  Since Ly is not 
empty and L'y is empty, M- is not empty.  Thus, by theorem  "Precedence is a 
Strict Ordering"
there must exist m1 Î M- that precedes all other majorities in M- 
given (R,s).  Since m1 Î Aff, m1 Î Maj.  By 2, m1 Î Maj'.  Since m1 Î Maj'  
and m1 Ï Aff', m1 must be inconsistent with Aff' Ç Precede'(m1).  By theorem 
"Minimal Inconsistent Set (1)"
, there exists Aff'0m1+ Í Aff' Ç Precede'(m1
that is a minimal set with which m1 is inconsistent.  By 5, x Î Top', which 
implies x is not second in any majority in Aff'.  Thus x is not second in any 
majority in Aff'0m1+.  Since x is also not second in m1, by theorem "Minimal 
Inconsistent Set (3)"
 no majority in Aff'0m1+ involves x.  By 2, Aff'0m1+ Í Maj, 
and by 4 Aff'0m1+ Í Precede(m1).  Since m1 Î Aff, by theorem "Consistency 
Maintained (2)"
at least one majority in Aff'0m1+ is not in Aff.  Thus we can 
let m2 denote a majority in Aff'0m1+\Aff.  Since m2 Î Maj\Aff, m2 must be 
inconsistent with Aff Ç Precede(m2).  By theorem "Minimal Inconsistent Set (1)"
there exists Aff0m2+ Í Aff Ç Precede(m2) that is a minimal set with which m2 is 
inconsistent.  Since x is not second in any majority in Aff, x is not second in 
any majority in Aff0m2+.  Since x is also not second in m2, by theorem "Minimal 
Inconsistent Set (3)"
no majority in Aff0m2+ involves x.  By 2, Aff0m2+ Í Maj'
and by 4 Aff0m2+ Í Precede'(m2).  Since m2 Î Aff', by theorem "Consistency 
Maintained (2)"
at least one majority in Aff0m2+ is not in Aff'.  Thus we can 
let m3 denote a majority in Aff0m2+\Aff'.  Thus m3 Î Aff\Aff' and x is not 
second in m3.  Thus m3 Î M-.  Since m3 Î Precede(m2) and m2 Î Precede(m1), 
by theorem "Precedence is a Strict Ordering" m3 Î Precede(m1).  But this 
contradicts the definition of m1, implying the contrary assumption cannot hold.  
Thus Top' Í Top, establishing 6.     QED 

We show that MAM' = x.  Since MAM = x, by the definition of MAM() x Î Top 
and RVH ranks x over all y Î Top\{x}.  By 6, Top' Í Top.  Thus RVH ranks x over 
all y Î Top'\{x}.  By 3, RVH' ranks x over all y Î Top'\{x}.  By 5, x Î Top'.  
Since x Î Top' and RVH' ranks x over all y Î Top'\{x}, MAM' = x.  Since s  
was picked arbitrarily from Wx, it follows that MAM(A,R',s') = x for all s Î Wx.  
Thus Wx Í W'x, so #W'x ³ #Wx.  This means the probability that x is elected by 
MAM does not decrease when x is upranked.  Thus MAM is monotonic.    QED


Proof #2 that MAM is monotonic:  (This relies on theorem "MAM2 = MAM".)  
Refer to the definitions and propositions above.  Pick any s Î Wx(R,A).  Let s'  
denote the ordered pair (s'R,sA) Î L(R',A) where s'R is the strict ordering of 
the votes in R' such that, for all i,j Î (1,2,...,#R}, s'R ranks R'i over R'j 
if and only if sR ranks Ri over Rj.  Make the following abbreviations:  

For all r Î L(A), Agreed(r) = Agreed(r,A,R). 
For all r Î L(A), Agreed'(r) = Agreed(r,A,R'). 
For all r,r' Î L(A), Distinct(r,r') = DistinctAgreed(r,r',A,R). 
For all r,r' Î L(A), Distinct'(r,r') = DistinctAgreed(r,r',A,R'). 
For all r,r' Î L(A) such that Distinct(r,r') is not empty, 
          LDA(r,r') = LargestDistinctAgreed(r,r',A,R,s). 
For all r,r' Î L(A) such that Distinct'(r,r') is not empty, 
          LDA'(r,r') = LargestDistinctAgreed(r,r',A,R',s'). 
Undom = UndominatedRankings(A,R,s). 
Undom' = UndominatedRankings(A,R',s').  
Top2 = Top2(A,R,s).  
Top2' = Top2(A,R',s'). 
MAM2 = MAM2(A,R,s).  
MAM2' = MAM2(A,R',s'). 
Wx = Wx(R,A). 
W'x = Wx(R',A). 

Since s Î Wx(R,A), MAM2 = x.  This implies x Î Top2 and RVH ranks x over 
all other alternatives in Top2.  Monotonicity will follow easily if we establish 
the following three propositions:

Proposition 7:  For all r,r' Î L(A) and all a,b Î A, if x tops r 
and r dominates r' given (R,s) and (a,b) Î Distinct'(r,r'
and (a,b) precedes LDA(r,r') given (R',s') then a = x

Proposition 8:  There exists r Î Undom' topped by x.

Proposition 9:  For all y Î A, if no r Î Undom is topped by y
then no r Î Undom' is topped by y.  

Proof of 7:  Pick any r,r' Î L(A) and any a,b Î A.  Assume x tops r and 
r dominates r' given (R,s) and (a,b) Î Distinct'(r,r') and (a,b) precedes 
LDA(r,r') given (R',s').  We must show a = x.  Suppose to the contrary 
that a ¹ x.  Let (c,d) denote LDA(r,r').  Since r dominates r' given (R,s)
(c,d) Î Agreed(r).  Thus, since x tops r, d ¹ x.  By 4.2, (a,b) precedes (c,d) 
given (R,s).  Since (a,b) Î Distinct'(r,r'), (a,b) Î Maj'.  Since (a,b) Î Maj' 
and a ¹ x, by 2.4 and 2.5 (a,b) Î Maj.  Since (a,b) Î Distinct'(r,r') and 
(a,b) Î Maj, (a,b) Î Distinct(r,r').  Since (c,d) = LDA(r,r') and 
(a,b) Î Distinct(r,r'), by the definition of LargestDistinctAgreed() 
(a,b) does not precede (c,d) given (R,s).  But this is a contradiction,  
which means the contrary assumption cannot hold, establishing a = x.   QED 

Proof of 8:  Since x Î Top2, there exists r Î Undom topped by x.  We aim 
to show no r' Î L(A) dominates r given (R',s').  Pick any r' Î L(A).  Since 
r Î Undom, r' does not dominate r given (R,s).  There are two cases to consider: 

Case 8.1:  r dominates r' given (R,s).  This means LDA(r,r') Î Agreed(r
and LDA(r,r') Ï Agreed(r').  Let (a,b) denote LDA(r,r').  Thus 
(a,b) Î Maj.  Since x tops r, b ¹ x.  Since (a,b) Î Maj and b ¹ x
by 2.3 and 2.5 (a,b) Î Maj'.  Thus (a,b) Î Agreed'(r) and 
(a,b) Ï Agreed'(r').  Hence (a,b) Î Distinct'(r,r').  
By 7, the following statement must hold:  
        (8.1.1)  For all c,d Î A, if (c,d) Î Distinct'(r,r'
                    and (c,d) precedes (a,b) given (R',s') then c = x.  
Since (a,b) Î Distinct'(r,r') and x tops r, by 8.1.1 LDA'(r,r') Î Agreed'(r), 
which means r dominates r' given (R',s').  By theorem "Dominance is 
an Ordering"
this implies r' does not dominate r given (R',s')

Case 8.2:  r does not dominate r' given (R,s).  Since neither 
dominates the other given (R,s), Distinct(r,r') must be empty.  
There are two subcases to consider: 

Case 8.2.1:  Distinct'(r,r') is empty.  Clearly r' does not 
dominate r given (R',s')

Case 8.2.2:  Distinct'(r,r') is not empty.  Since Distinct(r,r') is 
empty, by 2 the following statement must hold:  
         (8.2.2.1)  For all (a,b) Î Distinct'(r,r'), a = x.  
Since x tops r, this implies LDA'(r,r') Î Agreed'(r), which 
implies r dominates r'  given (R',s').  By theorem "Dominance 
is an Ordering"
 this implies r' does not dominate r given (R',s').

Since r' does not dominate r given (R',s') in either subcase, r' does not 
dominate r given (R',s') in case 8.2.

Since r' does not dominate r given (R',s') in either case, and since r' was 
picked arbitrarily, this implies r Î Undom', establishing 8.     QED 

Proof of 9:  Pick any y Î A.  Assume no r Î Undom is topped by y.  We must 
show no r Î Undom' is topped by y.  Since x Î Top2, there exists r' Î Undom 
topped by x.  Thus y ¹ x.  Pick any r Î L(A) topped by y.  Since r Ï Undom, 
by theorem "Dominance is an Ordering" r' must dominate r given (R,s).  
By the same reasoning as in case 8.1, r' must dominate r given (R',s').  
Thus, since r was an arbitrarily picked strict ordering topped by y
this implies no r Î Undom' is topped by y, establishing 8.     QED 

By 8 and the definition of Top2(), x Î Top2'.  Since x Î Top2, 
by 9 and the definition of Top2() the following statement must hold:  
        (10)  For all y Î A, if y Ï Top2 then y Ï Top2'.  
Thus, Top2' Í Top2.  Since MAM2 = x, by the definition of MAM2() RVH ranks x  
over all other alternatives in Top2.  By 3, RVH' ranks x over  all other alternatives in 
Top2.  Since Top2' Í Top2, RVH' ranks x over all other alternatives in Top2'.  
Thus, since x Î Top2', MAM2' = x.  Since s was picked arbitrarily from Wx
it follows that Wx Í W'x, so #W'x ³ #Wx.  This means the  probability that x is 
elected by MAM2 does not decrease when x is upranked.  Thus MAM2 is 
monotonic.  By theorem "MAM2 = MAM", MAM is monotonic.        QED