Definitely interested.  Let us know when you're ready to reveal it...

On Wed, Dec 28, 2016 at 6:24 AM, Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:

On 12/29/2016 01:30 PM, Andy Jennings wrote:

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

On 12/28/2016 09:57 PM, Monkey Puzzle wrote:

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.

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@t-online.de> wrote:

On 01/05/2017 05:34 AM, Monkey Puzzle wrote:

Sure. I'll add some tables as well. If the ASCII art messes up, try
accessing the post from the web,
http://lists.electorama.com/pipermail/election-methods-electorama.com/2017-January/

Here's a relatively simple example: the vote management example from
Wikipedia's article on Schulze STV,
https://en.wikipedia.org/wiki/Schulze_STV#Scenario

The unmanaged ballot set is

12: A>B>C
38: A>C>B
13: C>A>B
27: B

The Droop quota for two seats is 30.

Ordinary elect-and-punish Bucklin goes like this:

First round (first preferences only): A has 50 votes and is elected. The
surplus is 20, and after reweighting and elimination, the ballot set is:

4.8: *>B>C
15.2: >C>B
13.0: C>>B
27.0: B

(here, * means "nobody at that rank", since Bucklin permits skipping ranks.)

Nobody else exceeds the Droop quota by first preferences only, so
consider the first two preferences.

Second round (first two preferences):
B has a support of 31.8 and C has a support of 28.2. B exceeds the Droop
quota, is elected, and we're done. The winners are A and B.

The vote-managed ballot set is

12: A>B>C
26: A>C>B
25: C>A>B
27: B

(A bunch of A>C>B voters decided to strategically vote C first in the
hope of getting C elected because "A is going to win anyway".)

Ordinary Bucklin goes like this:

First round: A has a support of 38, B has 27, C has 25.
A is the only one exceeding the Droop quota, and is elected. The surplus
is 8.
After reweighting, we have:

2.53: *>B>C
5.47: >C>B
25.00: C>>B
27.00: B

Second round: B has a support of 29.53. C has a support of 30.47. C is
the only candidate exceeding the Droop quota, and is thus elected, so
the winners are A and C. The vote-management paid off.

So, on to Puzzle Bucklin. I'm not going to do the unmanaged one, just
show that the managed one has A and B win (so the vote management
doesn't pay off).

The table we're going to use is like this:

Index  Ballot    x_0_*  x_1_*

x_0  A>B>C    12
x1  A>C>B    26
x2  C>A>B    25
x_3  B        27

In the first round, there are no constraints and all the x_0_* values
are the ballots' respective weights.

A's score is the max you can get A's support to be, considering only the
ballots that rank A first. This is 12+26 = 38 as above, so the first
round plays out like ordinary Bucklin.

A has a score of 38.
B has a score of 27.
C has a score of 25.

Only one of these exceed the quota, so A is elected.

Now we add a constraint:

Surplus constraint:
x_1_0 + x_1_1 = x_0_0 + x_0_1 - 30
Pass all weights not involved in the election of A onwards:
x_1_2 = x_0_2 and x_1_3 = x_0_3
Negative weights are not permitted:
x_1_* >= 0

The table ends up like this:

Index  Ballot    x_0_*  x_1_*

x_0  A>B>C    12      ???
x1  A>C>B    26      ???
x2  C>A>B    25  --> 25
x_3  B        27  --> 27

Constraints:
x_1_0 + x_1_1 = 38 - 30
= 8
all nonnegative

We're now in the second round (since nobody else could be elected by
first preferences alone). We have to determine C and B's scores to know
if any can be pushed above a Droop quota, in order to determine who to
elect.

So first try to maximize C's support. We can change the ??? above
subject to that the sum of the two must be 8. The puzzle is to change
the ???s to get C's support as high as possible.

C's support is x_1_1 + x_1_2 (since these correspond to the ballots that
rank C either first or second). It's pretty clear that the optimal
solution is

Index  Ballot    x_0_*  x_1_*

x_0  A>B>C    12      0
x1  A>C>B    26      8
x2  C>A>B    25  --> 25
x_3  B        27  --> 27

and so C's score is 8+25 = 33.

Now for B's score:

B's support is x_1_0 + x_1_3, since these correspond to the ballots that
rank B either first or second. Again, it's pretty clear to put all of
the surplus to the one ballot that can support B, i.e., x_1_0, so we get:

Index  Ballot    x_0_*  x_1_*

x_0  A>B>C    12      8
x1  A>C>B    26      0
x2  C>A>B    25  --> 25
x_3  B        27  --> 27

and B's score is 8+27 = 35.

So B is elected in the second round, the winners are A and B, and the
vote management failed.

It gets trickier with more than two seats because the constraints can
interleave. Here's an example of that, from
http://www.rangevoting.org/STVPRunger.html :

20: A>B>C>D
20: B>D>E>F
20: F>A>C
20: D>C>E>F
19: C>D>B

three to elect, Droop quota is 24.75.

The table is

Index  Ballot    x_0_*  x_1_*    x_2_*

x_0  A>B>C>D  20
x1  B>D>E>F  20
x2  F>A>C    20
x3  D>C>E>F  20
x*_4  C>D>B    19

