"Maximize Affirmed Majorities" (MAM) is resolvable and reasonably deterministic.

Revised:  December 31, 2002

Resolvability:  For all collections of votes for which two or more alternatives 
have a chance of being elected, there must exist some admissible vote such that, 
if this vote were added to the collection of votes, one alternative would be elected 
with certainty and the rest defeated with certainty.  In particular, the one which 
would be elected with certainty with this vote added must be one of those having 
a non-zero chance of being elected without this vote added.

Reasonable Determinism:  For all collections of votes such that no alternatives 
tie pairwise and no majorities are the same size, there must exist an alternative 
which is elected with certainty.

These two criteria are closely related, satisfaction implying the voting rule will usually 
leave nothing to chance when electing the winner.  Compliance with these criteria 
means that in large public elections the outcome will nearly always be deterministic.  

It would be undesirable to require complete determinism in all scenarios.  That would 
require sacrificing either neutrality of the alternatives or anonymity of the voters.  
To illustrate this, suppose there are two alternatives x and y, and half of the voters 
rank x over y and the other half rank y over x.  Neutrality requires neither x nor y  
be privileged over the other, and anonymity requires no voter be privileged over 
any other voters.  Therefore in this example both alternatives must be given an equal 
chance (½) of being elected.  (If one of the alternatives is "continue the status quo," 
it would be reasonable to violate neutrality by privileging the status quo for the sake 
of stability, rather than resort to chance when breaking a tie.)  If the number of voters 
is large, it is unlikely that exactly half will rank x over y (or y over x).  What matters 
more is that the voting rule be deterministic in more likely scenarios, which raises 
the question of how to express such a criterion. 

Resolvability is more widely recognized than reasonable determinism by the political 
science community as a desirable criterion.  Reasonable determinism is tailored in 
favor of "pairwise" voting procedures such as MAM, Simpson, Copeland, etc. (but 
not Borda nor Instant Runoff) and thus should only be used when comparing pairwise 
election procedures.  Reasonable determinism is mentioned here because MAM 
complies, in case anyone wonders and because understanding the proof (provided 
elsewhere) may augment one's understanding of MAM.

Two examples illustrate resolvability and reasonable determinism:

Example 1:  Suppose there are 3 alternatives x, y and z.  Suppose there are 15 voters 
who rank the alternatives as follows:

It can be seen that a majority (9 voters) rank y over z, and a majority (10 voters) rank x 
over y, and a majority (11 voters) rank z over x.  Thus no two majorities are the same size 
and no two alternatives are tied pairwise, so reasonable determinism demands that the 
voting procedure elect one of the alternatives with certainty.  Consider the Copeland 
procedure, which awards each alternative a point for each pairing it wins plus a half point 
for each pairing it ties, and then chooses the alternative(s) having the highest score. (This 
is the same procedure used to rank teams in many professional sports, such as baseball.)  
In this example, Copeland awards each alternative 1 point. (For instance, since a majority 
ranked x over y and a majority ranked z over x, x wins the "x versus y" pairing and loses 
the "x versus z" pairing; thus x has a score of 1 + 0 = 1.)  Therefore Copeland chooses 
all three alternatives, proving Copeland does not satisfy reasonable determinism.  
It can also be checked that there is no admissible vote (a ranking of the alternatives) 
which, if added to the 15 votes, would affect the three Copeland scores.  Thus 
Copeland also does not satisfy resolvability.

Example 2:  (Illustrates satisfaction of resolvability)  Suppose there are 3 alternatives 
x, y and z.  Suppose there are 14 voters who rank the alternatives as follows:

It can be seen that a majority (9 voters) rank y over z, and a majority (9 voters) rank x 
over y, and a majority (10 voters) rank z over x.  Consider the operation of MAM in 
this example:  Only two of the three majorities can be affirmed since the three together 
are not internally consistent. (In other words, they cycle.)  First MAM affirms "z over x" 
since it has the largest majority.  Since both of the other majorities are the same size, 
the one given greater precedence by MAM depends on a tiebreaking strict ranking 
constructed using the Random Voter Hierarchy procedure.  Thus there is a 4/14 
chance that the tiebreaking ranking will be "x over y over z" and a 5/14 chance that 
the tiebreaking ranking will be "y over z over x" and a 5/14 chance that the tiebreaking 
ranking will be "z over x over y."  The loser of the "y over z" majority is z, and the loser 
of the "x over y" majority is y.  Since there is a 9/14 chance that the tiebreaking ranking 
ranks y over z, there is a 9/14 chance that MAM gives greater precedence to "y over z" 
than to "x over y."  Thus "x over y" has a 9/14 chance of not being affirmed, and "y over z" 
has a 5/14 chance of not being affirmed.  Thus there is a 9/14 chance that MAM elects y  
and a 5/14 chance that MAM elects z.  There is no alternative that MAM elect with 
certainty.  Now suppose one extra vote that ranks "z over x over y" were added to the 
14 votes.  Then, as in example 1, there would be a majority of 9 who rank y over z, 
and a majority of 10 who rank x over y, and a majority of 11 who rank z over x.  This 
means MAM would affirm "z over x" and then affirm "x over y" and would not affirm 
"y over z."  Thus, if that vote were added, MAM would elect z with certainty and 
would defeat x and y with certainty.  

