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 {σ ∈ L(R,A) such that MAM(A,R,σ) = 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 xA and all i ∈ {1,2,...,#R}, both of 
the following conditions hold: 

(1.1)  For all yA, 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,zA 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 σ ∈ Wx.  
Let σ' denote the ordered pair (σ'RA)L(R',A) such that σ'R is the strict 
ordering of the votes in R' such that, for all i,j ∈ (1,2,...,#R}, σ'R orders R'i  
over R'j if and only if σR orders Ri over Rj.  Make the following abbreviations: 

Maj = Majorities(A,R). 
Maj' = Majorities(A,R').  
RVH = RVH(A,R,σ) 
RVH' = RVH(A,R',σ').  
Precede(a,b) = Precede(a,b,A,R,σ) for all (a,b)Pairs.
Precede'(a,b) = Precede(a,b,A,R',σ') for all (a,b)Pairs.
Aff = Affirmed(A,R,σ). 
Aff' = Affirmed(A,R',σ'). 
For all aA, 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,σ).  
Top' = Top(A,R',σ').  
MAM = MAM(A,R,σ).  
MAM' = MAM(A,R',σ'). 

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 yA, #R'(x,y) ≥ #R(x,y) and #R'(y,x) ≤ #R(y,x).
        (2.2)  For all y,zA\{x}, #R'(y,z) = #R(y,z).  
        (2.3)  For all yA, if (x,y) ∈ Maj then (x,y) ∈ Maj'.  
        (2.4)  For all yA, if (y,x) ∈ Maj' then (y,x) ∈ Maj.  
        (2.5)  For all y,zA\{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 yA, if RVH ranks x over y then RVH' ranks x over y
        (3.2)  For all yA, if RVH' ranks y over x then RVH ranks y over x
        (3.3)  For all σ ∈ L(R,A) and all y,zA 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,σ) and x is neither 
                  second in p nor first in p' then p precedes p' given (R',σ')
        (4.2)  For all p,p'Pairs, if p precedes p' given (R',σ') and x is neither 
                  first in p nor second in p', then p precedes p' given (R,σ).

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 σ ∈ Wx, MAM = x, which implies x ∈ Top.  Suppose to the 
contrary x ∉ Top'.  This implies L'x ≠ φ.  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',σ').  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 m1M-, so M- is not empty.  Thus, by theorem "Precedence is a 
Strict Ordering"
there exists m2M- that precedes all other majorities in M-  
given (R,σ). (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-, m4M-.  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,σ) = 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 m1M- that precedes all other majorities in M- 
given (R,σ).  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 m3M-.  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 σ  
was picked arbitrarily from Wx, it follows that MAM(A,R',σ') = x for all σ ∈ Wx.  
Thus WxW'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 σ ∈ Wx(R,A).  Let σ'  
denote the ordered pair (σ'RA)L(R',A) where σ'R is the strict ordering of 
the votes in R' such that, for all i,j ∈ (1,2,...,#R}, σ'R ranks R'i over R'j 
if and only if σR ranks Ri over Rj.  Make the following abbreviations:  

For all rL(A), Agreed(r) = Agreed(r,A,R). 
For all rL(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,σ). 
For all r,r'L(A) such that Distinct'(r,r') is not empty, 
          LDA'(r,r') = LargestDistinctAgreed(r,r',A,R',σ'). 
Undom = UndominatedRankings(A,R,σ). 
Undom' = UndominatedRankings(A,R',σ').  
Top2 = Top2(A,R,σ).  
Top2' = Top2(A,R',σ'). 
MAM2 = MAM2(A,R,σ).  
MAM2' = MAM2(A,R',σ'). 
Wx = Wx(R,A). 
W'x = Wx(R',A). 

Since σ ∈ 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,bA, if x tops r 
and r dominates r' given (R,σ) and (a,b) ∈ Distinct'(r,r'
and (a,b) precedes LDA(r,r') given (R',σ') then a = x

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

Proposition 9:  For all yA, 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,bA.  Assume x tops r and 
r dominates r' given (R,σ) and (a,b) ∈ Distinct'(r,r') and (a,b) precedes 
LDA(r,r') given (R',σ').  We must show a = x.  Suppose to the contrary 
that ax.  Let (c,d) denote LDA(r,r').  Since r dominates r' given (R,σ)
(c,d) ∈ Agreed(r).  Thus, since x tops r, dx.  By 4.2, (a,b) precedes (c,d) 
given (R,σ).  Since (a,b) ∈ Distinct'(r,r'), (a,b) ∈ Maj'.  Since (a,b) ∈ Maj' 
and ax, 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,σ).  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',σ').  Pick any r'L(A).  Since 
r ∈ Undom, r' does not dominate r given (R,σ).  There are two cases to consider: 

Case 8.1:  r dominates r' given (R,σ).  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, bx.  Since (a,b) ∈ Maj and bx
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,dA, if (c,d) ∈ Distinct'(r,r'
                    and (c,d) precedes (a,b) given (R',σ') 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',σ').  By theorem "Dominance is 
an Ordering"
this implies r' does not dominate r given (R',σ')

Case 8.2:  r does not dominate r' given (R,σ).  Since neither 
dominates the other given (R,σ), 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',σ')

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',σ').  By theorem "Dominance 
is an Ordering"
 this implies r' does not dominate r given (R',σ').

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

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

Proof of 9:  Pick any yA.  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 yx.  Pick any rL(A) topped by y.  Since r ∉ Undom, 
by theorem "Dominance is an Ordering" r' must dominate r given (R,σ).  
By the same reasoning as in case 8.1, r' must dominate r given (R',σ').  
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 yA, 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 σ was picked arbitrarily from Wx
it follows that WxW'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