[EM] A Bucklin-like Range weighted candidate/party list method

[Kristofer Munsterhjelm]

Here's a (seemingly simple) sketch of a weighted candidate/party list 
method that looks a lot like Bucklin, but isn't since it reduces to 
Range in the one-seat case.

I am, as usual, bad at giving names to methods, so any suggestions for a 
name would be appreciated.

If you want to know how I constructed this method, or what it's based 
on, ask. I won't write that here, as it might distract from the method 
itself :-)

I also have a Python implementation of the thresholded election routine 
below. Again, ask me if you'd like to have it.

---

First we need to define a "thresholded election routine":

Let r[c][v] be voter v's rating of candidate c, and let rmax be the 
maximum possible rating. Let p be a given threshold penalty. Start with 
set V being the set of every voter, and let a variable b (for "barrier") 
start at b = rmax.

A candidate may be unelected or elected, and every elected candidate has 
at least one voter assigned to him. Each candidate starts off unelected 
with no voters assigned to him.

The inputs are the r matrix (number of candidates by number of voters) 
and p. The actual routine goes like this:

1. While there are voters left in V (i.e. V is not the empty set):

1.1. If there exists some unelected candidate i so that
(sum over every v in V: max(0, r[i][v] - b)) >= p:
	elect i.

1.2. For every voter v in V that rates some elected candidate c greater 
than or equal to rating b:
	assign v to c and remove v from V.

1.3. If neither any voters nor any candidates were found (i.e. no change 
has occurred), decrement b by some small amount (somewhat akin to how 
Bucklin or QLTD works).

2. Each elected candidate is a winner, and each elected candidate's 
weight is equal to the number of voters assigned to him.

---

Second, we define the weighted method or party list proper:

For the weighted method, given a desired number of winners, s, perform a 
binary search on the thresholded election routine. Greater p leads to 
fewer candidates being elected, and this effect is monotone, so simply 
first find the value of p which gives a single winner (call it pmax), 
then run a binary search (or other bracketed root-finder) on the 
interval [0...pmax] to get the outcome for w winners.

For the party list method, the execution is similar.
Let the "candidates" in the thresholded election routine be the parties. 
Voters then rate the parties, and the r matrix consists of the voters' 
ratings of the parties. Let s be the total number of seats in the assembly.

Define the "Websterized thresholded election routine with s seats" as a 
function that calls the thresholded election routine with given inputs, 
runs the output through Webster with s seats, and returns the result for 
each elected party.

Then, taking advantage of monotonicity as above, find the least value of 
p for which every elected party gets at least one seat. Return the 
assignment given by the Websterized thresholded election for s seats and 
this value of p.

---

Note that there's no mention of how to deal with ties. This is simply 
because I haven't found out which tiebreaker is the best. The two tie 
situations that may happen is that more than one unelected candidate is 
eligible in step 1.1. but that the voters overlap so that once the 
voters were assigned to one of the candidates, the others would no 
longer be eligible; and that in 1.2., a voter might rate more than one 
elected candidate greater than or equal to b.

Possible tiebreakers might be:
	- Choose every candidate in 1.1. and use a fractional assignment in 
1.2. E.g. if v rates two candidates at or above b, each gets assigned to 
half a voter. Exact (ratings-wise) clones should then harmlessly split 
the vote, but this might cause the binary search to fail, e.g. if almost 
every candidate is a clone and we need exactly 2 candidates, then a low 
p will elect every clone and a high p will elect none.
	- Choose one candidate at random in 1.1. and use any kind of assignment 
in 1.2.
	- Choose one candidate at random in 1.1. and likewise in 1.2.
	- Choose every candidate in 1.1. and use a fractional ratings-weighted 
assignment in 1.2. This might cause discontinuity or monotonicity problems.
	- Choose a subset of candidates in 1.1 somehow depending on p (lower p 
leads to a greater subset being picked), and use fractional assignment 
in 1.2., so as to fix the binary search failure problem.

In general, I don't think the assignment values should be weighted by 
ratings in any way. The election and assignment processes themselves 
check if the ratings are good enough. If they are, then the voter is 
fully (or fractionally) assigned to the candidate (or candidates, 
depending on tiebreak).

---

What properties does this method exhibit? Well, it reduces to Range. I 
prefer median methods, so it's not ideal. (I initially thought I was 
generalizing Bucklin, but while testing with a Python script, found that 
was not the case!) But if you like Range, there's a lot the method above 
has going for it.

- It seems to be monotone. Assume you raise a candidate X. In 1.1., this 
can only elect X earlier. In 1.2., this can only assign you to X 
earlier. So you can't harm X unless the optimal value of p changes. But 
if it does (increases), then it will drop candidates inferior to X 
before it drops X, so again, you can't harm X.

- It resolves the LCR situation properly. Consider the following setup:
	3: L: 10, C: 5, R: 0
	3: L: 0, C: 5, R: 10
	1: L: 6, C: 10, R: 0
	1: L: 0, C: 10, R: 5

With p = 9, L and R are elected at b=6.999, and the L- and R-voters are 
assigned at this value of b. Then, at b=5.999, the left centrist is 
assigned to L, and at b=4.999, the right centrist is assigned to R.

With p = 30, C is elected at b=2.5 and all the voters are assigned to him.

- The party list variant could probably be pretty easily adapted to 
biproportional representation. In 1.1., we can consider
	(sum over every v in V: max(0, r[i][v] - b)) >= p
to be equal the same as
	(sum over every v in V: max(0, r[i][v] - b)) >= p * w[i]

where w[i] is a weight for party i. And since greater p makes it harder 
for a party to be elected, and this relation is monotone, increasing 
w[i] will decrease the number of seats party i gets.

---

It is not perfect, though.

- It is not summable, or if it is, I can't see how. (Since the 
membership of V is altered as the process continues, we need to take 
nonlinear sums over very different subsets in 1.1.)

- It's not strictly speaking polytime. Let there be |C| candidates and 
|V| voters. By heap or priority queue tricks, one can run the 
thresholded election routine in (|C|+|V|) log (|C|+|V|) time. But |V| 
may increase exponentially for a fixed |C|. One might argue that this 
problem exists in any method (even in Condorcet, you'd need to count |V| 
ballots...), which is why I say "strictly speaking".

- Although the method seems similar to STV (a bunch of relatively simple 
procedural rules to do over and over), hand counts would probably be 
impractical.

- I can't see if the weighted candidate method is cloneproof (in the 
sense that expanding or contracting a clone set should keep the total 
weight within the set equal). It might be - at least with the proper 
tiebreakers - but I'm unsure.

- The party list method is a bit of a hack. Excess votes that go to 
parties that wouldn't get any seats instead contribute to parties that 
do/will: voting for a fringe party is thus mostly harmless. But if a 
party gets a single seat, yet the voters vote in excess of one seat's 
worth, the excess votes won't help any other parties.
Say, for instance, that the left-wing voters in an election vote for a 
bunch of parties, and each party gets 1.4 seats' worth. If the voters 
had coordinated and the 0.4 for each had voted for only a single of 
them, the slices might have added up to another seat's worth. So the 
party list method clearly isn't cloneproof.

The problem might be solvable through Meek-like iteration. But I think I 
have a better idea of how to make a party list method that is more 
clone-compliant (as well as how to make a median version). It'd take a 
lot of time to actually design, though. An individual candidate method 
would be even trickier and probably involve local search, which would 
make it pretty inelegant. As for summability or polytime, I wouldn't 
know where to start.