[EM] Methods passing or failing INI

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