Immunity from Majority Complaints

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, 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 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.

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 that 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 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
"a₁ over a₂," "a₂ over a₃," ..., and "a_k_-1 over a_k" that 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 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:

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

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

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

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:

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

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

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:

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

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 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 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(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(), 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' = ϕ. 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' = ϕ, 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' 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,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.

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 x ∈ A such
that there exists y ∈ A 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 a₁,a₂,...,a_k ∈ A such that a₁ = x and a_k = y
and all three of the following conditions hold for all j ∈ {1,2,...,k-1}:

(2.5.1) V(a_j,a_j₊₁) > V(y,x) or [V(a_j,a_j₊₁) = V(y,x) and V(a_j₊₁,a_j) ≤ V(x,y)].
(2.5.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(2.5.3) a_j is socially ordered over a_j₊₁.

Since more than half the voters rank x no better than tied for bottom, V(x,a₂) 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 x ∈ A
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
x ∉ tc and y ∈ tc and more than half of the votes rank y over x and, for all a,b ∈ A,
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 a₁,a₂,...,a_k ∈ A
such that a₁ = x and a_k = y and all three of the following conditions hold for all
j ∈ {1,2,...,k-1}:

(2.6.1) V(a_j,a_j₊₁) > V(y,x) or [ V(a_j,a_j₊₁) = V(y,x) and V(a_j₊₁,a_j) ≤ V(x,y)].
(2.6.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(2.6.3) a_j is socially ordered over a_j₊₁.

By the definition of the sincere top cycle, it follows that for all t ∈ tc and all z ∉ tc, 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 t ∈ tc and all z ∉ tc. Since a₁ ∉ tc and a_k ∈ tc, by induction there must
exist h ∈ {1,2,...,k-1} such that a_h ∉ tc and a_h₊₁ ∈ tc. Therefore V(a_h,a_h₊₁) < 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

Lemma 3.1: If IMC is satisfied, then for all x,y ∈ A 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 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}:

(3.1.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)].
(3.1.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(3.1.3) r orders a_j over a_j₊₁.

Since r is an ordering, r must be transitive. Therefore, by induction on 3.1.3,
r must order a₁ over a_k. 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,y ∈ A}.)
Let D denote the subset of P on which r and r' disagree. Since r ≠ r', 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 a₁,a₂,...,a_k ∈ A such that
a₁ = d' and a_k = d and all three of the following conditions hold for all j ∈ {1,2,...,k-1}:

