<div dir="ltr">Hi Kristofer,<div><br></div><div>Thanks for your reply.</div><div><br></div><div>The constraints idea is good, but seems like it would be quite confusing the the average voter.</div><div><br></div><div>Could you illustrate the method with an example?</div><div><br></div><div>-- Ted</div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"> Frango ut patefaciam -- I break so that I may reveal<br></div></div>
<br><div class="gmail_quote">On Thu, Dec 29, 2016 at 3:24 PM, Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@t-online.de" target="_blank">km_elmet@t-online.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 12/29/2016 01:30 PM, Andy Jennings wrote:<br>
> Definitely interested. Let us know when you're ready to reveal it...<br>
<br>
</span>Here it is. I'm quoting a mail by Monkey Puzzle for context:<br>
<span class=""><br>
On 12/28/2016 09:57 PM, Monkey Puzzle wrote:<br>
> I am interested!<br>
><br>
> By "usual droop quota generalization", I assume you mean something of<br>
> the Bucklin reweighted voting form like this:<br>
><br>
> Initialize ballots with a weight of 1 and set Droop quota = N / (M + 1),<br>
> where N = number of voters, M = number of seats<br>
><br>
</span>> * For each candidate, find their Bucklin threshold by finding the<br>
<span class="">> minimum score K at which the candidate has a total weighted sum of<br>
> ballots at or above that score (T_k) that exceeds the quota.<br>
</span>> * The candidate with the highest Bucklin threshold K, using T_k as a<br>
> tie-breaker, wins the seat.<br>
> * Reweight ballots that score the latest winner at or above K using<br>
<span class="">> the factor F = 1 - (Q / T_k)<br>
</span>> * Repeat until M winners have been found<br>
<br>
You're right. That is the usual variant, or something I've called<br>
elect-and-punish, from how it elects a candidate and then "punishes"<br>
(reweights) the ballots of the voters who contributed to the candidate's<br>
election.<br>
<br>
The usual variant is like STV, but instead of using Plurality<br>
elimination when there're no eligible candidates, it advances<br>
Bucklin-style to include the next rank.<br>
<br>
My variant could be called "puzzle Bucklin" and is essentially the<br>
ordinary Bucklin with DSV for Hylland vote management.<br>
<br>
I may have a tendency to make things more complicated than they need to<br>
be, so let me know if any of this is too complicated.<br>
<br>
Like ordinary Bucklin, puzzle Bucklin broadly works like this:<br>
<br>
- Start at first rank (highest grade)<br>
- Check if any candidate is eligible using the voters who grade/rank<br>
that candidate at or above the current rank/grade in consideration.<br>
- If so, elect that candidate and attenuate the weight of those voters,<br>
then loop back to the previous step<br>
- Otherwise, advance to the next rank (lower grade).<br>
<br>
The difference is that the attenuation of the weights of the voters<br>
consist of adding a linear constraint to a set of constraints. The<br>
linear constraint simply says "the sum of weight for all the voters who<br>
helped contribute to the election of candidate A must be, in total,<br>
decreased by a Droop quota" *without specifying exactly whose weights<br>
are decreased*.<br>
<br>
Then the eligibility check for candidate X simply tries to maximize the<br>
support for X subject to the constraints (i.e. to assign as high total<br>
support as possible to candidate X given the constraints already in place).<br>
<br>
Because the constraint doesn't say anything about any particular ballot,<br>
but just constrains groups of ballots, any ballot of the form A>B<br>
contributes maximally to B in the second rank unless the constraint<br>
forces it otherwise, and the constraint only forces it otherwise if A<br>
wouldn't have won without that ballot, or if B couldn't have won anyway.<br>
<br>
-<br>
<br>
A constraint for candidate A at rank p is of the form:<br>
"We must remove a Droop quota's worth of weight from a given subset of<br>
ballots, all of which rank candidate A at rank p or higher, to support<br>
the election of A".<br>
<br>
Or, more formally:<br>
Let w_0,k = the kth ballot's weight for all k, 1 <= k <= n,<br>
where there are n balots.<br>
<br>
Let R be the set of indices to ballots that rank A at or above<br>
rank p, and Q be the set of indices to ballots that don't.<br>
E.g. if the kth ballot ranks A at or above rank p,<br>
k is in R, otherwise k is in Q.<br>
<br>
If the ith constraint is on A and rank p, it states<br>
1: w_i,k = w_(i-1),k for all k in Q<br>
2: (sum r in R: w_i,r) = (sum r in R: w_(i-1),r) - quota<br>
3: w_i,k >= 0 for all k in R<br>
<br>
The first constraint means that the weights of ballots not involved in<br>
the constraint is unchanged, and the second means that as a group, the<br>
voters who contributed to electing A will pay a Droop quota's worth of<br>
weight (just like in ordinary elect and punish). But as I said, the<br>
constraint doesn't say what the weights of each ballot in this set will be.<br>
<br>
Now the method is simple.<br>
<br>
Start at rank 1. Determine if a candidate has more than a Droop quota's<br>
support by counting only first rank (i.e. first preferences). If there's<br>
such a candidate (call him A), add a constraint on A and rank 1.<br>
<br>
Then go on to rank 2. Determine if a candidate has more than a Droop<br>
quota's support by counting the first two ranks, subject to the<br>
constraints already in place. If there's such a candidate (B), add a<br>
constraint on B and rank 2.<br>
<br>
And so on.<br>
<br>
There may be more than one candidate who's eligible at a single rank, so<br>
the method ends up like this:<br>
<br>
1. Start at rank p = first rank.<br>
2. Until we have elected all candidates we need:<br>
2.1. Let i be the number of constraints so far.<br>
2.2. For each unelected candidate c:<br>
2.2.1. Let c's score be the highest you can get the sum of [ballot<br>
weights w_i_k for all ballots k that rank c above or at rank p], subject<br>
to the constraints already in place.<br>
2.3. Let C be the unelected candidate with the greatest score. If C's<br>
score is greater than a Droop quota:<br>
2.3.1. Elect C and add a constraint on C at rank p.<br>
2.4. If nobody was elected, increment p.<br>
2.5. Go to 2.1.<br>
<br>
So when we're making the case for electing some candidate c, we're<br>
saying "the laws placed on us by earlier stages' elections say we need<br>
to pay off each of the elected candidates with a Droop quota's worth of<br>
voters, each. Now choose which ballots to remove to pay off that debt so<br>
that the support for c is as high as possible". If that support exceeds<br>
a Droop quota, then we know it's possible to pay off the debt for prior<br>
elected voters *and* for c. So c can be elected in turn without making<br>
the constraints impossible to fulfil unless there's some other candidate<br>
q with even greater support.<br>
<br>
Or, from a different perspective: suppose C is elected at first rank.<br>
Then the method doesn't know the weights of the voters who helped C get<br>
elected, except that they must collectively pay a Droop quota's worth.<br>
Now suppose the method is to decide how much support D can get at second<br>
rank. Then the method "automatically vote-manages" the voters so as to<br>
maximize D's support. Whoever can get the most support this way is<br>
elected next; but again, the method doesn't say anything about how the<br>
surplus is distributed, only that the voters who contributed to D<br>
getting elected must collectively pay a Droop quota's worth of weight.<br>
<br>
The "puzzle" in puzzle Bucklin is to maximize c's support subject to the<br>
constraints. This can be done using linear programming, though pretty<br>
slowly for elections with very large numbers of ballots. More<br>
specialized compsci algorithms might do better (possibly max-flow based<br>
ones?).<br>
<br>
The reason I think this method deals relatively well with Hylland free<br>
riding is:<br>
<br>
- Suppose that we have a skipped rank scenario where the candidates are<br>
graded/ranked to a common standard (like in MJ). Then suppose voter X<br>
votes A>B and A was elected based on only first preferences/highest<br>
grades. Voter X might either be crucial or not: crucial means that A<br>
would not have been elected at first rank if X had failed to rank/grade A.<br>
<br>
- If X isn't crucial to A's election, then when the method is counting<br>
B's score at the second rank, it will act as if X voted [none]>B, which<br>
is close to what X would have accomplished by Hylland free riding to<br>
begin with. IOW, the constraint isn't binding on X when counting B's score.<br>
<br>
- If, on the other hand, X is crucial to A's election, then if X had<br>
tried to do Hylland free riding by voting [none]>B instead of A>B, that<br>
would have caused A to lose, and thus wouldn't have been a good idea<br>
from X's point of view.<br>
<br>
By [none]>B, I mean "votes nothing in first place, and B in second<br>
place". In MJ terms, this would be like, instead of giving A "Very Good"<br>
and B "Good", not giving A any grade and still giving B "Good".<br>
<br>
Traditional Hylland free riding could still have some benefit; that is,<br>
voting B instead of A>B can get B elected. This is similar to how MJ<br>
passes IIA in the "common standard" setting but not in the pure ranking<br>
setting. But even in the pure ranking setting, if A is elected at first<br>
rank, and voting only for B would get B elected, then so would voting A=B.<br>
<div class="HOEnZb"><div class="h5">----<br>
Election-Methods mailing list - see <a href="http://electorama.com/em" rel="noreferrer" target="_blank">http://electorama.com/em</a> for list info<br>
</div></div></blockquote></div><br></div>