[EM] A Bucklin-based Droop proportional method with few monotonicity problems

[Kristofer Munsterhjelm]

In trying to generalize my 2-of-3 Bucklin method, I think I have found 
one that very seldomly fails monotonicity, if at all. Since I am using 
an experimental setup (basically trying what works and checking if the 
program can find a monotonicity failure), I can not be certain that the 
method is monotone, but my program has not found any failures so far (at 
4 candidates or less for any number of seats; or at 6 candidates with 
random number of seats).

If this truly is monotone, then it is, to my knowledge, the only Droop 
proportional method that is. I even thought that it would be impossible 
to have both monotonicity and Droop proportionality, but maybe I was 
wrong. (Or maybe the failure in this method only shows up after lots and 
lots of seats and candidates)

Because it's experimental, it's only really defined for the case where 
there are no equal ranks and every voter ranks at least as many choices 
as there are seats. Handling truncation before this point, or equal rank 
is "left as an exercise to the reader" :-) But I think that if we make 
use of symmetric completion, we don't need to show that the method is 
monotone even with truncated or equal-rank votes, because these can be 
simulated with an appropriate combination of ordinary votes.

So, here goes.

Say the election is to k seats and there are n candidates.

First, calculate the Bucklin result where the threshold is the Droop 
quota rather than 50%. Ties are broken by the amount of votes the 
candidate has got at the rank where it crosses the threshold. Further 
ties are broken by the method of first differences: if both A and B have 
10 more votes than the Droop quota at rank 2, but A had three more votes 
than B at top rank, A is better than B. This can be modeled as having an 
array of results: first the rank number where the threshold was exceeded 
(or the total number of ranks minus this, if greater is better), then 
the result at the rank where the threshold was exceeded, then results 
for the first rank, second rank, etc. A comparison operator between two 
candidates would compare the first element of each candidate's array, 
then the second, then the third, etc, until one is greater than the other.

Call this the tiebreaker order. Candidates can be compared by comparing 
their arrays. Subsets of candidates can be compared by comparing the sum 
of their arrays (e.g. {AB} vs {CD} by comparing A's array + B's array to 
C's array + D's array).

Then, the multiwinner Bucklin process:

This process consists of two steps, which I'll call the "increment" and 
the "eligibility check" respectively. In an increment with parameter k, 
you take every possible subset of k candidates, where at least one of 
the candidates is at the current rank and all candidates in the subset 
appear at or before the current rank in the ballot in question; and 
increment a score number associated with the subset. This is done for 
each ballot.

For instance, if you have ballot data like this:

10: A>B>C>D
  5: C>D>A>B

and the parameter k is 2, and current rank is third, then you add 10 to:
AC (A is at first rank, i.e. before third, and C is at current rank, 
thus satisfying that constraint),
BC (B is at first rank, and C is at current),
but not AB (none at current rank) or CD (D is at a lower rank).

You then add 5 to AC and AD.

In this respect, the increment is like Bucklin. An increment with a 
parameter 1 is the same thing as one round of single-winner Bucklin.

If you have a parameter greater than the current rank, the function will 
of course not increment anything.

-

The eligibility check is rather simple, though takes a lot of time in 
practice. It may be optimized, but I haven't done so. Its logic is as 
follows:

Each subset that has a score of p can give q candidates to the outcome, 
where q is the minimum of the number of candidates in the subset, and 
the number of Droop quotas for which the score of that subset is greater 
than this number of Droop quotas.

Each set of candidates so that it is possible to assign the candidates 
to the subsets without violating the q-constraint above is a possible 
outcome. Of possible outcomes, pick the one with the best tiebreaker 
order. Since these outcomes will involve multiple candidates, in 
practice, you compare sums as mentioned above. If there are more than 
one subset with the same tiebreaker order/sum, break randomly (or 
according to a casting vote, etc).

To give an example of the eligibility check, consider an election with

50: A>B>C>D
50: D>E>F>G

two seats, and we're at second rank so the subsets are:

50: AB
50: DE

with the Droop quota being 100/3 = 33 + 1/3.

Then the AB set supports one candidate and the DE set supports another. 
So the possible outcomes are {AD, BD, AE, BE} but not, say, {AB} 
(because the AB subset can only support one candidate), nor {DE} (for 
the same reason). The winner here would be {AD} because both reach the 
Droop quota at first rank, and so they would have better tiebreaker 
scores than any of the other candidates.

If there are no possible outcomes, the eligibility check returns nothing.

-

So now we just have to put all of this together. There are two variants 
- one that is weakly summable and one that is not. Let's call the 
former, "variant A", and the latter, "variant B".

In variant A, first calculate the tiebreaker. Then, for each rank from 
top rank and down:
  1. increment with parameter 1 and current rank.
  2. increment with parameter equal to number of seats, and current rank.
  3. run an eligibility check. If it returns something, that's the 
outcome, otherwise loop to next rank.

In variant B, first calculate the tiebreaker. Then, for each rank from 
top rank down:
  1. for every integer r = 1...number of seats, inclusive:
    1.1. increment with parameter r and current rank.
  (end for)
  2. run an eligibility check. If it returns something, that's the 
outcome, otherwise loop to next rank.

-

I have been testing just variant A, and it seems to be monotone, but 
there may be complex "revelation" scenarios where you could trick it to 
be nonmonotone. On the other hand, if A is monotone all the time, then 
it is preferable because it's weakly summable.

I put the "parameter 1" thing in A because of just such a "revelation" 
scenario. The parameter 1 scenario goes something like:

C and D have more than a Droop quota each at first rank, but we don't 
detect this because we don't have a parameter-1 subset.

So at rank 2, a set that includes C or D has more than a Droop quota. 
Say it's {AD}, and {AC} is exactly at the Droop quota. However, these 
are on different ballots so they don't increment {CD} enough. So {CD} is 
never a possible outcome and, say, AD wins. The method can't pick from 
{AC} either - {AC} needs to exceed the quota, not just be at it, for 
that to be possible.

Now someone raises A on a ballot that used to go

C>B>A>D.

That increments the count for {AC}, so now one can pick one candidate 
from {AD} and one from {AC}. The method then finds out that if it picks 
D from the former and C from the latter, it gets something with a much 
better tiebreaker result - so it does, so the method fails monotonicity.

The problem is that it can't know, by cardinality-two subsets alone, 
whether A or C caused {AC} to go above the Droop quota. By using a 
parameter 1 increment, if C and/or D go above the quota in the first 
rank (and so would dominate every other subset in the tiebreaker), then 
the method will include them in possible outcomes, thus averting the 
situation.

It seems to me you could use the same reasoning as for why a 3-seat 
method also needs to consider 2-seat subsets, but I haven't been able to 
get the method to fail monotonicity even with variant A. So maybe I'm 
missing something -- or maybe the monotonicity failure example would be 
very hard to find, something on the order of Smith,Minmax examples of 
mono-add-top failure.

-

Any suggestions? Comments? Failure examples? Ideas for a name?

(And now I'll be away for some time, dealing with real world things!)