Immunity from Majority Complaints

This paper presents a strong criterion, immunity from majority complaints (IMC),
which 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 may occur 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, anonymity, neutrality, resolvability, 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:

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 which do not permit voters to completely express their orders of
preference, such as "Vote for One, Plurality Rule" and "Approval" (which lets each voter
to 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 which prefers 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 which prefers 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 which differs from "a over b over c."
This is a matter of consistency: If the principles which 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 which is "natural" for the voting procedure. For instance, the following
six techniques are fairly obvious:

1. For procedures which 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 which eliminate alternatives one at a time, it is natural to
order the alternatives in the reverse of the elimination order.

3. For procedures which 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 which distinguish an acyclic subset of the pairwise majorities,
it is natural to construct a social ordering consistent with the acyclic subset.

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

6. In general, given any procedure which 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 which 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 which are hard to rebut could undermine the winner's
mandate, and could undermine confidence in the voting procedure, particularly if there
exists another procedure which 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.

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

For all non-empty B Í A, 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,y Î B}.)

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 which is not socially ordered below any alternative,
and for all x,y Î A such that [V(x,y) > V(y,x) and x is not socially ordered over y]
there must exist a sequence of alternatives a₁,a₂,...,a_k Î A such that a₁ = y and
a_k = x and all three of the following conditions hold:

