Independence from Pareto-dominated alternatives
A criterion for voting rules

Revised:  January 26, 2003

Let A denote the finite non-empty set of nominated alternatives.

For all xA, call x weakly Pareto-dominated if and only if
there exists yA such that at least one voter ranks y over x
and no voters rank x over y

Strong Pareto criterion:
No weakly Pareto-dominated alternative may be elected.

Independence from Pareto-dominated alternatives (IPDA) criterion:
The election outcome must not change if a weakly Pareto-dominated
alternative is deleted from the set of nominees and from the votes.

The Strong Pareto criterion is well-known and easy to justify (and easy to satisfy).
But we believe it is desirable that voting methods also satisfy the stronger criterion,
IPDA.  Here are two reasons why, followed by an example that illustrates the
problem that may arise if the voting method fails IPDA

1.  It is relatively easy to find alternatives that are Pareto-dominated
(or nearly so) by an alterative already under consideration, so would-be
manipulators may nominate such "inferior" alternatives to change election
outcomes in their favor if the voting method does not satisfy IPDA

Pareto-dominated alternatives is essentially redundant.  Thus it would
be inconsistent if such information affected an election outcome.

Example 1:  Borda fails IPDA
Suppose 5 voters rank 3 alternatives {a,b,c} as follows:

 3 2 a b b c c a

(Every voter ranks b over c, which means c is Pareto-dominated.)
The Borda voting rule scores for each nominee x the total number of times
any nominee is ranked below x, and elects the nominee with the largest score.
If only a and b are nominated, Borda would score 3 points for a (since b is
ranked below a in 3 votes) and 2 points for b (since a is ranked below b
in 2 votes), and would elect a.  But if c is also nominated, Borda would
score 3 + 3 = 6 points for a and 3 + 2 + 2 = 7 points for b and 2 points
for c, and would elect b.  This means people who prefer b over a have
an incentive to also nominate c, even though everyone believes c is inferior
to b.  For the same reason, people who prefer a have an incentive to seek
out and also nominate alternatives (not shown) that are inferior to a.
Thus elections under Borda could become farcical, with each faction
seeking to nominate as many inferior alternatives as possible, and with
outcomes dependent on which faction has more resources for that task.

IPDA is a weakening of one of Kenneth Arrow's criteria, independence of irrelevant
alternatives
(IIA), which is too demanding for any reasonable voting procedure to
satisfy. (Note: Some writers present Arrow's criteria using the name independence
of irrelevant alternatives
for a weak criterion that is easy to satisfy.  They move
the spirit of the too-demanding IIA to a criterion called choice consistency that
also is too demanding for any reasonable voting procedure to satisfy.  In that
framework, IPDA is a weakening of choice consistency.)

It may be harder to exploit violations of IPDA under some methods than under others,
since it is presumably easier to find Pareto-dominated "clone" alternatives than Pareto-
dominated "non-clone" alternatives that fit a particular configuration of preferences.
The following examples showing violations of IPDA by MAM and by PathWinner
are thus less egregious than the example above showing violation by Borda.

Example 2:  MAM, Ranked Pairs 1987, and Ranked Pairs 1989 fail IPDA.
Suppose 15 voters rank four alternatives {a,b,c,d} as follows:

 6 2 4 3 a d b b b a c d c b d a d c a c

Every voter ranks b over c, so b Pareto-dominates c. (Note that the first 12
voters rank c immediately below b.  Changing the example so that any or all
of the first 12 voters rank c indifferent to b, meaning b would merely weakly
Pareto-dominate c, would still be an example showing failure to satisfy IPDA
since the outcome here does not depend on the size of the b over c majority.)
There are 6 majorities:
15 voters rank b over c.
13 voters rank b over d.
11 voters rank a over c.
10 voters rank c over d
9 voters rank d over a
8 voters rank a over b
MAM first affirms the largest majority, b over c.  Then MAM affirms the next
largest majority, b over d (since it is consistent with the majorities already affirmed).
Then MAM affirms the next largest majority, a over c (since it is consistent with
the majorities already affirmed).  Then MAM affirms the next largest majority,
c over d (since it is consistent with the majorities already affirmed).  Then MAM
does not affirm the next largest majority, d over a (since it is inconsistent with
the majorities already affirmed, specifically a over c and c over d).  Then MAM
affirms the next largest majority, a over b (since it is consistent with the majorities
already affirmed).  Thus the MAM social ordering is "a over b over c over d
and MAM elects a since a is not second in any affirmed majority.
To satisfy IPDA, MAM must still elect a if c is not an alternative under
consideration.  If c were not an alternative, there would be 3 majorities:
13 voters rank b over d.
9 voters rank d over a
8 voters rank a over b
Without c, MAM would affirm the two largest majorities, b over d and d over a
and not affirm the smallest majority, a over b (since it is inconsistent with those
already affirmed).  The MAM social ordering would be "b over d over a" and
MAM would elect b since b would not be second in any affirmed majority.
Thus MAM does not satisfy IPDA.

