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
B>C>(rest) and another votes C>B>(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 satisfaction takes a partial council
PC, a list L of candidates, and a cardinality number c.
We start at the top of the list L of candidates. If PC is full, we just
return PC. Otherwise, call the next candidate to check, Cr. If Cr is in
L, loop to the next candidate on the list. Otherwise, check if we can
put the Cr into PC. If we can, do so, and in any case, loop to the next
candidate on the list.
We can put Cr into PC if there exists a coalition C so that:
- C contains Cr
- C has more votes (points) assigned to it than q+1 Droop quotas,
where q is the cardinality of the intersection of PC and C.
If we find such a C, that means there's a Droop proportionality
constraint that we can satisfy (or come closer to satisfying) by adding
the prospective candidate Cr to our partial council PC. In other words,
we're trying to satisfy as many cardinality-c Droop constraints as
possible, and if they can be satisfied in many ways, we do so with the
highest ranked candidates (since the quota Bucklin ranking is monotone).
---
Finally, the outer procedure works like this:
First, get the list of candidates in quota Bucklin ranked order. Call
this list L.
Then, run the constraint satisfaction with PC and c = 1 - i.e. consider
only single-candidate constraints. This may append candidates to PC, so
check if it's full. If it is full, return it, otherwise go on and run
the constraint satisfaction with c = 2. Do the same thing with c = 3, c
= 4, etc, until either PC is full or we've exhausted all ranks.
(PC should be full at the end, because there's always a coalition that
has points equal to the number of voters and contains all candidates. So
assume that we reach c = number of candidates. Then every hitherto
unadmitted candidate can now be included in Cr, so the method fills PC
with unadmitted candidates from the top of L towards the bottom until PC
is full.)
---
The general logic is: we use a ranked order that is monotone, and then
we fix the partial council according to one-candidate constraints. These
will then exclude certain ambiguities when we consider two-candidate
constraints, and so on. So we use a sort of optimal substructure idea to
build larger councils upon smaller ones. I imagine the same approach
could be used to build a proportional ordering.
I also see that the method is extremely complex, but it works to show
that it's possible to have DPC and monotonicity. Making something more
elegant that still does... that's a challenge :-)
-
And now for an example after all that theory.
I'll give an 55%/45% example. The ballots have weights 24, 23, 9, 23,
and 21. Three seats, so the Droop quota is 25:
24: BCADE (these prefer {ABC} to everybody else)
23: ABCED
9: ABCDE
23: DEBAC (these prefer {DE} to everybody else)
21: DEABC
The DAC/DSC sets with at least a Droop quota's worth of support are:
A (support is 32)
AB (support is 32)
ABC (support is 56)
ABCD (support is 33)
ABCDE (support is 100) <-- set of all candidates.
ABDE (support is 44)
D (support is 44)
DE (support is 44)
And the quota Bucklin arrays are
Candidate A : 0 2 2 -77
Candidate D : 0 3 3 -77
Candidate B : 1 1 2 -79
Candidate E : 1 3 4 -100
Candidate C : 2 2 4 -100
so the ranked ordering is A > D > B > E > C. Note that my program uses
0-indexing, so "rank 0" is actually first rank.
The procedure then goes like this:
First, consider one-candidate constraints.
PC is {}, the empty set. Can we elect A based on one-candidate
constraints? Yes, because the coalition {A} contains A and has more
points than 1 (0 + 1) Droop quotas, since it has 32 points which is
greater than 25. The intersection of {} and {A} is clearly empty, hence
the 0 term in the "has-more-than" check.
So add A to PC.
PC is {A}. Can we elect D based on one-candidate constraints? Yes,
because the coalition {D} contains D and has more points than 1 (0 + 1)
Droop quotas, since it has 44 points which is greater than 25. Again,
the intersection of {A} and {D} is clearly empty, so the first term is zero.
No other single-candidate constraint has more than a Droop quota, so
we're done with one-candidate constraints.
Now check if PC is full. No, we have only two candidates and we need
three. So let's go to two-candidate constraints.
PC is {AD}. We skip A and D in the list because they're already elected.
Next up is B. Can we elect B based on two-candidate constraints? No,
since {AB} only exceeds one Droop quota and we already have A. (I.e. it
doesn't have more points than 2 (1 + 1) Droop quotas.) There aren't any
other two-candidate constraints containing B, so that's it for B in this
round.
Can we elect E based on two-candidate constraints? No, since {DE} only
exceeds one Droop quota and we already have D.
Can we elect C based on two-candidate constraints? No, since no
two-candidate constraint containing C even reaches a single Droop quota.
So no go for two-candidate constraints. Let's go to three-candidate
constraints.
PC is {AD} still. We skip A and D in the list because they're already
elected. Next up is B. Can we elect B based on three-candidate
constraints? Yes, because {ABC} contains B and has more points than 2 (1
+ 1) Droop quotas, since it has 56 points which is greater than 50. The
intersection of {AD} and {ABC} is {A}, hence the first term in that sum
was 1.
So add B to PC.
Now check if PC is full. We have three candidates, so we're done! The
outcome is {ABD}. The 55% group got A and B, while the 45% group got
their unanimous preference, D.
-
In this particular case, the elected candidates were in order of quota
Bucklin rank. This happens more often than you'd think, so quota Bucklin
might make a good strongly summable method if that's what you want.
However, do note that no PR method making use of only the positional
matrix (this candidate got that many votes in first place, second,
third, etc), can satisfy the Droop proportionality criterion in general.
Therefore, there will be instances where the outcome differs from the
plain quota Bucklin ordering.
----
Election-Methods mailing list - see http://electorama.com/em for list info
