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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
