[EM] Bucklin multiwinner method
Monkey Puzzle
araucaria.araucana at gmail.com
Wed Jan 4 20:34:31 PST 2017
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>
More information about the Election-Methods
mailing list