The "Maximize Affirmed Majorities" voting method (MAM) 
satisfies Strong Pareto and Weak Pareto.

Revised:  January 03, 2003

The following wordings of strong and weak Pareto-efficiency are conventional but 
narrow in scope. (Below we will provide more general wordings.) 

Strong Pareto-efficiency:  For all alternatives, for instance x, x must not be 
elected if there exists another alternative, say y, such that no voters rank x  
over y and at least one voter ranks y over x.

Weak Pareto-efficiency:  For all alternatives, for instance x, x must not be 
elected if there exists an alternative, say y, such that every voter ranks y over x.

The above wordings assume the voting procedure is electing one alternative.  It makes 
sense to generalize the criteria to include elections where more than one alternative is 
to be elected and/or where a social ordering of the alternatives is to be constructed: 

Strong Pareto-efficiency:  For all pairs of alternatives x and y, if no voters 
rank x over y and at least one voter ranks y over x then x must not be elected 
unless y is also elected, and x must not be socially ordered as high as y. 

Weak Pareto-efficiency:  For all pairs of alternatives x and y, if all voters 
rank y over x, then x must not be elected unless y is also elected, and 
x must not be socially ordered as high as y. 

Clearly, with either set of wordings, any voting method that satisfies strong Pareto-
efficiency also satisfies weak Pareto-efficiency.  

Before proving MAM satisfies strong Pareto and weak Pareto, we provide an example 
that shows the Ranked Pairs method defined by TN Tideman [1987] can violate strong 
Pareto.  Ranked Pairs bears some similarities to MAM, but there are important differences.  
It ranks the majorities from "largest" to "smallest" too, but using a different sense of these 
terms, measuring the size of each majority by the difference between the sizes of its 
supporting coalition and its opposing coalition, whereas MAM measures size primarily by 
the size of its supporting coalition.  Also, Ranked Pairs considers all possible ways of 
breaking ties (two or more majorities that are the same size) in the precedence ordering 
of majorities, whereas MAM constructs a single strict precedence ordering. (The 1989 
revision of Ranked Pairs by TM Zavist and Tideman also constructs a single strict 
precedence ordering, but not in the same manner as MAM.  Ranked Pairs 1989 
satisfies strong Pareto, but proving that is beyond the scope of this document.)  

Example 1.  Ranked Pairs (1987) violates strong Pareto.  
Suppose there are 4 alternatives {a,b,c,d} and 3 voters who vote as follows: 
    1            2            3 
   a~b           c            d 
    c            d            a 
    d           a~b           b 
                              c

Since no voters rank b over a and one voter (voter 3) ranks a over b, 
strong Pareto requires that b be defeated with certainty.  
There are 6 majorities: 
        2 voters rank a over c, while only 1 ranks c over a.  Thus (a,c) is a majority.  
        2 voters rank b over c, while only 1 ranks c over b.  Thus (b,c) is a majority.   
        2 voters rank c over d, while only 1 ranks d over c.  Thus (c,d) is a majority.   
        2 voters rank d over a, while only 1 ranks a over d.  Thus (d,a) is a majority.   
        2 voters rank d over b, while only 1 ranks b over d.  Thus (d,b) is a majority.   
        1 voter ranks a over b, while none rank b over a.  Thus (a,b) is a majority.   
All 6 majorities have the same size according to Ranked Pairs 1987, so it considers 
all possible orderings of the majorities.  Thus there are some orderings that rank 
(b,c), (c,d) and (d,a) ahead of the other majorities.  Given any of those orderings 
of the majorities, b tops the social ordering.  Thus there is a non-zero chance that 
Ranked Pairs 1987 elects b, violating strong Pareto. 

Theorem:  "MAM satisfies strong Pareto."  

Proof:  Refer to the formal definition of MAM.  Pick any alternatives x,y Î A.  Assume 
no voters rank x over y and at least one voter ranks y over x.  That is, #R(x,y) = 0 
and #R(y,x) > 0.  We must show MAM does not elect x and socially orders y over x.  
We will show that (y,x) is a majority affirmed by MAM, after which it will follow easily 
that MAM does not elect x and socially orders y over x.  Pick any s Î L(R,A).  
Make the following abbreviations: 

