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

[Jameson Quinn]

Interesting. I have no useful comments, but I'd be interested to hear as
you explore this kind of method further.

2015-01-01 8:19 GMT-05:00 Kristofer Munsterhjelm <km_elmet at t-online.de>:

> 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.
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20150101/af460605/attachment.htm>