(3.2.1) V(a_j,a_j₊₁) > V(d,d') or [V(a_j,a_j₊₁) = V(d,d') and V(a_j₊₁,a_j) ≤ V(d',d)].
(3.2.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(3.2.3) r' orders a_j over a_j₊₁.

Since a₁ = d' and a_k = d and V(d,d') > V(d',d), by 3.2.2 the sequence formed by
concatenating d' to the end of a₁,a₂,...,a_k 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(a_j,a_j₊₁) > V(d,d') or [V(a_j,a_j₊₁) = V(d,d') and V(a_j₊₁,a_j) < V(d',d)].

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

In other words, for all j ∈ {1,2,...,k-1}, r and r' must agree on the relative ordering of a_j
and a_j₊₁. Thus, by 3.2.3 r must order a_j over a_j₊₁ for all j ∈ {1,2,...,k-1}. Since r is
an ordering, r is transitive. It follows by induction that r orders a₁ over a_k. 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,y ∈ A such that r orders x equal to y. Let Y denote {a ∈ A\{x} such
that r orders x equal to a}. By lemma 3.1, V(a,x) = V(x,a) for all a ∈ E. 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 a ∈ E, 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,y ∈ A, 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 r₀. We will show that r₀ can
always be constructed so r₀ complies with Strong Pareto. Then we will show that if r₀
complies with Strong Pareto then the social ordering constructed from R and r₀ 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 r₀ can always be constructed to comply with Strong Pareto,
consider the following iterative procedure for constructing r₀:

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

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

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

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

Pick the unpicked vote ordered highest by r_V and call it v.
For all x,y ∈ A such that r₀ ranks x equal to y and v does not rank x equal to y,
amend r₀ so r₀ ranks x relative to y the same as v does.

If r₀ is not yet a strict ordering, then for all x,y ∈ A such that r₀ ranks x equal to y,
amend r₀ so r₀ ranks x relative to y the same as r_A does.

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

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

Proof of 4.2: Assume r₀ complies with Strong Pareto. Let r denote the social ordering
constructed from the votes and from r₀ 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 a ∈ A, 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 a ∈ A.
(4.2.2) V(a,x) ≤ V(a,y) for all a ∈ A.

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

(4.2.3) R_P orders (x,a) over (y,a) for all a ∈ A.
(4.2.4) R_P orders (a,y) over (a,x) for all a ∈ A.

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

{(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, R_P is a strict ordering
of Pairs(A). Thus, since D is not empty, we can pick the unique (z,z') ∈ D such that
R_P 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 a₁,a₂,...,a_k ∈ A such that a₁ = z' and a_k = x and both
of the following conditions hold:

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

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

Case 4.2.8: z ≠ y. 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 a₁,a₂,...,a_k ∈ A such that a₁ = y and a_k = z and
both of the following conditions hold:

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

By 4.2.3, R_P orders (x,a₂) over (y,a₂). By 4.2.8.2, R_P orders (y,a₂) over (z,y).
By 4.2.4, R_P orders (z,y) over (z,x). Thus, since R_P is a strict ordering, R_P must
order (x,a₂) over (z,x). Since R_P orders no pair in D over (z,x), this implies
(x,a₂) ∉ D. Thus since (y,a₂) ∈ Aff, (x,a₂) ∈ Aff. Since (x,a₂) ∈ Aff and
(a_j,a_j+1) ∈ Aff for all j ∈ {2,3,...,k-1} and (z,x) ∈ Aff and a_k = 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 a₁,a₂,...,a_k ∈ A such that a₁ = y
and a_k = x and both of the following conditions hold:

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

By 4.2.9, (y,a₂) ∈ Aff. Thus, since D is empty, this implies (x,a₂) ∈ Aff. Since
(x,a₂) ∈ Aff and (a_j,a_j+1) ∈ Aff for all j ∈ {2,3,...,k-1} and a_k = 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 r₀ 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,y ∈ A 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 B ⊆ A 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 B ⊆ A 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 C ⊆ A
such that #C ≥ 2 and no voter ranks any alternative in A\C between any alternatives in C,
if any strict subset C₀ ⊂ C is dropped from all votes, then for all x ∈ C\C₀ and all y ∈ A\C
the relative social ordering of x and y must be unchanged.

Proof of theorem 5: Refer to the definitions of MAM() and R_social() 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,y ∈ A, Precede(x,y) = Precede(x,y,A,R,σ).
Aff = Affirmed(A,R,σ).
w = MAM(A,R,σ).
r = R_social(A,R,σ).

By inspection of the definition of R_social(), 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 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}:

(5.1.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)].
(5.1.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(5.1.3) r orders a_j over a_j₊₁.

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 a₁,a₂,...,a_k ∈ A such that a₁ = y and a_k = x and,
letting P denote {(a₁,a₂),(a₂,a₃),...,(a_k_-1,a_k)}, 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(a_j,a_j₊₁) > V(x,w) or [V(a_j,a_j₊₁) = V(x,w) and
V(a_j₊₁,a_j) ≤ V(w,x)]. Thus condition 5.1.1 must hold for the sequence a₁,a₂,...,a_k.
By inspection of the definition of Affirmed(), Aff ⊆ Maj. Therefore P ⊆ Maj.
This implies (a_j,a_j₊₁) ∈ Maj for all j ∈ {1,2,...,k-1}. Thus condition 5.1.2 must hold
for a₁,a₂,...,a_k.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order
a_j over a_j₊₁ for all j ∈ {1,2,...,k-1}. Thus condition 5.1.3 must hold for a₁,a₂,...,a_k.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a₁,a₂,...,a_k and since a₁ = w and a_k = x,
it follows that MAM satisfies IMC.

Next we show MAM satisfies IMC2. By inspection of the definition of R_social(), 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:

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 x ∈ A, let ρ(x) denote the probability x is chosen by the voting rule.

For all x,y ∈ A, 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,x ∈ A, 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,x ∈ A. 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:

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.

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,b ∈ A, Precede(a,b) = Precede(a,b,A,R,σ).
For all a,b ∈ A', 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 (a₁,a₂),(a₂,a₃),...,(a_k_-1,a_k) ∈ Aff ∩ Precede(x,w) such that a₁ = w and a_k = x.
By the definition of Affirmed(), Aff ⊆ Maj. Thus (a_k_-1,x) ∈ Maj. Therefore a_k_-1 ≠ w,
which implies a_k_-1 ∈ A' and (a_k_-1,x) ∈ Maj'.  Since MAM(A',R',σ') = x, this implies x
is not second in any pair in Aff'. Therefore (a_k_-1,x) ∉ Aff'.  Since (a_k_-1,x) ∈ Maj'\Aff',
(a_k_-1,x) must be inconsistent with Aff' ∩ Precede'(a_k_-1,x).  Thus there must exist
(b₁,b₂),(b₂,b₃),...,(b_j_-1,b_j) ∈ Aff' ∩ Precede'(a_k_-1,x) such that b₁ = x and b_j = a_k_-1.
Let P denote {(b₁,b₂),(b₂,b₃),...,(b_j_-1,b_j)}. By theorem "Consistency Maintained (2)",
Aff must be internally consistent.  Thus since (a_k_-1,x) ∈ Aff there must exist (b,b') ∈ P
such that (b,b') ∉ Aff.  Let P₂ denote the pairs in Aff' or in Aff ∩ Pairs(A') but not
in both.  Since (b,b') ∈ Aff'\Aff, (b,b') ∈ P₂. Since P₂ is not empty, by theorem
"Precedence is a Strict Ordering" we can pick (y,y') ∈ P₂ such that the following
condition holds:

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 (c₁,c₂),(c₂,c₃),...,(c_h_-1,c_h) ∈ Aff ∩ Precede(y,y')
such that c₁ = y' and c_h = y. Let P₃ denote {(c₁,c₂),(c₂,c₃),...,(c_h_-1,c_h)}.
There are two subcases to consider:

Case 5.3.2.1: w ∈ {c₁,c₂,...,c_h}. Since c₁ ∈ A' and w ∉ A', this implies
w ∈ {c₂,...,c_h}. Therefore w must be second in at least one pair in P₃. But
since P₃ ⊆ 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 ∉ {c₁,c₂,...,c_h}. This implies P₃ ⊆ Pairs(A'). Since P₃ ⊆ Aff,
P₃ ⊆ Maj. Since P₃ ⊆ Pairs(A') ∩ Maj, P₃ ⊆ Maj'. By theorem "Consistency
Maintained (2)", Aff' must be internally consistent. Therefore, since (y,y') ∈ Aff'
there must exist (c,c') ∈ P₃ such that (c,c') ∉ Aff'. Since (c,c') ∈ Aff\Aff' and
(c,c') ∈ Pairs(A'), (c,c') ∈ P₂. Since σ' = σ|_A' and (c,c') ∈ Precede(y,y'),
by theorem "Precedence is Independent of Irrelevant Alternatives"
(c,c') ∈ Precede'(y,y'). Since (c,c') ∈ P₂ 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') ∈ P₂, 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
(c₁,c₂),(c₂,c₃),...,(c_h_-1,c_h) ∈ Aff' ∩ Precede'(y,y') such that c₁ = y' and c_h = y.
Let P₃ denote {(c₁,c₂),(c₂,c₃),...,(c_h_-1,c_h)}. By theorem "Consistency Maintained (2)",
Aff must be internally consistent. Thus since (y,y') ∈ Aff there must exist (c,c') ∈ P₃
such that (c,c') ∉ Aff. Since (c,c') ∈ Aff'\Aff, (c,c') ∈ P₂. Since (c,c') ∈ P₂ 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 a₁,a₂,...,a_k ∈ A such that a₁ = y and a_k = x
and, letting P denote {(a₁,a₂),(a₂,a₃),...,(a_k_-1,a_k)}, 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(a_j,a_j₊₁) > V(x,w) or [ V(a_j,a_j₊₁) = V(x,w)
and V(a_j₊₁,a_j) ≤ V(w,x)].

Thus condition 5.1.1 must hold for the sequence a₁,a₂,...,a_k.
By inspection of the definition of Affirmed(), Aff ⊆ Maj. Therefore P ⊆ Maj.
This implies (a_j,a_j₊₁) ∈ Maj for all j ∈ {1,2,...,k-1}. Thus condition 5.1.2 must hold
for a₁,a₂,...,a_k.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order
a_j over a_j₊₁ for all j ∈ {1,2,...,k-1}. Thus condition 5.1.3 must hold for a₁,a₂,...,a_k.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a₁,a₂,...,a_k and since a₁ = w and a_k = 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 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}:

(5.2.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)].
(5.2.2) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(5.2.3) r orders a_j over a_j₊₁.

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 a₁,a₂,...,a_k ∈ A such that a₁ = y and a_k = x and,
letting P denote {(a₁,a₂),(a₂,a₃),...,(a_k_-1,a_k)}, 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(a_j,a_j₊₁) > V(x,w) or [ V(a_j,a_j₊₁) = V(x,w) and
V(a_j₊₁,a_j) ≤ V(w,x)]. Thus condition 5.1.1 must hold for the sequence a₁,a₂,...,a_k.
By inspection of the definition of Affirmed(), Aff ⊆ Maj. Therefore P ⊆ Maj.
This implies (a_j,a_j₊₁) ∈ Maj for all j ∈ {1,2,...,k-1}. Thus condition 5.1.2 must hold
for a₁,a₂,...,a_k.   Since P ⊆ Aff, by theorem "Properties of RSocial (3)" r must order
a_j over a_j₊₁ for all j ∈ {1,2,...,k-1}. Thus condition 5.1.3 must hold for a₁,a₂,...,a_k.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a₁,a₂,...,a_k and since a₁ = w and a_k = x,
it follows that MAM satisfies I2C.

By inspection of the definition of R_social(), 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.

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:

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:

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

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 TM_s denote the majorities thwarted by the social
ordering. Assume TM_s is not empty. Thus, by 6.1 we can let (x,y) denote a pair in TM_s
such that no pair in TM_s is larger than (x,y). Pick any r ∈ O(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) ∈ TM_s, both of the following
statements must hold:

Since IMC is satisfied, by 6.2 and 6.3 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}:

(6.4) 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)].
(6.5) V(a_j,a_j₊₁) > V(a_j₊₁,a_j).
(6.6) a_j is socially ordered over a_j₊₁.

Case 6.7: r orders a_j over a_j₊₁ for all j ∈ {1,2,...,k-1}. Since r ∈ O(A), r is transitive.
Thus, by induction r must order a₁ over a_k. This implies (x,y) ∈ TM(r).

Case 6.8: There exists j ∈ {1,2,...,k-1} such that r does not order a_j over a_j₊₁.
By 6.5, (a_j,a_j+1) ∈ TM(r). By 6.4, (a_j,a_j+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

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