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 x Î A, call x weakly Pareto-dominated if and only if 
there exists y Î A 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. 

2.  The additional information about voters' preferences regarding 
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: 

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

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: 

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,y Î A, 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 B Í A and all x Î B, let max(x,B,R) denote the maximum, over all y Î B, 
        of #R(y,x). (In other words, the largest "pairwise opposition" to x.) 
For all B Í A, let minimax(B,R) denote {x Î B such that, 
        for all y Î B, max(x,B,R) £ max(y,B,R)}. 
For all B Í A, let topcycle(B,R) denote the smallest non-empty T Í B 
        such that #R(x,y) > #R(y,x) for all x Î T and all y Î B\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,y Î A.  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 z Î A, every voter who ranks x over z also ranks y over z. 
        (3.2)  For all z Î A, 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 z Î A, #R(y,z) ³ #R(x,z).  
        (4.2)  For all z Î A, #R(z,y) £ #R(z,x).  
By 4.2, the following condition holds: 
        (5)  For all B Í A, 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,w Î A', #R(z,w) = #R'(z,w). 

Next we establish the following propositions: 

Proposition 7:  For all B Í A and all z Î B\{x}, 
if y Î B then max(z,B,R) = max(z,B\{x},R').

Proposition 8:  For all B Í A, 
if y Î B then minimax(B,R)\{x} = minimax(B\{x},R'). 

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

Proof of 7:  Pick any B Í A and any z Î B\{x}.  Assume y Î B.  
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:  z ¹ y.  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 B Í A.  Assume y Î B.  
Make the following abbreviations: 
        For all z Î A, max(z) = max(z,B,R). 
        For all z Î A, 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 w Î B\{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 w Î B 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 y Î B, this implies z Ï minimax', a contradiction.  Thus case 8.1 
is impossible.   

Case 8.2:  w ¹ x.  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 z Î A, 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 z Î A 
that f(z,A,R) = f(z,A',R').  Pick any z Î A.  There are three cases to consider:  

Case 5.1:  z = x.  By 4, the following condition must hold: 
        (5.1.1)  If x Î minimax(A,R) then y Î minimax(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 x Ï A', clearly f(x,A',R') = 0.  Thus f(x,A,R) = f(x,A',R').

Case 5.2:  z = y.  

Case 5.3:  z ¹ x and z ¹ y.  

It remains to show for all z Î A' 
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 z Î A.  There are three cases to consider:  

Case 1.1:  z = x.      

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

any s Î L(R,A) and 

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