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 σ ∈ 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,σ).        (The strict "tie-breaking" ranking of A constructed using 
                                           the "Random Voter Hierarchy" procedure RVH().)
Precede(a,b) = Precede(a,b,A,R,σ) for all (a,b)Pairs(A).   (The ordered 
                                           pairs that "precede" (a,b).  
Aff = Affirmed(A,R,σ).     (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 zA 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 zA\{x,y}, #R(z,x) ≥ #R(z,y).  
(1.2)  For all zA\{x,y}, #R(y,z) ≥ #R(x,z).  

Make the following definitions: 

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

For all subsets of majorities M ∈ 2Maj, let min(M,R,σ) denote {(a,b)M  
such that, for all (c,d)M, (a,b) does not precede (c,d) given (R,σ)}. 
(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,σ) is a 
singleton (a unique majority) for all non-empty M ∈ 2Maj.)  Since R and σ 
are fixed in this context, abbreviate min(M). 

For all pairs of subsets of majorities M,M' ∈ 2Maj, let Diff(M,M') denote 
(MM')\(MM'). (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' ∈ 2Maj.  Thus min(Diff(M,M')) 
is a singleton (a unique majority) for all distinct M,M' ∈ 2Maj.  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' ∈ 2Maj

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

Next we show that the exceeds relation is a strict ordering of 2Maj.  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' ∈ 2Maj.  Assume M does not 
exceed M'.  We must show M' exceeds M.  Since MM', 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" ∈ 2Maj.  
Assume M exceeds M' and M' exceeds M".  We must show M exceeds M".  
Suppose the contrary.  Since exceeds is irreflexive, MM' and M'M".  
Since exceeds is asymmetricMM".  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 2Maj.  

Make some additional definitions: 

For all pairs of alternatives a,bA 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 
c1,c2,...,ck such that c1 = a and ck = b and M = {(c1,c2),(c2,c3),...,(ck-1,ck)}.  

For all pairs of alternatives a,bA, 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,bA, let Max(a,b) denote {MMaj(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,bA 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,z1),(z1,z2,),...,(zk-1,zk),(zk,y)}.  Clearly (x,z1) ∈ Aff and (zk,y) ∈ Aff, 
which implies (x,z1) ∈ Maj and (zk,y) ∈ Maj, which means #R(x,z1) > #R(z1,x
and #R(zk,y) > #R(y,zk).  By 1.1 and 1.2, the following statements hold: 
        (4.1)  #R(y,z1) ≥ #R(x,z1) > #R(z1,x) ≥ #R(z1,y).  
        (4.2)  #R(zk,x) ≥ #R(zk,y) > #R(y,zk) ≥ #R(x,zk).  
By 4.1, (y,z1) ∈ Maj.  By 4.2, (zk,x) ∈ Maj.  Since {(z1,z2,),...,(zk,y)} ⊆ Aff, 
and since by theorem "Consistency Maintained" Aff is internally consistent, 
it follows that (y,z1) ∉ Aff.  Similarly, since {(x,z1),...,(zk-1,zk)} ⊆ Aff, 
(zk,x) ∉ Aff.  Thus, by 3 both of the following statements hold: 
        (5.1)  Max(z1,y) is a singleton and max(z1,y) ⊆ Precede(y,z1).  
        (5.2)  Max(x,zk) is a singleton and max(x,zk) ⊆ Precede(zk,x).  

We will establish both of the following propositions:  
        (6.1)  max(z1,y) = max(x,y)\{(x,z1)}. (That is, {(z1,z2,),(z2,z3,),...,(zk,y)}.) 
        (6.2)  max(x,zk) = max(x,y)\{(zk,y)}. (That is, {(x,z1),(z1,z2),...,(zk-1,zk)}.) 