The consequence of MAM's failure to satisfy IPDA in the example is that if a, b and d
are already under consideration, voters who prefer a over b have a strategic incentive
to seek out and nominate c even though they (and the other voters) believe c is worse
than b.  No one can say for certain which alternative most deserves to be elected or
which is best for the group (particularly since the majorities are sincerely cyclic), but
we can say that nominating c adds clutter to the ballot--and there may be additional
"inferior" alternatives whose nomination may swing the outcome back and forth, thus
creating incentives to clutter the ballot even more.  Also, spending time on strategic
ploys is time that could be spent on other, perhaps more useful, endeavors.

On the other hand, other strategies could come into play in such scenarios:

1.  The majority who prefer a over b could simply rank a top, so that a will
be elected regardless of what other alternatives are nominated or how the
other voters vote.

2.  If some of b's supporters are as strategically-minded as those who would
strategically nominate c, the three b supporters who rank c bottom could
strategically vote c higher, over a and d, so that b will be elected.

Thus it may be that satisfaction of IPDA is significant only in elections where few voters
will vote strategically--perhaps public elections or small unprofessional committees--
but some are strategically-minded, capable of predicting preferences and finding
an alternative like c, and have the power to nominate that alternative.

Example 3:  PathWinner fails IPDA.
Suppose 30 voters rank five alternatives {a,b,c,d,e} as follows:

 1 5 3 2 2 6 4 5 2 a a a b b c c d d d d b a d b a e b e e d d e a b c e c b e e c d d a c b c c c a e e b a

Since every voter ranks d over e, d Pareto-dominates e. (Note that even if some of
the first 28 voters, who rank d immediately over e, instead are indifferent between d
and e, the example still shows a violation of IPDA.)  Without e there are 6 majorities:
21 voters rank a over d.
20 voters rank d over c.
19 voters rank c over a.
18 voters rank a over b
17 voters rank b over d
16 voters rank c over b
Without e, PathWinner elects a:
The strength of the strongest path from a to b, ab, is 18.
The strength of the strongest path from b to a, bdca, is 17.
Thus a finishes over b.
The strength of the strongest path from a to c, adc, is 20.
The strength of the strongest path from c to a, ca, is 19.
Thus a finishes over c.
The strength of the strongest path from a to d, ad, is 21.
The strength of the strongest path from d to a, dca, is 19.
Thus a finishes over d.
But with e included, there are 4 additional majorities and PathWinner elects b
30 voters rank d over e.
21 voters rank a over e.
20 voters rank e over c.
19 voters rank b over e.
The strength of the strongest path from b to a, beca, is 19.
The strength of the strongest path from a to b, ab, is 18.
Thus b finishes over a.
The strength of the strongest path from b to c, bec, is 19.
The strength of the strongest path from c to b, cab, is 18.
Thus b finishes over c.
The strength of the strongest path from b to d, becad, is 19.
The strength of the strongest path from d to b, dcab, is 18.
Thus b finishes over d.
The strength of the strongest path from b to e, be, is 19.
The strength of the strongest path from e to b, ecab, is 18.
Thus b finishes over e.
Thus PathWinner does not satisfy IPDA
(I have not spent time trying to reduce the number of voters needed to show
that PathWinner fails IPDA.  Presumably this can be done.  More interesting is
the question whether the number of alternatives can be reduced and still show
that PathWinner fails IPDA.)

Theorem:  "Minimax and TopCycle-Minimax satisfy IPDA."

Some definitions:
For all x,yA, let R(x,y) denote the votes that rank x over y
and let #R(x,y) denote the number of votes that rank x over y.
For all BA and all xB, let max(x,B,R) denote the maximum, over all yB
of #R(y,x). (In other words, the largest "pairwise opposition" to x.)
For all BA, let minimax(B,R) denote {xB such that,
for all yB, max(x,B,R) ≤ max(y,B,R)}.
For all BA, let topcycle(B,R) denote the smallest non-empty TB
such that #R(x,y) > #R(y,x) for all xT and all yB\T

Minimax elects an alternative in minimax(A,R). (If there is more than one,
the Random Voter Hierarchy procedure is used to pick one of them.  Note
that Random Voter Hierarchy generates a strict ordering of the alternatives
that ranks Pareto-dominated alternatives below the alternatives that Pareto-
dominate them.  It generalizes the Random Dictator procedure in order to
generate a strict ordering even when votes may be non-strict orderings.)

TopCycle-Minimax elects an alternative in minimax(topcycle(A,R),R).
(If there is more than one, the Random Voter Hierarchy procedure is
used to pick one of them.)

