[EM] Methods passing or failing INI
Richard Moore
moore3t1 at cox.net
Thu Apr 8 00:17:04 PDT 2004
I recently wrote that I believed Shulze and Tideman would fail INI.
I said I would post a demonstration if I could construct one, and I
have done that; in fact the same counterexample applies to both methods.
For those who missed it, I defined Independence from Nonsupporting
Information (INI) as: "If X wins and Y loses, and margin(X,Z) <=
margin(Y,Z), then removing candidate Z from the election shall not
cause Y to win and X to lose."
As Ken Johnson pointed out, the phrase "from the election" isn't quite
accurate, and he suggested "from the count". I think a better phrase
than either would be "from all ballots", so my modified definition is
"If X wins and Y loses, and margin(X,Z) <= margin(Y,Z), then removing
candidate Z from all ballots, leaving those ballots otherwise
unchanged, shall not cause Y to win and X to lose."
margin(X,Y) represents the number of voters favoring X to Y minus the
number of voters favoring Y to X. This value can be positive,
negative, or zero.
The above definition supports single- and multi-winner methods. For
only single-winner methods it can be simplified to: "If margin(X,Z) <=
margin(Y,Z), and the winner is X, then removing Z from all ballots,
leaving those ballots otherwise unchanged, shall not change the winner
to Y."
A very simple (but imprecise) paraphrase of INI is: "A method's result
should not depend on information that does not support that result."
If A wins and B loses an election, then the presence of candidate C in
the election provides evidence supporting this result iff margin(A,C)
> margin(B,C). If margin(A,C) <= margin(B,C), then the presence of C
is nonsupporting with respect to the A>B result. As shorthand, we
could say "C supports A over B" in the first case, or "C does not
support A over B" in the second case; I will use these phrases in the
following discussion.
My counterexample proving RP and Schulze both fail INI is:
5: A=C>B>D
5: B>D>A=C
4: C=D>A>B
4: A>B>C=D
3: B=C>D>A
3: D>A>B=C
2: A=B>D>C
2: D>C>A=B
1: B=D>C>A
1: C>A>B=D
In this example, D does not support A over C; in fact, D actually
supports C over A (6: D>A, 4: D>C).
In both Shulze and Tideman, A wins. If D is removed, the ballots become:
5: A=C>B
5: B>A=C
4: C>A>B
4: A>B>C
3: B=C>A
3: A>B=C
2: A=B>C
2: C>A=B
1: B>C>A
1: C>A>B
and C wins. (Results checked using the ranked-ballot voting calculator
at http://cec.wustl.edu/~rhl1/rbvote/calc.html.)
IRV and FPTP (using ranked ballots for FPTP) both fail INI in the
following case:
49: X>Y>Z
30: Z>Y>X
21: Y>X>Z
X wins in both methods. Z does not support X over Y, but removing Z
makes Y win in both methods.
Proof that Bucklin fails:
2: X>Y>A>B>Z
2: X>Z>Y>A>B
4: Y>Z>A>B>X
1: Y>Z>B>A>X
4: B>X>Y>A>Z
The winner is X. margin(X,Z) = 3, and margin(Y,Z) = 9, so Z is
non-supporting of X over Y. Now remove Z:
4: X>Y>A>B
4: Y>A>B>X
1: Y>B>A>X
4: B>X>Y>A
and Y wins.
Approval passes: In single-winner elections, removing a non-winning
candidate from every ballot cannot change the winner. In multi-winner
elections, if X wins with Z included, then removing Z cannot make X a
loser.
Copeland passes: If X wins and Y loses, then removing Z can reverse
those results only if X beats Z and Y does not beat Z. In all such
cases, Z supports X over Y -- so a change in winner from X to Y caused
by removing Z is allowed under INI.
Borda may pass or fail INI, depending on the scoring method and on
ballot restrictions. I will consider the scoring method in which
candidate X's Borda score is the sum of X's margins over each of the
other candidates.
score(X) = sum_i(margin(X,Ci))
Ci represents the ith candidate, and sum_i represents the sum over
all the values of i. It doesn't matter if we include Ci = X in the sum
since margin(X,X) = 0.
Suppose that X beats Y strictly:
sum_i(margin(X,Ci) > sum_i(margin(Y,Ci)
Now imagine we find a candidate Cj (where Cj is some candidate that is
neither X nor Y), such that removing Cj changes the winner from X to Y
(i.e., reverses the above inequality, or changes it to an equality so
that a tie-breaker picks a different winner). In order to do that, it
is necessary that
margin(X,Cj) > margin(Y,Cj)
i.e., Cj supports X over Y. The same would have to hold if X beats Y
via a tie-breaker before Cj is removed, and Y strictly beats X after
Cj is removed. [There is an assumption here that tie-breakers between
any two candidates are invariant with respect to removal of a third
candidate, as would be the case where a random tie-breaking ranking is
selected beforehand. Then, if X beats Y by tie-breaker, and removing
Cj affects both X's and Y's scores identically, the winner of the
tie-breaker does not change from X to Y. Choice of tie-breaking
procedure can affect a method's compliance with INI. One way around
this would be to define INI in terms of not changing the probability
of X beating Y, for a given set of ballots, when Z is removed.]
If we allow tied rankings, *and* use the more traditional Borda count
(summing the pairwise votes in favor of X over each other candidate,
rather than margins), Borda fails INI. We can construct an example
where Y is tied with C0 (or Z) on every ballot, and approximately half
the voters prefer X to Z while the remainder prefer Z to X:
49: X>Y=Z
51: Y=Z>X
Here X wins. But remove Z, and Y wins. However, the presence of Z
actually supports Y over X, not X over Y. So "traditional" Borda, with
tied rankings allowed, fails INI.
I have not determined whether "traditional" Borda would pass INI if
only truncation is allowed (i.e., no tied rankings above a ballot's
truncation point).
Noticing that, so far, methods passing INI have not been
clone-resistant, it's time to ask whether INI is too strong a
criterion. Obviously it is a weaker criterion than IIA, since IIA
compliance implies INI compliance, but not the other way around. So
far, I haven't found a satisfactory way of weakening INI. I'm open to
suggestions.
I don't want to give the impression that I think INI is an absolute
must-pass criterion. Obviously some of the methods that fail it still
have goood qualities. Rather, INI is motivated by a desire to replace
IIA with something that actually does provide useful information about
a method. If INI is more acceptable than IIA (and I believe it should
be), surely this reduces the significance of Arrow's theorem, because
there are non-dictatorial, Pareto-optimal, monotonic ranked methods
that pass INI.
-- Richard
More information about the Election-Methods
mailing list