[EM] Bucklin multiwinner method

[Kristofer Munsterhjelm]

On 12/29/2016 01:30 PM, Andy Jennings wrote:
> Definitely interested.  Let us know when you're ready to reveal it...

Here it is. I'm quoting a mail by Monkey Puzzle for context:

On 12/28/2016 09:57 PM, Monkey Puzzle wrote:
> I am interested!
> 
> By "usual droop quota generalization", I assume you mean something of
> the Bucklin reweighted voting form like this:
> 
> Initialize ballots with a weight of 1 and set Droop quota = N / (M + 1),
> where N = number of voters, M = number of seats
> 
>   * For each candidate, find their Bucklin threshold by finding the
>     minimum score K at which the candidate has a total weighted sum of
>     ballots at or above that score (T_k) that exceeds the quota.
>   * The candidate with the highest Bucklin threshold K, using T_k as a
>     tie-breaker, wins the seat.
>   * Reweight ballots that score the latest winner at or above K using
>     the factor F = 1 - (Q / T_k)
>   * Repeat until M winners have been found

You're right. That is the usual variant, or something I've called
elect-and-punish, from how it elects a candidate and then "punishes"
(reweights) the ballots of the voters who contributed to the candidate's
election.

The usual variant is like STV, but instead of using Plurality
elimination when there're no eligible candidates, it advances
Bucklin-style to include the next rank.

My variant could be called "puzzle Bucklin" and is essentially the
ordinary Bucklin with DSV for Hylland vote management.

I may have a tendency to make things more complicated than they need to
be, so let me know if any of this is too complicated.

Like ordinary Bucklin, puzzle Bucklin broadly works like this:

- Start at first rank (highest grade)
- Check if any candidate is eligible using the voters who grade/rank
that candidate at or above the current rank/grade in consideration.
- If so, elect that candidate and attenuate the weight of those voters,
then loop back to the previous step
- Otherwise, advance to the next rank (lower grade).

The difference is that the attenuation of the weights of the voters
consist of adding a linear constraint to a set of constraints. The
linear constraint simply says "the sum of weight for all the voters who
helped contribute to the election of candidate A must be, in total,
decreased by a Droop quota" *without specifying exactly whose weights
are decreased*.

Then the eligibility check for candidate X simply tries to maximize the
support for X subject to the constraints (i.e. to assign as high total
support as possible to candidate X given the constraints already in place).

Because the constraint doesn't say anything about any particular ballot,
but just constrains groups of ballots, any ballot of the form A>B
contributes maximally to B in the second rank unless the constraint
forces it otherwise, and the constraint only forces it otherwise if A
wouldn't have won without that ballot, or if B couldn't have won anyway.

-

A constraint for candidate A at rank p is of the form:
	"We must remove a Droop quota's worth of weight from a given subset of
ballots, all of which rank candidate A at rank p or higher, to support
the election of A".

Or, more formally:
	Let w_0,k = the kth ballot's weight for all k, 1 <= k <= n,
	where there are n balots.

	Let R be the set of indices to ballots that rank A at or above
	rank p, and Q be the set of indices to ballots that don't.
		E.g. if the kth ballot ranks A at or above rank p,
		k is in R, otherwise k is in Q.

	If the ith constraint is on A and rank p, it states
		1: w_i,k = w_(i-1),k	for all k in Q
		2: (sum r in R: w_i,r) = (sum r in R: w_(i-1),r) - quota
		3: w_i,k >= 0		for all k in R

The first constraint means that the weights of ballots not involved in
the constraint is unchanged, and the second means that as a group, the
voters who contributed to electing A will pay a Droop quota's worth of
weight (just like in ordinary elect and punish). But as I said, the
constraint doesn't say what the weights of each ballot in this set will be.

Now the method is simple.

Start at rank 1. Determine if a candidate has more than a Droop quota's
support by counting only first rank (i.e. first preferences). If there's
such a candidate (call him A), add a constraint on A and rank 1.

Then go on to rank 2. Determine if a candidate has more than a Droop
quota's support by counting the first two ranks, subject to the
constraints already in place. If there's such a candidate (B), add a
constraint on B and rank 2.

And so on.

There may be more than one candidate who's eligible at a single rank, so
the method ends up like this:

1. Start at rank p = first rank.
2. Until we have elected all candidates we need:
2.1. Let i be the number of constraints so far.
2.2. For each unelected candidate c:
2.2.1. Let c's score be the highest you can get the sum of [ballot
weights w_i_k for all ballots k that rank c above or at rank p], subject
to the constraints already in place.
2.3. Let C be the unelected candidate with the greatest score. If C's
score is greater than a Droop quota:
2.3.1. Elect C and add a constraint on C at rank p.
2.4. If nobody was elected, increment p.
2.5. Go to 2.1.

So when we're making the case for electing some candidate c, we're
saying "the laws placed on us by earlier stages' elections say we need
to pay off each of the elected candidates with a Droop quota's worth of
voters, each. Now choose which ballots to remove to pay off that debt so
that the support for c is as high as possible". If that support exceeds
a Droop quota, then we know it's possible to pay off the debt for prior
elected voters *and* for c. So c can be elected in turn without making
the constraints impossible to fulfil unless there's some other candidate
q with even greater support.

Or, from a different perspective: suppose C is elected at first rank.
Then the method doesn't know the weights of the voters who helped C get
elected, except that they must collectively pay a Droop quota's worth.
Now suppose the method is to decide how much support D can get at second
rank. Then the method "automatically vote-manages" the voters so as to
maximize D's support. Whoever can get the most support this way is
elected next; but again, the method doesn't say anything about how the
surplus is distributed, only that the voters who contributed to D
getting elected must collectively pay a Droop quota's worth of weight.

The "puzzle" in puzzle Bucklin is to maximize c's support subject to the
constraints. This can be done using linear programming, though pretty
slowly for elections with very large numbers of ballots. More
specialized compsci algorithms might do better (possibly max-flow based
ones?).

The reason I think this method deals relatively well with Hylland free
riding is:

- Suppose that we have a skipped rank scenario where the candidates are
graded/ranked to a common standard (like in MJ). Then suppose voter X
votes A>B and A was elected based on only first preferences/highest
grades. Voter X might either be crucial or not: crucial means that A
would not have been elected at first rank if X had failed to rank/grade A.

- If X isn't crucial to A's election, then when the method is counting
B's score at the second rank, it will act as if X voted [none]>B, which
is close to what X would have accomplished by Hylland free riding to
begin with. IOW, the constraint isn't binding on X when counting B's score.

- If, on the other hand, X is crucial to A's election, then if X had
tried to do Hylland free riding by voting [none]>B instead of A>B, that
would have caused A to lose, and thus wouldn't have been a good idea
from X's point of view.

By [none]>B, I mean "votes nothing in first place, and B in second
place". In MJ terms, this would be like, instead of giving A "Very Good"
and B "Good", not giving A any grade and still giving B "Good".

Traditional Hylland free riding could still have some benefit; that is,
voting B instead of A>B can get B elected. This is similar to how MJ
passes IIA in the "common standard" setting but not in the pure ranking
setting. But even in the pure ranking setting, if A is elected at first
rank, and voting only for B would get B elected, then so would voting A=B.