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

Kristofer Munsterhjelm km_elmet at t-online.de
Thu Jan 1 05:19:16 PST 2015

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