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

there exists

and no voters rank

* Strong Pareto*
criterion:

No weakly Pareto-dominated alternative may be elected.

* Independence from Pareto-dominated alternatives* (

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:

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

satisfy. (Note: Some writers present Arrow's criteria using the name

of irrelevant alternatives

the spirit of the too-demanding

also is too demanding for any reasonable voting procedure to satisfy. In that

framework,

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,y* ∈ ** A**, let

and let #

For all

of #

For all

for all

For all

such that #

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**)

(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) #

(1.2) #

(Thus

Voter Hierarchy that the following condition holds:

(2) Any strict ordering of the alternatives generated by the

Random Voter Hierarchy procedure ranks

By 1.2, no voters rank

(3.1) For all

(3.2) For all

By 3.1 and 3.2, both of the following conditions hold:

(4.1) For all

(4.2) For all

By 4.2, the following condition holds:

(5) For all

Make the following abbreviations:

Since

(6) For all

Next we establish the following propositions:

Proposition 7: For all *B* ⊆
** A** and all

if

Proposition 8: For all *B* ⊆ ** A**,

if

Proposition 9: topcycle(*A**,*** R**)\{

Proof of 7: Pick any *B* ⊆
** A** and any

There are two cases to consider:

Case 7.1:

Case 7.2:

Thus max(

Proof of 8: Pick any *B* ⊆
** A**. Assume

Make the following abbreviations:

For all

For all

minimax = minimax(

minimax

First we show minimax\{

there exists

exists

and max

a contradiction, which means the contrary assumption cannot hold, establishing

minimax\{

the contrary. This means there exists

This implies there exists

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

First we show tc\{

First we show Minimax satisfies *IPDA*. For all *z* ∈
** A**, let

probability that Minimax elects

probability that Minimax elects

that

Case 5.1: *z* = *x*.
By 4, the following condition must hold:

(5.1.1) If *x* ∈
minimax(*A**,*** R**) then

Since the Random Voter Hierarchy procedure satisfies

any strict ordering of the alternatives generated by Random Voter Hierarchy

ranks

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*) =

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

any σ ∈
L(* R,A*) and

σ** '**
= σ|