Proof:  Pick any x,yA.  Assume both of the following conditions hold:
(1.1)  #R(y,x) > 0.
(1.2)  #R(x,y) = 0.
(Thus y weakly Pareto-dominates x.)  It follows by the definition of Random
Voter Hierarchy that the following condition holds:
(2) Any strict ordering of the alternatives generated by the
Random Voter Hierarchy procedure ranks y over x.
By 1.2, no voters rank x over y, so both of the following conditions hold:
(3.1)  For all zA, every voter who ranks x over z also ranks y over z
(3.2)  For all zA, every voter who ranks z over y also ranks z over x.
By 3.1 and 3.2, both of the following conditions hold:
(4.1)  For all zA, #R(y,z) ≥ #R(x,z).
(4.2)  For all zA, #R(z,y) ≤ #R(z,x).
By 4.2, the following condition holds:
(5)  For all BA, max(y,B,R) ≤ max(x,B,R).
Make the following abbreviations:
A' = A\{x}.
R' = R|A' (that is, the restriction of R to the alternatives excluding x).
Since R' = R|A', the following condition holds:
(6)  For all z,wA', #R(z,w) = #R'(z,w).

Next we establish the following propositions:

Proposition 7:  For all BA and all zB\{x},
if yB then max(z,B,R) = max(z,B\{x},R').

Proposition 8:  For all BA
if yB then minimax(B,R)\{x} = minimax(B\{x},R').

Proposition 9:  topcycle(A,R)\{x} = topcycle(A',R').

Proof of 7:  Pick any BA and any zB\{x}.  Assume yB.
There are two cases to consider:
Case 7.1:  z = y.  By 1.2 and 6, max(y,B,R) = max(y,B\{x},R').
Case 7.2:  zy.  By 4.1 and 6, max(z,B,R) = max(z,B\{x},R').
Thus max(z,B,R) = max(z,B\{x},R') in both cases, establishing 7.

Proof of 8:  Pick any BA.  Assume yB.
Make the following abbreviations:
For all zA, max(z) = max(z,B,R).
For all zA, max'(z) = max(z,B\{x},R').
minimax = minimax(B,R),
minimax' = minimax(B\{x},R').
First we show minimax\{x} ⊆ minimax'.  Suppose the contrary.  This means
there exists z ∈ minimax\{x} that is not in minimax'.  This implies there
exists wB\{x} such that max'(w) < max'(z).  By 7, max'(w) = max(w
and max'(z) = max(z).  Thus max(w) < max(z).  But this implies z ∉ minimax,
a contradiction, which means the contrary assumption cannot hold, establishing
minimax\{x} ⊆ minimax'.  Next we show minimax' ⊆ minimax.  Suppose
the contrary.  This means there exists z ∈ minimax' that is not in minimax.
This implies there exists wB such that max(w) < max(z).  There are two
cases to consider:

Case 8.1:  w = x.  By 5, max(y) ≤ max(x).  Thus max(y) < max(z).
By 7, max(y) = max'(y) and max(z) = max'(z).  Thus max'(y) < max'(z).
Since yB, this implies z ∉ minimax', a contradiction.  Thus case 8.1
is impossible.

Case 8.2:  wx.  By 7, max(w) = max'(w) and max(z) = max'(z).
It follows that max'(y) < max'(z).  But this implies z ∉ minimax'
a contradiction.  Thus case 8.2 is impossible.

Since both cases are impossible, the contrary assumption cannot hold.
Thus minimax' ⊆ minimax.  Since minimax\{x} ⊆ minimax' and
minimax' ⊆ minimax, 8 is established.

Proof of 9:  Make the following abbreviations:
tc = topcycle(A,R).
tc' = topcycle(A',R').
First we show tc\{x} ⊆ tc'.  Pick any z ∈ tc\{x}.  We must show z ∈ tc'.

First we show Minimax satisfies IPDA.  For all zA, let f(z,A,R) denote the
probability that Minimax elects z from A given R, and let f(z,A',R') denote the
probability that Minimax elects z from A' given R'.  We must show for all zA
that f(z,A,R) = f(z,A',R').  Pick any zA.  There are three cases to consider:

Case 5.1:  z = x.  By 4, the following condition must hold:
(5.1.1)  If xminimax(A,R) then yminimax(A,R).
Since the Random Voter Hierarchy procedure satisfies strong Pareto
any strict ordering of the alternatives generated by Random Voter Hierarchy
ranks y over x.  Thus, by 5.1.1 Minimax does not elect x, which means
f(x,A,R) = 0.  Since xA', clearly f(x,A',R') = 0.  Thus f(x,A,R) = f(x,A',R').

Case 5.2:  z = y.

Case 5.3:  zx and zy.

It remains to show for all zA'
that f(z,A,R) = f(z,A',R').  To do so we first establish the following proposition:

Proposition 6:  minimax(A,R) ∩ A' = minimax(A',R').

Pick any zA.  There are three cases to consider:

Case 1.1:  z = x.

that w is elected by Minimax from A' given R' and σ'

any σ ∈ L(R,A) and

σ'  = σ|A' (that is, the restriction of σ to the alternatives excluding x).