Immunity from Majority Complaints:  a criterion for voting rules   (DRAFT)

Steve Eppley <seppley@alumni.caltech.edu>

Revised:  November 2, 2008

Abstract

This paper presents a strong criterion, immunity from majority complaints (IMC), 
that is failed by most voting procedures.  Satisfaction of IMC allows an easy rebuttal 
on behalf of the chosen alternative when a majority of the voters claim they prefer 
another alternative (which they may do no matter what voting procedure is used).  
Furthermore, it is shown that IMC is nearly a characterization of the Maximize 
Affirmed Majorities procedure (MAM).  (Elsewhere it is shown that MAM also 
satisfies many other desirable criteria, including Condorcet-consistency, top cycle
strong Pareto, monotonicity, anonymityneutralityresolvability, independence 
of clone alternatives
, local independence of irrelevant alternatives, minimal 
defense
 and truncation resistance.)

Condorcet's Paradox tells us that when a society elects one alternative from three or more, 
no matter what voting procedure is used it is possible a majority of the voters will prefer a 
losing alternative over the elected alternative, as in the following scenario: 

Scenario 1:  9 voters rank three alternatives {a,b,c}:

4 3 2
a b c
b c a
c a b

 

The table shows each voter's order of preference:  4 voters prefer a over b over c,  
3 prefer b over c over a, and 2 prefer c over a over b.  Thus a majority (6 voters) 
prefer a over b, a majority (7 voters) prefer b over c, and a majority (5 voters) 
prefer c over a.  Therefore, for every alternative some other alternative is preferred 
by a majority. 

Even voting procedures that do not permit voters to completely express their orders of 
preference, such as "Vote for One, Plurality Rule" and "Approval" (which lets each voter 
select as many candidates as desired and elects the one selected by the most voters), 
are not immune from this phenomenon since it is determined by the voters' underlying 
preferences, not by votes.  Unofficial polling may establish the existence of a majority 
preference for a losing alternative.  

A majority who prefer a losing alternative over the elected alternative might complain 
that "democratic majority rule" has somehow been violated.  When will this be trouble 
for society?  That may depend on the voting procedure.  For instance, in the scenario 
above, if the procedure socially orders the alternatives as "a over b over c" then the 
five voters who voted c over a may complain a majority voted for c over the winner.  
However, in this case they can be easily rebutted by turning their own argument against 
them, specifically by showing a larger majority (7 voters) rank b over c and a larger 
majority (6 voters) rank a over b.  If on the other hand the procedure does not 
elect a or does not find the social ordering to be "a over b over c" then it may be 
harder to rebut the complainers' argument:  

If b is elected, the 6 voters who prefer a over b cannot be easily rebutted 
since the only majority who prefer something over a is smaller.

If c is elected, the 7 voters who prefer b over c cannot be easily rebutted 
since the only majority who prefer something over b is smaller.  

If the voting procedure socially orders the alternatives as "a over c over b
then the rebuttal involving "b over c" and "a over b" is inconsistent with the 
social ordering, which undermines the voting procedure and the election of a.  

Even if the voting procedure elects a and does not socially order the alternatives, 
it may be hard to rebut the complainers if there exists a natural way to extend the 
procedure to produce a social ordering that differs from "a over b over c."  
This is a matter of consistency:  If the principles that allow the voting procedure 
to find the elected alternative "better" than any other alternative cannot also be used 
to find which of any pair of alternatives is "better" than the other, this incompleteness 
of the "better" relation may suggest to many people that something is amiss with the 
procedure's principles, which in turn may undermine confidence in the procedure.  
Furthermore, it is always possible to unofficially construct a social ordering in 
some way that is "natural" for the voting procedure.  For instance, the following 
six techniques are fairly obvious: 

1. For procedures that compute a score for each alternative and elect the one 
    with the best score, it is natural to order the alternatives from best score to 
    worst score.  

2. For procedures that eliminate alternatives one at a time, it is natural to 
    order the alternatives in the reverse of the elimination order.  

3. For procedures that compute a transitive binary relation on the alternatives, 
    it is natural to use that relation (or possibly its reverse) as the social ordering.  

4. For procedures that distinguish an acyclic subset of the pairwise majorities, 
    it is natural to construct a social ordering consistent with the acyclic subset.  

5. For procedures that rank the possible social orderings and elect the 
    alternative atop the highest-ranked ordering, it is natural to take 
    that highest-ranked ordering as the social ordering.  

6. In general, given any procedure that elects one alternative, one can always 
    construct a social ordering by iteratively deleting the elected alternative from 
    the votes and computing which of the remaining alternatives would be elected, 
    repeating until no alternatives remain, and taking that election order as the 
    social order.

If the complainers construct a social ordering using a technique that appears natural 
for the voting procedure and show that the rebuttal sequence is inconsistent with that 
natural ordering, the force of the rebuttal could be undermined.

Complaints by a losing majority that are hard to rebut could undermine the winner's 
mandate, and could undermine confidence in the voting procedure, particularly if there 
exists another procedure that satisfies the criteria the people consider important, 
would have elected the alternative favored by the complainers, and over the long run 
would elect alternatives preferred by more voters.  We consider it desirable to be 
able to easily turn the complainers' argument against them since we do not expect 
people to entirely agree about the relative importance of the criteria used to select the 
voting procedure (and there would certainly be an incentive for cheap talk favoring 
some other voting procedure in such scenarios).  Turning their argument against them 
seems a straight-forward way to win the debate.  With these considerations in mind 
we formally define the criterion immunity from majority complaints (IMC):

Let A denote a finite non-empty set of alternatives from which one must be elected.  

Let R denote a collection of votes, one per voter.

For all x,yA, let V(x,y) denote the number of votes in R that rank x over y.  

For all non-empty BA, let Pairs(B) denote the set of all possible ordered pairs 
        of alternatives
in B. (That is, Pairs(B) is the set {(x,y) such that x,yB}.)

For all (x,y),(z,w)Pairs(A), call (x,y) the same size as (z,w) if and only if 
        V(x,y) = V(z,w) and V(y,x) = V(w,z).  
For all (x,y),(z,w)Pairs(A), call (x,y) larger than (z,w) if and only if 
        V(x,y) > V(z,w) or [V(x,y) = V(z,w) and V(y,x) < V(w,z)].  
For all (x,y),(z,w)Pairs(A), call (x,y) at least as large as (z,w)  
        if and only if (x,y) is the same size as (z,w) or (x,y) is larger than (z,w).

Immunity from majority complaints (IMC):  The voting procedure must let 
each voter vote any ordering of the alternatives, must socially order the alternatives, 
must elect a single alternative that is not socially ordered below any alternative, 
and for all x,yA such that [V(x,y) > V(y,x) and x is not socially ordered over y
there must exist a sequence of alternatives a1,a2,...,akA such that a1 = y and 
ak = x and all three of the following conditions hold: 

(1)  (aj,aj+1) is at least as large as (x,y) for all j ∈ {1,2,...,k-1}.  
(2)  V(aj,aj+1) > V(aj+1,aj) for all j ∈ {1,2,...,k-1}.
(3)  aj is socially ordered over aj+1 for all j ∈ {1,2,...,k-1}.

IMC can be decomposed into several criteria.  Letting each vote be any ordering is a 
universal domain criterion which should allow the votes to trump any unofficial poll 
of the voters' preferences that might be proffered by a complaining majority. (Thus 
procedures such as Approval and "Vote for only one, Plurality Rule" are disqualified.)  
Requiring a single alternative be elected is the resoluteness criterion, required by the 
innate mutual exclusivity of the alternatives.  Requiring existence of a majority sequence 
"a1 over a2," "a2 over a3," ..., and "ak-1 over ak" that are each at least as large as the 
majority who may complain ak should have finished over a1 (indicated by conditions 1 
and 2) enables the complainers' "majority rule" argument to be easily rebutted by turning 
it against them.  Requiring the procedure to socially order the alternatives rather than 
merely elect one strengthens the force of the "rebuttal sequence" when condition 3 holds 
and undermines it if condition 3 is not met.  Requiring the elected alternative to be one 
that tops the social ordering is a basic consistency criterion; voters would lack confidence 
in the voting procedure if the elected alternative were socially ordered below another.  

We next present a criterion that is less demanding than IMC in one sense and more 
demanding in another: 

Immunity from majority complaints #2 (IMC2):  The voting procedure must 
let each voter vote any ordering of the alternatives, must elect a single alternative 
(denoted w), must socially order the alternatives in a "natural" way (i.e., consistent 
with the manner in which w is elected), and for all xA such that V(x,w) > V(w,x
there must exist a sequence of alternatives a1,a2,...,akA such that a1 = w and 
ak = x and all three of the following conditions hold: 

1.  (aj,aj+1) is at least as large as (x,w) for all j ∈ {1,2,...,k-1}.  
2.  V(aj,aj+1) > V(aj+1,aj) for all j ∈ {1,2,...,k-1}.
3.  aj is socially ordered over aj+1 for all j ∈ {1,2,...,k-1}.

IMC2 is less demanding than IMC in the sense that it only requires a rebuttal sequence 
against a majority who vote any losing alternative x over the elected alternative w
whereas IMC requires a rebuttal sequence against any majority who vote any x over 
any y socially ordered over or equal to xIMC2 is more demanding than IMC in that 
IMC2 explicitly requires the social ordering be "natural," consistent with the manner in 
which the elected alternative is elected, such as one of the six techniques listed above.  
This is to prevent inconsistency from undermining the force of the rebuttal sequence, 
as discussed above.  Unfortunately a rigorous definition of "natural" seems elusive; 
it would be bold and possibly short-sighted to explicitly require one of the six listed 
techniques.  This lack of rigor in the specification of a "natural" social ordering is 
problematic, but it is hoped the meaning is sufficiently clear for consensus to be 
reached regarding whether some particular voting procedure satisfies IMC2.  

IMC2 could be further strengthened by requiring agreement by all social orderings that 
seem natural for the voting procedure.  For instance, if the procedure computes a score 
for each alternative and elects the one with the best score (such as Borda and Minimax), 
both techniques 1 and 6 are natural.  Requiring agreement by all natural social orderings 
would rule out the possibility that a complaining majority could unofficially construct a 
natural ordering that disagrees with the official social ordering and thereby start an 
argument that could undermine the voting procedure and the mandate of the winner.  
Call this stronger criterion IMC2a.

Ideally, rather than being able to show each majority in a rebuttal sequence is at least 
as large as the complaining majority (condition 1 in IMC and in IMC2), we would like 
to always be able to show each is larger.  The following example shows this ideal will 
sometimes be too much to expect:

Scenario 2:  3 voters rank three alternatives {a,b,c}:

1 1 1
a b c
b c a
c a b

 

The cycle in scenario 2 is perfectly symmetric.  Without loss of generality, assume a is 
elected (perhaps by drawing straws).  A majority (2 voters) rank c over a and no majority 
is larger than 2 voters.  Thus the most we can expect from a rebutting sequence of majorities 
from a to c is that the rebutting majorities be at least as large as the majority  who voted c  
over a.  It is too much to demand the rebutting sequence be comprised of larger majorities 
in such "symmetric" scenarios; however we consider it sufficient to turn the complainers' 
argument against them when each of the rebutting majorities is at least as large.  In large 
public elections, the ideal would usually be satisfied (assuming IMC and IMC2 are 
satisfied) since the likelihood that two majorities will be the same size decreases as 
the number of voters increases. 

Presuming that the attention of the media and the voters tends to focus mostly on the top 
two alternatives, the lack of an easy rebuttal against a complaining majority who favor the 
"second" alternative over the elected alternative would seem to make such a failure more 
egregious.  We next present a criterion that expresses this idea:  

Immunity from second-place complaints (I2C):  The voting procedure must 
allow each voter to vote any ordering of the alternatives, must elect a single 
alternative (denoted w), and, letting x denote the alternative that would be 
elected if w were dropped from the votes, V(x,w) must not exceed V(w,x).

I2C is more demanding than IMC2 in the sense that I2C implicitly uses technique 6 to 
determine which alternative is second in the social ordering (defining the second alternative 
as the one that would be elected if the elected alternative were deleted).  I2C is less 
demanding in the sense that the voting procedure is not required to socially order the 
alternatives.  And I2C is less demanding in the sense that it focuses only on the top two 
alternatives: clearly there could be no rebuttal sequence if a majority prefer the second 
alternative over the elected alternative, so the second alternative must not be ranked 
over the elected alternative by a majority.  

Appendix A provides examples showing failures of IMC, IMC2 and I2C by widely-
known voting procedures: Plurality Rule, Majority Runoff, Instant Runoff, Borda, Nanson, 
Copeland, Minimax, Maximin, Simpson-Kramer, TopCycle/Minimax, TopCycle/Maximin, 
Kemeny-Young, Tideman's "Ranked Pairs," Tideman-Zavist and PathWinner.

We will prove there exists a voting procedure ("Maximize Affirmed Majorities," or MAM) 
that can be quickly computed and satisfies IMC, IMC2, IMC2a and I2C, and will prove 
that all social orderings natural to MAM (techniques 4, 5 and 6) agree.  We will also show 
that satisfaction of IMC implies satisfaction of many other desirable criteria.  We state the 
important theorems next, with most proofs provided in Appendix B. (The remaining proofs 
are provided in separate documents about MAM.) 

Theorem 1:  There is always at least one social ordering capable of satisfying IMC.

Theorem 2:  Satisfaction of IMC implies satisfaction of Condorcet-consistency
top cycle
weak Pareto, resolvability, minimal defense and truncation resistance

(Note that any voting procedure that satisfies resolvability is usually deterministic.  
This implies IMC is nearly a complete characterization of the voting procedures that 
satisfy it, and implies that in elections having many voters the outcome would rarely 
depend on chance if the voting procedure satisfies IMC.) 

Theorem 3:  Say no pairings are tied if and only if V(x,y) ≠ V(y,x) for all distinct 
x,yA.  Say every cycle has only one smallest majority if and only if, for all 
sequences of alternatives a1,a2,...,akA such that [a1 = ak and a1,a2,...,ak-1 are 
distinct and V(aj,aj+1) > V(aj+1,aj) for all j ∈ {1,2,...,k-1}], there exists a unique 
h ∈ {1,2,...,k-1} such that (aj,aj+1) is larger than (ah,ah+1) for all j ∈ {1,2,...,k-1} 
distinct from h.  If no pairings are tied and every cycle has only one smallest majority, 
then only one social ordering is capable of satisfying IMC

(Theorem 3 implies that in elections having many voters the outcome would rarely depend 
on chance if the voting procedure satisfies IMC.)

Theorem 4:  In the (large) subdomain domain of votes where only one social 
ordering is capable of satisfying IMC, satisfaction of IMC implies satisfaction 
of strong Paretomonotonicity, anonymityneutralityhomogeneity
local independence of irrelevant alternatives
and independence of clone 
alternatives

Theorem 5:  The MAM voting procedure satisfies IMC, IMC2, IMC2a and I2C
and all social orderings natural to MAM (techniques 4, 5 and 6 listed above) agree. 

(Note that it follows by theorem 2 that MAM also satisfies Condorcet-consistency
top cycle
weak Pareto, resolvability, minimal defense and truncation resistance.  
Elsewhere we prove that MAM completely satisfies strong Pareto, monotonicity
anonymityneutrality, homogeneity, local independence of irrelevant alternatives 
and independence of clone alternatives, and can be computed in a time that in the 
worst case is a small polynomial function of the number of voters and the number 
of alternatives.)  

Theorem 6:  Let O(A) denote the set of all possible orderings of the alternatives A.  
For all rO(A) and all (x,y)Pairs(A), call (x,y) a majority thwarted by r  
if and only if V(x,y) > V(y,x) and r does not order x over y.  If IMC is satisfied 
and the social ordering thwarts at least one majority, then, for all rO(A), 
at least one majority is thwarted by r and the largest majority thwarted by r  
is at least as large as the largest majority thwarted by the social ordering. 
(In other words, satisfaction of IMC implies minimizing the largest thwarted 
majority.  Thus another plausible name for the "Maximize Affirmed Majorities" 
procedure would be "Minimize Thwarted Majorities.")

Conclusions

 

Appendix A - Examples showing most voting procedures fail IMC, IMC2 and I2C

Many prominent voting procedures fail IMC, IMC2 and I2C.  The examples that follow 
show failures by Plurality Rule, Majority Runoff, Instant Runoff, Borda, Nanson, Copeland, 
Minimax, Maximin, Simpson-Kramer, TopCycle/Minimax, TopCycle/Maximin, Kemeny-
Young, Tideman's "Ranked Pairs," Tideman-Zavist and PathWinner. (Note that Kemeny-
Young, Tideman and Tideman-Zavist satisfy I2C.)

