Immunity from Majority Complaints: a criterion for voting rules (DRAFT)
Steve Eppley <seppley@alumni.caltech.edu>
Revised: November 2, 2008
Abstract
This paper presents a strong criterion, immunity from majority complaints
(IMC),
that is failed by most voting procedures. Satisfaction of IMC allows an easy
rebuttal
on behalf of the chosen alternative when a majority of the voters claim
they prefer
another
alternative (which they may do no matter what voting procedure is used).
Furthermore, it is shown that IMC is nearly a characterization of the Maximize
Affirmed
Majorities procedure (MAM). (Elsewhere it is shown that MAM also
satisfies many other desirable
criteria, including Condorcet-consistency, top cycle,
strong Pareto, monotonicity, 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:
Scenario 1: 9 voters rank three alternatives {a,b,c}:
4 | 3 | 2 |
a | b | c |
b | c | a |
c | a | b |
The table shows each voter's order of preference: 4 voters prefer a over b
over c,
3 prefer b over c over a, and 2 prefer c over a
over b. Thus a majority (6 voters)
prefer a over b, a majority (7 voters) prefer b over c, and a majority (5 voters)
prefer c over a. Therefore, for every alternative some other
alternative is preferred
by a
majority.
Even voting procedures
that do not permit voters to completely express their orders of
preference, such as "Vote for One, Plurality Rule" and
"Approval" (which lets each voter
select as many candidates as desired and elects the one selected by the most
voters),
are not immune from this phenomenon since it is determined by
the voters'
underlying
preferences, not by votes. Unofficial polling may establish the existence of a
majority
preference for a losing alternative.
A majority who prefer a losing alternative over the elected alternative might complain
that "democratic majority rule" has somehow been violated. When will this
be trouble
for society? That may depend on the voting procedure. For instance, in the scenario
above, if the procedure socially orders the alternatives as "a
over b over c" then the
five voters who voted c over a may complain a majority voted for c over the winner.
However, in this case they can be easily rebutted
by turning their own argument against
them, specifically by showing a larger majority (7
voters) rank b over c and a larger
majority (6 voters) rank a over b. If
on the other hand the procedure does not
elect a or does not find the social ordering to be "a over b over c" then it may be
harder to rebut
the complainers' argument:
If b is elected,
the 6 voters who prefer a over b cannot be easily rebutted
since the only majority who prefer something over a is smaller.
If c is elected,
the 7 voters who prefer b over c cannot be easily rebutted
since the only majority who prefer something over b is smaller.
If the voting procedure
socially orders the alternatives as "a over c over b"
then the rebuttal involving "b over c" and "a over b"
is inconsistent with the
social ordering, which undermines the voting procedure and the
election of a.
Even if the voting procedure elects a
and does not socially order the alternatives,
it may be hard to rebut the complainers if there exists a natural way to extend
the
procedure to produce a social ordering that differs from "a over b
over c."
This is a matter of consistency: If the principles that allow the voting
procedure
to find the elected alternative "better" than any other
alternative
cannot also be used
to find which of any pair of alternatives is "better" than the other, this incompleteness
of the "better" relation may suggest to many
people that something is amiss with the
procedure's principles, which in turn may undermine confidence in the procedure.
Furthermore, it is
always possible to unofficially construct a social ordering in
some way that is
"natural" for the voting procedure. For instance, the following
six techniques are fairly obvious:
1. For procedures that
compute a score for each alternative and elect the one
with the best score, it is natural to order the alternatives from best score to
worst score.
2. For procedures that
eliminate alternatives one at a time, it is natural to
order the alternatives in the reverse of the elimination order.
3. For procedures that
compute a transitive binary relation on the alternatives,
it is natural to use that relation (or possibly its reverse) as the social
ordering.
4. For procedures that
distinguish an acyclic subset of the pairwise majorities,
it is natural to construct a social ordering consistent with the acyclic
subset.
5. For procedures that
rank the possible social orderings and elect the
alternative atop the highest-ranked ordering, it is natural to
take
that highest-ranked ordering as the social ordering.
6. In general, given any procedure that elects one alternative, one can
always
construct a social ordering by iteratively deleting the
elected alternative from
the votes and computing which of the remaining alternatives would be
elected,
repeating until no alternatives remain, and taking that
election order as the
social order.
If the complainers construct a social
ordering using a technique that appears natural
for the voting procedure and show that the rebuttal sequence is inconsistent with
that
natural ordering, the force of the rebuttal could be undermined.
Complaints by a losing majority that are hard to rebut could undermine the winner's
mandate, and could undermine confidence
in the
voting procedure, particularly if there
exists another procedure that satisfies the criteria
the people consider important,
would have elected the alternative favored by the complainers, and
over the long run
would elect alternatives preferred by more voters. We consider
it desirable to be
able to easily turn the complainers' argument against them since
we do not expect
people to entirely agree about the relative importance of the
criteria used to select the
voting procedure (and there would certainly be an incentive for cheap
talk favoring
some other voting procedure in such scenarios). Turning their argument against them
seems a straight-forward way to win the debate. With these considerations in
mind
we formally define the criterion immunity from majority complaints (IMC):
Let A denote a finite non-empty set of alternatives from which one must be elected.
Let R denote a collection of votes, one per voter.
For all x,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_{1},a_{2},...,a_{k}
∈ A such that a_{1} = 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}_{+1})
> V(a_{j}_{+1},a_{j}) for all
j ∈
{1,2,...,k-1}.
(3) a_{j} is socially ordered over a_{j}_{+1} for all
j ∈
{1,2,...,k-1}.
IMC can be decomposed into several
criteria. Letting each vote be any ordering is a
universal domain criterion which should allow the votes to trump any unofficial poll
of the voters' preferences that might be proffered by a complaining majority.
(Thus
procedures such as Approval and "Vote for only one, Plurality
Rule" are disqualified.)
Requiring
a single alternative be elected is the resoluteness criterion, required by
the
innate mutual exclusivity of the alternatives. Requiring existence of a majority
sequence
"a_{1} over a_{2}," "a_{2}
over a_{3}," ..., 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_{1}
(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_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(a_{j}_{+1},a_{j}) for all
j ∈
{1,2,...,k-1}.
3. a_{j} is socially ordered over a_{j}_{+1} for all
j ∈
{1,2,...,k-1}.
IMC2 is less demanding
than IMC in the sense that it only requires a rebuttal sequence
against a majority who vote any losing alternative x over the elected alternative w,
whereas IMC requires a rebuttal sequence against any majority who vote any x
over
any y socially ordered over or equal to 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:
Scenario 2: 3 voters rank three alternatives {a,b,c}:
1 | 1 | 1 |
a | b | c |
b | c | a |
c | a | b |
The cycle in scenario 2
is perfectly symmetric. Without loss of
generality, assume a is
elected (perhaps by drawing straws). A majority (2
voters) rank c over a and no majority
is larger than 2 voters. Thus the most we can expect from a rebutting sequence
of majorities
from a to c is that the rebutting majorities be at least as
large as the majority
who voted c
over a. It is too much to demand
the rebutting sequence be comprised of larger
majorities
in such "symmetric" scenarios; however
we consider it sufficient to turn the
complainers'
argument against them when each of the rebutting majorities is at least as large.
In large
public elections, the ideal would usually be satisfied (assuming IMC and
IMC2 are
satisfied)
since the likelihood that two majorities will be the same size decreases
as
the number of voters increases.
Presuming that the attention of the media and the voters tends to focus
mostly on the top
two alternatives, the lack of an easy rebuttal against a complaining majority who favor the
"second"
alternative over the elected alternative would seem to make such a failure more
egregious. We next present a criterion that expresses this idea:
Immunity from
second-place complaints (I2C): The voting procedure must
allow each voter to vote any ordering of the alternatives, must elect a single
alternative (denoted w), and, letting x denote the
alternative that would be
elected if w were dropped from the votes, V(x,w) must not exceed V(w,x).
I2C is more demanding than IMC2 in the
sense that I2C implicitly uses technique 6 to
determine which alternative is second in the social ordering (defining the second
alternative
as the one that would be elected if the elected alternative were deleted).
I2C is less
demanding in the sense that the voting procedure is not required to socially
order the
alternatives. And I2C is less demanding in the sense that it focuses only
on the top two
alternatives: clearly there could be no rebuttal sequence if a majority prefer
the second
alternative over the elected alternative, so the second
alternative must not be ranked
over the elected alternative by a majority.
Appendix A provides examples
showing
failures of IMC, IMC2 and I2C by widely-
known voting procedures: Plurality Rule,
Majority Runoff, Instant
Runoff, Borda, Nanson,
Copeland, Minimax, Maximin, Simpson-Kramer, TopCycle/Minimax, TopCycle/Maximin,
Kemeny-Young, Tideman's "Ranked Pairs,"
Tideman-Zavist and PathWinner.
We will prove there exists a voting procedure
("Maximize Affirmed Majorities," or MAM)
that can be quickly computed and satisfies IMC, IMC2, IMC2a and
I2C, and will prove
that all social orderings natural
to MAM (techniques 4, 5 and 6)
agree. We will also show
that satisfaction of IMC implies satisfaction of many other desirable criteria.
We state the
important theorems next, with most proofs provided in Appendix B. (The
remaining proofs
are provided in separate documents about MAM.)
Theorem 1: There is always at least one social ordering capable of satisfying IMC.
Theorem 2: Satisfaction of
IMC
implies satisfaction of Condorcet-consistency,
top cycle, weak Pareto, resolvability, minimal defense and
truncation resistance.
(Note
that any voting procedure that satisfies resolvability is usually deterministic.
This implies IMC is nearly a complete characterization of the voting procedures that
satisfy
it, and implies that in elections having many voters the outcome would rarely
depend on
chance if the voting procedure satisfies IMC.)
Theorem 3: Say no pairings are tied if and only if
V(x,y)
≠ V(y,x) for all distinct
x,y
∈ A. Say every cycle has
only one smallest majority if and only if, for all
sequences of alternatives a_{1},a_{2},...,a_{k}
∈ A such that [a_{1} = a_{k}
and a_{1},a_{2},...,a_{k}_{-1}
are
distinct and V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},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}_{+1}) for all j ∈
{1,2,...,k-1}
distinct from h. If no pairings are tied
and every cycle has only one smallest majority,
then only one social ordering is capable of satisfying IMC.
(Theorem 3 implies that in
elections having many voters the outcome would rarely depend
on chance if the voting procedure satisfies IMC.)
Theorem 4: In the
(large) subdomain domain of votes where only one social
ordering is capable of satisfying IMC, satisfaction of
IMC implies satisfaction
of strong 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.")
Conclusions
Appendix A - Examples showing most voting procedures fail IMC, IMC2 and I2C
Many prominent voting procedures fail IMC, IMC2 and I2C. The examples that
follow
show failures by Plurality Rule, Majority Runoff, Instant
Runoff, Borda, Nanson, Copeland,
Minimax, Maximin, Simpson-Kramer, TopCycle/Minimax, TopCycle/Maximin, Kemeny-
Young, Tideman's "Ranked Pairs," Tideman-Zavist and
PathWinner. (Note that Kemeny-
Young, Tideman and Tideman-Zavist satisfy I2C.)
We constructed the examples where possible so all votes are strict
orderings of the
alternatives, to avoid critiques that non-strict orderings are
implausible and that the
implementation could easily prevent voters from voting non-strict orderings. Showing
failures by Tideman and Tideman-Zavist requires some votes to be
non-strict orderings.
This is discussed more extensively below.
We constructed all examples to have an odd number of voters, since it is common
for
committees to have an odd number of members to reduce the frequency of tie
votes.
We constructed all examples to be deterministic. Some voting procedures
are defined
so that in some scenarios the winner is ambiguous, left to an unspecified
tie-breaker
(such as flipping a coin or drawing the short straw) or specifically depending on chance.
The
Copeland procedure in particular is "frequently" indeterminate (implied by its
failure of
the resolvability criterion). Though proponents of Copeland may in practice
recommend
a specific tie-breaker, it seems simplest to show Copeland's failures
without assuming
specific knowledge of the tie-breaker, even though this means the example may need to
involve more alternatives than needed to show failure with a specific tie-breaker.
No voting procedure that can defeat a "Condorcet winner" (an alternative x such that,
for all other
alternatives y, more than half the voters prefer x over y)
satisfies
IMC or IMC2.
Clearly, when
x is a Condorcet winner and is not elected, there cannot be a sequence of
majorities to rebut the
complaint by the majority who prefer x over the elected alternative.
Thus it would be easy
to show that Plurality Rule, Majority Runoff, Instant Runoff and
Borda fail IMC and IMC2. We go a
step further and construct examples for each that
also show failures of I2C, and moreover
in these examples the alternative used to show
failure of I2C is a Condorcet
winner that finishes second in a natural social ordering.
Scenario A1: Failures by Plurality Rule.
9 voters rank three alternatives {a,w,x} as
follows:
2 | 3 | 4 |
a | x | w |
x | a | x |
w | w | a |
Plurality Rule ignores all but the top of each vote. (Typical implementations
permit each
voter to express only the top of his/her ranking.) In scenario A1, since more votes
are
topped by w (4) than by any other alternative, Plurality Rule would
elect w. However,
a majority (5 voters) rank x
over w. Since x is a Condorcet winner, no rebutting sequence
can be constructed against the complaint that x
should be elected, which means Plurality
Rule fails IMC and IMC2. Furthermore, x
is second in both natural social orderings:
x has the second-best score (3 votes), and x
would be chosen if w were deleted from
the votes. Thus Plurality Rule also fails I2C.
Scenario A2: Failures by Majority Runoff and Instant Runoff.
9 voters rank three alternatives {a,w,x} as
follows:
3 | 2 | 4 |
a | x | w |
x | w | x |
w | a | a |
To simplify the analysis of Majority Runoff, which in
practice is implemented as two rounds
of voting in which each voter selects one alternative, we define it as one round
of voting in
which each voter orders the alternatives. (Thus we neglect that voter turnout
may differ in
the second round or that preferences may change between rounds.)
Considering only the
two alternatives that top the most votes, the one that is ranked over the other
by more votes
is elected. In scenario A2, alternatives a and w are ranked
top by the most voters, and
since w is ranked over a by a majority, Majority Runoff elects w.
However, a majority
(5 voters) rank x over w. Since x is a Condorcet winner,
no rebutting sequence can be
constructed against the complaint that x should be elected, which means
Majority Runoff
fails IMC and IMC2. Furthermore, one of the two natural techniques of
constructing
a social ordering will find x to be second in the social ordering, since x
would be elected
if w were deleted from the votes. Thus Majority Runoff also fails I2C.
Instant Runoff is similar to Majority Runoff.
It is an iterative elimination procedure
that,
in each iteration, counts each vote for its highest-ranked non-eliminated alternative and
eliminates the alternative with the smallest count, repeating until one alternative remains.
Thus in scenario A2 Instant Runoff elects the same as Majority Runoff, which
means
it too fails IMC, IMC2 and I2C.
Scenario A3: Failures by Borda.
5 voters rank three alternatives {a,w,x} as
follows:
3 | 2 |
x | w |
w | a |
a | x |
The Borda procedure counts for each alternative a point from each
vote for each alternative
ranked below it. In scenario A3, Borda counts 6 points
for x (3×2 + 2×0), 7 points
for w
(3×1 + 2×2), and 2 points
for a (3×0 + 2×1). Thus Borda
elects w. However,
a majority
(3 voters) rank x over w. Since x is a Condorcet
winner, no rebutting sequence can be
constructed against the complaint that x should be chosen, which means
Borda fails IMC
and IMC2. Furthermore, x is second in both natural social
orderings: x has the second-
best score (6 votes), and x would be elected if w were deleted from the
votes. Thus,
Borda also fails I2C.
Scenario A4a: Failures by Nanson.
13 voters rank four alternatives {a,b,w,x} as
follows:
1 | 1 | 5 | 3 | 1 | 2 |
w | w | x | a | b | b |
a | b | w | w | w | a |
x | a | b | x | a | x |
b | x | a | b | x | w |
The Nanson procedure is an iterative elimination
procedure based on the Borda procedure.
In each iteration, Nanson recomputes the Borda score of each non-eliminated
alternative
(neglecting eliminated alternatives) and eliminates the one having the smallest
score,
repeating until only one alternative remains. In scenario A4a, first b
is eliminated
since b has the smallest Borda score (16). Next x is
eliminated since x has the smallest
Borda score (12; with b deleted before computing scores). Then a
is eliminated since a has
the smallest Borda score (5; with b and x deleted before computing
scores). Thus Nanson
elects w. However, a majority (7 voters) rank x over w,
and Nanson would elect x
if w were dropped from the votes. Thus Nanson fails I2C. To
show that Nanson also fails
IMC and IMC2 in scenario A4a, we show the only social ordering capable of
satisfying
IMC or IMC2 is "x over w over b over a":
Clearly IMC (or IMC2) requires w must be
socially ordered over b since no majority is as large as the majority (10
voters) who rank
w over b. Clearly IMC (or IMC2) requires x must be
socially ordered over b since the
majority who rank x over b (9 voters) is larger than the only
majority who rank something
over x (the 8 for a over x). Clearly IMC (or IMC2)
requires b must be socially ordered
over a since the majority who rank b over a (9 voters) is
larger than the only majority who
rank a over something (the 8 for a over x). Thus the
social ordering must be one of these
three: "x over w over b over a" or "x
~ w over b over a" or "w over x
over b over a."
Since a majority (7 voters) rank x over w, the last two orderings
cannot satisfy IMC or
IMC2. Thus the only social ordering capable of satisfying IMC or
IMC2 is
"x over w
over b over a" and it can be checked that this ordering
indeed satisfies IMC and IMC2.
It follow that IMC (or IMC2) requires x must be chosen, and thus Nanson
fails IMC,
IMC2 and I2C.
Failure of IMC and IMC2 by Nanson can be shown with
as few as three alternatives,
as the following scenario illustrates:
Scenario A4b: More failures of IMC and IMC2 by Nanson.
15 voters rank three alternatives {a,w,x} as
follows:
6 | 2 | 1 | 6 |
w | x | x | a |
a | w | a | x |
x | a | w | w |
In scenario A4b, first x is eliminated since
it has the smallest Borda score (12). Then a is
eliminated since it has the smallest Borda score (7; with x deleted
before computing scores).
Thus Nanson elects w. However, a majority (9 voters) rank x
over w. Since the majority
who rank w over a is smaller than 9, no rebutting sequence can be
constructed. Thus
Nanson can fail IMC and IMC2 with as few as three alternatives.
Scenario A5a: Failures by Copeland.
15 voters rank eight alternatives {a,b,c,d,e,f,w,x} as
follows:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
w | w | x | x | x | x | x | x | b | c | c | d | e | f | f |
a | b | w | w | a | f | f | f | a | b | f | a | d | d | e |
b | a | c | c | e | w | e | e | x | a | e | x | c | b | d |
x | x | b | d | w | e | d | d | w | x | b | w | b | x | c |
d | e | a | e | d | c | c | c | f | f | a | e | a | c | a |
c | d | f | b | c | d | w | b | e | e | x | c | x | w | b |
f | c | e | f | f | b | b | w | d | d | w | b | w | a | x |
e | f | d | a | b | a | a | a | c | w | d | f | f | e | w |
Copeland scores for each alternative the number of pairings
in which the votes that rank
it over its pairwise opponent exceed the votes that rank it below its pairwise
opponent,
and then chooses the alternative with the largest score. (Perhaps this
procedure should be
attributed to Ramon Lull, a 13th century monk who, according to historian Ian
McLean,
suggested electing the alternative with "the most votes in the most pairings." McLean
interpreted Lull's procedure as equivalent to the Borda procedure, but
it seems plausible
that Lull meant Copeland.) In scenario A5a, Copeland computes these
scores:
w wins 6 pairings (over a,b,c,d,e,f).
x wins 5 pairings (over c,d,e,f,w).
a wins 3 pairings (over e,f,x).
b wins 3 pairings (over a,b,x).
c wins 3 pairings (over a,b,f).
d wins 3 pairings (over a,b,c).
e wins 3 pairings (over b,c,d).
f wins 2 pairings (over d,e).
Thus Copeland elects w. However, a
majority (13 voters) rank x over w. Since no
other majority is as large as 13, no rebutting sequence can be constructed
against the
complaint that x should be elected, which means Copeland fails IMC and
IMC2.
Furthermore, x is second in both natural social orderings: x has
the second-best score
(5 won pairings), and x would be elected if w were deleted from the
votes. Thus,
Copeland also fails I2C. The example seems even more egregious since x is the
only
alternative whose largest
opposing majority is as small as 8 voters and w is the only
alternative whose largest opposing majority is as large as 13 voters.
Failure of IMC and IMC2 by Copeland can be shown with
fewer alternatives, as the
following two scenarios illustrate:
Scenario A5b: More failures by Copeland.
9 voters rank five alternatives {a,b,c,w,x} as
follows:
4 | 3 | 2 |
x | b | w |
w | c | c |
a | a | a |
b | x | b |
c | w | x |
In scenario A5b, Copeland computes these scores:
w wins 3 pairings (over a,b,c).
a wins 2 pairings (over b,x).
b wins 2 pairings (over c,x).
c wins 2 pairings (over a,x).
x wins 1 pairing (over w).
Thus Copeland elects w. However, a
majority (7 voters) rank x over w. Since the
only other majority that is as large as 7 is the "b over c"
majority, clearly no rebutting
sequence can be constructed against the complaint that x should be
elected, which again
shows Copeland fails IMC and IMC2. (Unlike scenario A5a, x is not
second in a social
ordering that is natural for Copeland, so scenario A5b is not as egregious in
that sense.)
Given knowledge of the tie-breaker, we could probably show
Copeland failures with
examples involving only three alternatives. For instance,
suppose the tie-breaker were
Plurality Rule, which we denote as Copeland/Plurality:
Scenario A5c: Failures by Copeland/Plurality.
15 voters rank three alternatives {a,w,x} as
follows:
4 | 2 | 5 | 4 |
w | w | x | a |
a | x | w | x |
x | a | a | w |
In scenario A5c, Copeland computes these scores:
w wins 1 pairing (over a).
a wins 1 pairing (over x).
x wins 1 pairing (over w).
All three alternatives have the same Copeland
score (1). The Plurality tie-breaker finds
w tops more votes (6) than any other alternative tops. Thus
Copeland/Plurality elects w.
However, a majority (9 voters) rank x over w. Since only 8
voters rank a over x, no
rebutting sequence can be constructed. Thus Copeland/Plurality can fail
IMC and IMC2
with as few as three alternatives. Furthermore, x is second in one
of the social orderings
that is natural for Copeland/Plurality since x tops more votes than a
tops. Thus, though
this example does not show Copeland/Plurality fails I2C (which was however shown
by
scenario A5a), it is an egregious failure with as few as three alternatives and
similar
to failing I2C.
Scenario A6: Failures by Minimax, Maximin and Simpson-Kramer.
15 voters rank four alternatives {a,b,c,w} as
follows:
3 | 3 | 3 | 2 | 2 | 2 |
a | b | c | w | w | w |
b | c | a | a | b | c |
c | a | b | b | c | a |
w | w | w | c | a | b |
In scenario A6, the pairwise counts of the votes are as follows:
V(a,b) = 10, V(b,a)
= 5
V(b,c) = 10, V(c,b)
= 5
V(c,a) = 10, V(a,c)
= 5
V(a,w) = 9, V(w,a)
= 6
V(b,w) = 9, V(w,b)
= 6
V(c,w) = 9, V(w,c)
= 6
Minimax scores each alternative x according to
its largest pairwise opposition and chooses
the alternative with the smallest score. Maximin scores each alternative x
according to its
smallest pairwise support and chooses the alternative with the largest
score. Simpson-
Kramer scores each alternative according to its smallest pairwise "support minus
opposition"
and elects the alternative with the largest score. (Other variations may be
obvious.) When
all votes are strict orderings of the alternatives, as in scenario A6, all three
procedures elect
the same, and here they elect w. For instance,
Minimax elects w since w's largest pairwise
opposition (V(a,w), V(b,w), and V(c,w))
is 9 voters, whereas all other alternatives have
larger pairwise oppositions (10 voters). Since only minorities (6
voters) prefer w over
any other alternative, no rebutting sequence can be constructed against the
complaint that
a different alternative should be chosen, which means Minimax, Maximin and Simpson-
Kramer fail IMC and IMC2. Furthermore, no matter how the social ordering is constructed,
one
of {a,b,c} must be second in the social ordering. Thus, Minimax, Maximin and
Simpson-Kramer
also fail I2C. (The behavior of these methods is especially egregious
since w is not in
the top cycle, and in fact for every other alternative there is a majority
who rank it over w.)
Scenario A7: Failures by TopCycle/Minimax and TopCycle/Maximin.
13 voters rank four alternatives {a,b,w,x} as
follows:
4 | 1 | 2 | 2 | 4 |
x | x | a | a | b |
w | a | w | b | w |
a | b | b | x | x |
b | w | x | w | a |
In scenario A7, the pairwise counts of the votes are as follows:
V(a,b) = 9, V(b,a)
= 4
V(x,a) = 9, V(a,x)
= 4
V(b,x) = 8, V(x,b)
= 5
V(w,a) = 8, V(a,w)
= 5
V(b,w) = 7, V(w,b)
= 6
V(x,w) = 7, V(w,x)
= 6
TopCycle/Minimax and TopCycle/Maximin are like
Minimax and Maximin, respectively,
except they neglect all alternatives that are not in the top cycle (the
smallest non-empty
subset of alternatives such that every alternative in the subset "beats
pairwise" every
alternative not in the subset). In
scenario A7, all alternatives are in the top cycle so the
two procedures behave equivalently to
Minimax and Maximin, respectively. Since all
votes are strict orderings, Minimax
and Maximin elect the same, so we can consider
just Minimax: For all alternatives
except w there is a majority larger than 7 voters who
rank something over it. Thus
Minimax elects w. However, a majority (7 voters)
rank x over w. Clearly x
is second in both natural social orderings, since x has the
second smallest largest opposing majority and x
would be elected if w were deleted.
Thus Minimax and Maximin and
TopCycle/Minimax and TopCycle/Maximin fail IMC2
and I2C. To show they also
fail IMC, we show the only social ordering capable of
satisfying IMC is "x over w over a
over b" (which implies x must be elected). Clearly,
IMC requires x must be
socially ordered over a since a majority of 9 rank x over a
and no majority as large as 9
ranks anything over x. Clearly, IMC requires a must be
socially ordered over b since a
majority of 9 rank a over b and if a is not socially ordered
over b no rebuttal
sequence of majorities as large as 9 can be constructed. Clearly,
IMC requires w must be socially
ordered over a since a majority of 8 rank w over a
and
no majority as large as 8 ranks
anything over w. Thus the social ordering must be one of
these three: "x over w
over a over b" or "x ~ w over a over b" or "w over x over a over b."
Since a majority (7 voters) rank x over w, the last two orderings cannot satisfy
IMC.
Thus the only social ordering capable of
satisfying IMC is "x over w over a over b"
and it can be
checked that this ordering indeed satisfies IMC. Therefore IMC requires
x must be elected. Thus TopCycle/Minimax and TopCycle/Maximin fail
IMC, IMC2
and I2C.
Scenario A8: Failures by Kemeny-Young.
15 voters rank four alternatives {a,b,w,x} as
follows:
6 | 5 | 4 |
x | w | a |
w | a | b |
a | b | x |
b | x | w |
For each possible social ordering, Kemeny-Young
computes a score equal to the sum of the
pairwise preferences with which it agrees, and then Kemeny-Young elects the
alternative
atop the ordering having the largest score. In scenario A8,
Kemeny-Young scores 60
for the ordering "w over a over b over x"
since this ordering agrees with 11 votes for w
over a plus 11 votes for w over b plus 5 votes for w
over x plus 15 votes for a over b
plus 9 votes for a over x plus 9 votes for b over x.
It can be checked that no other ordering
has a score as large. (Checking all possible orderings would be tedious, but one
may rule
out many possibilities since Kemeny-Young satisfies local independence of
irrelevant
alternatives (LIIA). For instance, note that if x were deleted then the
Kemeny-Young
ordering of the remaining alternatives would be "w over a over b."
Thus, by LIIA the only
strict ordering topped by x that needs checking is "x over w over a
over b" and the only
strict ordering trailed by x that needs checking is "w over a over b
over x." Similarly,
the only strict ordering topped by w that needs checking is "w
over a over b over x" and
the only strict ordering trailed by w that needs checking is "a
over b over x over w."
The only strict ordering topped by a that needs checking is "a
over x over w over b" and
the only strict ordering trailed by a that needs checking is "x
over w over b over a."
The only strict ordering topped by b that needs checking is "b
over x over w over a" and
the only strict ordering trailed by b that needs checking is "x
over w over a over b."
One can reduce these even further by noting contradictions where an alternative
atop one
trails another, etc., which reduces to two the number of orderings that need
checking.
For these two orderings, Kemeny-Young scores 59 for "x over w
over a over b" and 60
for "w over a over b over x.") Thus
Kemeny-Young elects w. However, a
majority
(10 voters) rank x over w. Since no majority as large as
10 prefers any alternative over x,
no rebutting sequence can be constructed
against the complaint that x should be elected,
which means Kemeny-Young fails IMC. It can also be shown that
Kemeny-Young fails
IMC2, since both natural social orderings (techniques 5 and 6) are the same
"w over a
over b over x." (Indeed, techniques 5 and 6 must agree under
any voting procedure
that satisfies LIIA.)
Kemeny-Young satisfies I2C. (In general,
any procedure that satisfies LIIA and is
majoritarian when there are only two alternatives satisfies I2C.)
Scenario A9: Failures by Tideman's "Ranked Pairs" and
Tideman-Zavist.
15 voters rank three alternatives {a,w,x} as
follows:
5 | 3 | 7 |
a | x | w |
x | w | |
w | a | x~a |
Tideman's "Ranked Pairs" (hereafter
abbreviated Tideman) and Zavist-Tideman are similar
to MAM. A major difference is that they rank the pairings by "margin
of victory", which
means subtracting pairwise opposition from pairwise support. (This distinction
matters
only if some voters vote non-strict orderings, which we argue ought to be
allowed since
voting two or more alternatives bottom can be a benevolent strategy--creating a
desirable
non-manipulative equilibrium for the sincere winner--with a
procedure such as MAM.
See the discussion of the minimal defense criterion elsewhere.) Thus, in scenario A9
Tideman and
Tideman-Zavist sort the pairings in the following decreasing order of
precedence:
w over a (since 10-5 =
5)
a over x (since 5-3 = 2)
x over w (since 8-7 = 1)
Then Tideman and Tideman-Zavist would affirm "w
over a" and "a over x" since these
two pairings have the greatest precedence, and they would not affirm "x
over w" since it
cycles with those already affirmed. The affirmed pairings produce the
social ordering
"w over a over x." Thus Tideman and
Tideman-Zavist elect w. However, a majority
(8 voters) rank x over w. Since no majority as large as
8 prefers any alternative over x,
no rebutting sequence can be constructed
against the
complaint that x should be elected,
which means Tideman and Tideman-Zavist fail IMC and IMC2. (Note that if enough
of
the 7 voters who rank x and a bottom had instead ranked x
over a, then x would be
a Condorcet winner. The implication is that "truncation of preferences" is an
effective
manipulative strategy under Tideman and Tideman-Zavist, and under many other
voting
procedures, but would not be manipulative under MAM. See the discussion of
the
truncation resistance criterion elsewher.)
Tideman and Tideman-Zavist satisfy local
independence of irrelevant alternatives
and are majoritarian when there are only two alternatives, so they satisfy I2C.
Scenario A10: Failures by PathWinner.
13 voters rank four alternatives {a,b,w,x} as
follows:
1 | 5 | 2 | 2 | 3 |
w | x | a | a | b |
b | w | b | b | w |
x | a | w | x | x |
a | b | x | w | a |
In scenario A10, the following shows the pairwise counts of the votes:
V(x,a) = 9, V(a,x)
= 4
V(w,a) = 9, V(a,w)
= 4
V(a,b) = 9, V(b,a)
= 4
V(b,x) = 8, V(x,b)
= 5
V(x,w) = 7, V(w,x)
= 6
V(b,w) = 7, V(w,b)
= 6
PathWinner calculates the strengths of the strongest paths as shown in the following table:
From | To | Strongest Path | Strength of Strongest Path |
x | a | xa | 9 |
a | x | abx | 8 |
x | b | xab | 9 |
b | x | bx | 8 |
x | w | xw | 7 |
w | x | wabx | 8 |
a | b | ab | 9 |
b | a | bxa | 8 |
a | w | abw | 7 |
w | a | wa | 9 |
b | w | bw | 7 |
w | b | wab | 9 |
The strength of a path (sequence of majorities) is the size of its smallest
majority. Since
the strongest path from w to any other alternative is stronger
than the strongest path from
that alternative to w, PathWinner elects w. However, a majority
(7 voters) rank x over w.
It can be checked that the only sequence that can rebut that majority is w,a,b,x;
thus the
only ordering that might possibly satisfy IMC is "w over a
over b over x." But that
ordering can also be shown to fail IMC: Since a majority (9 voters) rank x
over a and
no majority as large as 9 ranks any alternative over x, every social
ordering that
satisfies IMC orders x over a. Thus PathWinner fails
IMC. Furthermore, the social
ordering natural for PathWinner is "w over x over a
over b." This is shown as follows:
We have already established that w must top the PathWinner social
ordering. Since x has
stronger paths to a and to b than a or b have to x,
and since x would be elected if w were
dropped, x must be second in the natural ordering. Since a
has a stronger path to b than
b has to a, and since a would be elected if w and x
were dropped, a must be third in
the natural ordering. Thus either technique 3 or 6 produces the natural
social ordering
"w over x over a over b." Since a
majority prefer the second alternative (x) over the
elected alternative (w), this implies PathWinner also fails IMC2 and
I2C.
Appendix B - Proofs of the theorems
Proof of theorem 1:
We must show there is always at least one social ordering that is
capable of satisfying IMC. Let r_{0}
denote some strict ordering of A. (The manner in
which r_{0} is constructed does not matter for theorem 1, but it
is possible to construct r_{0}
so r_{0} 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_{0} ranks w over y.
(1.4) V(x,y) = V(z,w) and V(y,x)
= V(w,z)
and w = y and r_{0} ranks x over z.
(Clearly R_{P} depends only on R and r_{0}.) We next establish the following lemma:
Lemma 1.5: R_{P} is a strict ordering of P.
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_{0} 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_{0} 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_{0} 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_{0} ranks y over y.
(1.5.8) r_{0} 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_{0} 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_{0} 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_{0} 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_{0} 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_{0} ranks z over u.
There are three cases to consider:
Case 1.5.17:
Either 1.1 or 1.2 holds. This implies either
[V(x,y)
> V(u,v)] or [V(x,y) = V(u,v) and V(y,x)
< V(v,u)],
which implies 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_{0} orders w over y
and
r_{0} orders v over w. Since r_{0}
is a strict ordering, r_{0} 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_{0} 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_{0} orders w over y, and
thus r_{0} orders v over y. Since V(x,y) =
V(u,v) and V(y,x) = V(v,u)
and r_{0} 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_{0} orders v over w, and
thus r_{0} orders v over y. Since V(x,y) =
V(u,v) and V(y,x) = V(v,u)
and r_{0} 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_{0}
orders x
over z and r_{0} orders z over u. Since r_{0}
is a strict ordering, r_{0} must
order x over u. Since V(x,y) = V(u,v) and V(y,x) = V(v,u)
and y = v
and r_{0} 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} = 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:
Lemma 1.6: Aff is an acyclic subset of Maj.
Proof of 1.6:
Clearly Aff is a subset of M. Suppose to the
contrary Aff is cyclic.
This means there exists a sequence of alternatives s = x_{1},x_{2},...,x_{c}
∈ A such that
x_{1} = 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}_{+1}) 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}_{+1} is first and x_{h}
is last. Thus we can relabel the alternatives
so s' = a_{1},a_{2},...,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_{1},a_{2},...,a_{k} is a sequence
of
alternatives such that a_{1} = x_{h}_{+1} 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}_{+1}) 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.)
Let B_{1} denote A.
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_{0} orders no y ∈ T_{n}
over x}.
For all n ∈ {2,3,...,#A}, let B_{n} denote B_{n}_{-1}\W_{n}_{-1}.
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}.
We next establish the following lemma:
Lemma 1.7: r is a strict ordering of A consistent with Aff.
Proof of 1.7: Since
Aff is acyclic, P(B) ∩
Aff must be acyclic for all non-empty 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_{0} 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(x,y) or [ V(a_{j},a_{j}_{+1})
= V(x,y) and V(a_{j}_{+1},a_{j})
≤ V(y,x)].
(1.9) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(1.10) r orders a_{j} over a_{j}_{+1}.
By lemma 1.7, r orders a
over b for all (a,b) ∈ Aff.
This implies (x,y) ∉ Aff. Since
V(x,y) > V(y,x), (x,y)
∈ M. Since (x,y) ∈
M\Aff, by the definition of Aff there must
exist a sequence a_{1},a_{2},...,a_{k}
∈ A such that all three of the following conditions hold:
(1.11) a_{1}
= 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_{1},a_{2},...,a_{k}.
By
inspection of the definition of Aff, Aff ⊆ M.
Therefore, 1.12 implies 1.9 holds
for a_{1},a_{2},...,a_{k}.
Since r orders a over b for all (a,b) ∈
Aff,
1.12
implies 1.10 holds
for a_{1},a_{2},...,a_{k}.
Since a_{1}
= y and a_{k} = x and 1.8, 1.9 and 1.10 all hold for a_{1},a_{2},...,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_{1},a_{2},...,a_{k}
∈ A such that
a_{1} = 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}_{+1})
> V(t,w) or [ V(a_{j},a_{j}_{+1})
= V(t,w) and V(a_{j}_{+1},a_{j})
≤ V(w,t)].
(2.1.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(2.1.3) a_{j} is socially ordered over a_{j}_{+1}.
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:
(2.2.1) V(a,b)
≤ n for all a,b ∈
A.
(2.2.2) V(y,x) = 0.
By IMC, there must exist a sequence a_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(x,y) or [ V(a_{j},a_{j}_{+1})
= V(x,y) and V(a_{j}_{+1},a_{j})
≤ V(y,x)].
(2.2.4) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(2.2.5) a_{j} is socially ordered over a_{j}_{+1}.
By 2.2.1, 2.2.2 and 2.2.3 the following condition must hold:
(2.2.6) V(a_{j},a_{j}_{+1}) = n and V(a_{j}_{+1},a_{j}) = 0 for all j ∈ {1,2,...,k-1}.
It follows by induction on 2.2.6 that V(a_{1},a_{k})
= n. But since a_{1} = y and a_{k} =
x, this
contradicts 2.2.2. The contradiction implies the contrary assumption
cannot hold,
establishing satisfaction of Weak Pareto.
Next we establish the following lemma:
For all orderings of
the alternatives r, let Agree(r) denote {(x,y) ∈
Pairs(A)
such that r orders x over y}.
For all distinct
orderings of the alternatives r and r', let Disagree(r,r')
denote
{(x,y) ∈ Pairs(A)
such that r and r' disagree on the relative ordering of x
and y}.
For all distinct
orderings of the alternatives r and r', let Largest(r,r',R)
denote
{(x,y) ∈ Disagree(r,r') such that V(x,y)
> V(y,x) and, for all (z,w) ∈
Disagree(r,r')
such that V(z,w) > V(w,z), either [V(x,y)
> V(z,w) or [V(x,y)
= V(z,w) and
V(y,x)
≤ V(w,z)]}. (That is, Largest(r,r',R)
is(are) the largest majority(majorities) upon which
r and r' disagree.)
Lemma 2.3: For
all orderings of the alternatives r,r', if Largest(r,r',R)
is a
non-empty subset of Agree(r) then r' is incapable of satisfying
IMC.
Proof of 2.3:
Pick any two distinct orderings of the alternatives r and r'.
Make the following abbreviations:
Ag = Agree(r).
Ag' = Agree(r'),
D = Disagree(r,r').
L = Largest(r,r',R).
Maj = {(x,y) ∈ Pairs(A)
such that V(x,y) > V(y,x)}.
Assume L is a
non-empty subset of Ag. We must show r' is incapable of
satisfying IMC.
Suppose the contrary. By inspection of the definition of Largest(), 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(x,y) or [V(a_{j},a_{j}_{+1})
= V(x,y) and V(a_{j}_{+1},a_{j})
≤ V(y,x)].
(2.3.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(2.3.3) r' orders a_{j} over a_{j}_{+1}.
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}_{+1} for all
j ∈
{1,2,...,k-1}. Since r is an ordering, r must
be transitiv; thus
r must order a_{1} 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)}.
Since r' ≠ r, D is not empty. There are two cases to consider:
(2.4.6) L
is empty. This implies V(a,b) = V(b,a) for all (a,b) ∈
D. By 2.4.4 and 2.4.5,
V'(a,b) > V'(b,a) for all (a,b)
∈ 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(y,x) or [V(a_{j},a_{j}_{+1})
= V(y,x) and V(a_{j}_{+1},a_{j})
≤ V(x,y)].
(2.5.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(2.5.3) a_{j} is socially ordered over a_{j}_{+1}.
Since more than half the voters rank x
no better than tied for bottom, V(x,a_{2}) 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_{1},a_{2},...,a_{k}
∈ A
such that a_{1} = 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}_{+1})
> V(y,x) or [ V(a_{j},a_{j}_{+1})
= V(y,x) and V(a_{j}_{+1},a_{j})
≤ V(x,y)].
(2.6.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(2.6.3) a_{j} is socially ordered over a_{j}_{+1}.
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_{1} ∉ tc
and a_{k} ∈ tc, by induction
there must
exist h ∈
{1,2,...,k-1} such that a_{h} ∉
tc and a_{h}_{+1} ∈ tc.
Therefore V(a_{h},a_{h}_{+1}) < V(y,x).
But this means 2.6.1 does not hold for j = h. The
contradiction means the contrary
assumption cannot hold, which means x cannot be chosen, establishing
satisfaction
of Truncation Resistance.
QED
Proof of theorem 3: First we establish the following lemma:
Lemma 3.1: If IMC
is satisfied, then for all x,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_{1},a_{2},...,a_{k}
∈ A such that a_{1} =
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}_{+1})
> V(x,y) or [V(a_{j},a_{j}_{+1})
= V(x,y) and V(a_{j}_{+1},a_{j})
≤ V(y,x)].
(3.1.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(3.1.3) r orders a_{j} over a_{j}_{+1}.
Since r is an
ordering, r must be transitive. Therefore, by induction on
3.1.3,
r must order a_{1} 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_{1},a_{2},...,a_{k}
∈ A
such that
a_{1} = 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}_{+1})
> V(d,d') or [V(a_{j},a_{j}_{+1}) = V(d,d')
and V(a_{j}_{+1},a_{j}) ≤
V(d',d)].
(3.2.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(3.2.3) r' orders a_{j} over a_{j}_{+1}.
Since a_{1} = 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_{1},a_{2},...,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}_{+1}) > V(d,d') or [V(a_{j},a_{j}_{+1}) = V(d,d') and V(a_{j}_{+1},a_{j}) < V(d',d)].
Since no pairing in D is larger than (d,d'), by 3.2.4 the following condition must hold:
(3.2.5) (a_{j},a_{j+1}) ∉ D for all j ∈ {1,2,...,k-1}.
In other words,
for all
j ∈
{1,2,...,k-1}, r
and r' must agree on the relative ordering of a_{j}
and a_{j}_{+1}. Thus, by 3.2.3 r must order a_{j}
over a_{j}_{+1} for all
j ∈
{1,2,...,k-1}. Since r is
an ordering, r is transitive. It follows by induction that r
orders a_{1} 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_{0}.
We will show that r_{0} can
always be constructed so r_{0} complies with Strong Pareto.
Then we will show that if r_{0}
complies with Strong Pareto then the social ordering constructed from R
and r_{0} 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_{0} can always be constructed to
comply with Strong Pareto,
consider the following iterative procedure for constructing r_{0}:
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_{0} so that at first r_{0} ranks all alternatives equal to each other.
Repeat the following until r_{0} 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_{0}
ranks x equal to y and v does not rank x equal to y,
amend r_{0} so r_{0} ranks x relative to y
the same as v does.
If r_{0}
is not yet a strict ordering, then for all x,y ∈
A such that r_{0} ranks x equal to y,
amend r_{0} so r_{0} ranks x relative to y
the same as r_{A} does.
Clearly, if r_{0} is
constructed under this procedure, then r_{0} complies with Strong
Pareto.
That is, for all x,y ∈ A such
that V(x,y) > 0
and V(y,x) = 0, r_{0} orders x over y.
Next
we establish the following lemma:
Lemma 4.2: Given
any votes, if r_{0} complies with Strong Pareto, the social
ordering
constructed from the votes and from r_{0} under the procedure of
theorem 1 complies
with both IMC and Strong Pareto.
Proof of 4.2:
Assume r_{0} complies with Strong Pareto. Let r
denote the social ordering
constructed from the votes and from r_{0} 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_{0}
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.
By 4.2.1 and 4.2.2, both of the following conditions must hold:
(4.2.5) V(x,a)
> V(a,x) for all 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).
Let D denote the union of the following two subsets of Aff:
{(a,x) ∈
Aff such that (a,y) ∉ Aff}
{(y,b) ∈ Aff such that (x,b) ∉
Aff}
We will show that D
is empty. Suppose not. By lemma 1.5, 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} = 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_{1} =
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_{1},a_{2},...,a_{k}
∈ A such that a_{1} = 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_{2})
over (y,a_{2}). By 4.2.8.2, R_{P} orders
(y,a_{2})
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_{2})
over (z,x). Since R_{P} orders no pair in D
over (z,x), this implies
(x,a_{2}) ∉ D.
Thus since (y,a_{2}) ∈ Aff,
(x,a_{2}) ∈ Aff.
Since (x,a_{2}) ∈ 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_{1},a_{2},...,a_{k}
∈ A such that a_{1} = 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_{2})
∈ Aff. Thus, since D is empty,
this implies (x,a_{2}) ∈ Aff.
Since
(x,a_{2}) ∈ 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_{0}
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_{0} ⊂ C
is dropped from all votes, then for all x ∈ C\C_{0}
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_{1},a_{2},...,a_{k}
∈
A such that a_{1} = 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}_{+1})
> V(x,y) or [ V(a_{j},a_{j}_{+1}) = V(x,y)
and V(a_{j}_{+1},a_{j}) ≤ V(y,x)].
(5.1.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(5.1.3) r orders a_{j} over a_{j}_{+1}.
Since r orders y
over x, it follows by theorem
"Properties of RSocial (3)" (proved in
the document "Theorems Used in
Proofs About MAM") that (x,y) ∉ Aff. Since
V(x,y)
> V(y,x), (x,y) ∈
Maj. Since (x,y) ∈
Maj\Aff,
by inspection of the definition
of Affirmed() (x,y) must be inconsistent
with Aff ∩ Precede(x,y). This means
there
exists a sequence of alternatives a_{1},a_{2},...,a_{k}
∈
A such that a_{1} = y and a_{k} = x
and,
letting P denote {(a_{1},a_{2}),(a_{2},a_{3}),...,(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}_{+1})
> V(x,w) or [V(a_{j},a_{j}_{+1}) = V(x,w)
and
V(a_{j}_{+1},a_{j}) ≤ V(w,x)].
Thus
condition 5.1.1 must hold for the sequence a_{1},a_{2},...,a_{k}.
By inspection of the definition of Affirmed(), Aff ⊆
Maj. Therefore P ⊆ Maj.
This implies (a_{j},a_{j}_{+1}) ∈
Maj
for all j ∈
{1,2,...,k-1}. Thus condition 5.1.2 must hold
for a_{1},a_{2},...,a_{k}.
Since P ⊆ Aff, by theorem
"Properties of RSocial (3)" r must order
a_{j} over a_{j}_{+1}
for
all j ∈
{1,2,...,k-1}. Thus condition 5.1.3 must hold for a_{1},a_{2},...,a_{k}.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a_{1},a_{2},...,a_{k}
and since
a_{1} = 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:
1 | 1 | 1 | 1 | 1 |
w | w | x | a | b |
a | x | b | b | x |
b | a | a | x | w |
x | b | w | w | a |
In scenario B1 it can be seen that all
six pairings have majorities of 3 to 2. Thus the
precedence of the majorities depends on chance, and it can be checked that there
is
a 1/5 chance that MAM chooses w. That would happen if the left-most
vote is picked
first by the Random Voter Hierarchy procedure, since then the majority
precedence
order would be "b over x", "a over b",
"w over a", "x over a", "b
over w", "x over w."
Given this majority precedence order, MAM affirms "b over x",
"a over b", and
"w over a", producing the social ordering "w
over a over b over x." (If instead the
second vote is picked first, x would top the social ordering. If
the third vote is
picked
first, b would top the social ordering. If the fourth vote is picked first, a would top
the social ordering. If the fifth vote is picked
first, b would top the social ordering.
Thus there is a 1/5 chance that MAM chooses x, a 1/5 chance MAM chooses a, and
a 2/5 chance MAM chooses b.) Clearly the social ordering "w over a over b over x"
satisfies Local Independence of Irrelevant Alternatives and does not show a failure of I2C.
If the Random Voter Hierarchy procedure
picks votes in the same order when identifying
the chosen alternative and the second alternative for testing I2C compliance,
then it could
be said that MAM satisfies I2C. But if I2C is not generously interpreted,
different votes
could conceivably be picked "first" by Random Voter Hierarchy when
identifying the
chosen alternative and the second place alternative. Suppose the left-most
vote is picked
first when identifying the chosen alternative, so w is identified as the
chosen alternative.
Suppose also that the second vote or third vote is picked "first" when
identifying the
second alternative. It can be checked that MAM would choose x if w
were dropped
from all the votes and Random Voter Hierarchy picks the second vote or third
vote.
Since a majority rank x over w, it might be said that MAM does not
strictly satisfy I2C,
if the chance elements when identifying the chosen alternative and the second
alternative
are allowed to be treated independently of each other.
(If strict satisfaction of I2C is
considered more important than strict satisfaction of
Anonymity and Neutrality, MAM could be slightly altered to be entirely
deterministic.
Where MAM uses a random voter hierarchy, it could instead use a non-random
hierarchy
such as a seniority system. Where MAM uses a random ordering of the
alternatives, it
could instead use a non-neutral fixed ordering of the alternatives such as the
time of
nomination or alphabetical order.)
We next show that MAM satisfies a less
ambiguous wording of I2C that may be
considered slightly weaker than I2C:
For all 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:
Since V(x,w) > V(w,x), (x,w) ∈ Maj. There are three cases to consider:
Case 5.2.4:
Condition 5.2.1 holds. Since ρ(x-w) >
0, we can pick σ ∈ L(R,A)
such
that MAM(A,R|-w,σ)
= x. Since ρ(w) = 1, this means w
is chosen with certainty,
which implies MAM(A,R,σ)
= w. This implies (x,w) ∉ Affirmed(A,R,σ).
Case 5.2.5:
Condition 5.2.2 holds. Since ρ(w) >
0, we can pick σ ∈ L(R,A)
such
that MAM(A,R,σ)
= w. Since ρ(x-w) = 1, this means
x would be chosen with certainty
if w were dropped from each vote, which implies MAM(A,R|-w,σ)
= x.
Case 5.2.6: Condition 5.2.3 holds.
Since all three cases
are impossible, this implies the contrary assumption cannot hold,
which means V(x,w) ≤ V(w,x).
Thus MAM satisfies I2C'.
Abbreviate A' = A\{w} and
R' = R|_{A\{w}}. Assume MAM(A',R',σ')
= x
for
all σ' ∈
L(R',A'). (Thus x is chosen with
certainty from A\{w} by MAM given R'.)
We must
establish V(w,x) ≥ V(x,w).
Suppose to the contrary V(w,x) < V(x,w).
Pick σ' ∈
L(R',A') such that σ' =
σ|_{A'}. Make the following abbreviations:
Maj = Majorities(A,R).
Maj' = Majorities(A',R').
RVH = RVH(A,R,σ).
RVH' = RVH(A',R',σ').
For all a,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_{1},a_{2}),(a_{2},a_{3}),...,(a_{k}_{-1},a_{k})
∈ Aff ∩ Precede(x,w)
such that a_{1} = 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_{1},b_{2}),(b_{2},b_{3}),...,(b_{j}_{-1},b_{j})
∈ Aff' ∩
Precede'(a_{k}_{-1},x) such
that b_{1} = x and b_{j} = a_{k}_{-1}.
Let P denote {(b_{1},b_{2}),(b_{2},b_{3}),...,(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_{2}
denote the pairs in Aff' or in Aff ∩
Pairs(A') but not
in both. Since (b,b') ∈ Aff'\Aff,
(b,b') ∈ P_{2}. Since P_{2}
is not empty, by theorem
"Precedence is a Strict Ordering" we can pick (y,y') ∈
P_{2} such that the following
condition holds:
(5.3.1) For all (z,z') ∈ P_{2}, (z,z') ∉ Precede'(y,y').
There are two cases to consider:
Case 5.3.2: (y,y')
∈ Aff'\Aff. Since (y,y') ∈
Aff', (y,y') ∈ Maj'.
Thus (y,y') ∈ Maj.
Since (y,y') ∈ Maj\Aff, (y,y') must be
inconsistent with Aff ∩ Precede(y,y').
This implies there exist (c_{1},c_{2}),(c_{2},c_{3}),...,(c_{h}_{-1},c_{h})
∈ Aff ∩ Precede(y,y')
such that c_{1} = y' and c_{h} = y.
Let P_{3} denote {(c_{1},c_{2}),(c_{2},c_{3}),...,(c_{h}_{-1},c_{h})}.
There are two subcases to consider:
Case 5.3.2.1: w
∈ {c_{1},c_{2},...,c_{h}}.
Since c_{1} ∈ A' and w
∉ A', this implies
w
∈ {c_{2},...,c_{h}}.
Therefore w must be second in at least one pair in P_{3}.
But
since P_{3}
⊆ 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_{1},c_{2},...,c_{h}}.
This implies P_{3} ⊆ Pairs(A').
Since P_{3} ⊆ Aff,
P_{3} ⊆ Maj. Since P_{3}
⊆ Pairs(A')
∩ Maj, P_{3}
⊆ Maj'. By theorem
"Consistency
Maintained (2)", Aff' must be internally consistent. Therefore, since (y,y')
∈ Aff'
there must exist (c,c') ∈ P_{3} such that
(c,c') ∉ Aff'. Since (c,c')
∈ Aff\Aff' and
(c,c')
∈ Pairs(A'),
(c,c') ∈
P_{2}. 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_{2} 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_{2}, 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_{1},c_{2}),(c_{2},c_{3}),...,(c_{h}_{-1},c_{h})
∈ Aff' ∩
Precede'(y,y') such that c_{1} = y'
and c_{h} = y.
Let P_{3} denote {(c_{1},c_{2}),(c_{2},c_{3}),...,(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_{3}
such that
(c,c') ∉ Aff. Since (c,c') ∈
Aff'\Aff, (c,c') ∈ P_{2}. Since
(c,c') ∈
P_{2} 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_{1},a_{2},...,a_{k}
∈
A such that a_{1} = y and a_{k} = x
and, letting P denote {(a_{1},a_{2}),(a_{2},a_{3}),...,(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}_{+1})
> V(x,w) or [ V(a_{j},a_{j}_{+1}) = V(x,w)
and V(a_{j}_{+1},a_{j}) ≤ V(w,x)].
Thus
condition 5.1.1 must hold for the sequence a_{1},a_{2},...,a_{k}.
By inspection of the definition
of Affirmed(), Aff ⊆
Maj. Therefore P ⊆ Maj.
This implies (a_{j},a_{j}_{+1}) ∈
Maj
for all j ∈
{1,2,...,k-1}. Thus condition 5.1.2 must hold
for a_{1},a_{2},...,a_{k}.
Since P ⊆ Aff, by theorem
"Properties of RSocial (3)" r must order
a_{j} over a_{j}_{+1}
for
all j ∈
{1,2,...,k-1}. Thus condition 5.1.3 must hold for a_{1},a_{2},...,a_{k}.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a_{1},a_{2},...,a_{k}
and since
a_{1} = 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_{1},a_{2},...,a_{k}
∈
A such that a_{1} = 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}_{+1})
> V(x,y) or [ V(a_{j},a_{j}_{+1}) = V(x,y)
and V(a_{j}_{+1},a_{j}) ≤ V(y,x)].
(5.2.2) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(5.2.3) r orders a_{j} over a_{j}_{+1}.
Since r orders y
over x, it follows by theorem
"Properties of RSocial (3)" (proved in
the document "Theorems Used in
Proofs About MAM") that (x,y) ∉ Aff. Since
V(x,y)
> V(y,x), (x,y) ∈
Maj. Since (x,y) ∈
Maj\Aff,
by inspection of the definition
of Affirmed() (x,y) must be inconsistent
with Aff ∩ Precede(x,y). This means
there
exists a sequence of alternatives a_{1},a_{2},...,a_{k}
∈
A such that a_{1} = y and a_{k} = x
and,
letting P denote {(a_{1},a_{2}),(a_{2},a_{3}),...,(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}_{+1})
> V(x,w) or [ V(a_{j},a_{j}_{+1}) = V(x,w)
and
V(a_{j}_{+1},a_{j}) ≤ V(w,x)].
Thus
condition 5.1.1 must hold for the sequence a_{1},a_{2},...,a_{k}.
By inspection of the definition
of Affirmed(), Aff ⊆
Maj. Therefore P ⊆ Maj.
This implies (a_{j},a_{j}_{+1}) ∈
Maj
for all j ∈
{1,2,...,k-1}. Thus condition 5.1.2 must hold
for a_{1},a_{2},...,a_{k}.
Since P ⊆ Aff, by theorem
"Properties of RSocial (3)" r must order
a_{j} over a_{j}_{+1}
for
all j ∈
{1,2,...,k-1}. Thus condition 5.1.3 must hold for a_{1},a_{2},...,a_{k}.
Since conditions 5.1.1, 5.1.2 and 5.1.3 hold for a_{1},a_{2},...,a_{k}
and since
a_{1} = 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.
QED
Proof of theorem 6: First we establish the following lemma:
(6.1) The "larger than" and "at least as large as" relations are transitive.
Proof of 6.1: By
inspection, the "larger than" and "at least as large as"
relations are
binary relations on Pairs(A).
First we show "larger than" is transitive. Assume (x,y)
is
larger than (z,w) and (z,w) is larger than (a,b). We
must show (x,y) is larger than (a,b).
Since (x,y) is larger than (z,w), the following condition must
hold:
(6.1.1) V(x,y) > V(z,w) or [V(x,y) = V(z,w) and V(y,x) < V(w,z)].
Since (z,w) is larger than (a,b), the following condition must hold:
(6.1.2) V(z,w) > V(a,b) or [V(z,w) = V(a,b) and V(w,z) < V(b,a)].
By inspection of 6.1.1 and 6.1.2, the following condition must hold:
(6.1.3) V(x,y) > V(a,b) or [V(x,y) = V(a,b) and V(y,x) < V(b,a)].
By 6.1.3, (x,y)
is larger than (a,b). Thus the "larger than" relation is
transitive.
Next we show "at least as large as" is transitive. Assume (x,y)
is at least as large
as (z,w) and (z,w) is at least as large as (a,b). We
must show (x,y) is at least as large
as (a,b). Since (x,y) is at least as large as (z,w),
the following condition must hold:
(6.1.4) V(x,y) > V(z,w) or [V(x,y) = V(z,w) and V(y,x) ≤ V(w,z)].
Since (z,w) is at least as large as (a,b), the following condition must hold:
(6.1.5) V(z,w) > V(a,b) or [V(z,w) = V(a,b) and V(w,z) ≤ V(b,a)].
By inspection of 6.1.4 and 6.1.5, the following condition must hold:
(6.1.6) V(x,y) > V(a,b) or [V(x,y) = V(a,b) and V(y,x) ≤ V(b,a)].
By 6.1.6, (x,y) is at least as large as (a,b). Thus "at least as large as" is transitive. QED
(We could have established further that
the "at least as large as" relation is an ordering and
that the "larger
than" relation is irreflexive and asymmetric, but these results are not needed
to prove the theorem at hand.)
Resuming the proof of
6... Assume IMC is satisfied. This implies the voting
procedure
socially orders the alternatives. Let 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:
(6.2) V(x,y)
>
V(y,x).
(6.3) x is not socially ordered over y.
Since IMC is satisfied, by 6.2 and 6.3 there must exist a sequence a_{1},a_{2},...,a_{k}
∈ A such that
a_{1} = 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}_{+1})
> V(x,y) or [V(a_{j},a_{j}_{+1})
= V(x,y) and V(a_{j}_{+1},a_{j})
≤ V(y,x)].
(6.5) V(a_{j},a_{j}_{+1})
> V(a_{j}_{+1},a_{j}).
(6.6) a_{j} is socially ordered over a_{j}_{+1}.
There are two cases to consider:
Case 6.7: r orders a_{j} over a_{j}_{+1}
for all j ∈
{1,2,...,k-1}. Since r ∈
O(A), r is
transitive.
Thus, by induction r must order a_{1} 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}_{+1}.
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