Theorem "MAM is resolvable."  We provide two proofs; the second demonstrates 
MAM₂ is resolvable and relies on theorem "MAM₂ = MAM".  Refer to the definitions 
in the document defining MAM.  

Proof #1 that MAM is resolvable:  Assume no alternative in A is elected with certainty 
by MAM given the votes R.  By theorem "At Least One Top" and inspection of the 
definition of MAM, at least one alternative always has a non-zero chance of being 
elected by MAM.  Relabel the alternatives if necessary so that x denotes an alternative 
that has a non-zero chance of being elected by MAM given R.  This means there exists 
σ ∈ L(R,A) such that MAM(A,R,σ) = x.  We must show there exists an admissible 
vote r such that MAM chooses x with certainty and defeats all other alternatives with 
certainty given R+r.  Make the following abbreviations:

Maj = Majorities(A,R). 
For all (a,b) ∈ Pairs(A), let Precede(a,b) denote Precede(a,b,A,R,σ).
Aff = Affirmed(A,R,σ). 
Top = Top(A,R,σ). 
MAM = MAM(A,R,σ). 

Let r = R_social(A,R,σ).   By theorem "Properties of RSocial (1)", r is a strict ranking 
of A. (That is, r ∈ L(A).)  This implies r ∈ O(A) (an ordering of A), so r is an admissible 
vote.  By theorem "Properties of R_Social (3)" the following statement must hold:

(1.1)  For all (a,b) ∈ Aff, r ranks a over b. 

Let P_r denote {(a,b) ∈ Pairs(A) such that r ranks a over b}.  (In words, the ordered 
pairs that "agree" with r.)  Since r is a strict ranking, P_r must be internally consistent.  
By 1.1, Aff ⊆ P_r.  

