Re: [EM] My Bucklin multiwinner method turned more sequential
On 02/10/2012 11:18 PM, Ted Stern wrote:
Hi Kristofer,
I am very interested in PR multiwinner methods, especially those that
use ER-Bucklin.
However, I have a hard time following your logic.
Would it be possible to work out a relatively simple example using a 3
winner election, a Droop-like quota of 25% (just to make things easy),
and two factions, one with 3 candidates and 55% of the vote (thus
winning two seats), and another with two candidates and 45% of the
vote (thus winning one seat)?
Alternatively, you could use Warren Smith's 'real world' example with
9 seats and an 'Easy' Droop-like quota of 4 votes (10% of 39 votes =
3.9, plus 10% of one vote), to compare to other methods that can work
with range ballots.
http://rangevoting.org/June2011RealWorldRRVvotes.txt
My implementation of Bucklin Transferable Vote finds the following
winners for that example:
{106,102,109,101,103,108,105,110,116}
Oops. This is where I pick up a brown paper bag and pull it over my
head, because after a little tinkering, I found out my code was wrong
and it didn't actually pass the DPC.
In facing that, I went with something a little more conventional, a
little more brute force, and I actually checked my DPC and monotonicity
test code more rigorously.
So I'll describe the new logic and then give an example with a 55%/45%
situation.
The advantage of my re-engineering is that the method now handles
truncated votes. The disadvantage is that it is no longer weakly summable.
The general idea is that we first look at all one-candidate constraints
given by the Droop proportionality criterion. We go through candidates
from best scored (according to a quota Bucklin variant) to worst, and
elect those that the one-candidate constraints says we should. Then,
with our council partially decided, we go to two-candidate constraints
and do the same: fill in, from best to worst, the candidates that are
consistent with passing the two-candidate constraints. And so on for the
three, four, ... n-candidate constraints. At any time, if the council is
full, that's the outcome and we return it.
Let's be more specific.
The altered method consists of three parts: the quota Bucklin procedure,
the DAC/DSC set generation, and the constraint satisfaction (eligibility
check). These parts are then joined in an outer procedure that brings it
all together.
---
The quota Bucklin procedure ranks candidates in order of a method that
only considers the candidates one at a time. It works like this:
Each candidate is associated with an array. This array consists first of
the rank at which the candidate exceeded one Droop quota worth of
points, then the rank at which the candidate exceeded two Droop quotas,
then three Droop quotas, and so on.
A candidate's array also has, as its last entry, the number of points it
had last time it exceeded some multiple of a Droop quota, negated.
If a candidate never exceeds k Droop quotas, it's considered to exceed k
Droop quotas at a rank equal to one more than the number of candidates.
The candidates are then sorted in less-first lexicographical order of
their arrays. For instance, if you have something like:
A: 1 2 -48 (exceeded one DQ at rank 1, two DQs at rank 2, and had
48 points when it exceeded two DQs)
B: 1 1 -45
C: 1 1 -50
The negation and the exceeds k Droop quotas at a rank equal to one more
than the number of candidates tricks are both employed so that the
sorting goes right -- that someone that never exceeds k Droop quotas is
always beaten by someone who does, and that if two candidates tie as
regards the ranks at which they exceed multiples of Droop quotas, the
number of points they got after the last one was exceeded breaks the tie.
In the example above, the sorted order is:
C before B (according to the last entry: C exceeded two Droop quotas by
more than did B),
B before A (according to the second entry: B exceeded two Droop quotas
at a higher (earlier) rank than A),
and so the output ranking from the quota Bucklin procedure is C B A.
---
The DAC/DSC set generation is next. This is conceptually quite simple
when there is no equal-rank, though rather brute-force.
For each ballot, you add one point to a subset (properly called a
coalition) that consists of the first candidate ranked on the ballot.
You then add one point to the coalition consisting of the first two
candidates ranked; and then to the coalition consisting of the first
three, and so on.
With equal-rank, it gets a bit more hairy, and different interpretations
are possible (kind of like wv versus margins versus pairwise opposition
in Condorcet). For simplicity's sake, I'll leave that for now.
Note that all the subsets are unordered. So if one voter votes
BC(rest) and another votes CB(rest), that counts as one point each
towards {BC}.
---
The constraint satisfaction is a whole lot like the original method's
eligibility check. The constraint
[EM] My Bucklin multiwinner method turned more sequential
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
Re: [EM] My Bucklin multiwinner method turned more sequential
On 02/10/2012 11:02 PM, Kristofer Munsterhjelm wrote: 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. Oops, seems I reused a letter there. This should be: We can add a candidate C_i 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_i. I.e. the k in C_k had nothing to do with the cardinality of the intersection. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Bucklin multiwinner method turned more sequential
Hi Kristofer,
I am very interested in PR multiwinner methods, especially those that
use ER-Bucklin.
However, I have a hard time following your logic.
Would it be possible to work out a relatively simple example using a 3
winner election, a Droop-like quota of 25% (just to make things easy),
and two factions, one with 3 candidates and 55% of the vote (thus
winning two seats), and another with two candidates and 45% of the
vote (thus winning one seat)?
Alternatively, you could use Warren Smith's 'real world' example with
9 seats and an 'Easy' Droop-like quota of 4 votes (10% of 39 votes =
3.9, plus 10% of one vote), to compare to other methods that can work
with range ballots.
http://rangevoting.org/June2011RealWorldRRVvotes.txt
My implementation of Bucklin Transferable Vote finds the following
winners for that example:
{106,102,109,101,103,108,105,110,116}
Ted
On 10 Feb 2012 14:05:36 -0800, Kristofer Munsterhjelm wrote:
On 02/10/2012 11:02 PM, Kristofer Munsterhjelm wrote:
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.
Oops, seems I reused a letter there. This should be:
We can add a candidate C_i 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_i.
I.e. the k in C_k had nothing to do with the cardinality of the
intersection.
Election-Methods mailing list - see http://electorama.com/em for list info
--
araucaria dot araucana at gmail dot com
Election-Methods mailing list - see http://electorama.com/em for list info
