[EM] Bucklin multiwinner method

[Monkey Puzzle]

Hi Kristofer,

Thanks for your reply.

The constraints idea is good, but seems like it would be quite confusing
the the average voter.

Could you illustrate the method with an example?

-- Ted

 Frango ut patefaciam -- I break so that I may reveal

On Thu, Dec 29, 2016 at 3:24 PM, Kristofer Munsterhjelm <
km_elmet at t-online.de> wrote:

> 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.
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20170104/b73915ff/attachment.htm>