[EM] Path dependence monotonicity failure in BTV
Kristofer Munsterhjelm
2018-02-18 14:23:40 UTC
Here's a concrete example of the kind of BTV monotonicity failure I've
been talking about. It's not optimized, so go ahead and do so if you'd like:

9: A>B
2: A>B>E
975: A
8: A>E
10: B>A
984: B>C
19: C
993: E

3000 voters, two seats. The Droop quota is 1000.

I'm using BTV without skipping ranks. Thus after some candidate is
elected, the elimination of the winner shifts the remaining candidates
up (like in STV); there's no "hole" in the ballot ranking where the
winner used to be.

For the profile above, the first round count is as follows:
A: 994, B: 994, C: 19, E: 993
Nobody exceeds a Droop quota, so we go to the second round.

The second round count is: A: 1004, B: 1005, C: 1003, E: 1001
Everybody exceeds the Droop quota. B is elected no matter whether the
tiebreak is greatest count in last round or leximax/first differences
(as they amount to the same thing here).

After the reweighting, the first round count is:
A: 983.055, C: 19, E: 993
and the second round count is:
A: 983.105, C: 23.92, E: 1001

so E wins.

Now raise E on the two A>B>E ballots to A>E>B.

The first round is as above (no change to first ranks). The second round
count is:
A: 1004, B: 1003, C: 1003, E: 1003

so A is elected. After reweighting, the first round count is
B: 984.04, C: 19, E: 993
and the second round count is:
B: 984.076, C: 1003, E: 993.032

so C wins. Thus raising E made E lose, which is a monotonicity failure.


The general pattern is to set up a situation where A and B are nearly
tied; and electing A means C will get the second seat, whereas electing
B means E will get the second seat.
Then let some ...>B>E>... ballots swing the near-tie in favor of B.
Raising E then obscures B and A wins instead.

I think the "right" outcome of the election above is {A, B}. That's also
what STV picks.

I initially thought that perhaps the right leximax tiebreak disregards
the last s-1 ranks up to the rank of the tie inclusive, where s is the
number of seats, but that would cause certain... problems if a tie were
to occur, say, in the first round. Maybe we would need to exclude every
outcome that doesn't contain one of the tied-for-win candidates (or more
than one of, depending).


If we pad the

975: A
19: C
993: E

ballots to

975: A>X
19: C>Y
993: E>Z

then the method of
fails to produce an outcome. Thus it's not nonmonotone; it just doesn't
work. (Which is a more serious error, I'd imagine. It is in some sense
analogous to something like
1: A
1: B
1: Z
with ordinary Bucklin, where nobody ever attains a Droop quota, but more
serious than this.)

Symmetrically completing the ballots instead of padding doesn't work;
the method just says that every two-candidate subset exceeds a Droop
quota at the third round. Since the tiebreak is the usual leximax, the
method ends up being vulnerable.
Election-Methods mailing list - see http://electorama.com/em for list info
Continue reading on narkive: