MAM is monotonic

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 {s Î L(R,A) such that MAM(A,R,s) = 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 s Î W_x.
Let s' denote the ordered pair (s'_R,s_A) Î 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 s_R orders R_i over R_j. 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 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,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 Î W_x, 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 m_x 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'(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,s). (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'_0m₂₊ Í 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'_0m₂₊involves x.
By 2, Aff'_0m2+ Í Maj.  Since Aff'₀_m2+ Í Precede'(m₂), by 4 Aff'_0m₂₊ Í Precede(m₂). Since m₂ Î Aff and Aff'_0m₂₊ Í 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'₀_m₂₊ 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_m₃₊denote Aff Ç Precede(m₃). By theorem "Minimal Inconsistent Set (1)",
there exists Aff_0m3+ Í Aff_m₃₊ 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_0m₃₊ involves x. By 2, Aff_0m₃₊ Í Maj', and by 4 Aff_0m₃₊ Í Precede'(m₃).
Since m₃ Î Aff', by theorem "Consistency Maintained (2)" at least one majority
in Aff_0m₃₊ is not in Aff'. Thus we can let m₄ denote a majority in Aff_0m₃₊\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,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 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,s). 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'_0m₁₊.  Since x is also not second in m₁, by theorem "Minimal
Inconsistent Set (3)" no majority in Aff'_0m₁₊ involves x.  By 2, Aff'_0m₁₊ Í Maj,
and by 4 Aff'_0m₁₊ Í Precede(m₁).  Since m₁ Î Aff, by theorem "Consistency
Maintained (2)" at least one majority in Aff'_0m₁₊ is not in Aff. Thus we can
let m₂ denote a majority in Aff'_0m₁₊\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_0m₂₊. Since x is also not second in m₂, by theorem "Minimal
Inconsistent Set (3)" no majority in Aff_0m₂₊ involves x.  By 2, Aff_0m₂₊ Í Maj',
and by 4 Aff_0m₂₊ Í Precede'(m₂). Since m₂ Î Aff', by theorem "Consistency
Maintained (2)" at least one majority in Aff_0m₂₊ is not in Aff'. Thus we can
let m₃ denote a majority in Aff_0m₂₊\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 s
was picked arbitrarily from W_x, it follows that MAM(A,R',s') = x for all s Î 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 s Î W_x(R,A). Let s'
denote the ordered pair (s'_R,s_A) Î 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 s_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,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 = Top₂(A,R,s).
Top2' = Top₂(A,R',s').
MAM2 = MAM₂(A,R,s).
MAM2' = MAM₂(A,R',s').
W_x = W_x(R,A).
W'_x = W_x(R',A).

Since s Î 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,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 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 s 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