We constructed the examples where possible so all votes are strict orderings of the 
alternatives, to avoid critiques that non-strict orderings are implausible and that the 
implementation could easily prevent voters from voting non-strict orderings.  Showing 
failures by Tideman and Tideman-Zavist requires some votes to be non-strict orderings.  
This is discussed more extensively below.  

We constructed all examples to have an odd number of voters, since it is common for 
committees to have an odd number of members to reduce the frequency of tie votes.  

We constructed all examples to be deterministic.  Some voting procedures are defined 
so that in some scenarios the winner is ambiguous, left to an unspecified tie-breaker 
(such as flipping a coin or drawing the short straw) or specifically depending on chance.  
The Copeland procedure in particular is "frequently" indeterminate (implied by its failure of 
the resolvability criterion).  Though proponents of Copeland may in practice recommend 
a specific tie-breaker, it seems simplest to show Copeland's failures without assuming 
specific knowledge of the tie-breaker, even though this means the example may need to 
involve more alternatives than needed to show failure with a specific tie-breaker. 

No voting procedure that can defeat a "Condorcet winner" (an alternative x such that, 
for all other alternatives y, more than half the voters prefer x over y) satisfies IMC or IMC2.  
Clearly, when x is a Condorcet winner and is not elected, there cannot be a sequence of 
majorities to rebut the complaint by the majority who prefer x over the elected alternative.  
Thus it would be easy to show that Plurality Rule, Majority Runoff, Instant Runoff and 
Borda fail IMC and IMC2.  We go a step further and construct examples for each that 
also show failures of I2C, and moreover in these examples the alternative used to show 
failure of I2C is a Condorcet winner that finishes second in a natural social ordering. 

Scenario A1:  Failures by Plurality Rule. 
9 voters rank three alternatives {a,w,x} as follows:

2 3 4
a x w
x a x
w w a

 

Plurality Rule ignores all but the top of each vote. (Typical implementations permit each 
voter to express only the top of his/her ranking.)  In scenario A1, since more votes are 
topped by w (4) than by any other alternative, Plurality Rule would elect w.  However, 
a majority (5 voters) rank x over w.  Since x is a Condorcet winner, no rebutting sequence 
can be constructed against the complaint that x should be elected, which means Plurality 
Rule fails IMC and IMC2.  Furthermore, x is second in both natural social orderings: 
x has the second-best score (3 votes), and x would be chosen if w were deleted from 
the votes.  Thus Plurality Rule also fails I2C.  

Scenario A2:  Failures by Majority Runoff and Instant Runoff. 
9 voters rank three alternatives {a,w,x} as follows:

3 2 4
a x w
x w x
w a a

 

To simplify the analysis of Majority Runoff, which in practice is implemented as two rounds 
of voting in which each voter selects one alternative, we define it as one round of voting in 
which each voter orders the alternatives. (Thus we neglect that voter turnout may differ in 
the second round or that preferences may change between rounds.)  Considering only the 
two alternatives that top the most votes, the one that is ranked over the other by more votes 
is elected.  In scenario A2, alternatives a and w are ranked top by the most voters, and 
since w is ranked over a by a majority, Majority Runoff elects w.  However, a majority 
(5 voters) rank x over w.  Since x is a Condorcet winner, no rebutting sequence can be 
constructed against the complaint that x should be elected, which means Majority Runoff 
fails IMC and IMC2.  Furthermore, one of the two natural techniques of constructing 
a social ordering will find x to be second in the social ordering, since x would be elected 
if w were deleted from the votes.  Thus Majority Runoff also fails I2C.  

Instant Runoff is similar to Majority Runoff.  It is an iterative elimination procedure that, 
in each iteration, counts each vote for its highest-ranked non-eliminated alternative and 
eliminates the alternative with the smallest count, repeating until one alternative remains.  
Thus in scenario A2 Instant Runoff elects the same as Majority Runoff, which means 
it too fails IMC, IMC2 and I2C.

Scenario A3:  Failures by Borda. 
5 voters rank three alternatives {a,w,x} as follows:

3 2
x w
w a
a x

 

The Borda procedure counts for each alternative a point from each vote for each alternative 
ranked below it.  In scenario A3, Borda counts 6 points for x (3×2 + 2×0), 7 points for w 
(3×1 + 2×2), and 2 points for a (3×0 + 2×1).  Thus Borda elects w.  However, a majority 
(3 voters) rank x over w.  Since x is a Condorcet winner, no rebutting sequence can be 
constructed against the complaint that x should be chosen, which means Borda fails IMC 
and IMC2.  Furthermore, x is second in both natural social orderings: x has the second-
best score (6 votes), and x would be elected if w were deleted from the votes.  Thus, 
Borda also fails I2C.  

Scenario A4a:  Failures by Nanson. 
13 voters rank four alternatives {a,b,w,x} as follows:

1 1 5 3 1 2
w w x a b b
a b w w w a
x a b x a x
b x a b x w

 

The Nanson procedure is an iterative elimination procedure based on the Borda procedure.  
In each iteration, Nanson recomputes the Borda score of each non-eliminated alternative 
(neglecting eliminated alternatives) and eliminates the one having the smallest score, 
repeating until only one alternative remains.  In scenario A4a, first b is eliminated 
since b has the smallest Borda score (16).  Next x is eliminated since x has the smallest 
Borda score (12; with b deleted before computing scores).  Then a is eliminated since a has 
the smallest Borda score (5; with b and x deleted before computing scores).  Thus Nanson 
elects w.  However, a majority (7 voters) rank x over w, and Nanson would elect x 
if w were dropped from the votes.  Thus Nanson fails I2C.  To show that Nanson also fails 
IMC and IMC2 in scenario A4a, we show the only social ordering capable of satisfying 
IMC or IMC2 is "x over w over b over a":  Clearly IMC (or IMC2) requires w must be 
socially ordered over b since no majority is as large as the majority (10 voters) who rank 
w over b.  Clearly IMC (or IMC2) requires x must be socially ordered over b since the 
majority who rank x over b (9 voters) is larger than the only majority who rank something 
over x (the 8 for a over x).  Clearly IMC (or IMC2) requires b must be socially ordered 
over a since the majority who rank b over a (9 voters) is larger than the only majority who 
rank a over something (the 8 for a over x).  Thus the social ordering must be one of these 
three: "x over w over b over a" or "x ~ w over b over a" or "w over x over b over a."  
Since a majority (7 voters) rank x over w, the last two orderings cannot satisfy IMC or 
IMC2.  Thus the only social ordering capable of satisfying IMC or IMC2 is "x over w 
over b over a" and it can be checked that this ordering indeed satisfies IMC and IMC2.  
It follow that IMC (or IMC2) requires x must be chosen, and thus Nanson fails IMC
IMC2 and I2C.  

Failure of IMC and IMC2 by Nanson can be shown with as few as three alternatives, 
as the following scenario illustrates:

Scenario A4b:  More failures of IMC and IMC2 by Nanson. 
15 voters rank three alternatives {a,w,x} as follows:

6 2 1 6
w x x a
a w a x
x a w w

 

In scenario A4b, first x is eliminated since it has the smallest Borda score (12).  Then a is 
eliminated since it has the smallest Borda score (7; with x deleted before computing scores).  
Thus Nanson elects w.  However, a majority (9 voters) rank x over w.  Since the majority 
who rank w over a is smaller than 9, no rebutting sequence can be constructed.  Thus 
Nanson can fail IMC and IMC2 with as few as three alternatives.  

Scenario A5a:  Failures by Copeland. 
15 voters rank eight alternatives {a,b,c,d,e,f,w,x} as follows:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
w w x x x x x x b c c d e f f
a b w w a f f f a b f a d d e
b a c c e w e e x a e x c b d
x x b d w e d d w x b w b x c
d e a e d c c c f f a e a c a
c d f b c d w b e e x c x w b
f c e f f b b w d d w b w a x
e f d a b a a a c w d f f e w

 

Copeland scores for each alternative the number of pairings in which the votes that rank 
it over its pairwise opponent exceed the votes that rank it below its pairwise opponent, 
and then chooses the alternative with the largest score. (Perhaps this procedure should be 
attributed to Ramon Lull, a 13th century monk who, according to historian Ian McLean, 
suggested electing the alternative with "the most votes in the most pairings."  McLean 
interpreted Lull's procedure as equivalent to the Borda procedure, but it seems plausible 
that Lull meant Copeland.)  In scenario A5a, Copeland computes these scores: 

w wins 6 pairings (over a,b,c,d,e,f). 
x wins 5 pairings (over c,d,e,f,w). 
a
wins 3 pairings (over e,f,x). 
b wins 3 pairings (over a,b,x). 
c wins 3 pairings (over a,b,f). 
d wins 3 pairings (over a,b,c). 
e wins 3 pairings (over b,c,d). 
f wins 2 pairings (over d,e). 

