[EM] A simpler vote management-resistant Bucklin LP

[Kristofer Munsterhjelm]

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).