Abbreviate R' = R+r and Maj' = Majorities(A,R').  Pick any σ' ∈ L(R',A). 
Make the following abbreviations: 

For all (a,b) ∈ Pairs(A), let Precede'(a,b) denote Precede(a,b,A,R',σ').
Aff' = Affirmed(A,R',σ'). 
Top' = Top(A,R',σ').  
MAM' = MAM(A,R',σ').  

We aim to show MAM(A,R',σ') = x.  To facilitate this we first establish 
the following four propositions:

Proposition 1.2:  Aff' ⊆ P_r.  
Proposition 1.3:  Aff ⊆ Maj'.
Proposition 1.4:  Aff ⊆ Aff'.  
Proposition 1.5:  x ∈ Top'.
Proposition 1.6:  For all y ∈ A\{x}, y ∉ Top'.  

Proof of 1.2:  Suppose the contrary.  This means Aff'\P_r is not empty.  By theorem 
"Precedence is a Strict Ordering" we can pick (a,b) ∈ Aff'\P_r such that no pair 
in Aff'\P_r precedes (a,b) given (R',σ').  Since (a,b) ∈ Aff', (a,b) ∈ Maj'.  Since 
(a,b) ∉ P_r, r does not rank a over b.  Since r is a strict ranking, r ranks b over a.  
Thus #R'(a,b) = #R(a,b) and #R'(b,a) = #R(b,a) + 1.  This implies (a,b) ∈ Maj.  
Since (a,b) ∉ P_r and Aff ⊆ P_r, (a,b) ∉ Aff.  Since (a,b) ∈ Maj\Aff, (a,b) must 
be inconsistent with Aff ∩ Precede(a,b).  Since (a,b) ∈ Aff', there must exist 
(c,d) ∈ Aff ∩ Precede(a,b) such that (c,d) ∉ Aff' ∩ Precede'(a,b).  Since 
(c,d) ∈ Aff, by the definition of Affirmed() (c,d) ∈ Maj.  Since (c,d) ∈ Aff and 
Aff ⊆ P_r, (c,d) ∈ P_r.  This means r ranks c over d.  Thus #R'(c,d) = #R(c,d) + 1 
and #R'(d,c) = #R(d,c).  Thus (c,d) ∈ Maj'.  Since (c,d) ∈ Precede(a,b), 
#R(c,d) ≥ #R(a,b).  Thus #R'(c,d) > #R'(a,b), implying (c,d) ∈ Precede'(a,b).  
Since (c,d) ∈ Maj'\Aff', (c,d) must be inconsistent with Aff' ∩ Precede'(c,d).  
Since (c,d) ∈ P_r and P_r is internally consistent, (c,d) is consistent with P_r.  
Since (c,d) is consistent with P_r but not with Aff' ∩ Precede'(c,d), there must 
exist (e,f) ∈ Aff' ∩ Precede'(c,d) such that (e,f) ∉ P_r.  This means (e,f) ∈ Aff'\P_r 
and (e,f) ∈ Precede'(c,d).  Since (e,f) ∈ Precede'(c,d) and (c,d) ∈ Precede'(a,b), 
by theorem "Precedence is a Strict Ordering" (e,f) ∈ Precede'(a,b).  Since 
(e,f) ∈ Aff'\P_r and (e,f) ∈ Precede'(a,b), this means there exists a pair in Aff'\P_r  
that precedes (a,b) given (R',σ').  But this contradicts the definition of (a,b), 
so the contrary assumption cannot hold, establishing 1.2.     QED 

Proof of 1.3:  Pick any (a,b) ∈ Aff.  We must show (a,b) ∈ Maj'.  By the 
definition of Affirmed(), (a,b) ∈ Maj.  This means #R(a,b) > #R(b,a).  
By 1.1, (a,b) ∈ P_r.  Thus r ranks a over b.  Thus #R'(a,b) = #R(a,b) + 1 
and #R'(b,a) = #R(b,a).  It follows that #R'(a,b) > #R'(b,a), so (a,b) ∈ Maj'.  
Thus 1.3 has been established.   QED 

Proof of 1.4:  Since Aff ⊆ P_r and P_r is internally consistent, every pair in Aff is 
consistent with P_r.  By 1.2 Aff' ⊆ P_r, so every pair in Aff is consistent with Aff'.  
By 1.3, Aff ⊆ Maj'.  Since every pair in Aff is in Maj' and every pair in Aff is 
consistent with Aff', it follows by the definition of Affirmed() that Aff ⊆ Aff'.  
Thus 1.4 has been established.     QED 

Proof of 1.5:  Since x tops r, P_r contains no pair in which x is second.  Thus, 
by 1.2 Aff' contains no pair in which x is second.  It follows by the definition 
of Top() that x ∈ Top'.  Thus 1.5 has been established.     QED 

Proof of 1.6:  Assume y ∈ A\{x}.  There are two cases to consider:

Case 1.6.1:  y ∈ Top.  By the definition of R_social(), MAM = x.  Thus, 
by the definition of MAM x ∈ Top.   Since {x,y} ⊆ Top, by theorem 
"MAM is Reasonably Deterministic (1)" #R(x,y) = #R(y,x).  Since x 
tops r, #R'(x,y) = #R'(y,x) + 1.  By 1.5, x ∈ Top'.  Since x ∈ Top'  
and #R'(x,y) ≠ #R'(y,x), by theorem "MAM is Reasonably Deterministic 
(1)" y ∉ Top'.  

Case 1.6.2:  y ∉ Top.  By the definition of Top(), there exists a ∈ A  
such that (a,y) ∈ Aff.  By 1.4 (a,y) ∈ Aff'.  Therefore y ∉ Top'.

Since y ∉ Top' in both cases, 1.6 has been established.     QED 

By 1.4 and 1.5, Top' = {x}.  Thus MAM' = x.  Since σ' was picked arbitrarily from 
L(R',A), it follows that MAM(A,R',σ') = x for all σ' ∈ O(R',A).  This implies MAM 
elect x with certainty and defeats all other alternatives with certainty given R+r.  
Thus MAM is resolvable.    QED

Proof #2 that MAM is resolvable:  We rely on theorem "MAM₂ = MAM" and 
show that MAM₂ is resolvable.  Assume x has a non-zero chance of being elected 
by MAM₂.  This means there exists σ ∈ L(R,A) and r ∈ L(A) topped by x such 
that r ∈ UndominatedRankings(A,R,σ).  Since r is an ordering of A, r is an 
admissible vote.  We will show UndominatedRankings(A,R+r,σ') = {r} for 
all σ' ∈ L(R+r,A), after which it will follow easily that MAM₂ elects x with certainty 
and defeats all other alternatives with certainty given R+r.  Abbreviate R' = R+r.  
Clearly both of the following statements hold:

(2.1)  #R'(a,b) = 1 + #R(a,b) for all a,b ∈ A such that r ranks a over b.  
(2.2)  #R'(a,b) = #R(a,b) for all a,b ∈ A such that r does not rank a over b.  

Pick any σ' ∈ O(R',A) and any r' ∈ L(A) distinct from r.  We aim to show 
that r dominates r' given (R',σ').  Make the following abbreviations: 

Agreed(r) = Agreed(r,A,R). 
Agreed(r') = Agreed(r',A,R). 
Agreed'(r) = Agreed(r,A,R'). 
Agreed'(r') = Agreed(r',A,R'). 
Distinct = DistinctAgreed(r,r',A,R). 
Distinct' = DistinctAgreed(r,r',A,R'). 
LDA = LargestDistinctAgreed(r,r',A,R,σ).          (if Distinct ≠ φ)
LDA' = LargestDistinctAgreed(r,r',A,R',σ').       (if Distinct' ≠ φ)
Undom = UndominatedRankings(A,R,σ). 
Undom' = UndominatedRankings(A,R',σ'). 

Since r ∈ Undom, the following statement must hold:

(2.3)  If Distinct ≠ φ, then LDA ∈ Distinct ∩ Agreed(r).  

Since r and r' are distinct strict rankings of A, the following statement must hold: 

(2.4)  There exist a,b ∈ A such that r ranks a over b and r' does not rank a over b.  

By 2.1 and 2.2, both of the following statements must hold:

(2.5)  #R'(a,b) = 1 + #R(a,b) for all a,b ∈ A such that r ranks a over b and r' does not. 
(2.6)  #R'(a,b)  = #R(a,b) for all a,b ∈ A such that r' ranks a over b and r does not.  

By 2.3, 2.5 and 2.6, both of the following statements must hold:

(2.7)  If Distinct ≠ φ, then LDA ∈ Distinct' ∩ Agreed'(r). 
(2.8)  Distinct' ∩ Agreed'(r')  ⊆  Distinct ∩ Agreed(r').  

Since r ∈ Undom, r' does not dominate r given (R,σ).  There are two cases to consider: 

Case 2.9:  r does not dominate r' given (R,σ).  Since neither dominates the other 
given (R,σ), Distinct must be empty.  This implies #R(a,b) = #R(b,a) 
for all a,b ∈ A such that r and r' disagree on the relative ranking of a and b.  
By 2.5 and 2.6, both of the following statements must hold: 
        (2.9.1)  For all a,b ∈ A such that r ranks a over b  
                     and r' does not rank a over b, #R'(a,b) = #R'(b,a) + 1. 
        (2.9.2)  For all a,b ∈ A such that r' ranks a over b  
                     and r does not rank a over b, #R'(a,b) = #R'(b,a) - 1. 
By 2.9.1 and 2.9.2, both of the following statements must hold: 
        (2.9.3)  For all a,b ∈ A such that r ranks a over b  
                     and r' does not rank a over b, (a,b) ∈ Distinct' ∩ Agreed'(r). 
        (2.9.4)  For all a,b ∈ A such that r' ranks a over b  
                     and r does not rank a over b, (a,b) ∉ Maj'.  
By 2.4, 2.9.3 and 2.9.4, Distinct' ≠ φ and Distinct' ⊆ Agreed'(r).  
This implies LDA' ∈ Agreed'(r).  Thus r dominates r' given (R',σ') in case 2.9.

Case 2.10:  r dominates r' given (R,σ).  This implies Distinct ≠ φ and 
LDA ∈ Agreed(r).  By 2.1 and 2.2, LDA is larger than (a,b) given R'  
for all (a,b) ∈ Distinct ∩ Agreed(r').  By 2.8, LDA is larger than (a,b)  
given R' for all (a,b) ∈ Distinct' ∩ Agreed'(r').  By 2.7, LDA' ∈ Agreed'(r).  
Thus r dominates r' given (R',σ') in case 2.10.

Since r dominates r' given (R',σ') in both cases and since r' was any ranking 
distinct from r, Undom' = {r}.  Since σ'  also was picked arbitrarily, this implies 
UndominatedRankings(A,R',σ') = {r} for all σ' ∈ L(R',A).  Since x tops r, 
MAM₂ elects x with certainty and defeats all other alternatives with certainty 
given R'.  Thus MAM₂ is resolvable.  By theorem "MAM₂ = MAM", 
MAM is resolvable.     QED