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