<div dir="ltr">Interesting. I have no useful comments, but I'd be interested to hear as you explore this kind of method further.</div><div class="gmail_extra"><br><div class="gmail_quote">2015-01-01 8:19 GMT-05:00 Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@t-online.de" target="_blank">km_elmet@t-online.de</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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.<br>
<br>
I am, as usual, bad at giving names to methods, so any suggestions for a name would be appreciated.<br>
<br>
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 :-)<br>
<br>
I also have a Python implementation of the thresholded election routine below. Again, ask me if you'd like to have it.<br>
<br>
---<br>
<br>
First we need to define a "thresholded election routine":<br>
<br>
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.<br>
<br>
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.<br>
<br>
The inputs are the r matrix (number of candidates by number of voters) and p. The actual routine goes like this:<br>
<br>
1. While there are voters left in V (i.e. V is not the empty set):<br>
<br>
1.1. If there exists some unelected candidate i so that<br>
(sum over every v in V: max(0, r[i][v] - b)) >= p:<br>
        elect i.<br>
<br>
1.2. For every voter v in V that rates some elected candidate c greater than or equal to rating b:<br>
        assign v to c and remove v from V.<br>
<br>
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).<br>
<br>
2. Each elected candidate is a winner, and each elected candidate's weight is equal to the number of voters assigned to him.<br>
<br>
---<br>
<br>
Second, we define the weighted method or party list proper:<br>
<br>
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.<br>
<br>
For the party list method, the execution is similar.<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
---<br>
<br>
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.<br>
<br>
Possible tiebreakers might be:<br>
        - 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.<br>
        - Choose one candidate at random in 1.1. and use any kind of assignment in 1.2.<br>
        - Choose one candidate at random in 1.1. and likewise in 1.2.<br>
        - Choose every candidate in 1.1. and use a fractional ratings-weighted assignment in 1.2. This might cause discontinuity or monotonicity problems.<br>
        - 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.<br>
<br>
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).<br>
<br>
---<br>
<br>
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.<br>
<br>
- 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.<br>
<br>
- It resolves the LCR situation properly. Consider the following setup:<br>
        3: L: 10, C: 5, R: 0<br>
        3: L: 0, C: 5, R: 10<br>
        1: L: 6, C: 10, R: 0<br>
        1: L: 0, C: 10, R: 5<br>
<br>
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.<br>
<br>
With p = 30, C is elected at b=2.5 and all the voters are assigned to him.<br>
<br>
- The party list variant could probably be pretty easily adapted to biproportional representation. In 1.1., we can consider<br>
        (sum over every v in V: max(0, r[i][v] - b)) >= p<br>
to be equal the same as<br>
        (sum over every v in V: max(0, r[i][v] - b)) >= p * w[i]<br>
<br>
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.<br>
<br>
---<br>
<br>
It is not perfect, though.<br>
<br>
- 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.)<br>
<br>
- 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".<br>
<br>
- 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.<br>
<br>
- 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.<br>
<br>
- 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.<br>
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.<br>
<br>
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.<br>
----<br>
Election-Methods mailing list - see <a href="http://electorama.com/em" target="_blank">http://electorama.com/em</a> for list info<br>
</blockquote></div><br></div>