Thus Copeland elects w.  However, a majority (13 voters) rank x over w.  Since no 
other majority is as large as 13, no rebutting sequence can be constructed against the 
complaint that x should be elected, which means Copeland fails IMC and IMC2.  
Furthermore, x is second in both natural social orderings: x has the second-best score 
(5 won pairings), and x would be elected if w were deleted from the votes.  Thus, 
Copeland also fails I2C.  The example seems even more egregious since x is the only 
alternative whose largest opposing majority is as small as 8 voters and w is the only 
alternative whose largest opposing majority is as large as 13 voters.  

Failure of IMC and IMC2 by Copeland can be shown with fewer alternatives, as the 
following two scenarios illustrate:

Scenario A5b:  More failures by Copeland. 
9 voters rank five alternatives {a,b,c,w,x} as follows:

4 3 2
x b w
w c c
a a a
b x b
c w x

 

In scenario A5b, Copeland computes these scores: 

w wins 3 pairings (over a,b,c). 
a wins 2 pairings (over b,x). 
b wins 2 pairings (over c,x). 
c wins 2 pairings (over a,x). 
x wins 1 pairing (over w).  

Thus Copeland elects w.  However, a majority (7 voters) rank x over w.  Since the 
only other majority that is as large as 7 is the "b over c" majority, clearly no rebutting 
sequence can be constructed against the complaint that x should be elected, which again 
shows Copeland fails IMC and IMC2. (Unlike scenario A5a, x is not second in a social 
ordering that is natural for Copeland, so scenario A5b is not as egregious in that sense.) 
Given knowledge of the tie-breaker, we could probably show Copeland failures with 
examples involving only three alternatives.  For instance, suppose the tie-breaker were 
Plurality Rule, which we denote as Copeland/Plurality:

Scenario A5c:  Failures by Copeland/Plurality. 
15 voters rank three alternatives {a,w,x} as follows:

4 2 5 4
w w x a
a x w x
x a a w

 

In scenario A5c, Copeland computes these scores: 

w wins 1 pairing (over a). 
a wins 1 pairing (over x). 
x wins 1 pairing (over w). 

All three alternatives have the same Copeland score (1).  The Plurality tie-breaker finds 
w tops more votes (6) than any other alternative tops.  Thus Copeland/Plurality elects w.  
However, a majority (9 voters) rank x over w.  Since only 8 voters rank a over x, no 
rebutting sequence can be constructed.  Thus Copeland/Plurality can fail IMC and IMC2 
with as few as three alternatives.  Furthermore, x is second in one of the social orderings 
that is natural for Copeland/Plurality since x tops more votes than a tops.  Thus, though 
this example does not show Copeland/Plurality fails I2C (which was however shown by 
scenario A5a), it is an egregious failure with as few as three alternatives and similar 
to failing I2C.

Scenario A6:  Failures by Minimax, Maximin and Simpson-Kramer. 
15 voters rank four alternatives {a,b,c,w} as follows:

3 3 3 2 2 2
a b c w w w
b c a a b c
c a b b c a
w w w c a b

 

In scenario A6, the pairwise counts of the votes are as follows: 

V(a,b) = 10,  V(b,a) = 5 
V(b,c) = 10,  V(c,b) = 5 
V(c,a) = 10,  V(a,c) = 5 
V(a,w) =  9,  V(w,a) = 6 
V(b,w) =  9,  V(w,b) = 6 
V(c,w) =  9,  V(w,c) = 6 

Minimax scores each alternative x according to its largest pairwise opposition and chooses 
the alternative with the smallest score.  Maximin scores each alternative x according to its 
smallest pairwise support and chooses the alternative with the largest score.  Simpson-
Kramer scores each alternative according to its smallest pairwise "support minus opposition" 
and elects the alternative with the largest score. (Other variations may be obvious.)  When 
all votes are strict orderings of the alternatives, as in scenario A6, all three procedures elect 
the same, and here they elect w.  For instance, Minimax elects w since w's largest pairwise 
opposition (V(a,w), V(b,w), and V(c,w)) is 9 voters, whereas all other alternatives have 
larger pairwise oppositions (10 voters).  Since only minorities (6 voters) prefer w over 
any other alternative, no rebutting sequence can be constructed against the complaint that 
a different alternative should be chosen, which means Minimax, Maximin and Simpson-
Kramer fail IMC and IMC2.  Furthermore, no matter how the social ordering is constructed, 
one of {a,b,c} must be second in the social ordering.  Thus, Minimax, Maximin and 
Simpson-Kramer also fail I2C.  (The behavior of these methods is especially egregious 
since w is not in the top cycle, and in fact for every other alternative there is a majority 
who rank it over w.)

Scenario A7:  Failures by TopCycle/Minimax and TopCycle/Maximin. 
13 voters rank four alternatives {a,b,w,x} as follows:

4 1 2 2 4
x x a a b
w a w b w
a b b x x
b w x w a

 

In scenario A7, the pairwise counts of the votes are as follows: 

V(a,b) = 9,  V(b,a) = 4 
V(x,a) =  9,  V(a,x) = 4 
V(b,x) = 8,  V(x,b) = 5 
V(w,a) = 8,  V(a,w) = 5 
V(b,w) =  7,  V(w,b) = 6 
V(x,w) =  7,  V(w,x) = 6 

TopCycle/Minimax and TopCycle/Maximin are like Minimax and Maximin, respectively, 
except they neglect all alternatives that are not in the top cycle (the smallest non-empty 
subset of alternatives such that every alternative in the subset "beats pairwise" every 
alternative not in the subset).  In scenario A7, all alternatives are in the top cycle so the 
two procedures behave equivalently to Minimax and Maximin, respectively.  Since all 
votes are strict orderings, Minimax and Maximin elect the same, so we can consider 
just Minimax:  For all alternatives except w there is a majority larger than 7 voters who 
rank something over it.  Thus Minimax elects w.  However, a majority (7 voters) 
rank x over w.  Clearly x is second in both natural social orderings, since x has the 
second smallest largest opposing majority and x would be elected if w were deleted.  
Thus Minimax and Maximin and TopCycle/Minimax and TopCycle/Maximin fail IMC2 
and I2C.  To show they also fail IMC, we show the only social ordering capable of 
satisfying IMC is "x over w over a over b" (which implies x must be elected).  Clearly, 
IMC requires x must be socially ordered over a since a majority of 9 rank x over a  
and no majority as large as 9 ranks anything over x.  Clearly, IMC requires a must be 
socially ordered over b since a majority of 9 rank a over b and if a is not socially ordered 
over b no rebuttal sequence of majorities as large as 9 can be constructed.  Clearly, 
IMC requires w must be socially ordered over a since a majority of 8 rank w over a and 
no majority as large as 8 ranks anything over w.  Thus the social ordering must be one of 
these three: "x over w over a over b" or "x ~ w over a over b" or "w over x over a over b."  
Since a majority (7 voters) rank x over w, the last two orderings cannot satisfy IMC.  
Thus the only social ordering capable of satisfying IMC is "x over w over a over b
and it can be checked that this ordering indeed satisfies IMC.  Therefore IMC requires 
x must be elected.  Thus TopCycle/Minimax and TopCycle/Maximin fail IMC, IMC2 
and I2C

Scenario A8:  Failures by Kemeny-Young. 
15 voters rank four alternatives {a,b,w,x} as follows:

6 5 4
x w a
w a b
a b x
b x w

 

For each possible social ordering, Kemeny-Young computes a score equal to the sum of the 
pairwise preferences with which it agrees, and then Kemeny-Young elects the alternative 
atop the ordering having the largest score.  In scenario A8, Kemeny-Young scores 60 
for the ordering "w over a over b over x" since this ordering agrees with 11 votes for w 
over a plus 11 votes for w over b plus 5 votes for w over x plus 15 votes for a over b 
plus 9 votes for a over x plus 9 votes for b over x.  It can be checked that no other ordering 
has a score as large. (Checking all possible orderings would be tedious, but one may rule 
out many possibilities since Kemeny-Young satisfies local independence of irrelevant 
alternatives
(LIIA).  For instance, note that if x were deleted then the Kemeny-Young 
ordering of the remaining alternatives would be "w over a over b."  Thus, by LIIA the only 
strict ordering topped by x that needs checking is "x over w over a over b" and the only 
strict ordering trailed by x that needs checking is "w over a over b over x."  Similarly, 
the only strict ordering topped by w that needs checking is "w over a over b over x" and 
the only strict ordering trailed by w that needs checking is "a over b over x over w."  
The only strict ordering topped by a that needs checking is "a over x over w over b" and 
the only strict ordering trailed by a that needs checking is "x over w over b over a."  
The only strict ordering topped by b that needs checking is "b over x over w over a" and 
the only strict ordering trailed by b that needs checking is "x over w over a over b."  
One can reduce these even further by noting contradictions where an alternative atop one 
trails another, etc., which reduces to two the number of orderings that need checking.  
For these two orderings, Kemeny-Young scores 59 for "x over w over a over b" and 60 
for "w over a over b over x.")  Thus Kemeny-Young elects w.  However, a majority 
(10 voters) rank x over w.  Since no majority as large as 10 prefers any alternative over x
no rebutting sequence can be constructed against the complaint that x should be elected, 
which means Kemeny-Young fails IMC.  It can also be shown that Kemeny-Young fails 
IMC2, since both natural social orderings (techniques 5 and 6) are the same "w over a 
over b over x." (Indeed, techniques 5 and 6 must agree under any voting procedure 
that satisfies LIIA.)  

Kemeny-Young satisfies I2C. (In general, any procedure that satisfies LIIA and is 
majoritarian when there are only two alternatives satisfies I2C.)  

Scenario A9:  Failures by Tideman's "Ranked Pairs" and Tideman-Zavist. 
15 voters rank three alternatives {a,w,x} as follows:

5 3 7
a x w
x w  
w a x~a

 

Tideman's "Ranked Pairs" (hereafter abbreviated Tideman) and Zavist-Tideman are similar 
to MAM.  A major difference is that they rank the pairings by "margin of victory", which 
means subtracting pairwise opposition from pairwise support. (This distinction matters 
only if some voters vote non-strict orderings, which we argue ought to be allowed since 
voting two or more alternatives bottom can be a benevolent strategy--creating a desirable 
non-manipulative equilibrium for the sincere winner--with a procedure such as MAM.  
See the discussion of the minimal defense criterion elsewhere.)  Thus, in scenario A9 
Tideman and Tideman-Zavist sort the pairings in the following decreasing order of 
precedence:

w over a (since 10-5 = 5) 
a over x (since 5-3 = 2) 
x over w (since 8-7 = 1) 

Then Tideman and Tideman-Zavist would affirm "w over a" and "a over x" since these 
two pairings have the greatest precedence, and they would not affirm "x over w" since it 
cycles with those already affirmed.  The affirmed pairings produce the social ordering 
"w over a over x."  Thus Tideman and Tideman-Zavist elect w.  However, a majority 
(8 voters) rank x over w.  Since no majority as large as 8 prefers any alternative over x
no rebutting sequence can be constructed against the complaint that x should be elected, 
which means Tideman and Tideman-Zavist fail IMC and IMC2. (Note that if enough of 
the 7 voters who rank x and a bottom had instead ranked x over a, then x would be 
a Condorcet winner.  The implication is that "truncation of preferences" is an effective 
manipulative strategy under Tideman and Tideman-Zavist, and under many other voting 
procedures, but would not be manipulative under MAM.  See the discussion of the 
truncation resistance criterion elsewher.)

Tideman and Tideman-Zavist satisfy local independence of irrelevant alternatives 
and are majoritarian when there are only two alternatives, so they satisfy I2C.  

Scenario A10:  Failures by PathWinner. 
13 voters rank four alternatives {a,b,w,x} as follows:

1 5 2 2 3
w x a a b
b w b b w
x a w x x
a b x w a

 

In scenario A10, the following shows the pairwise counts of the votes: 

V(x,a) = 9,  V(a,x) = 4 
V(w,a) = 9,  V(a,w) = 4 
V(a,b) = 9,  V(b,a) = 4 
V(b,x) = 8,  V(x,b) = 5 
V(x,w) = 7,  V(w,x) = 6 
V(b,w) = 7,  V(w,b) = 6 

PathWinner calculates the strengths of the strongest paths as shown in the following table: 

From To Strongest Path Strength of Strongest Path
x a xa 9
a x abx 8
x b xab 9
b x bx 8
x w xw 7
w x wabx 8
a b ab 9
b a bxa 8
a w abw 7
w a wa 9
b w bw 7
w b wab 9


