[EM] My Bucklin multiwinner method turned more sequential

[Kristofer Munsterhjelm]

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.