Proof of 6.1:  Abbreviate D1 = Diff(max(z1,y), max(x,y)\{(x,z1)}).  Suppose 
to the contrary 6.1 does not hold.  This means max(z1,y) and max(x,y)\{(x,z1)
are distinct affirmed paths from z1 to y.  Thus D1 is not empty.  Since exceeds is a 
strict ordering of 2Maj, it follows by the definition of max() that max(z1,y) exceeds 
max(x,y)\{(x,z1)}.  By the definition of exceeds, both of the following must hold: 
        (6.1.1)  min(D1) ∩ max(z1,y) is empty.  
        (6.1.2)  min(D1) ∩ (max(x,y)\{(x,z1)}) is not empty.  
Abbreviate D2 = Diff({(x,z1)} ∪ max(z1,y), max(x,y)).  Since (x,z1)max(x,y
and (x,z1)max(z1,y), D2 = D1.  Thus, by 6.1.1 min(D2) ∩ ({(x,z1)} ∪ max(z1,y)) 
is empty, and by 6.1.2 min(D2) ∩ max(x,y) is not empty.  Thus {(x,z1)} ∪ max(z1,y
exceeds max(x,y).  But since both {(x,z1)} ∪ max(z1,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 
D3 = Diff(max(x,zk), max(x,y)\{(zk,y)}).  Suppose to the contrary 6.2 does not 
hold.  Thus max(x,zk) and max(x,y)\{(zk,y)} are distinct affirmed paths from x  
to zk, and D3 is not empty.  It follows that max(x,zk) exceeds max(x,y)\{(zk,y)
and that both of the following hold: 
        (6.2.1)  min(D3) ∩ max(x,zk) is empty.  
        (6.2.2)  min(D3) ∩ (max(x,y)\{(zk,y)}) is not empty.  
Abbreviate D4 = Diff(max(x,zk) ∪ {(zk,y)}, max(x,y)).  Since (zk,y)max(x,y) and 
(zk,y)max(x,zk), D4 = D3.  Thus, by 6.2.1 min(D4) ∩ (max(x,zk) ∪ {(zk,y)}) is 
empty, and by 6.2.2 min(D4) ∩ max(x,y) is not empty.  Thus max(x,zk) ∪ {(zk,y)
exceeds max(x,y).  But since both max(x,zk) ∪ {(zk,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, (zk,y) precedes (y,z1).  By 5.2 and 6.2, (x,z1) precedes (zk,x).  
Thus, by the definition of precedence both of the following conditions must hold:  
        (7.1)  #R(zk,y) > #R(y,z1) or [ #R(zk,y) = #R(y,z1) and #R(z1,y) ≥ #R(y,zk)]. 
        (7.2)  #R(x,z1) > #R(zk,x) or [ #R(x,z1) = #R(zk,x) and #R(x,zk) ≥ #R(z1,x)]. 
By 7.1 and 1.1, the following holds:  
        (8)  #R(zk,x) ≥ #R(zk,y) ≥ #R(y,z1).  
By 7.2 and 1.2, the following holds: 
        (9)  #R(y,z1) ≥ #R(x,z1) ≥ #R(zk,x).  
Together, 8 and 9 imply the following holds: 
        (10)  #R(zk,x) = #R(zk,y) = #R(y,z1) = #R(x,z1). 
By 10, 7.1 and 1.1, the following holds:  
        (11)  #R(z1,x) ≥ #R(z1,y) ≥ #R(y,zk).  
By 10, 7.2 and 1.2, the following holds:  
        (12)  #R(y,zk) ≥ #R(x,zk) ≥ #R(z1,x).  
Together, 11 and 12 imply the following holds: 
        (13)  #R(z1,x) = #R(z1,y) = #R(y,zk) = #R(x,zk). 
By 10 and 13, the four majorities (x,z1), (y,z1), (zk,x) and (zk,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 (zk,y) precedes (y,z1), by 10 and 13 and the definition of precedence  
RVH must rank z1 over y.  Since (x,z1) precedes (zk,x), by 10 and 13 and 
the definition of precedence RVH must rank x over z1.  Since RVH ranks 
x over z1 and z1 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 σ was picked arbitrarily, this implies 
(y,x)Affirmed(A,R,σ) for all σ ∈ 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 (z1,z2),(z2,z3,),...,(zk-1,zk) ∈ Aff ∩ Precede(y,x
such that z1 = x and zk = y.  Thus (z1,z2),(z2,z3,),...,(zk-1,zk) ∈ Precede(y,x).  
By the definition of precedence, #R(zj,zj+1) ≥ #R(y,x) for all j ∈ {1,2,...,k-1}.  
Since #R(y,x) = n (the number of voters), it follows that #R(zj,zj+1) = n for 
all j ∈ {1,2,...,k-1}.  Thus z1Pz2 and z2Pz3 and ... and zk-1Pzk.  Since P is 
transitive, z1Pzk.  But since z1 = x and zk = 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