[EM] Path dependence monotonicity failure in BTV

[Kristofer Munsterhjelm]

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 
http://lists.electorama.com/pipermail/election-methods-electorama.com/2012-January/094876.html 
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.