Kristofer Munsterhjelm
2017-09-15 18:12:22 UTC
In an earlier post, I considered how to make Bucklin more resistant to
vote management, and I found a complex way of doing it by linear
programming. Unfortunately, the number of terms in the LP would grow
very quickly. I think I've found a simpler one that achieves much of the
same result.
Suppose we've already elected candidates c_1, ..., c_n, and c_k was
elected when we were considering voters' preferences at rank r_k and up,
so e.g. if c_1 was elected with only first preferences, r_1 = 1; if c_1
was elected with only first and second preferences, r_1 = 2.
Suppose we're now at rank r_(n+1) and we want to see how many voters we
can use to support potential candidate C. Let c_(n+1) tentatively be C,
then run the following linear program:
maximize: sum over all voters v: support[v][c_n+1]
subject to:
for i = 1..(n+1):
(sum over all voters v: support[v][c_i]) > Droop quota
for all voters v, for i = 1..(n+1):
support[v][c_i] >= 0 if voter v ranks c_i at or higher than rank r_i
support[v][c_i] = 0 otherwise
for all voters v:
(sum over i=1..n+1: support[v][c_i]) <= that voter's weight
-
What that says, in essence, is:
We have to assign the voters so that:
Every elected candidate has to exceed a Droop quota considering only
the ranks that were in play when he was elected.
Every voter can give some of his vote to candidate c_i if he ranks c_i
at or above rank r_i
No voter can give more of his vote than he his weight (for weighted
ballots).
Now assign as much weight as possible to c_i.
The LP will fail outright if c_i can't be elected (can't get above a
Droop quota by any means). Otherwise, it will return a score (the value
of the objective function at maximum). In each round, the candidate with
the greatest score wins. That is, the method itself goes something like:
Start at first rank (i.e. first preferences only), with i = 1, r = 1:
While the assembly is not yet full:
- For each unelected candidate C
Let s_C be his score from the LP, or s_C = -inf if the LP is nonfeasible
- If there's at least one candidate with finite score s_C
Move the candidate with maximum score from the unelected candidate
pool to the elected candidate pool
Set c_i = this candidate, r_i = r
- If there were no candidates with finite score s_C
increment r
It's pretty easy to make the method party list: just let the parties be
the candidates and don't remove the candidates from the unelected pool.
Or just preprocess the ballots by replacing each party by that party's
candidates in order: the latter is more complex, but has the advantage
of handling underhang seats more naturally.
-
Unfortunately, this method is only monotone for the first elected
candidate. The simple failure example goes like this:
Suppose B is aligned with many C voters and a few A voters in the sense
that these voters respectively vote C>B and A>B. At rank r_k, both C and
A have more than a Droop quota's worth of votes, but A has greater
support than C, so A wins the kth seat. Then on the next rank, B wins
the (k+1)th seat.
Now some A voters decide to switch from A>B to B>A. This decreases A's
support on rank r_k so that C wins instead. Then C ties down too many
C>B voters and thus B can't win on rank k+1. So raising B made B lose.
(One could say that the method reacts to A's decreasing support by
replacing A with a more compromise-like candidate, C. But it's still a
monotonicity failure.)
This feels reminiscent of Brams' observation about the minister-picking
method in Mathematics and Democracy. In it, parties that form a
government get to choose ministerial positions sequentially in
Sainte-Laguë order. Brams observes that sometimes, it pays off not being
first. Brams suggested a trading scheme for the minister-picking method
where later parties could ask earlier ones if they want to trade
positions, but that's not really possible here since the method is
completely mechanical.
The analogous observation for this method is that it fails because it
doesn't look ahead (just like the minister-picking method without
trading fails because it can't look ahead, either).
----
Election-Methods mailing list - see http://electorama
vote management, and I found a complex way of doing it by linear
programming. Unfortunately, the number of terms in the LP would grow
very quickly. I think I've found a simpler one that achieves much of the
same result.
Suppose we've already elected candidates c_1, ..., c_n, and c_k was
elected when we were considering voters' preferences at rank r_k and up,
so e.g. if c_1 was elected with only first preferences, r_1 = 1; if c_1
was elected with only first and second preferences, r_1 = 2.
Suppose we're now at rank r_(n+1) and we want to see how many voters we
can use to support potential candidate C. Let c_(n+1) tentatively be C,
then run the following linear program:
maximize: sum over all voters v: support[v][c_n+1]
subject to:
for i = 1..(n+1):
(sum over all voters v: support[v][c_i]) > Droop quota
for all voters v, for i = 1..(n+1):
support[v][c_i] >= 0 if voter v ranks c_i at or higher than rank r_i
support[v][c_i] = 0 otherwise
for all voters v:
(sum over i=1..n+1: support[v][c_i]) <= that voter's weight
-
What that says, in essence, is:
We have to assign the voters so that:
Every elected candidate has to exceed a Droop quota considering only
the ranks that were in play when he was elected.
Every voter can give some of his vote to candidate c_i if he ranks c_i
at or above rank r_i
No voter can give more of his vote than he his weight (for weighted
ballots).
Now assign as much weight as possible to c_i.
The LP will fail outright if c_i can't be elected (can't get above a
Droop quota by any means). Otherwise, it will return a score (the value
of the objective function at maximum). In each round, the candidate with
the greatest score wins. That is, the method itself goes something like:
Start at first rank (i.e. first preferences only), with i = 1, r = 1:
While the assembly is not yet full:
- For each unelected candidate C
Let s_C be his score from the LP, or s_C = -inf if the LP is nonfeasible
- If there's at least one candidate with finite score s_C
Move the candidate with maximum score from the unelected candidate
pool to the elected candidate pool
Set c_i = this candidate, r_i = r
- If there were no candidates with finite score s_C
increment r
It's pretty easy to make the method party list: just let the parties be
the candidates and don't remove the candidates from the unelected pool.
Or just preprocess the ballots by replacing each party by that party's
candidates in order: the latter is more complex, but has the advantage
of handling underhang seats more naturally.
-
Unfortunately, this method is only monotone for the first elected
candidate. The simple failure example goes like this:
Suppose B is aligned with many C voters and a few A voters in the sense
that these voters respectively vote C>B and A>B. At rank r_k, both C and
A have more than a Droop quota's worth of votes, but A has greater
support than C, so A wins the kth seat. Then on the next rank, B wins
the (k+1)th seat.
Now some A voters decide to switch from A>B to B>A. This decreases A's
support on rank r_k so that C wins instead. Then C ties down too many
C>B voters and thus B can't win on rank k+1. So raising B made B lose.
(One could say that the method reacts to A's decreasing support by
replacing A with a more compromise-like candidate, C. But it's still a
monotonicity failure.)
This feels reminiscent of Brams' observation about the minister-picking
method in Mathematics and Democracy. In it, parties that form a
government get to choose ministerial positions sequentially in
Sainte-Laguë order. Brams observes that sometimes, it pays off not being
first. Brams suggested a trading scheme for the minister-picking method
where later parties could ask earlier ones if they want to trade
positions, but that's not really possible here since the method is
completely mechanical.
The analogous observation for this method is that it fails because it
doesn't look ahead (just like the minister-picking method without
trading fails because it can't look ahead, either).
----
Election-Methods mailing list - see http://electorama