The strength of a path (sequence of majorities) is the size of its smallest majority.  Since 
the strongest path from w to any other alternative is stronger than the strongest path from 
that alternative to w, PathWinner elects w.  However, a majority (7 voters) rank x over w.  
It can be checked that the only sequence that can rebut that majority is w,a,b,x; thus the 
only ordering that might possibly satisfy IMC is "w over a over b over x."  But that 
ordering can also be shown to fail IMC: Since a majority (9 voters) rank x over a and 
no majority as large as 9 ranks any alternative over x, every social ordering that 
satisfies IMC orders x over a.  Thus PathWinner fails IMC.  Furthermore, the social 
ordering natural for PathWinner is "w over x over a over b."  This is shown as follows:  
We have already established that w must top the PathWinner social ordering.  Since x has 
stronger paths to a and to b than a or b have to x, and since x would be elected if w were 
dropped, x must be second in the natural ordering.  Since a has a stronger path to b than 
b has to a, and since a would be elected if w and x were dropped, a must be third in 
the natural ordering.  Thus either technique 3 or 6 produces the natural social ordering 
"w over x over a over b."  Since a majority prefer the second alternative (x) over the 
elected alternative (w), this implies PathWinner also fails IMC2 and I2C.

Appendix B - Proofs of the theorems

Proof of theorem 1:  We must show there is always at least one social ordering that is 
capable of satisfying IMC.  Let r0 denote some strict ordering of A. (The manner in 
which r0 is constructed does not matter for theorem 1, but it is possible to construct r0  
so r0 satisfies anonymity, neutrality, strong Pareto, monotonicity, and independence 
of irrelevant alternatives
.  MAM's tie-breaking procedure, Random Voter Hierarchy, 
accomplishes this.)  Abbreviate P = Pairs(A), the set of all possible ordered pairs of 
alternatives in A.  Let RP denote the binary relation on P such that, for all (x,y),(z,w)P
RP ranks (x,y) over (z,w) if and only if one of the following four conditions holds: 

(1.1)  V(x,y) > V(z,w). 
(1.2)  V(x,y) = V(z,w) and V(y,x) < V(w,z).  
(1.3)  V(x,y) = V(z,w) and V(y,x) = V(w,z) and r0 ranks w over y.  
(1.4)  V(x,y) = V(z,w) and V(y,x) = V(w,z) and w = y and r0 ranks x over z.  

(Clearly RP depends only on R and r0.)  We next establish the following lemma:  

Lemma 1.5:  RP is a strict ordering of P.  

Proof of 1.5:  We must show RP is complete, irreflexive, asymmetric and transitive.  
To show completeness, pick any distinct (x,y),(z,w)P and assume RP does not 
rank (x,y) over (z,w).  We must show RP ranks (z,w) over (x,y).  Clearly none 
of 1.1, 1.2, 1.3 or 1.4 hold.  Since r0 is a strict ordering, this implies one of 
the following four conditions must hold: 

(1.5.1)  V(z,w) > V(x,y). 
(1.5.2)  V(z,w) = V(x,y) and V(w,z) < V(y,x).  
(1.5.3)  V(z,w) = V(x,y) and V(w,z) = V(y,x) and r0 ranks y over w.  
(1.5.4)  V(z,w) = V(x,y) and V(w,z) = V(y,x) and w = y and r0 ranks z over x.  

It follows by the definition of RP that RP ranks (z,w) over (x,y); thus RP is complete.  
To show irreflexivity, pick any (x,y)P.  We must show RP does not rank (x,y)  
over itself.  Clearly none of the following four conditions can hold: 

(1.5.5)  V(x,y) > V(x,y). 
(1.5.6)  V(y,x) < V(y,x).  
(1.5.7)  r0 ranks y over y.  
(1.5.8)  r0 ranks x over x.  

By the definition of RP, RP does not rank (x,y) over (x,y); thus RP is irreflexive.  
To show asymmetry, pick any two pairs (x,y),(z,w)P.  Assume RP ranks (x,y)  
over (z,w).  We must show RP does not rank (z,w) over (x,y).  Since one of 1.1, 
1.2, 1.3 or 1.4 holds and since r0 is a strict ordering, clearly none of the following 
four conditions can hold: 

(1.5.9)  V(z,w) > V(x,y). 
(1.5.10)  V(z,w) = V(x,y) and V(w,z) < V(y,x).  
(1.5.11)  V(z,w) = V(x,y) and V(w,z) = V(y,x) and r0 ranks y over w.  
(1.5.12)  V(z,w) = V(x,y) and V(w,z) = V(y,x) and w = y and r0 ranks z over x.  

By the definition of RP, RP does not rank (z,w) over (x,y); thus RP is asymmetric.  
To show transitivity, pick any three pairs (x,y),(z,w),(u,v)P.  Assume RP ranks 
(x,y) over (z,w) and (z,w) over (u,v).  We must show RP ranks (x,y) over (u,v).  
Since RP ranks (x,y) over (z,w), one of 1.1, 1.2, 1.3 or 1.4 must hold.  
Since RP ranks (z,w) over (u,v), one of the following four conditions must hold: 

(1.5.13)  V(z,w) > V(u,v). 
(1.5.14)  V(z,w) = V(u,v) and V(w,z) < V(v,u).  
(1.5.15)  V(z,w) = V(u,v) and V(w,z) = V(v,u) and r0 ranks v over w.  
(1.5.16)  V(z,w) = V(u,v) and V(w,z) = V(v,u) and v = w and r0 ranks z over u

There are three cases to consider:  

Case 1.5.17:  Either 1.1 or 1.2 holds.  This implies either 
[V(x,y) > V(u,v)] or [V(x,y) = V(u,v) and V(y,x) < V(v,u)], 
which implies RP ranks (x,y) over (u,v).

Case 1.5.18:  Either 1.5.13 or 1.5.14 holds.  This implies either 
[V(x,y) > V(u,v)] or [V(x,y) = V(u,v) and V(y,x) < V(v,u)], 
which implies RP ranks (x,y) over (u,v).

