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 W_a(R,A) denote {σ ∈ L(R,A) such that MAM(A,R,σ) = a}. 
(Note: When W_a(R,A) is empty, MAM defeats a with certainty, 
and when W_a(R,A) = L(R,A), MAM chooses a with certainty.)

We provide two proofs that MAM is monotonic.  The second proof shows MAM₂ is 
monotonic and relies on the equivalence of MAM₂ 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 R_i denote the i^th ballot in R and let R'_i denote the i^th  
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 R_i ranks x over y then R'_i ranks x over y, 
          and if R'_i ranks y over x then R_i ranks y over x.

(1.2)  For all y,z ∈ A distinct from x, R'_i ranks y over z  
          if and only if R_i ranks y over z. 

Abbreviate W_x = W_x(R,A) and W'_x = W_x(R',A).  By the definition of MAM, the 
probability that MAM elects x given R is #W_x/#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 ≥ #W_x.  Pick any σ ∈ W_x.  
Let σ' denote the ordered pair (σ'_R,σ_A) ∈ 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 R_i over R_j.  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 a ∈ A, let L_a 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, 
        L_a = {(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 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 σ ∈ 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,σ) 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 σ ∈ W_x, 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 m_x 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'(m_x). 
(Perhaps Aff'₊ is empty.)  It follows from the definitions of m_x and Aff'₊ 
that x is not second in any majority in Aff'_mx+.  Since x ∈ Top, L_x is empty, 
implying m_x ∉ Aff.  By 1.1, m_x ∈ Maj.  Thus m_x must be inconsistent with 
Aff ∩ Precede(m_x).  Let Aff_mx+ denote Aff ∩ Precede(m_x).  By theorem 
"Minimal Inconsistent Set (1)", there must exist Aff_0mx+ ⊆ Aff_mx+ such that 
Aff_0mx+ is a minimal set with which m_x is inconsistent.  By theorem "Minimal 
Inconsistent Set (2)", x is not second in any majority in Aff_0mx+.  By 2, 
Aff_0mx+ ⊆ Maj'.  Since Aff_0mx+ ⊆ Precede(m_x), by 4 Aff_0mx+ ⊆ Precede'(m_x).  
Since m_x ∈ Aff' and Aff_0mx+ ⊆ Precede'(m_x), by theorem "Consistency 
Maintained (2)" at least one majority in Aff_0mx+ is not in Aff'.  Thus we can 
let m₁ denote a majority in Aff_0mx+\Aff'.  It has been established that m₁ ∈ Maj 
and m₁ ∈ Maj' and m₁ ∈ Aff_0mx+ and m₁ ∉ Aff' and m₁ ∈ Precede(m_x) 
and m₁ ∈ Precede'(m_x) and x is not second in m₁. 

Let M- denote the majorities (like m₁) in which x is not second and which are in 
Maj and in Maj' and in Aff and in Precede(m_x) and in Precede'(m_x) but not in Aff'.  
Clearly m₁ ∈ M-, so M- is not empty.  Thus, by theorem "Precedence is a 
Strict Ordering" there exists m₂ ∈ M- that precedes all other majorities in M-  
given (R,σ). (Perhaps m₂ = m₁.)  Since m₂ ∈ Maj'\Aff', m₂ must be inconsistent 
with Aff' ∩ Precede'(m₂).  Let Aff'_m2+ denote Aff' ∩ Precede'(m₂).  By theorem 
"Minimal Inconsistent Set (1)", there must exist Aff'_0m2+ ⊆ Aff'_m2+ that is a minimal 
set with which m₂ 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 m₂, by theorem "Minimal Inconsistent Set (3)" no majority in Aff'_0m2+ involves x.  
By 2, Aff'_0m2+ ⊆ Maj.  Since Aff'_0m2+ ⊆ Precede'(m₂), by 4 Aff'_0m2+ ⊆ Precede(m₂).  Since m₂ ∈ Aff and Aff'_0m2+ ⊆ Precede(m₂), by theorem "Consistency Maintained 
(2)" at least one majority in Aff'_0m2+ is not in Aff.  Thus we can let m₃ denote a 
majority in Aff'_0m2+\Aff.  It has been established that m₃ does not involve x and 
m₃ ∈ Maj and m₃ ∈ Maj' and m₃ ∈ Aff'_0m2+ and m₃ ∉ Aff and m₃ ∈ Precede(m₂) 
and m₃ ∈ Precede'(m₂).

Since m₃ ∈ Maj and m₃ ∉ Aff, m₃ must be inconsistent with Aff ∩ Precede(m₃).  
Let Aff_m3+ denote Aff ∩ Precede(m₃).  By theorem "Minimal Inconsistent Set (1)", 
there exists Aff_0m3+ ⊆ Aff_m3+ that is a minimal set with which m₃ is inconsistent.  
Since x ∈ Top, x is not second in any majority in Aff, and since m₃ does not 
involve x it follows by theorem "Minimal Inconsistent Set (3)" that  no majority 
in Aff_0m3+ involves x.  By 2, Aff_0m3+ ⊆ Maj', and by 4 Aff_0m3+ ⊆ Precede'(m₃).  
Since m₃ ∈ Aff', by theorem "Consistency Maintained (2)" at least one majority 
in Aff_0m3+ is not in Aff'.  Thus we can let m₄ denote a majority in Aff_0m3+\Aff'.

By the definition of M-, m₄ ∈ M-.  Since m₄ ∈ Precede(m₃) and m₃ ∈ Precede(m₂), 
by theorem  "Precedence is a Strict Ordering" m₄ ∈ Precede(m₂).  But this 
contradicts the definition of m₂.  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 L_y is not 
empty and L'_y is empty, M- is not empty.  Thus, by theorem  "Precedence is a 
Strict Ordering" there must exist m₁ ∈ M- that precedes all other majorities in M- 
given (R,σ).  Since m₁ ∈ Aff, m₁ ∈ Maj.  By 2, m₁ ∈ Maj'.  Since m₁ ∈ Maj'  
and m₁ ∉ Aff', m₁ must be inconsistent with Aff' ∩ Precede'(m₁).  By theorem 
"Minimal Inconsistent Set (1)", there exists Aff'_0m1+ ⊆ Aff' ∩ Precede'(m₁) 
that is a minimal set with which m₁ 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 m₁, by theorem "Minimal 
Inconsistent Set (3)" no majority in Aff'_0m1+ involves x.  By 2, Aff'_0m1+ ⊆ Maj, 
and by 4 Aff'_0m1+ ⊆ Precede(m₁).  Since m₁ ∈ Aff, by theorem "Consistency 
Maintained (2)" at least one majority in Aff'_0m1+ is not in Aff.  Thus we can 
let m₂ denote a majority in Aff'_0m1+\Aff.  Since m₂ ∈ Maj\Aff, m₂ must be 
inconsistent with Aff ∩ Precede(m₂).  By theorem "Minimal Inconsistent Set (1)", 
there exists Aff_0m2+ ⊆ Aff ∩ Precede(m₂) that is a minimal set with which m₂ is 
inconsistent.  Since x is not second in any majority in Aff, x is not second in 
any majority in Aff_0m2+.  Since x is also not second in m₂, by theorem "Minimal 
Inconsistent Set (3)" no majority in Aff_0m2+ involves x.  By 2, Aff_0m2+ ⊆ Maj', 
and by 4 Aff_0m2+ ⊆ Precede'(m₂).  Since m₂ ∈ Aff', by theorem "Consistency 
Maintained (2)" at least one majority in Aff_0m2+ is not in Aff'.  Thus we can 
let m₃ denote a majority in Aff_0m2+\Aff'.  Thus m₃ ∈ Aff\Aff' and x is not 
second in m₃.  Thus m₃ ∈ M-.  Since m₃ ∈ Precede(m₂) and m₂ ∈ Precede(m₁), 
by theorem "Precedence is a Strict Ordering" m₃ ∈ Precede(m₁).  But this 
contradicts the definition of m₁, 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 W_x, it follows that MAM(A,R',σ') = x for all σ ∈ W_x.  
Thus W_x ⊆ W'_x, so #W'_x ≥ #W_x.  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 "MAM₂ = MAM".)  
Refer to the definitions and propositions above.  Pick any σ ∈ W_x(R,A).  Let σ'  
denote the ordered pair (σ'_R,σ_A) ∈ 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 R_i over R_j.  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,σ). 
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 = Top₂(A,R,σ).  
Top2' = Top₂(A,R',σ'). 
MAM2 = MAM₂(A,R,σ).  
MAM2' = MAM₂(A,R',σ'). 
W_x = W_x(R,A). 
W'_x = W_x(R',A). 

Since σ ∈ W_x(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,σ) 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 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,σ) 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 a ≠ x.  Let (c,d) denote LDA(r,r').  Since r dominates r' given (R,σ), 
(c,d) ∈ Agreed(r).  Thus, since x tops r, d ≠ x.  By 4.2, (a,b) precedes (c,d) 
given (R,σ).  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,σ).  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, 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',σ') 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 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,σ).  
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 Top₂(), x ∈ Top2'.  Since x ∈ Top2, 
by 9 and the definition of Top₂() 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 MAM₂() 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 W_x, 
it follows that W_x ⊆ W'_x, so #W'_x ≥ #W_x.  This means the  probability that x is 
elected by MAM₂ does not decrease when x is upranked.  Thus MAM₂ is 
monotonic.  By theorem "MAM₂ = MAM", MAM is monotonic.        QED