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