Case 1.5.19:  None of {1.1, 1.2, 1.5.13, 1.5.14} hold.  This implies one of 
{1.3, 1.4} holds and one of {1.5.15, 1.5.16} holds.  Clearly V(x,y) = V(u,v
and V(y,x) = V(v,u).  Thus there are four subcases to consider:  

Case 1.5.19.1:  yw and wv.  This implies r0 orders w over y and 
r0 orders v over w.  Since r0 is a strict ordering, r0 must order v over y.  
This implies yv.  Since V(x,y) = V(u,v) and V(y,x) = V(v,u
and r0 orders v over y, it follows that RP ranks (x,y) over (u,v).  

Case 1.5.19.2:  yw and w = v.  This implies r0 orders w over y, and 
thus r0 orders v over y.  Since V(x,y) = V(u,v) and V(y,x) = V(v,u
and r0 orders v over y,  it follows that RP ranks (x,y) over (u,v).  

Case 1.5.19.3:  y = w and wv.  This implies r0 orders v over w, and 
thus r0 orders v over y.  Since V(x,y) = V(u,v) and V(y,x) = V(v,u
and r0 orders v over y, it follows that RP ranks (x,y) over (u,v).  

Case 1.5.19.4:  y = w and w = v.  This implies y = v and r0 orders x  
over z and r0 orders z over u.  Since r0 is a strict ordering, r0 must 
order x over u.  Since V(x,y) = V(u,v) and V(y,x) = V(v,u) and y = v  
and r0 orders x over u, it follows that RP ranks (x,y) over (u,v)

Since in all four subcases RP ranks (x,y) over (u,v), RP must rank (x,y)  
over (u,v) in case 1.5.19.

Since in all three cases RP ranks (x,y) over (u,v), RP must be transitive.  Since RP is 
complete, irreflexive, asymmetric and transitive, RP is a strict ordering of P.   QED

Let Majorities denote {(x,y)P such that V(x,y) > V(y,x)}.  
Let AffirmedMajorities denote {(x,y)Majorities such that there exists no sequence 
a1,a2,...,akA such that a1 = y and ak = x and [(aj,aj+1)AffirmedMajorities for 
all j ∈ {1,2,...,k-1}] and [RP orders (aj,aj+1) over (x,y) for all j ∈ {1,2,...,k-1}]}.  
(Note that the definition of AffirmedMajorities is recursive but not circular.)  
Abbreviate Maj = Majorities and Aff = AffirmedMajorities.  
Next we establish the following lemma: 

Lemma 1.6:  Aff is an acyclic subset of Maj.  

Proof of 1.6:  Clearly Aff is a subset of M.  Suppose to the contrary Aff is cyclic.  
This means there exists a sequence of alternatives s = x1,x2,...,xcA such that 
x1 = xc and (xj,xj+1)Aff for all j ∈ {1,2,...,c-1}. (Clearly c ≥ 4.)  Since RP is 
a strict ordering of P and MajP, there must exist h ∈ {1,2,...,c-1} such that 
RP orders (xj,xj+1) over (xh,xh+1) for all j ∈ {1,2,...,c-1}.  Let s' denote the 
sequence of alternatives constructed from s by first dropping xc and then rotating 
the remainder so xh+1 is first and xh is last.  Thus we can relabel the alternatives 
so s' = a1,a2,...,ak where k = c-1 and [aj = xj+h for all j ∈ {1,2,...,k-h)}] and 
[aj = xj+h-k for all j ∈ {1+k-h,2+k-h,...,k}].  Clearly a1,a2,...,ak is a sequence of 
alternatives such that a1 = xh+1 and ak = xh and (aj,aj+1)Aff all j ∈ {1,2,...,k-1} 
and RP orders (aj,aj+1) over (xh,xh+1) for all j ∈ {1,2,...,k-1}.  By the definition 
of Aff this implies (xh,xh+1)Aff.  But this is a contradiction, which implies 
the contrary assumption cannot hold, establishing Aff is acyclic.    QED

We next show that, since Aff is acyclic, there exists at least one strict ordering of 
the alternatives r that is consistent with Aff in the sense that r orders x over y for 
all (x,y)Aff. (It is also possible some non-strict orderings are consistent with Aff.)  
To show this, consider the following recursive definition of a binary relation r (which 
corresponds to an iterative construction in which n is incremented by 1 each iteration, 
from 1 to #A):  

Abbreviate P(B) = Pairs(B) for all non-empty BA. (The ordered pairs 
of alternatives in B.)

Let B1 denote A.  

For all n ∈ {1,2,...,#A}, let Tn denote {xBn such that x is not the second 
alternative in any ordered pair in P(Bn) ∩ Aff}.  
For all n ∈ {1,2,...,#A}, let Wn denote {xTn such that r0 orders no yTn over x}.  

For all n ∈ {2,3,...,#A}, let Bn denote Bn-1\Wn-1

Let r denote the binary relation on A such that, for all x,yA, r ranks x over y 
if and only if there exists n ∈ {1,2,...,#A} such that Wn = {x} and yBn

We next establish the following lemma:  

Lemma 1.7:  r is a strict ordering of A consistent with Aff.  

Proof of 1.7:  Since Aff is acyclic, P(B) ∩ Aff must be acyclic for all non-empty BA.  
This implies that for all non-empty BA there exists at least one xB such that x is 
not second in any ordered pair in P(B) ∩ Aff.  This implies Tn is not empty for all 
n ∈ {1,2,...,#A}.  Thus, since r0 is a strict ordering, Wn must be a singleton for all 
n ∈ {1,2,...,#A}.  Also, clearly WmWn for all distinct m,n ∈ {1,2,...,#A}.  It follows 
that r is a strict ordering of A.  To show r is consistent with Aff, pick any (x,y)Aff.  
We must show r orders x over y.  Let n denote the smallest integer in {1,2,...,#A} such 
that either Wn = {x} or Wn = {y}.  We must show Wn = {x} and yBn.  By the 
definition of n, clearly {x,y} ⊆ Bn.  Thus (x,y)P(Bn).  Since (x,y)P(Bn) ∩ Aff
this means y is the second alternative in an ordered pair in P(Bn) ∩ Aff.  Thus yTn
which implies Wn ≠ {y}, which implies Wn = {x}.  This implies r orders x over y
which implies r is consistent with Aff.  Thus r is a strict ordering of A consistent 
with Aff.     QED

It remains only to show r is capable of satisfying IMC.  Pick any x,yA and assume 
V(x,y) > V(y,x) and r does not order x over y.  We must show there exists a sequence 
of alternatives a1,a2,...,akA such that a1 = y and ak = x and all three of the following 
conditions hold for all j ∈ {1,2,...,k-1}: 

(1.8)  V(aj,aj+1) > V(x,y) or [ V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(1.9)  V(aj,aj+1) > V(aj+1,aj).
(1.10)  r orders aj over aj+1.

By lemma 1.7, r orders a over b for all (a,b)Aff.  This implies (x,y)Aff.  Since 
V(x,y) > V(y,x), (x,y)M.  Since (x,y)M\Aff, by the definition of Aff  there must 
exist a sequence a1,a2,...,akA such that all three of the following conditions hold: 

(1.11)  a1 = y and ak = x
(1.12)  (aj,aj+1)Aff for all j ∈ {1,2,...,k-1}.  
(1.13)  RP orders (aj,aj+1) over (x,y) for all j ∈ {1,2,...,k-1}.

By inspection of the definition of RP, 1.13 implies 1.8 holds for a1,a2,...,ak.  By 
inspection of the definition of AffAff  ⊆ M.  Therefore, 1.12 implies 1.9 holds 
for a1,a2,...,ak.  Since r orders a over b for all (a,b)Aff, 1.12 implies 1.10 holds 
for a1,a2,...,ak.  Since a1 = y and ak = x and 1.8, 1.9 and 1.10 all hold for a1,a2,...,ak
it follows that r is capable of satisfying IMC.  Thus we have established that r is a 
(strict) ordering of A capable of satisfying IMC.     QED

Proof of theorem 2:  We must show satisfaction of IMC implies satisfaction of Condorcet-
consistency, Top Cycle, Weak Pareto, Resolvability, Minimal Defense and Truncation 
Resistance.  Assume satisfaction of IMC.  Let w denote the chosen alternative.  

First we show satisfaction of Top Cycle:  Let tc denote the smallest non-empty BA such 
that V(b,a) > V(a,b) for all bB and all aA\B.  Suppose to the contrary wtc.  
Since tc is not empty, we can pick ttc such that no t'tc is socially ordered over t.  
Clearly V(t,w) > V(w,t).  By IMC there must exist a sequence a1,a2,...,akA such that 
a1 = w and ak = t and all three of the following conditions hold for all j ∈ {1,2,...,k-1}: 

(2.1.1)  V(aj,aj+1) > V(t,w) or [ V(aj,aj+1) = V(t,w) and V(aj+1,aj) ≤ V(w,t)].  
(2.1.2)  V(aj,aj+1) > V(aj+1,aj).
(2.1.3)  aj is socially ordered over aj+1.

Since no alternative in tc is socially ordered over t, 2.1.3 implies ak-1tc.  This implies 
V(ak-1,ak) < V(ak,ak-1), which means 2.1.2 does not hold for j = k-1.  The contradiction 
means the contrary assumption cannot hold, establishing wtc, which means Top Cycle 
is satisfied. 

Satisfaction of Top Cycle implies Condorcet-consistency, which requires that if there 
exists xA such that [V(x,y) > V(y,x) for all yA\{x}] then x must be chosen.  
Clearly if such an alternative exists, tc would include only that alternative.

Next we show satisfaction of Weak Pareto, which requires that, for all x,yA, if every 
vote ranks x over y then x must be socially ordered over y. (Note that the MAM procedure 
also satisfies Strong Pareto.)  Assume every vote ranks x over y.  Suppose to the contrary 
that x is not socially ordered over y.  Let n denote the total number of votes.  Clearly the 
following conditions must hold:  

(2.2.1)  V(a,b) ≤ n for all a,bA.  
(2.2.2)  V(y,x) = 0.

By IMC, there must exist a sequence a1,a2,...,akA such that a1 = y and ak = x and 
all three of the following conditions hold for all j ∈ {1,2,...,k-1}: 

(2.2.3)  V(aj,aj+1) > V(x,y) or [ V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(2.2.4)  V(aj,aj+1) > V(aj+1,aj).
(2.2.5)  aj is socially ordered over aj+1.

By 2.2.1, 2.2.2 and 2.2.3 the following condition must hold:  

(2.2.6)  V(aj,aj+1) = n and V(aj+1,aj) = 0 for all j ∈ {1,2,...,k-1}.  

It follows by induction on 2.2.6 that V(a1,ak) = n.  But since a1 = y and ak = x, this 
contradicts 2.2.2.  The contradiction implies the contrary assumption cannot hold, 
establishing satisfaction of Weak Pareto.  

Next we establish the following lemma: 

For all orderings of the alternatives r, let Agree(r) denote {(x,y)Pairs(A
such that r orders x over y}.

For all distinct orderings of the alternatives r and r', let Disagree(r,r') denote 
{(x,y)Pairs(A) such that r and r' disagree on the relative ordering of x and y}.  

For all distinct orderings of the alternatives r and r',  let Largest(r,r',R) denote 
{(x,y) ∈ Disagree(r,r') such that V(x,y) > V(y,x) and, for all (z,w) ∈ Disagree(r,r'
such that V(z,w) > V(w,z), either [V(x,y) > V(z,w) or [V(x,y) = V(z,w) and 
V(y,x) ≤ V(w,z)]}. (That is, Largest(r,r',R) is(are) the largest majority(majorities) upon which 
r and r' disagree.)  

Lemma 2.3:  For all orderings of the alternatives r,r', if Largest(r,r',R) is a 
non-empty subset of Agree(r) then r' is incapable of satisfying IMC.  

Proof of 2.3:  Pick any two distinct orderings of the alternatives r and r'.  
Make the following abbreviations: 

Ag = Agree(r). 
Ag' = Agree(r'), 
D = Disagree(r,r'). 
L = Largest(r,r',R).  
Maj = {(x,y)Pairs(A) such that V(x,y) > V(y,x)}.

Assume L is a non-empty subset of Ag.  We must show r' is incapable of satisfying IMC.  
Suppose the contrary.  By inspection of the definition of Largest(), LD ∩ Maj.  
Pick any (x,y)L.  Since LAg, r must order x over y.  Since LAg and LD
LAg' = ϕ.  This implies r' does not order x over y.  Since (x,y) ∈ Maj and 
r' does not order x over y, by the contrary assumption there must exist a sequence 
a1,a2,...,akA such that a1 = y and ak = x and all three of the following conditions 
hold for all j ∈ {1,2,...,k-1}: 

(2.3.1)  V(aj,aj+1) > V(x,y) or [V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(2.3.2)  V(aj,aj+1) > V(aj+1,aj).
(2.3.3)  r' orders aj over aj+1.

By 2.3.2, (aj+1,aj) ∈ Maj for all j ∈ {1,2,...,k-1}.  By 2.3.3, (aj+1,aj)Ag' for all 
j ∈ {1,2,...,k-1}.  Since LAg' = ϕ, this implies (aj+1,aj)L for all j ∈ {1,2,...,k-1}.  
It follows by 2.3.1 that (aj+1,aj)D for all j ∈ {1,2,...,k-1}.  This implies r orders aj  
over aj+1 for all j ∈ {1,2,...,k-1}.  Since r is an ordering, r must be transitiv; thus 
r must order a1 over ak.  This means r orders y over x.  But this is a contradiction, 
which means the contrary assumption cannot hold.  Thus r' is incapable of satisfying 
IMC.     QED

Next we show satisfaction of Resolvability, which requires that for all xA such that 
x has a non-zero chance of being chosen given the votes R, there must exist an admissible 
vote r such that, if r were appended to R, then x would be chosen with certainty and every 
other alternative would have no chance of being chosen.  Moreover, we show satisfaction 
of "Strong" Resolvability, which requires that if a strict social ordering of the alternatives 
is not unambiguously specified then there must exist an admissible vote r such that, if r were 
appended to R, the social ordering would be specified with certainty and would be a strict 
ordering.  Assume x has a non-zero chance if being chosen.  By IMC, there must exist an 
ordering of the alternatives rx such that rx is the social ordering and x is an alternative 
atop rx. (Note that rx is not necessarily a strict ordering and may be topped by more than 
one alternative.)  It is straight-forward to construct an ordering r such that all three of the 
following conditions hold: 

(2.4.1)  r is a strict ordering of A
(2.4.2)  x is the unique alternative atop r
(2.4.3)  For all a,bA, if rx orders a over b then r orders a over b.  

By IMC, a vote may be any ordering of A, so r is an admissible vote.  We aim to show that 
r must with certainty be the social ordering given R+r.  Let R' denote R+r.  For all a,bA
let V'(a,b) denote the number of votes in R' that rank a over b.  Let Maj denote 
{(a,b)Pairs(A) such that V(a,b) > V(b,a)}.  Let Maj' denote {(a,b)Pairs(A
such that V'(a,b) > V'(b,a)}.  By 2.4.1, clearly both of the following conditions hold:  

(2.4.4)  V'(a,b) = 1 + V(a,b) for all a,bA such that r orders a over b
(2.4.5)  V'(a,b) = V(a,b) for all a,bA such that r does not order a over b

Pick any ordering of the alternatives r'r.  Define Agree(), Disagree() and Largest() 
the same as they are defined above in the definition of lemma 2.3.  Make the following 
abbreviations:  

Ag = Agree(r). 
Ag' = Agree(r'), 
D = Disagree(r,r'). 
L = Largest(r,r',R).  
L' = Largest(r,r',R'). 
Maj = {(a,b)Pairs(A) such that V(a,b) > V(b,a)}. 
Maj' = {(a,b)Pairs(A) such that V'(a,b) > V'(b,a)}.

Since r'rD is not empty.  There are two cases to consider: 

(2.4.6)  L is empty.  This implies V(a,b) = V(b,a) for all (a,b)D.  By 2.4.4 and 2.4.5, 
V'(a,b) > V'(b,a) for all (a,b)DAg and V'(a,b) < V'(b,a) for all (a,b)DAg'.  
It follows that L' is a non-empty subset of Ag.  By lemma 2.3, r' is incapable of 
satisfying IMC given R' in case 2.4.6.

(2.4.7)  L is not empty.  Since r is capable of satisfying IMC given R, it follows by 
lemma 2.3 that L is not a subset of Ag'.  This implies L intersects Ag.  Therefore we 
can pick (a,b)LAg.  Since LD, (a,b)D.  Since (a,b)D and (a,b)Ag
(a,b)Ag'.  By 2.4.4 and 2.4.5, V'(a,b) = 1 + V(a,b) and V'(b,a) = V(b,a).  It follows 
by 2.4.4 and 2.4.5 that (a,b)L'.  By 2.4.5, V'(z,w) = V(z,w) for all (z,w)DAg'.  
This implies V'(a,b) > V'(z,w) for all (z,w)DAg'.  Thus Ag'L' must be empty.  
Thus L'Ag.  Since L' is not empty and L'Ag, by lemma 2.3 r' is incapable of 
satisfying IMC given R' in case 2.4.7.

Since r' is incapable of satisfying IMC given R' in either case, it follows that r is the only 
ordering capable of satisfying IMC given R'.  By theorem 1, r must be the one and only 
ordering capable of satisfying IMC.  By IMC, r must be the social ordering given R'.  
Since x is the unique alternative atop r, by IMC x must be chosen with certainty given R' 
and no other alternative has a non-zero chance of being chosen given R', establishing 
satisfaction of Resolvability.  Moreover, since r must be the social ordering given R' 
and since r is a strict ordering, satisfaction of Strong Resolvability has been established. 

Next we show satisfaction of Minimal Defense, which requires that for all xA such 
that there exists yA sincerely preferred over x by more than half the voters, there must 
exist a set of voting strategies for the voters who prefer y over x that ensures x will not 
be chosen, does not require any of them to misrepresent any preferences regarding any pair 
of alternatives she prefers as much as or more than y, and does not require any of them to 
downrank x below tied for bottom.  Assume more than half the voters prefer y over x.  
Suppose each voter who prefers y over x votes x either bottom or tied for bottom in her 
ordering and does not  misrepresent any preferences regarding any pair of alternatives 
she prefers as much as or more than y. (These votes are consistent with the strategies 
allowed by the definition of Minimal Defense.)  We must show x cannot be chosen.  
Suppose to the contrary x is chosen.  By IMC, x must be an alternative atop the social 
ordering.  Since more than half of the voters rank y over x and y is not socially ordered 
over x, by IMC there must exist a sequence a1,a2,...,akA such that a1 = x and ak = y  
and all three of the following conditions hold for all j ∈ {1,2,...,k-1}: 

(2.5.1)  V(aj,aj+1) > V(y,x) or [V(aj,aj+1) = V(y,x) and V(aj+1,aj) ≤ V(x,y)].  
(2.5.2)  V(aj,aj+1) > V(aj+1,aj).
(2.5.3)  aj is socially ordered over aj+1.

Since more than half the voters rank x no better than tied for bottom, V(x,a2) must be less 
than half the votes.  But this means 2.5.1 does not hold for j = 1.  The contradiction means 
the contrary assumption cannot hold, which means x cannot be chosen, establishing 
satisfaction of Minimal Defense.

Next we show satisfaction of Truncation Resistance, which requires that for all xA 
not in the sincere top cycle, x must not be chosen if more than half the votes rank some 
alternative in the sincere top cycle over x and no vote expresses any insincere strict 
preferences. (Note that votes that include insincere indifference are consistent with 
the premise of this criterion; it is only assumed that votes include no insincere strict 
preferences.  A voter who votes indifference when she has a sincere strict preference 
is said to be "truncating" her preference.)  Let tc denote the sincere top cycle.  Assume 
xtc and ytc and more than half of the votes rank y over x and, for all a,bA
every vote that ranks a over b expresses a sincere preference for a over b.  We must 
show x cannot be chosen.  Suppose to the contrary x is chosen.  By IMC, x must be an 
alternative atop the social ordering.  Since more than half the voters rank y over x and 
y is not socially ordered over x, by IMC there must exist a sequence a1,a2,...,akA 
such that a1 = x and ak = y and all three of the following conditions hold for all 
j ∈ {1,2,...,k-1}: 

(2.6.1)  V(aj,aj+1) > V(y,x) or [ V(aj,aj+1) = V(y,x) and V(aj+1,aj) ≤ V(x,y)].  
(2.6.2)  V(aj,aj+1) > V(aj+1,aj).
(2.6.3)  aj is socially ordered over aj+1.

By the definition of the sincere top cycle, it follows that for all ttc and all ztc, the 
number of voters who sincerely prefer z over t must be less than half the voters.  Thus, 
since no vote expresses an insincere strict preference, V(z,t) must be less than half the 
votes for all ttc and all ztc.  Since a1tc and aktc, by induction there must 
exist h ∈ {1,2,...,k-1} such that ahtc and ah+1tc.  Therefore V(ah,ah+1) < V(y,x).  
But this means 2.6.1 does not hold for j = h.  The contradiction means the contrary 
assumption cannot hold, which means x cannot be chosen, establishing satisfaction 
of Truncation Resistance.  
QED

Proof of theorem 3:  First we establish the following lemma: 

Lemma 3.1:  If IMC is satisfied, then for all x,yA such that V(x,y) ≠ V(y,x
the social ordering does not order x equal to y. (In other words, if the number of 
votes that rank x over y does not equal the number of votes that rank y over x
IMC requires either x is socially ordered over y or y is socially ordered over x.) 

Proof of lemma 3.1:  Assume satisfaction of IMC and V(x,y) ≠ V(y,x).  Let r denote 
the social ordering.  Suppose to the contrary r orders x equal to y.  Without loss of 
generality assume V(x,y) > V(y,x). (We could swap the labels of x and y if necessary 
to make this so.)  Since r does not order x over y, by IMC there must exist a sequence 
of alternatives a1,a2,...,akA such that a1 = y and ak = x and all three of the 
following conditions hold for all j ∈ {1,2,...,k-1}: 

(3.1.1)  V(aj,aj+1) > V(x,y) or [V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(3.1.2)  V(aj,aj+1) > V(aj+1,aj).
(3.1.3)  r orders aj over aj+1.

Since r is an ordering, r must be transitive.  Therefore, by induction on 3.1.3, 
r must order a1 over ak.  This means r orders y over x.  But this contradicts 
the contrary assumption, which means the contrary assumption cannot hold.  
Thus lemma 3.1 is established.     QED

Resuming the proof of theorem 3...  Assume no pairing is a tie and every cycle has only 
one smallest majority.  We must show there exists a unique social ordering capable of 
satisfying IMC, and furthermore that it is a strict ordering.   Suppose to the contrary 
there exist distinct orderings r and r' capable of satisfying IMC.  Let P denote all 
possible ordered pairings of alternatives in A. (That is, P = {(x,y) such that x,yA}.)  
Let D denote the subset of P on which r and r' disagree.  Since rr', D is not empty.  
Let (d,d') denote a pairing in D such that, for all (x,y)D, either V(d,d') > V(x,y) or 
[V(d,d') = V(x,y) and V(d',d) ≤ V(y,x)]. (In other words, no pairing in D is larger 
than (d,d').)  Since no pairings are ties, it follows that V(d,d') > V(d',d).  Since 
no pairings are ties and both r and r' are capable of satisfying IMC, by lemma 3.1 
both r and r' must be strict orderings of A.  Thus, without loss of generality assume 
r orders d over d' and r' orders d' over d. (We could swap the labels of r and r' if 
necessary to make this so.)  Since r' is capable of satisfying IMC and  V(d,d') > V(d',d
and r' does not order d over d', there must exist a sequence a1,a2,...,akA such that 
a1 = d' and ak = d and all three of the following conditions hold for all j ∈ {1,2,...,k-1}: 

(3.2.1)  V(aj,aj+1) > V(d,d') or [V(aj,aj+1) = V(d,d') and V(aj+1,aj) ≤ V(d',d)].  
(3.2.2)  V(aj,aj+1) > V(aj+1,aj).
(3.2.3)  r' orders aj over aj+1.

Since a1 = d' and ak = d and V(d,d') > V(d',d), by 3.2.2 the sequence formed by 
concatenating d' to the  end of a1,a2,...,ak is a majority cycle.  By 3.2.1, each majority 
in this cycle is at least as large as (d,d').  Since every cycle has only one smallest 
majority, the '≤'  in 3.2.1 must be strict '<'.  That is, the following condition must hold 
for all j ∈ {1,2,...,k-1}: 

(3.2.4)  V(aj,aj+1) > V(d,d') or [V(aj,aj+1) = V(d,d') and V(aj+1,aj) < V(d',d)].  

Since no pairing in D is larger than (d,d'), by 3.2.4 the following condition must hold: 

(3.2.5)  (aj,aj+1)D for all j ∈ {1,2,...,k-1}.  

In other words, for all j ∈ {1,2,...,k-1}, r and r' must agree on the relative ordering of aj  
and aj+1.  Thus, by 3.2.3 r must order aj over aj+1 for all j ∈ {1,2,...,k-1}.  Since r is 
an ordering, r is transitive.  It follows by induction that r orders a1 over ak.  But this 
means r orders d' over d, a contradiction which implies the contrary assumption cannot 
hold.  Thus there is a unique social ordering capable of satisfying IMC when no pairings 
are ties and every cycle has only one smallest majority.  Furthermore, by lemma 3.1 
this unique ordering must be a strict ordering.  Thus theorem 3 is established.     QED

Proof of theorem 4:  We must show that in the domain of votes where only one social 
ordering can satisfy IMC, satisfaction of IMC implies satisfaction of Strong Pareto, 
Monotonicity, Anonymity, Neutrality, Homogeneity, Local Independence of Irrelevant 
Alternatives, and Independence of Clones.  First we establish the following lemma:

Lemma 4.1:  If only one social ordering is capable of satisfying IMC, then it is 
a strict ordering.  

Proof of 4.1:  Suppose r is the only ordering of the alternatives capable of satisfying 
IMC, and suppose to the contrary r is not a strict ordering.  Since r is not strict, there 
must exist distinct x,yA such that r orders x equal to y.  Let Y denote {aA\{x} such 
that r orders x equal to a}.  By lemma 3.1, V(a,x) = V(x,a) for all aE.  Let r' denote 
the ordering that is the same as r except x is raised over E.  Since r is capable 
of satisfying IMC and V(a,x) = V(x,a) for all aE, clearly r' is also capable of 
satisfying IMC.  But since r'r, this contradicts the premise that r is the only ordering 
of the alternatives capable of satisfying IMC.  The contradiction means the contrary 
assumption cannot hold, which means r must be a strict ordering.     QED 

Resuming the proof of theorem 4...  Assume the voting procedure satisfies IMC and given 
the votes R only one social ordering is capable of satisfying IMC.  Let r denote the unique 
ordering capable of satisfying IMC given R.  By lemma 4.1, r must be a strict ordering.  
Let w denote the unique alternative atop r.  By IMC, w must be chosen given R.  

First we show satisfaction of Strong Pareto, which requires that, for all x,yA, x must be 
socially ordered over y if V(x,y) > 0 and V(y,x) = 0.  The proof of theorem 1 above provides 
a procedure for constructing a social ordering capable of satisfying IMC that depends 
only on the votes and some strict ordering of the alternatives r0.  We will show that r0 can 
always be constructed so r0 complies with Strong Pareto.  Then we will show that if r0 
complies with Strong Pareto then the social ordering constructed from R and r0 under the 
procedure of theorem 1 must also satisfy Strong Pareto. (It will follow that, since it is 
always possible to construct a social ordering capable of satisfying both IMC and Strong 
Pareto, and since r is the only ordering capable of satisfying IMC, r must comply with 
Strong Pareto.)  To show r0 can always be constructed to comply with Strong Pareto, 
consider the following iterative procedure for constructing r0

Let rV denote some strict ordering of the voters. (Note that rv may be constructed 
randomly if complete satisfaction of Anonymity is desired.)  

Let rA denote some strict ordering of the alternatives. (Note that rA may be 
constructed randomly if complete satisfaction of Neutrality is desired.)  

Initialize r0 so that at first r0 ranks all alternatives equal to each other.  

Repeat the following until r0 is a strict ordering or all votes have been picked: 

Pick the unpicked vote ordered highest by rV and call it v.  
For all x,yA such that r0 ranks x equal to y and v does not rank x equal to y
amend r0 so r0 ranks x relative to y the same as v does.  

If r0 is not yet a strict ordering, then for all x,yA such that r0 ranks x equal to y
amend r0 so r0 ranks x relative to y the same as rA does.    

Clearly, if r0 is constructed under this procedure, then r0 complies with Strong Pareto.  
That is, for all x,yA such that V(x,y) > 0  and V(y,x) = 0, r0 orders x over y.  Next 
we establish the following lemma: 

Lemma 4.2:  Given any votes, if r0 complies with Strong Pareto, the social ordering 
constructed from the votes and from r0 under the procedure of theorem 1 complies 
with both IMC and Strong Pareto.  

Proof of 4.2:  Assume r0 complies with Strong Pareto.  Let r denote the social ordering 
constructed from the votes and from r0 under the procedure of theorem 1.  Assume 
V(x,y) > 0  and V(y,x) = 0.  We must show r orders x over y.  Since V(y,x) = 0 and 
every vote is an ordering of A, it follows that for all aA,  every vote that ranks y  
over a also ranks x over a, and every vote that ranks a over x  also ranks a over y.  
Thus both of the following conditions must hold: 

(4.2.1)  V(x,a) ≥ V(y,a) for all aA
(4.2.2)  V(a,x) ≤ V(a,y) for all aA.

Since r0 must rank x over y, by 4.2.1 and 4.2.2 and inspection of the definition of RP  
both of the following conditions must hold: 

(4.2.3)  RP orders (x,a) over (y,a) for all aA
(4.2.4)  RP orders (a,y) over (a,x) for all aA

By 4.2.1 and 4.2.2, both of the following conditions must hold: 

(4.2.5)  V(x,a) > V(a,x) for all aA such that V(y,a) > V(a,y). 
(4.2.6)  V(a,y) > V(y,a) for all aA such that V(a,x) > V(x,a). 

Let D denote the union of the following two subsets of Aff

{(a,x)Aff such that (a,y)Aff
{(y,b)Aff such that (x,b)Aff}

We will show that D is empty.  Suppose not.  By lemma 1.5, RP is a strict ordering 
of Pairs(A).  Thus, since D is not empty, we can pick the unique (z,z')D such that 
RP orders (z,z') over all other pairs in D.  There are two cases to consider: 

Case 4.2.7:  z = y.  By inspection of the definition of D, this implies (y,z')Aff 
and (x,z')Aff.  Since (y,z')Aff, (y,z')M.  Therefore, by 4.2.5, (x,z')M.  
Since (x,z')M\Aff, by inspection of the definition of Aff there must exist a 
sequence of alternatives a1,a2,...,akA such that a1 = z' and ak = x and both 
of the following conditions hold: 

(4.2.7.1)  (aj,aj+1)Aff for all j ∈ {1,2,...,k-1}. 
(4.2.7.2)  RP orders (aj,aj+1) over (x,z') for   all j ∈ {1,2,...,k-1}. 

By 4.2.4, RP orders (ak-1,y) over (ak-1,x).  By 4.2.7.2, RP orders (ak-1,x) over (x,z').  
By 4.2.3, RP orders (x,z') over (y,z').  Thus, since RP is a strict ordering, RP must 
order (ak-1,y) over (y,z').  Since RP orders no pair in D over (y,z'), this implies 
(ak-1,y)D.  Thus, since (ak-1,x)Aff, (ak-1,y)Aff.  Since (aj,aj+1)Aff 
for all j ∈ {1,2,...,k-2} and (ak-1,y)Aff and (y,z')Aff and a1 = z', Aff is cyclic.  
But by lemma 1.6, Aff is acyclic.  Thus case 4.2.7 is impossible.

Case 4.2.8:  zy.  By inspection of the definition of D, this implies z' = x and 
(z,x)Aff and (z,y)Aff.  Since (z,x)Aff, (z,x)M.  Therefore, by 4.2.6, 
(z,y)M.  Since (z,y)M\Aff, by inspection of the definition of Aff there must 
exist a sequence of alternatives a1,a2,...,akA such that a1 = y and ak = z and 
both of the following conditions hold: 

(4.2.8.1)  (aj,aj+1)Aff for all j ∈ {1,2,...,k-1}. 
(4.2.8.2)  RP orders (aj,aj+1) over (z,y) for   all j ∈ {1,2,...,k-1}. 

By 4.2.3, RP orders (x,a2) over (y,a2).  By 4.2.8.2, RP orders (y,a2) over (z,y).  
By 4.2.4, RP orders (z,y) over (z,x).  Thus, since RP is a strict ordering, RP must 
order (x,a2) over (z,x).  Since RP orders no pair in D over (z,x), this implies 
(x,a2)D.  Thus since (y,a2)Aff, (x,a2)Aff.  Since (x,a2)Aff and 
(aj,aj+1)Aff for all j ∈ {2,3,...,k-1} and (z,x)Aff and ak = z, Aff is cyclic.  
But by lemma 1.6, Aff is acyclic.  Thus case 4.2.8 is impossible.

Since both cases are impossible, the contrary assumption that D is not empty cannot 
hold, which means D must be empty.  Next we show (x,y)Aff.  Suppose not.  
Since V(x,y) > V(y,x), (x,y)M.  Since (x,y)M\Aff, by inspection of the definition 
of Aff there must exist a sequence of alternatives a1,a2,...,akA such that a1 = y  
and ak = x and both of the following conditions hold: 

(4.2.9)  (aj,aj+1)Aff for all j ∈ {1,2,...,k-1}. 
(4.2.10)  RP orders (aj,aj+1) over (x,y) for  all j ∈ {1,2,...,k-1}. 

By 4.2.9, (y,a2)Aff.  Thus, since D is empty, this implies (x,a2)Aff.  Since 
(x,a2)Aff and (aj,aj+1)Aff for all j ∈ {2,3,...,k-1} and ak = x, Aff is cyclic.  
But by lemma 1.6, Aff is acyclic.  The contradiction means the contrary assumption 
cannot hold, establishing (x,y)Aff.  By lemma 1.7, r must order x over y.  Thus 
r complies with Strong Pareto.  It was established in the proof of theorem 1 that 
r complies with IMC.  Thus lemma 4.2 has been established.     QED 

Having shown above that r0 can always be constructed so it complies with Strong Pareto, 
it follows by lemma 4.2 that there always exists a social ordering that complies with 
both Strong Pareto and IMC.  Thus, in the domain of votes such that only one social 
ordering complies with IMC, satisfaction of IMC implies satisfaction of Strong Pareto.  

Next we show satisfaction of Monotonicity, which requires that w must still be chosen if 
the relative ranking of all x,yA distinct from w is not changed in any vote and w is not 
lowered in any vote.

Next we show satisfaction of Anonymity, which requires the outcome must not change if 
any two voters swap votes.

Next we show satisfaction of Neutrality, which requires that if any two alternatives are 
switched in every vote, the social ordering must be unchanged except those same two 
alternatives are switched in the social ordering.

Next we show satisfaction of Homogeneity, which requires that if x is chosen given a 
set of votes R, then x must be chosen given R+R

Next we show satisfaction of Local Independence of Irrelevant Alternatives, which requires
that for all BA contiguous in the social ordering, the relative ordering of B remains the
same if all alternatives not in B are deleted from consideration.  Let r denote the social
ordering.  Assume BA is contiguous in r.  Let r' denote the social ordering when
all alternatives not in B are deleted from consideration.  Let r|B denote the restriction
of r to B. (That is, r|B is the same as r except all alternatives not in B are deleted.) 
We must show r|B = r'.  Suppose the contrary. 

Next we show satisfaction of Independence of Clones, which requires that, for all CA 
such that #C ≥ 2 and no voter ranks any alternative in A\C between any alternatives in C
if any strict subset C0C is dropped from all votes, then for all xC\C0 and all yA\C 
the relative social ordering of x and y must be unchanged.

Proof of theorem 5:  Refer to the definitions of MAM() and Rsocial() in the document 
"MAM Formal Definition."  We must show that MAM satisfies IMC, IMC2, IMC2a, 
I2C and I2Ca, and that all social  orderings natural to MAM (techniques 4, 5 and 6 
listed above) agree.  Pick any σ ∈ L(R,A).  Make the following abbreviations:  

Maj = Majorities(A,R).  
For all x,yA, Precede(x,y) = Precede(x,y,A,R,σ). 
Aff = Affirmed(A,R,σ).  
w = MAM(A,R,σ). 
r = Rsocial(A,R,σ).

By inspection of the definition of Rsocial(), r must be a strict ordering of A.  

First we show MAM satisfies IMC.  Assume V(x,y) > V(y,x) and r does not order y over x.  
We must show there exists a sequence of alternatives a1,a2,...,akA such that a1 = y and 
ak = x and all three of  the following conditions hold for all j ∈ {1,2,...,k-1}: 

(5.1.1)  V(aj,aj+1) > V(x,y) or [ V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(5.1.2)  V(aj,aj+1) > V(aj+1,aj).
(5.1.3)  r orders aj over aj+1.

Since r orders y over x, it follows by theorem "Properties of RSocial (3)" (proved in 
the document "Theorems Used in Proofs About MAM") that (x,y) ∉ Aff.  Since 
V(x,y) > V(y,x), (x,y) ∈ Maj.  Since (x,y) ∈ Maj\Aff,  by inspection of the definition 
of Affirmed() (x,y) must be inconsistent  with Aff ∩ Precede(x,y).  This means there 
exists a sequence of alternatives a1,a2,...,akA such that a1 = y and ak = x and, 
letting P denote {(a1,a2),(a2,a3),...,(ak-1,ak)}, P ⊆ Aff ∩ Precede(x,y).  Since 
P ⊆ Precede(x,y), by inspection of the definition of Precede()  it follows that, 
for all j ∈ {1,2,...,k-1}, either V(aj,aj+1) > V(x,w) or [V(aj,aj+1) = V(x,w) and 
V(aj+1,aj) ≤ V(w,x)].  Thus condition 5.1.1 must hold for the sequence a1,a2,...,ak.  
By inspection of the definition of Affirmed(), Aff ⊆ Maj.  Therefore P ⊆ Maj.  
This implies (aj,aj+1) ∈ Maj  for all j ∈ {1,2,...,k-1}.  Thus condition 5.1.2 must hold 
for a1,a2,...,ak.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order 
aj over aj+1 for  all j ∈ {1,2,...,k-1}.  Thus condition 5.1.3 must hold for a1,a2,...,ak.  
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a1,a2,...,ak   and since a1 = w and ak = x
it follows that MAM satisfies IMC.  

Next we show MAM satisfies IMC2.  By inspection of the definition of Rsocial(), it is 
clear that the MAM social ordering is constructed according to natural technique 6.  
Therefore, since it has been established that MAM satisfies IMC, it follows that 
MAM satisfies IMC2.  

Next we show that all social orderings natural to MAM (techniques 4, 5 and 6 listed 
above) agree.  More formally, we show that the following three social orderings 
are the same:

Next we show MAM satisfies IMC2a.  This follows immediately from the previous 
results that MAM satisfies IMC2 and all social  orderings natural to MAM agree.

Next we show MAM satisfies I2C.  Since MAM satisfies Local Independence of 
Irrelevant Alternatives, it follows immediately that MAM satisfies I2C.  Actually, 
a caveat must be mentioned:  

 

 (and then we will show MAM satisfies a less ambiguous 
wording of I2C that may be considered more generous): Since chance may play a 
role in MAM's choice, there are some scenarios where, if the chance element in the 
identification of the second place alternative is independent of the chance element 
used to identify the chosen alternative, then I2C does not strictly hold.  Consider the 
following scenario: 

Scenario B1:  MAM and I2C when chance plays a role. 
5 voters rank four alternatives {a,b,w,x} as follows:

1 1 1 1 1
w w x a b
a x b b x
b a a x w
x b w w a

 

In scenario B1 it can be seen that all six pairings have majorities of 3 to 2.  Thus the 
precedence of the majorities depends on chance, and it can be checked that there is 
a 1/5 chance that MAM chooses w.  That would happen if the left-most vote is picked 
first by the Random Voter Hierarchy procedure, since then the majority precedence 
order would be "b over x", "a over b", "w over a", "x over a", "b over w", "x over w."  
Given this majority precedence order, MAM affirms "b over x", "a over b", and 
"w over a", producing the social ordering "w over a over b over x." (If instead the 
second vote is picked first, x would top the social ordering.  If the third vote is picked 
first, b would top the social ordering.  If the fourth vote is picked first, a would top 
the social ordering.  If the fifth vote is picked first, b would top the social ordering.  
Thus there is a 1/5 chance that MAM chooses x, a 1/5 chance MAM chooses a, and 
a 2/5 chance MAM chooses b.)  Clearly the social ordering "w over a over b over x
satisfies Local Independence of Irrelevant Alternatives and does not show a failure of I2C.  

If the Random Voter Hierarchy procedure picks votes in the same order when identifying 
the chosen alternative and the second alternative for testing I2C compliance, then it could 
be said that MAM satisfies I2C.  But if I2C is not generously interpreted, different votes 
could conceivably be picked "first" by Random Voter Hierarchy when identifying the 
chosen alternative and the second place alternative.  Suppose the left-most vote is picked 
first when identifying the chosen alternative, so w is identified as the chosen alternative.  
Suppose also that the second vote or third vote is picked "first" when identifying the 
second alternative.  It can be checked that MAM would choose x if w were dropped 
from all the votes and Random Voter Hierarchy picks the second vote or third vote.  
Since a majority rank x over w, it might be said that MAM does not strictly satisfy I2C, 
if the chance elements when identifying the chosen alternative and the second alternative 
are allowed to be treated independently of each other.  

(If strict satisfaction of I2C is considered more important than strict satisfaction of 
Anonymity and Neutrality, MAM could be slightly altered to be entirely deterministic.  
Where MAM uses a random voter hierarchy, it could instead use a non-random hierarchy 
such as a seniority system.  Where MAM uses a random ordering of the alternatives, it 
could instead use a non-neutral fixed ordering of the alternatives such as the time of 
nomination or alphabetical order.)  

We next show that MAM satisfies a less ambiguous wording of I2C that may be 
considered slightly weaker than I2C: 

For all xA, let ρ(x) denote the probability x is chosen by the voting rule.  

For all x,yA, let ρ(y-x) denote the probability y would be chosen by the voting 
rule if x were dropped from each voter's vote. 

I2C':  For all w,xA, V(x,w) must not exceed V(w,x) if any of the following 
three conditions holds: 

(5.2.1)  ρ(w) = 1 and ρ(x-w) > 0. 
(5.2.2)  ρ(w) > 0 and ρ(x-w) = 1. 
(5.2.3)  ρ(w) > 0 and ρ(x-w) > 0 and ρ(x) = 0. 

Proof MAM satisfies I2C':  Pick any w,xA.  Assume at least one of conditions 5.2.1, 
5.2.2, or 5.2.3 holds.  We must show V(x,w) ≤ V(w,x).  Suppose the contrary.  Let R|-w 
denote the restriction of the votes to A\{w}.  That is, R|-w is the same as R except w is 
dropped from each vote in R.  Make the following abbreviations:  

 

Since V(x,w) > V(w,x), (x,w) ∈ Maj.  There are three cases to consider: 

Case 5.2.4:  Condition 5.2.1 holds.  Since ρ(x-w) > 0, we can pick σ ∈ L(R,A) such 
that MAM(A,R|-w,σ) = x.  Since ρ(w) = 1, this means w is chosen with certainty, 
which implies MAM(A,R,σ) = w.  This implies (x,w)Affirmed(A,R,σ). 

Case 5.2.5:  Condition 5.2.2 holds.  Since ρ(w) > 0, we can pick σ ∈ L(R,A) such 
that MAM(A,R,σ) = w.  Since ρ(x-w) = 1, this means x would be chosen with certainty 
if w were dropped from each vote, which implies MAM(A,R|-w,σ) = x.  

Case 5.2.6:  Condition 5.2.3 holds.

Since all three cases are impossible, this implies the contrary assumption cannot hold, 
which means V(x,w) ≤ V(w,x).  Thus MAM satisfies I2C'.

Abbreviate A' = A\{w} and R' = R|A\{w}.  Assume MAM(A',R',σ') = x for 
all σ'L(R',A'). (Thus x is chosen with certainty from A\{w} by MAM given R'.)  
We must establish V(w,x) ≥ V(x,w).  Suppose to the contrary V(w,x) < V(x,w).  
Pick σ'L(R',A') such that σ' =  σ|A'.  Make the following abbreviations:  

Maj = Majorities(A,R).  
Maj' = Majorities(A',R').  
RVH = RVH(A,R,σ). 
RVH' = RVH(A',R',σ'). 
For all a,bA, Precede(a,b) = Precede(a,b,A,R,σ). 
For all a,bA', Precede'(a,b) = Precede(a,b,A',R',σ'). 
Aff = Affirmed(A,R,σ). 
Aff' = Affirmed(A',R',σ'). 

Since V(w,x) < V(x,w), (x,w) ∈ Maj and (w,x) ∉ Maj.  Since MAM(A,R,σ) = w, by 
the definition of MAM() this implies w is not second in any pair in Aff.  Thus (x,w) ∉ Aff.  
Since (x,w) ∈ Maj\Aff, (x,w) must be inconsistent with Aff ∩ Precede(x,w).  Thus there 
must exist (a1,a2),(a2,a3),...,(ak-1,ak) ∈ Aff ∩ Precede(x,w) such that a1 = w and ak = x.  
By the definition of Affirmed(), Aff ⊆ Maj.  Thus (ak-1,x) ∈ Maj.  Therefore ak-1w
which implies ak-1A' and (ak-1,x) ∈ Maj'.  Since MAM(A',R',σ') = x, this implies x 
is not second in any pair in Aff'.  Therefore (ak-1,x) ∉ Aff'.  Since (ak-1,x) ∈ Maj'\Aff'
(ak-1,x) must be inconsistent with Aff' ∩ Precede'(ak-1,x).  Thus there must exist 
(b1,b2),(b2,b3),...,(bj-1,bj) ∈ Aff' ∩ Precede'(ak-1,x) such that b1 = x and bj = ak-1.  
Let P denote {(b1,b2),(b2,b3),...,(bj-1,bj)}.  By theorem "Consistency Maintained (2)"
Aff must be internally consistent.  Thus since (ak-1,x) ∈ Aff there must exist (b,b')P  
such that (b,b') ∉ Aff.  Let P2 denote the pairs in Aff' or in Aff ∩ Pairs(A') but not 
in both.  Since (b,b') ∈ Aff'\Aff, (b,b')P2.  Since P2 is not empty, by theorem 
"Precedence is a Strict Ordering"
we can pick (y,y')P2 such that the following 
condition holds:

(5.3.1)  For all (z,z')P2, (z,z') ∉ Precede'(y,y').

There are two cases to consider: 

Case 5.3.2:  (y,y') ∈ Aff'\Aff.  Since (y,y') ∈ Aff', (y,y') ∈ Maj'.  Thus (y,y') ∈ Maj.  
Since (y,y') ∈ Maj\Aff, (y,y') must be inconsistent with Aff ∩ Precede(y,y').  
This implies there exist (c1,c2),(c2,c3),...,(ch-1,ch) ∈ Aff ∩ Precede(y,y'
such that c1 = y' and ch = y.  Let P3 denote {(c1,c2),(c2,c3),...,(ch-1,ch)}.  
There are two subcases to consider:

Case 5.3.2.1:  w ∈ {c1,c2,...,ch}.  Since c1A' and wA', this implies 
w ∈ {c2,...,ch}.  Therefore w must be second in at least one pair in P3.  But 
since P3 ⊆ Aff and w is not second in any pair in Aff, this is a contradiction.  
Therefore subcase 5.3.2.1 is impossible. 

Case 5.3.2.2:  w ∉ {c1,c2,...,ch}.  This implies P3Pairs(A').  Since P3 ⊆ Aff, 
P3 ⊆ Maj.  Since P3Pairs(A') ∩ Maj, P3 ⊆ Maj'.  By theorem "Consistency 
Maintained (2)"
, Aff' must be internally consistent.  Therefore, since (y,y') ∈ Aff'  
there must exist (c,c')P3 such that (c,c') ∉ Aff'.  Since (c,c') ∈ Aff\Aff' and 
(c,c')Pairs(A'), (c,c')P2.  Since σ' =  σ|A' and (c,c') ∈ Precede(y,y'), 
by theorem "Precedence is Independent of Irrelevant Alternatives" 
(c,c') ∈ Precede'(y,y').  Since (c,c')P2 and (c,c') ∈ Precede'(y,y'), 
this contradicts 5.3.1.  Therefore subcase 5.3.2.2 is impossible.

Since both subcases 5.3.2.1 and 5.3.2.2 are impossible, case 5.3.2 is impossible.

Case 5.3.3:  (y,y') ∉ Aff'\Aff.  Since (y,y')P2, this implies (y,y') ∈ Aff ∩ Pairs(A'
and (y,y') ∉ Aff'.  Since (y,y') ∈ Aff, (y,y') ∈ Maj.  Since (y,y') ∈ Maj ∩ Pairs(A'), 
this implies (y,y') ∈ Maj'.  Since (y,y') ∈ Maj'\Aff', by the definition of Affirmed() 
(y,y') must be inconsistent with Aff' ∩ Precede'(y,y').  Therefore there must exist 
(c1,c2),(c2,c3),...,(ch-1,ch) ∈ Aff' ∩ Precede'(y,y') such that c1 = y' and ch = y.  
Let P3 denote {(c1,c2),(c2,c3),...,(ch-1,ch)}.  By theorem "Consistency Maintained (2)"
Aff must be internally consistent.  Thus since (y,y') ∈ Aff there must exist (c,c')P3  
such that (c,c') ∉ Aff.  Since (c,c') ∈ Aff'\Aff, (c,c')P2.  Since (c,c')P2 and 
(c,c') ∈ Precede'(y,y'), this contradicts 5.3.1.  Thus case 5.3.3 is impossible. 

Since both cases 5.3.2 and 5.3.3 are impossible, the contrary assumption cannot hold.  
Therefore V(w,x) ≥ V(x,w), establishing MAM satisfies I2C.

 

 

 

Let x denote an alternative that has a non-zero 
chance of being chosen by MAM if w is dropped from all the votes.  We must show 
V(w,x) ≥ V(x,w).  Suppose to the contrary that V(x,w) > V(w,x).  Thus (x,w) ∈ Maj.  
By inspection of the definition of MAM, w is not second in any ordered pair in Aff.  
Thus (x,w) ∉ Aff.  Since (x,w) ∈ Maj\Aff, it follows by inspection of the definition 
of Affirmed() that (x,w) must be inconsistent with Aff ∩ Precede(x,w).  This means 
there exists a sequence of alternatives a1,a2,...,akA such that a1 = y and ak = x 
and, letting P denote {(a1,a2),(a2,a3),...,(ak-1,ak)}, P ⊆ Aff ∩ Precede(x,w).  
Since P ⊆ Precede(x,w), by inspection of the definition of Precede()  it follows 
that, for all j ∈ {1,2,...,k-1}, either V(aj,aj+1) > V(x,w) or [ V(aj,aj+1) = V(x,w
and V(aj+1,aj) ≤ V(w,x)].  

 

Thus condition 5.1.1 must hold for the sequence a1,a2,...,ak.  
By inspection of the definition  of Affirmed(), Aff ⊆ Maj.  Therefore P ⊆ Maj.  
This implies (aj,aj+1) ∈ Maj  for all j ∈ {1,2,...,k-1}.  Thus condition 5.1.2 must hold 
for a1,a2,...,ak.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order 
aj over aj+1 for  all j ∈ {1,2,...,k-1}.  Thus condition 5.1.3 must hold for a1,a2,...,ak.  
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a1,a2,...,ak   and since a1 = w and ak = x
it follows that MAM satisfies I2C. 

 


Since  chooses Assume V(x,w) > V(w,x) and r does not order y over x.  
We must show there exists a sequence of alternatives a1,a2,...,akA such that a1 = y  
and ak = x and all three of  the following conditions hold for all j ∈ {1,2,...,k-1}: 

(5.2.1)  V(aj,aj+1) > V(x,y) or [ V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(5.2.2)  V(aj,aj+1) > V(aj+1,aj).
(5.2.3)  r orders aj over aj+1.

Since r orders y over x, it follows by theorem "Properties of RSocial (3)" (proved in 
the document "Theorems Used in Proofs About MAM") that (x,y) ∉ Aff.  Since 
V(x,y) > V(y,x), (x,y) ∈ Maj.  Since (x,y) ∈ Maj\Aff,  by inspection of the definition 
of Affirmed() (x,y) must be inconsistent  with Aff ∩ Precede(x,y).  This means there 
exists a sequence of alternatives a1,a2,...,akA such that a1 = y and ak = x and, 
letting P denote {(a1,a2),(a2,a3),...,(ak-1,ak)}, P ⊆ Aff ∩ Precede(x,y).  Since 
P ⊆ Precede(x,y), by inspection of the definition of Precede()  it follows that, 
for all j ∈ {1,2,...,k-1}, either V(aj,aj+1) > V(x,w) or [ V(aj,aj+1) = V(x,w) and 
V(aj+1,aj) ≤ V(w,x)].  Thus condition 5.1.1 must hold for the sequence a1,a2,...,ak.  
By inspection of the definition  of Affirmed(), Aff ⊆ Maj.  Therefore P ⊆ Maj.  
This implies (aj,aj+1) ∈ Maj  for all j ∈ {1,2,...,k-1}.  Thus condition 5.1.2 must hold 
for a1,a2,...,ak.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order 
aj over aj+1 for  all j ∈ {1,2,...,k-1}.  Thus condition 5.1.3 must hold for a1,a2,...,ak.  
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a1,a2,...,ak   and since a1 = w and ak = x
it follows that MAM satisfies I2C.

 

By inspection of the definition of Rsocial(), it is clear that the MAM social ordering is 
constructed according to technique 6.  Thus, since MAM satisfies IMC, it follows 
that MAM satisfies I2C.  

 

QED 

Proof of theorem 6:  First we establish the following lemma: 

(6.1)  The "larger than" and "at least as large as" relations are transitive.  

Proof of 6.1:  By inspection, the "larger than" and "at least as large as" relations are 
binary relations on Pairs(A).  First we show "larger than" is transitive.  Assume (x,y) is 
larger than (z,w) and (z,w) is larger than (a,b).  We must show (x,y) is larger than (a,b).  
Since (x,y) is larger than (z,w), the following condition must hold: 

(6.1.1)  V(x,y) > V(z,w) or [V(x,y) = V(z,w) and V(y,x) < V(w,z)]. 

Since (z,w) is larger than (a,b), the following condition must hold: 

(6.1.2)  V(z,w) > V(a,b) or [V(z,w) = V(a,b) and V(w,z) < V(b,a)]. 

By inspection of 6.1.1 and 6.1.2, the following condition must hold: 

(6.1.3)  V(x,y) > V(a,b) or [V(x,y) = V(a,b) and V(y,x) < V(b,a)]. 

By 6.1.3, (x,y) is larger than (a,b).  Thus the "larger than" relation is transitive.  
Next we show "at least as large as" is transitive.  Assume (x,y) is at least as large 
as (z,w) and (z,w) is at least as large as (a,b).  We must show (x,y) is at least as large 
as (a,b).  Since (x,y) is at least as large as (z,w), the following condition must hold: 

(6.1.4)  V(x,y) > V(z,w) or [V(x,y) = V(z,w) and V(y,x) ≤ V(w,z)]. 

Since (z,w) is at least as large as (a,b), the following condition must hold: 

(6.1.5)  V(z,w) > V(a,b) or [V(z,w) = V(a,b) and V(w,z) ≤ V(b,a)]. 

By inspection of 6.1.4 and 6.1.5, the following condition must hold: 

(6.1.6)  V(x,y) > V(a,b) or [V(x,y) = V(a,b) and V(y,x) ≤ V(b,a)]. 

By 6.1.6, (x,y) is at least as large as (a,b).  Thus "at least as large as" is transitive.   QED 

(We could have established further that the "at least as large as" relation is an ordering and 
that the "larger than" relation is irreflexive and asymmetric, but these results are not needed 
to prove the theorem at hand.)

Resuming the proof of 6...  Assume IMC is satisfied.  This implies the voting procedure 
socially orders the alternatives.  Let TMs denote the majorities thwarted by the social 
ordering.  Assume TMs is not empty.  Thus, by 6.1 we can let (x,y) denote a pair in TMs 
such that no pair in TMs is larger than (x,y).  Pick any rO(A).  Let TM(r) denote the 
set of majorities thwarted by r.  We must show TM(r) is not empty and that the largest 
pair in TM(r) is at least as large as (x,y).  Since (x,y) ∈ TMs, both of the following 
statements must hold: 

(6.2)  V(x,y) > V(y,x). 
(6.3)  x is not socially ordered over y.  

Since IMC is satisfied, by 6.2 and 6.3 there must exist a sequence a1,a2,...,akA such that 
a1 = y and ak = x and all three of the following conditions hold for all j ∈ {1,2,...,k-1}: 

(6.4)  V(aj,aj+1) > V(x,y) or [V(aj,aj+1) = V(x,y) and V(aj+1,aj) ≤ V(y,x)].  
(6.5)  V(aj,aj+1) > V(aj+1,aj).
(6.6)  aj is socially ordered over aj+1.

There are two cases to consider: 

Case 6.7:  r orders aj over aj+1 for all j ∈ {1,2,...,k-1}.  Since rO(A), r is transitive.  
Thus, by induction r must order a1 over ak.  This implies (x,y) ∈ TM(r).  

Case 6.8:  There exists j ∈ {1,2,...,k-1} such that r does not order aj over aj+1.  
By 6.5, (aj,aj+1) ∈ TM(r).  By 6.4, (aj,aj+1) is at least as large as (x,y).  

In both cases there exists at least one pair in TM(r) that is at least as large as (x,y).  
Thus, by 6.1 the largest majority thwarted by r must be at least as large as the largest 
majority thwarted by the social ordering.  Thus the theorem is established.     QED