Nobody is elected in the first round because nobody exceeds the Droop quota.

For the second round (two first ranks), the support levels are
A: 40 (x_0 and x2)
B: 40 (x0 and x1)
C: 39 (x3 and x4)
D: 59 (x1, x3, and x4)
E:  0
F: 20 (x_2)

---================

D is elected, and we set a constraint. I'm going to use different codes
for the different unknowns since we'll be adding additional constraints,
but as above, I'll call the first unknowns "???".

Surplus constraint for "???":
x_1_1 + x_1_3 + x_1_4 = 59 - 24.75 = 34.25
Everything else is ported through:
x_1_0 = x_0_0 and x_1_2 = x_0_2
Non-negativity:
x_1_* >= 0

and out table after the first election is

Index  Ballot    x_0_*  x_1_*    x_2_*

x_0  A>B>C>D  20  --> 20
x1  B>D>E>F  20      ???
x2  F>A>C    20  --> 20
x3  D>C>E>F  20      ???
x*_4  C>D>B    19      ???

The remaining candidates are A, B, C, E, F.
E's score is still 0 (nothing has changed), F's score is still 20
(because x_1_2 is known), and A's score is still 40 (because both x_1_0
and x_1_2 are known).

B's score is determined by maximizing x_1_0 + x_1_1. We need to fill in
the ???s so that x_1_0 + x_1_1 becomes as large as possible, constrained
to that the sum of ???s can't be greater than 34.25.

As in the example above, it's pretty clear how to do so. Put everything
into x_1_1 because that's the only one that affects B's score. And thus
B's score is 54.25, in this way:

Index  Ballot    x_0_*  x_1_*    x_2_*

x_0  A>B>C>D  20  --> 20
x1  B>D>E>F  20      34.25
x2  F>A>C    20  --> 20
x3  D>C>E>F  20      0
x*_4  C>D>B    19      0

C's score is determined by maximizing x_1_3 + x_1_4. This puzzle has a
number of solutions, but all of them involves setting x_1_1 to 0 and
spreading the surplus over x_1_3 and x_1_4. So C's score can't be more
than 34.25.

Thus we have

A: 40
B: 54.25
C: 34.25
E: 0
F: 20

so B is elected next. Set a constraint:

Surplus constraint for "?!":
x_2_0 + x_2_1 = x_1_0 + x_1_1 - 24.75
Everything else is copied over:
x_2_* = x_1_* except for x_2_0 and x_2_1
Non-negativity:
x_2_* >= 0

Index  Ballot    x_0_*  x_1_*    x_2_*

x_0  A>B>C>D  20  --> 20      ?!
x1  B>D>E>F  20      ???      ???/?!
x2  F>A>C    20  --> 20  --> 20
x3  D>C>E>F  20      ???      ???
x*_4  C>D>B    19      ???      ???

Now x_2_1 is both directly governed by constraint ?! and indirectly by
constraint ???, which makes the puzzle considerably harder. To a
computer, it's still doable through linear programming, but the
intuition becomes more complex.

D and B have been elected. The remaining candidates are A, C, E, F.

E still has support 0 and F still has support 20.
A's score is based on maximizing x_2_0 + x_2_2. Since x_2_2 is fixed at
20, we must maximize x_2_0 to maximize the complete expression.
The ?! constraint is:
x_2_0 + x_2_1 = x_1_0 + x_1_1 - 24.75
We can set x_2_1 to 0 because it doesn't contribute to A's support. This
in turn gives
x_2_0 = x_1_0 + x_1_1 - 24.75
= 20 + x_1_1 - 24.75

so the expression we're trying to maximize:
x_2_0 + x_2_2
ends up being
20 + x_1_1 - 24.75 + x_2_2
= 20 + x_1_1 - 24.75 + 20

and to maximize, we should put all of the weight from ??? into x_1_1.
The most we can put into ??? is 34.25, so we get the following:

Index  Ballot    x_0_*  x_1_*    x_2_*

x_0  A>B>C>D  20  --> 20        29.50
x1  B>D>E>F  20      34.25      0
x2  F>A>C    20  --> 20    --> 20
x3  D>C>E>F  20      0        0
x*_4  C>D>B    19      0        0

A's score is thus 49.50. The intuitive explanation is that the D-voters
from the first election can't get C elected, so they move their surplus
entirely to B (as if they all voted B>D or D>B), where it in turn flows
into A.

C's score is x_2_3 + x_2_4 = x_1_3 + x_1_4. There are no dual
constraints on this one, it's entirely governed by ???. The ???
constraint is
x_1_1 + x_1_3 + x_1_4 = 59 - 24.75 = 34.25
So the obvious solution is to set x_1_1 to 0 and x_1_3 + x_1_4 = 34.25,
so C's score must be 34.25.

We end up with the following scores:

A: 49.50
C: 34.25
E:  0
F: 20

so A wins the third seat for a result of {A, B, D}. At least it should
be unless I did some calculations wrong: I did all of this manually, and
it's easy to slip up doing nested constraints like this.

STV elects {B, D, F}.