[EM] Bucklin multiwinner method
Kristofer Munsterhjelm
km_elmet at t-online.de
Fri Jan 6 09:14:58 PST 2017
On 01/05/2017 05:34 AM, Monkey Puzzle wrote:
> 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?
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
x_*_1 A>C>B 26
x_*_2 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 ???
x_*_1 A>C>B 26 ???
x_*_2 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
x_*_1 A>C>B 26 8
x_*_2 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
x_*_1 A>C>B 26 0
x_*_2 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
x_*_1 B>D>E>F 20
x_*_2 F>A>C 20
x_*_3 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 x_*_2)
B: 40 (x_*_0 and x_*_1)
C: 39 (x_*_3 and x_*_4)
D: 59 (x_*_1, x_*_3, and x_*_4)
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
x_*_1 B>D>E>F 20 ???
x_*_2 F>A>C 20 --> 20
x_*_3 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
x_*_1 B>D>E>F 20 34.25
x_*_2 F>A>C 20 --> 20
x_*_3 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 ?!
x_*_1 B>D>E>F 20 ??? ???/?!
x_*_2 F>A>C 20 --> 20 --> 20
x_*_3 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
x_*_1 B>D>E>F 20 34.25 0
x_*_2 F>A>C 20 --> 20 --> 20
x_*_3 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}.
More information about the Election-Methods
mailing list