(1) (a_j,a_j+1) is at least as large as (x,y) for all j Î {1,2,...,k-1}.
(2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j) for all j Î {1,2,...,k-1}.
(3) a_j is socially ordered over a_j₊₁ 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 which 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
"a₁ over a₂," "a₂ over a₃," ..., and "a_k_-1 over a_k" which are each at least as large as the
majority who may complain a_k should have finished over a₁ (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 x Î A such that V(x,w) > V(w,x)
there must exist a sequence of alternatives a₁,a₂,...,a_k Î A such that a₁ = w and
a_k = x and all three of the following conditions hold:

1. (a_j,a_j+1) is at least as large as (x,w) for all j Î {1,2,...,k-1}.
2. V(a_j,a_j₊₁) > V(a_j₊₁,a_j) for all j Î {1,2,...,k-1}.
3. a_j is socially ordered over a_j₊₁ 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 x. IMC2 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 which disagrees with the official social ordering and thereby start an
argument which 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:

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 which 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 which 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 which 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)
which 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 which satisfies resolvability is usually deterministic.
This implies IMC is nearly a complete characterization of the voting procedures which
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,y Î A. Say every cycle has only one smallest majority if and only if, for all
sequences of alternatives a₁,a₂,...,a_k Î A such that [a₁ = a_k and a₁,a₂,...,a_k_-1 are
distinct and V(a_j,a_j₊₁) > V(a_j₊₁,a_j) for all j Î {1,2,...,k-1}], there exists a unique
h Î {1,2,...,k-1} such that (a_j,a_j+1) is larger than (a_h,a_h₊₁) 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 Pareto, monotonicity, anonymity, neutrality, homogeneity,
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,
anonymity, neutrality, 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 r Î O(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 r Î O(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.")

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

Many prominent voting procedures fail IMC, IMC2 and I2C. The examples which 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 which 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 which
also show failures of I2C, and moreover in these examples the alternative used to show
failure of I2C is a Condorcet winner which finishes second in a natural social ordering.

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

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:

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 which,
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:

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:

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:

Copeland scores for each alternative the number of pairings in which the votes which rank
it over its pairwise opponent exceed the votes which 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 elect 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:

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 which 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 which 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:

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
which 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

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:

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 which 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:

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
which tops 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 which needs checking is "x over w over a over b" and the only
strict ordering trailed by x which needs checking is "w over a over b over x." Similarly,
the only strict ordering topped by w which needs checking is "w over a over b over x" and
the only strict ordering trailed by w which needs checking is "a over b over x over w."
The only strict ordering topped by a which needs checking is "a over x over w over b" and
the only strict ordering trailed by a which needs checking is "x over w over b over a."
The only strict ordering topped by b which needs checking is "b over x over w over a" and
the only strict ordering trailed by b which 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 which 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:

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:

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:

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 which can rebut that majority is w,a,b,x; thus the
only ordering which 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 which
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.

Proof of theorem 1: We must show there is always at least one social ordering that is
capable of satisfying IMC. Let r₀ denote some strict ordering of A. (The manner in
which r₀ is constructed does not matter for theorem 1, but it is possible to construct r₀
so r₀ 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 R_P denote the binary relation on P such that, for all (x,y),(z,w) Î P,
R_P 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 r₀ ranks w over y.
(1.4) V(x,y) = V(z,w) and V(y,x) = V(w,z) and w = y and r₀ ranks x over z.

(Clearly R_P depends only on R and r₀.) We next establish the following lemma:

Proof of 1.5: We must show R_P is complete, irreflexive, asymmetric and transitive.
To show completeness, pick any distinct (x,y),(z,w) Î P and assume R_P does not
rank (x,y) over (z,w). We must show R_P ranks (z,w) over (x,y). Clearly none
of 1.1, 1.2, 1.3 or 1.4 hold. Since r₀ 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 r₀ ranks y over w.
(1.5.4) V(z,w) = V(x,y) and V(w,z) = V(y,x) and w = y and r₀ ranks z over x.

It follows by the definition of R_P that R_P ranks (z,w) over (x,y); thus R_P is complete.
To show irreflexivity, pick any (x,y) Î P. We must show R_P 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) r₀ ranks y over y.
(1.5.8) r₀ ranks x over x.

By the definition of R_P, R_P does not rank (x,y) over (x,y); thus R_P is irreflexive.
To show asymmetry, pick any two pairs (x,y),(z,w) Î P. Assume R_P ranks (x,y)
over (z,w). We must show R_P does not rank (z,w) over (x,y). Since one of 1.1,
1.2, 1.3 or 1.4 holds and since r₀ 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 r₀ ranks y over w.
(1.5.12) V(z,w) = V(x,y) and V(w,z) = V(y,x) and w = y and r₀ ranks z over x.

By the definition of R_P, R_P does not rank (z,w) over (x,y); thus R_P is asymmetric.
To show transitivity, pick any three pairs (x,y),(z,w),(u,v) Î P. Assume R_P ranks
(x,y) over (z,w) and (z,w) over (u,v). We must show R_P ranks (x,y) over (u,v).
Since R_P ranks (x,y) over (z,w), one of 1.1, 1.2, 1.3 or 1.4 must hold.
Since R_P 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 r₀ ranks v over w.
(1.5.16) V(z,w) = V(u,v) and V(w,z) = V(v,u) and v = w and r₀ ranks z over u.

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 R_P 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 R_P 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: y ¹ w and w ¹ v. This implies r₀ orders w over y and
r₀ orders v over w. Since r₀ is a strict ordering, r₀ must order v over y.
This implies y ¹ v. Since V(x,y) = V(u,v) and V(y,x) = V(v,u)
and r₀ orders v over y, it follows that R_P ranks (x,y) over (u,v).

Case 1.5.19.2: y ¹ w and w = v. This implies r₀ orders w over y, and
thus r₀ orders v over y. Since V(x,y) = V(u,v) and V(y,x) = V(v,u)
and r₀ orders v over y, it follows that R_P ranks (x,y) over (u,v).

Case 1.5.19.3: y = w and w ¹ v. This implies r₀ orders v over w, and
thus r₀ orders v over y. Since V(x,y) = V(u,v) and V(y,x) = V(v,u)
and r₀ orders v over y, it follows that R_P ranks (x,y) over (u,v).

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

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

Since in all three cases R_P ranks (x,y) over (u,v), R_P must be transitive. Since R_P is
complete, irreflexive, asymmetric and transitive, R_P 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
a₁,a₂,...,a_k Î A such that a₁ = y and a_k = x and [(a_j,a_j+1) Î AffirmedMajorities for
all j Î {1,2,...,k-1}] and [R_P orders (a_j,a_j+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:

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 = x₁,x₂,...,x_c Î A such that
x₁ = x_c and (x_j,x_j+1) Î Aff for all j Î {1,2,...,c-1}. (Clearly c ³ 4.) Since R_P is
a strict ordering of P and Maj Í P, there must exist h Î {1,2,...,c-1} such that
R_P orders (x_j,x_j+1) over (x_h,x_h₊₁) for all j Î {1,2,...,c-1}. Let s' denote the
sequence of alternatives constructed from s by first dropping x_c and then rotating
the remainder so x_h₊₁ is first and x_h is last. Thus we can relabel the alternatives
so s' = a₁,a₂,...,a_k where k = c-1 and [a_j = x_j_+h for all j Î {1,2,...,k-h)}] and
[a_j = x_j_+h-k for all j Î {1+k-h,2+k-h,...,k}]. Clearly a₁,a₂,...,a_k is a sequence of
alternatives such that a₁ = x_h₊₁ and a_k = x_h and (a_j,a_j+1) Î Aff all j Î {1,2,...,k-1}
and R_P orders (a_j,a_j+1) over (x_h,x_h₊₁) for all j Î {1,2,...,k-1}. By the definition
of Aff this implies (x_h,x_h+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 which 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 B Í A. (The ordered pairs
of alternatives in B.)

For all n Î {1,2,...,#A}, let T_n denote {x Î B_n such that x is not the second
alternative in any ordered pair in P(B_n) Ç Aff}.
For all n Î {1,2,...,#A}, let W_n denote {x Î T_n such that r₀ orders no y Î T_n over x}.

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

Proof of 1.7: Since Aff is acyclic, P(B) Ç Aff must be acyclic for all non-empty B Í A.
This implies that for all non-empty B Í A there exists at least one x Î B such that x is
not second in any ordered pair in P(B) Ç Aff.  This implies T_n is not empty for all
n Î {1,2,...,#A}. Thus, since r₀ is a strict ordering, W_n must be a singleton for all
n Î {1,2,...,#A}. Also, clearly W_m ¹ W_n 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 W_n = {x} or W_n = {y}. We must show W_n = {x} and y Î B_n. By the
definition of n, clearly {x,y} Í B_n.  Thus (x,y) Î P(B_n). Since (x,y) Î P(B_n) Ç Aff,
this means y is the second alternative in an ordered pair in P(B_n) Ç Aff. Thus y Ï T_n,
which implies W_n ¹ {y}, which implies W_n = {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,y Î A 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 a₁,a₂,...,a_k Î A such that a₁ = y and a_k = x and all three of the following
conditions hold for all j Î {1,2,...,k-1}:

(1.8) V(a_j,a_j₊₁) > V(x,y) or [ V(a_j,a_j₊₁) = V(x,y) and V(a_j₊₁,a_j) £ V(y,x)].
(1.9) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(1.10) r orders a_j over a_j₊₁.

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 a₁,a₂,...,a_k Î A such that all three of the following conditions hold:

(1.11) a₁ = y and a_k = x.
(1.12) (a_j,a_j+1) Î Aff for all j Î {1,2,...,k-1}.
(1.13) R_P orders (a_j,a_j+1) over (x,y) for all j Î {1,2,...,k-1}.

By inspection of the definition of R_P, 1.13 implies 1.8 holds for a₁,a₂,...,a_k. By
inspection of the definition of Aff, Aff Í M. Therefore, 1.12 implies 1.9 holds
for a₁,a₂,...,a_k. Since r orders a over b for all (a,b) Î Aff, 1.12 implies 1.10 holds
for a₁,a₂,...,a_k. Since a₁ = y and a_k = x and 1.8, 1.9 and 1.10 all hold for a₁,a₂,...,a_k,
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 B Í A such
that V(b,a) > V(a,b) for all b Î B and all a Î A\B. Suppose to the contrary w Ï tc.
Since tc is not empty, we can pick t Î tc such that no t' Î tc is socially ordered over t.
Clearly V(t,w) > V(w,t). By IMC there must exist a sequence a₁,a₂,...,a_k Î A such that
a₁ = w and a_k = t and all three of the following conditions hold for all j Î {1,2,...,k-1}:

(2.1.1) V(a_j,a_j₊₁) > V(t,w) or [ V(a_j,a_j₊₁) = V(t,w) and V(a_j₊₁,a_j) £ V(w,t)].
(2.1.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(2.1.3) a_j is socially ordered over a_j₊₁.

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

Satisfaction of Top Cycle implies Condorcet-consistency, which requires that if there
exists x Î A such that [V(x,y) > V(y,x) for all y Î A\{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,y Î A, 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:

By IMC, there must exist a sequence a₁,a₂,...,a_k Î A such that a₁ = y and a_k = x and
all three of the following conditions hold for all j Î {1,2,...,k-1}:

(2.2.3) V(a_j,a_j₊₁) > V(x,y) or [ V(a_j,a_j₊₁) = V(x,y) and V(a_j₊₁,a_j) £ V(y,x)].
(2.2.4) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(2.2.5) a_j is socially ordered over a_j₊₁.

(2.2.6) V(a_j,a_j₊₁) = n and V(a_j₊₁,a_j) = 0 for all j Î {1,2,...,k-1}.

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

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 the largest 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(), L Í D Ç Maj.
Pick any (x,y) Î L. Since L Í Ag, r must order x over y. Since L Í Ag and L Í D,
L Ç Ag' = f. 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
a₁,a₂,...,a_k Î A such that a₁ = y and a_k = x and all three of the following conditions
hold for all j Î {1,2,...,k-1}:

(2.3.1) V(a_j,a_j₊₁) > V(x,y) or [V(a_j,a_j₊₁) = V(x,y) and V(a_j₊₁,a_j) £ V(y,x)].
(2.3.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(2.3.3) r' orders a_j over a_j₊₁.

By 2.3.2, (a_j+1,a_j) Î Maj for all j Î {1,2,...,k-1}. By 2.3.3, (a_j+1,a_j) Î Ag' for all
j Î {1,2,...,k-1}. Since L Ç Ag' = f, this implies (a_j+1,a_j) Ï L for all j Î {1,2,...,k-1}.
It follows by 2.3.1 that (a_j+1,a_j) Ï D for all j Î {1,2,...,k-1}. This implies r orders a_j
over a_j₊₁ for all j Î {1,2,...,k-1}. Since r is an ordering, r must be transitiv; thus
r must order a₁ over a_k. 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 x Î A 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 r_x such that r_x is the social ordering and x is an alternative
atop r_x. (Note that r_x 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,b Î A, if r_x 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,b Î A,
let V'(a,b) denote the number of votes in R' which 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,b Î A such that r orders a over b.
(2.4.5) V'(a,b) = V(a,b) for all a,b Î A 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)}.

(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) Î D Ç Ag and V'(a,b) < V'(b,a) for all (a,b) Î D Ç Ag'.
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) Î L Ç Ag. Since L Í D, (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) Î D Ç Ag'.
This implies V'(a,b) > V'(z,w) for all (z,w) Î D Ç Ag'. 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.

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