Maj = Majorities(A,R).    ({(a,b) Î Pairs(A) such that #R(a,b) > #R(b,a)}) 
RVH = RVH(A,R,s).        (The strict "tie-breaking" ranking of A constructed using 
                                           the "Random Voter Hierarchy" procedure RVH().)
Precede(a,b) = Precede(a,b,A,R,s) for all (a,b) Î Pairs(A).   (The ordered 
                                           pairs that "precede" (a,b).  
Aff = Affirmed(A,R,s).     (The affirmed majorities {(a,b) Î Maj such that 
                                           (a,b) is consistent with Aff Ç Precede(a,b)}.)

Since #R(y,x) > #R(x,y), (y,x) Î Maj.  Furthermore, since no voters rank x over y, 
it follows that for all z Î A distinct from x and y, every voter who ranks z over y  
also ranks z over x, and every voter who ranks x over z also ranks y over z.  
Thus both of the following statements hold:  

(1.1)  For all z Î A\{x,y}, #R(z,x) ³ #R(z,y).  
(1.2)  For all z Î A\{x,y}, #R(y,z) ³ #R(x,z).  

Make the following definitions: 

Let 2^Maj denote the set of all subsets of Maj.  

For all subsets of majorities M Î 2^Maj, let min(M,R,s) denote {(a,b) Î M  
such that, for all (c,d) Î M, (a,b) does not precede (c,d) given (R,s)}. 
(In other words, the majority or majorities in M having the "least precedence."  
Note that by theorem "Precedence is a Strict Ordering", min(M,R,s) is a 
singleton (a unique majority) for all non-empty M Î 2^Maj.)  Since R and s 
are fixed in this context, abbreviate min(M). 

For all pairs of subsets of majorities M,M' Î 2^Maj, let Diff(M,M') denote 
(M È M')\(M Ç M'). (That is, the majorities in M or in M' but not in both.)  

Clearly Diff(M,M') is not empty for all distinct M,M' Î 2^Maj.  Thus min(Diff(M,M')) 
is a singleton (a unique majority) for all distinct M,M' Î 2^Maj.  Furthermore it is 
clear that either min(Diff(M,M')) Í M or min(Diff(M,M')) Í M', but not both, 
for all distinct M,M' Î 2^Maj. 

For all pairs of subsets of majorities M,M' Î 2^Maj, say M exceeds M'  
given (R,s) if and only if min(Diff(M,M')) Ç M is empty 
and min(Diff(M,M')) Ç M' is not empty.  Since R and s are 
fixed in this context, abbreviate by omitting "given (R,s)." 

Next we show that the exceeds relation is a strict ordering of 2^Maj.  That is, 
we show all four of the following properties hold:  
        Irreflexivity:  For all M Í Maj, M does not exceed M.  
        Asymmetry:  For all distinct M,M' Í Maj, if M exceeds M' 
                then M' does not exceed M.  
        Completeness:  For all distinct M,M' Í Maj, 
                either M exceeds M' or M' exceeds M.  
        Transitivity:  For all M,M',M" Í Maj, if M exceeds M'  
                and M' exceeds M" then M exceeds M".  
By inspection of its definition, clearly exceeds is irreflexive and asymmetric.  Next we 
show that exceeds is complete.  Pick any distinct M,M' Î 2^Maj.  Assume M does not 
exceed M'.  We must show M' exceeds M.  Since M ¹ M', Diff(M,M') is not empty.  
Thus, by theorem "Precedence is a Strict Ordering" there is a unique (a,b) Î Diff(M,M') 
such that min(Diff(M,M')) = {(a,b)}.  By the definition of Diff(), either (a,b) Î M  
or (a,b) Î M' but not both.  Thus either min(Diff(M,M')) Ç M is empty or 
min(Diff(M,M')) Ç M' is empty but not both.  Since M does not exceed M', it 
follows that min(Diff(M,M')) Ç M is not empty or min(Diff(M,M')) Ç M' is empty.  
Thus, since one is empty but not both, it follows that min(Diff(M,M')) Ç M is not 
empty and min(Diff(M,M')) Ç M' is empty.   Thus M' exceeds M.  Thus exceeds 
is complete.  Next we show exceeds is transitive.  Pick any M,M',M" Î 2^Maj.  
Assume M exceeds M' and M' exceeds M".  We must show M exceeds M".  
Suppose the contrary.  Since exceeds is irreflexive, M ¹ M' and M' ¹ M".  
Since exceeds is asymmetric, M ¹ M".  Since exceeds is complete and 
M does not exceed M", M" must exceed M.  By reasoning as in the argument 
that showed exceeds is complete, there must be a unique (a,b) Î Maj such 
that min(Diff(M,M')) = {(a,b)} and (a,b) Î M' and (a,b) Ï M.  Similarly, 
there must ve a unique (c,d) Î Maj such that min(Diff(M',M")) = {(c,d)} 
and (c,d) Î M" and (c,d) Ï M'.  Similarly, there must be a unique (e,f) Î Maj 
such that min(Diff(M,M")) = {(e,f)} and (e,f) Î M and (e,f) Ï M".  
There are four cases to consider:  

Case 2.1:  (a,b) = (c,d).  Since (a,b) Î M' and (c,d) Ï M', this case is impossible.  

Case 2.2:  (c,d) = (e,f).  Since (c,d) Î M" and (e,f) Ï M", this case is impossible.  

Case 2.3:  (a,b) = (e,f).  Since (e,f) Î M and (a,b) Ï M, this case is impossible.  

Case 2.4:  (a,b), (c,d) and (e,f) are three distinct majorities.  By theorem 
"Precedence is a Strict Ordering", one of these three majorities must be 
preceded by the other two.  Without loss of generality, assume (a,b) is 
preceded by (c,d) and by (e,f). (We could swap the labels of M, M'  
and/or M" if needed to make this so.)  Since (c,d) precedes (a,b)  
and min(Diff(M',M")) = {(c,d)} and (a,b) Î M', this implies (a,b) Î M".  
Since (a,b) Ï M, (a,b) Î Diff(M,M").  But since (e,f) precedes (a,b), 
this contradicts min(Diff(M,M")) = {(e,f)}.  Thus this case is impossible.  

Since all four cases are impossible, the contrary assumption cannot hold, 
establishing exceeds is transitive.  Since exceeds is irreflexive, asymmetric, 
complete and transitive, it is a strict ordering of 2^Maj.  

Make some additional definitions: 

For all pairs of alternatives a,b Î A and all M Í Maj, call M an affirmed path 
from a to b if and only if M Í Aff and there exists a sequence of alternatives 
c₁,c₂,...,c_k such that c₁ = a and c_k = b and M = {(c₁,c₂),(c₂,c₃),...,(c_k-1,c_k)}.  

For all pairs of alternatives a,b Î A, let Maj(a,b) denote {M Í Maj such that 
M is an affirmed path from a to b}. (In other words, the set of all affirmed 
paths from a to b. (Note that Maj(a,b) may be empty for some pairs a,b.)   

For all pairs of alternatives a,b Î A, let Max(a,b) denote {M Í Maj(a,b) 
such that, for all M' Í Maj(a,b), M' does not exceed M}. (In other words, 
the set of affirmed paths from a to b having "maximal precedence", as 
defined by a "maxileximin" comparison.  Note that since exceeds is a 
strict ordering of the subsets of Maj, Max(a,b) is a singleton--a unique 
affirmed path from a to b--whenever Maj(a,b) is not empty.)  

For all pairs of alternatives a,b Î A such that Max(a,b) is a singleton, 
let max(a,b) denote the unique affirmed path from a to b in Max(a,b).

By the definition of Affirmed(), it is clear that the following statement holds: 

(3)  For all (a,b) Î Maj\Aff) (that is, all non-affirmed majorities), 
       Maj(b,a) is not empty and Max(b,a) is a singleton 
       and max(b,a) Í Precede(a,b). 

We aim to show (y,x) Î Aff.  Suppose the contrary.  Since (y,x) Î Maj, it follows 
by 3 that Max(x,y) is a singleton and max(x,y) Í Precede(y,x).  We can represent 
max(x,y) as {(x,z₁),(z₁,z₂,),...,(z_k-1,z_k),(z_k,y)}.  Clearly (x,z₁) Î Aff and (z_k,y) Î Aff, 
which implies (x,z₁) Î Maj and (z_k,y) Î Maj, which means #R(x,z₁) > #R(z₁,x) 
and #R(z_k,y) > #R(y,z_k).  By 1.1 and 1.2, the following statements hold: 
        (4.1)  #R(y,z₁) ³ #R(x,z₁) > #R(z₁,x) ³ #R(z₁,y).  
        (4.2)  #R(z_k,x) ³ #R(z_k,y) > #R(y,z_k) ³ #R(x,z_k).  
By 4.1, (y,z₁) Î Maj.  By 4.2, (z_k,x) Î Maj.  Since {(z₁,z₂,),...,(z_k,y)} Í Aff, 
and since by theorem "Consistency Maintained" Aff is internally consistent, 
it follows that (y,z₁) Ï Aff.  Similarly, since {(x,z₁),...,(z_k-1,z_k)} Í Aff, 
(z_k,x) Ï Aff.  Thus, by 3 both of the following statements hold: 
        (5.1)  Max(z₁,y) is a singleton and max(z₁,y) Í Precede(y,z₁).  
        (5.2)  Max(x,z_k) is a singleton and max(x,z_k) Í Precede(z_k,x).  

We will establish both of the following propositions:  
        (6.1)  max(z₁,y) = max(x,y)\{(x,z₁)}. (That is, {(z₁,z₂,),(z₂,z₃,),...,(z_k,y)}.) 
        (6.2)  max(x,z_k) = max(x,y)\{(z_k,y)}. (That is, {(x,z₁),(z₁,z₂),...,(z_k-1,z_k)}.) 

Proof of 6.1:  Abbreviate D₁ = Diff(max(z₁,y), max(x,y)\{(x,z₁)}).  Suppose 
to the contrary 6.1 does not hold.  This means max(z₁,y) and max(x,y)\{(x,z₁)} 
are distinct affirmed paths from z₁ to y.  Thus D₁ is not empty.  Since exceeds is a 
strict ordering of 2^Maj, it follows by the definition of max() that max(z₁,y) exceeds 
max(x,y)\{(x,z₁)}.  By the definition of exceeds, both of the following must hold: 
        (6.1.1)  min(D₁) Ç max(z₁,y) is empty.  
        (6.1.2)  min(D₁) Ç (max(x,y)\{(x,z₁)}) is not empty.  
Abbreviate D₂ = Diff({(x,z₁)} È max(z₁,y), max(x,y)).  Since (x,z₁) Î max(x,y) 
and (x,z₁) Ï max(z₁,y), D₂ = D₁.  Thus, by 6.1.1 min(D₂) Ç ({(x,z₁)} È max(z₁,y)) 
is empty, and by 6.1.2 min(D₂) Ç max(x,y) is not empty.  Thus {(x,z₁)} È max(z₁,y) 
exceeds max(x,y).  But since both {(x,z₁)} È max(z₁,y) and max(x,y) are affirmed 
paths from x to y, it follows by the definition of max() that no affirmed path from x 
to y exceeds max(x,y).  This contradiction implies the contrary assumption cannot 
hold, establishing 6.1.        QED  

Proof of 6.2:  (This closely parallels the arguments in the proof of 6.1.)  Abbreviate 
D₃ = Diff(max(x,z_k), max(x,y)\{(z_k,y)}).  Suppose to the contrary 6.2 does not 
hold.  Thus max(x,z_k) and max(x,y)\{(z_k,y)} are distinct affirmed paths from x  
to z_k, and D₃ is not empty.  It follows that max(x,z_k) exceeds max(x,y)\{(z_k,y)} 
and that both of the following hold: 
        (6.2.1)  min(D₃) Ç max(x,z_k) is empty.  
        (6.2.2)  min(D₃) Ç (max(x,y)\{(z_k,y)}) is not empty.  
Abbreviate D₄ = Diff(max(x,z_k) È {(z_k,y)}, max(x,y)).  Since (z_k,y) Î max(x,y) and 
(z_k,y) Ï max(x,z_k), D₄ = D₃.  Thus, by 6.2.1 min(D₄) Ç (max(x,z_k) È {(z_k,y)}) is 
empty, and by 6.2.2 min(D₄) Ç max(x,y) is not empty.  Thus max(x,z_k) È {(z_k,y)} 
exceeds max(x,y).  But since both max(x,z_k) È {(z_k,y)} and max(x,y) are affirmed 
paths from x to y, it follows by the definition of max() that no affirmed path from x 
to y exceeds max(x,y).  This contradiction implies the contrary assumption cannot 
hold, establishing 6.2.        QED  

By 5.1 and 6.1, (z_k,y) precedes (y,z₁).  By 5.2 and 6.2, (x,z₁) precedes (z_k,x).  
Thus, by the definition of precedence both of the following conditions must hold:  
        (7.1)  #R(z_k,y) > #R(y,z₁) or [ #R(z_k,y) = #R(y,z₁) and #R(z₁,y) ³ #R(y,z_k)]. 
        (7.2)  #R(x,z₁) > #R(z_k,x) or [ #R(x,z₁) = #R(z_k,x) and #R(x,z_k) ³ #R(z₁,x)]. 
By 7.1 and 1.1, the following holds:  
        (8)  #R(z_k,x) ³ #R(z_k,y) ³ #R(y,z₁).  
By 7.2 and 1.2, the following holds: 
        (9)  #R(y,z₁) ³ #R(x,z₁) ³ #R(z_k,x).  
Together, 8 and 9 imply the following holds: 
        (10)  #R(z_k,x) = #R(z_k,y) = #R(y,z₁) = #R(x,z₁). 
By 10, 7.1 and 1.1, the following holds:  
        (11)  #R(z₁,x) ³ #R(z₁,y) ³ #R(y,z_k).  
By 10, 7.2 and 1.2, the following holds:  
        (12)  #R(y,z_k) ³ #R(x,z_k) ³ #R(z₁,x).  
Together, 11 and 12 imply the following holds: 
        (13)  #R(z₁,x) = #R(z₁,y) = #R(y,z_k) = #R(x,z_k). 
By 10 and 13, the four majorities (x,z₁), (y,z₁), (z_k,x) and (z_k,y) have the same 
size supporting coalitions and have the same size opposing coalitions, so their 
relative precedence is determined by RVH (the strict tiebreaking ordering).  
Since (z_k,y) precedes (y,z₁), by 10 and 13 and the definition of precedence  
RVH must rank z₁ over y.  Since (x,z₁) precedes (z_k,x), by 10 and 13 and 
the definition of precedence RVH must rank x over z₁.  Since RVH ranks 
x over z₁ and z₁ over y, by theorem "Random Voter Hierarchy is a Strict 
Ordering" RVH ranks x over y.  But since #R(y,x) > 0 and #R(x,y) = 0, it 
follows by the definition of Random Voter Hierarchy that RVH ranks y over x.  
This contradiction implies the contrary assumption (y,x) Ï Aff cannot hold, 
establishing (y,x) Î Aff.  Since s was picked arbitrarily, this implies 
(y,x) Î Affirmed(A,R,s) for all s Î L(R,A). (That is, with certainty.)   
Since x is second in at least one affirmed majority, it follows that MAM 
does not elect x (and the MAM social ordering ranks y over x).  
Thus MAM satisfies strong Pareto-efficiency.         QED

Next we show MAM also satisfies weak Pareto-efficiency.  Although we could 
simply point out that satisfaction of strong Pareto-efficiency implies satisfaction 
of weak Pareto-efficiency, it is more instructive to offer a more direct proof that 
does not rely on the properties of the Random Voter Hierarchy tie-breaker. 
(Hence this proof also works for Ranked Pairs 1987 and Ranked Pairs 1989.)  

Assume every voter ranks y over x.  Clearly (y,x) is a majority.  We aim to show 
that MAM affirms (y,x) since it will follow immediately that MAM does not elect x.  
Let n denote the number of voters.  Define the binary relation P on the alternatives 
as follows: 

For all pairs of alternatives a and b, say aPb if and only if 
every voter ranks a over b.  

We show that P is transitive.  Assume aPb and bPc.  We must show aPc.  
Since every voter ranks a over b and b over c, and since every vote is an 
ordering of the alternatives, it follows immediately that every voter ranks a  
over c.  Hence aPc.  Thus P is transitive.  

Suppose to the contrary that MAM does not affirm (y,x).  By the definition 
of Affirmed(), this implies (y,x) is inconsistent with Aff Ç Precede(y,x).  
Thus there must exist (z₁,z₂),(z₂,z₃,),...,(z_k-1,z_k) Î Aff Ç Precede(y,x) 
such that z₁ = x and z_k = y.  Thus (z₁,z₂),(z₂,z₃,),...,(z_k-1,z_k) Î Precede(y,x).  
By the definition of precedence, #R(z_j,z_j+1) ³ #R(y,x) for all j Î {1,2,...,k-1}.  
Since #R(y,x) = n (the number of voters), it follows that #R(z_j,z_j+1) = n for 
all j Î {1,2,...,k-1}.  Thus z₁Pz₂ and z₂Pz₃ and ... and z_k-1Pz_k.  Since P is 
transitive, z₁Pz_k.  But since z₁ = x and z_k = y, this means every voter ranks 
x over y, a contradiction.  Thus the contrary assumption cannot hold, which 
means MAM affirms (y,x).  Since x is second in at least one affirmed majority, 
it follows by the definition of MAM that MAM does not elect x.        QED