[EM] My Bucklin multiwinner method turned more sequential

[Kristofer Munsterhjelm]

Earlier I mentioned that I had found a way of making my Bucklin 
multiwinner method more managable - more sequential. I did not, however, 
say exactly how I had done that.

So why not do that here?

Consider my previous version of the Bucklin multiwinner method (for 
which I still haven't found a name). It consists of an addition part 
(where we add points to subsets consisting of candidates ranked at or 
above the rank corresponding to the current round), and of an 
eligibility part (where we try different combinations to see if we can 
make a council). The problem with the eligibility part is that the 
tiebreaker, which we use to find out which possible council is the best, 
uses the sum of the candidates' "quota Bucklin" tiebreaker scores.

But now consider what happens if we replace the sum-of operator with a 
leximax operator.

Say that the candidates, in order of greatest quota Bucklin score first, 
are C_1, C_2, C_3, etc.[1] Then, if the tiebreaker is leximax, we know 
that any council with C_1 on it will beat every council that doesn't 
have C_1 on it. Similarly, a council with C_1 and C_2 on it will beat 
every council with C_1 but without C_2 (and a council without C_1 but 
with C_2 will beat every council with neither C_1 nor C_2).

That sounds like something that can be approached with a greedy 
algorithm, and sure enough, it can be. This greedy algorithm, which 
replaces the eligibility check, goes like this:

==

Start at the top of the list of candidates (at C_1), and with a 
prospective council PC that starts as the empty set.

If PC has as many members as there are seats, we're done: return PC.
If we've exhausted the candidate list and PC is still not fully formed, 
return the empty set: no council can be picked yet.

Otherwise, check if we can add C_1 to PC without breaking the support 
constraint of the Bucklin method. If we can, add C_1 to PC, otherwise don't.

In either case, move down the list one step (so it is now C_2) and loop.

-

We can add a candidate C_k to PC if there exists a subset (coalition) 
that supports at least k+1 candidates, where k is the cardinality of the 
intersection of PC and that coalition, and that coalition also contains C_k.

A coalition supports q candidates if it has more points than q Droop 
quotas. (This handles the rounding problem with integer Droop quotas 
nicely.)

==

This greedy algorithm works because, at every step, it does the optimal 
thing given the leximax tiebreaker. At any given step, the subset to 
elect of candidates with greater tiebreaker score than the current 
candidate has been fixed. Thus, the best thing we can do is to get the 
current candidate on board. Whether or not that is possible, the same 
invariant holds when we go to the next step, because we *tried*.

Apart from the greedy algorithm above, the rest of the logic remains 
unchanged.

The add-points step for a single given ballot for round k and number of 
seats s is still: to each subset or coalition of cardinality s, where 
one of the candidates is the candidate ranked on that ballot at rank k, 
and all other candidates are ranked higher than kth place, add a point 
to that coalition. Also add a point to the one-member coalition 
consisting of just the candidate at rank k.

The add-points step for the whole ballot set is just the add-points step 
for every ballot in that set. Weighted ballots are handled as expected - 
add not one point, but a number of points equal to the weight.

The outer loop is also the same. For each round (from 1 to the number of 
ranks inclusive, or 0 to the number of ranks exclusive if you use 
0-based numbering), first do the add-points step with the current round 
number and the number of seats. Then run the greedy algorithm. If it 
returns a council, that's the outcome, otherwise proceed to the next round.

Finally, "quota Bucklin" - the single-candidate algorithm that produces 
the tiebreaker scores - remains unchanged. It's just Bucklin with a 
Droop quota as threshold rather than majority, and the outcome can be 
turned into scores by noticing at what rank each candidate exceeds the 
threshold, and by how much. I can give pseudocode if you need a more 
exact definition, but it should be simple enough.

-

So that's my more managable variant. Does it make it simpler? It seems 
so to me, at least. The add-points step is a reasonable generalization 
of Bucklin, and the eligibility algorithm narrows down the possible 
options until only one council remains.

The modification might give the method seat-independent polynomial 
runtime, but I am not certain of that. Like STV, the runtime depends on 
the number of ballots, however, not just the number of candidates 
(unlike say, Condorcet with a provided matrix).

At first, it might seem that the adding-points step could take 
superpolynomial time because there can be up to r choose s coalitions 
per round (where r is the rank number and s is the number of seats), but 
I think a counter similar to that of DAC/DSC can work here: if there are 
V different ballots, and V is small enough, then there can't be r choose 
s different coalitions because there aren't enough ballots to cover them 
all; and if V is large, then we can't do better than grow proportional 
to some polynomial of V anyway. However, I could be wrong, which is why 
I say it *might* give the method seat-independent polynomial runtime.

(You could also do a lot of optimization with sophisticated data 
structures to save on time doing set intersections and the likes. For 
clarity, I've omitted these optimizations in the description.)

Unlike STV, the method is weakly summable (i.e. with the number of seats 
fixed, you can do precinct summation with a polynomial amount of data). 
Also unlike STV, it appears to be monotone, but it probably isn't 
cloneproof (since Bucklin isn't). The "sequentialization" doesn't change 
any of these properties.

-

[1] I imagine true ties could be broken by incorporating something like 
Random Voter Hierarchy to the comparison operator used by the sorting 
algorithm.