[EM] Consensus and PR methods

Richard Lung voting at ukscientists.com
Wed Mar 7 11:14:52 PST 2018

So, the academic world has no consensus or standard model of election 

On 03/03/2018 19:57, Kristofer Munsterhjelm wrote:
> Say we have a consensus method M that works by choosing the council C 
> that minimizes the maximum penalty p(C, v) for the voter that 
> maximizes this penalty. That is, the method finds C according to
> C = arg min max p(c, v)
>          c   v
> where ties are broken in a leximax fashion (i.e. considering next to 
> max, then next to next to max and so on). Furthermore let the penalty 
> "nonnegative" in the sense that any voter with a real preference has 
> at least as great a penalty as a voter with no preference (the zero 
> voter, as it were).
> Now let the modified consensus method M' be one that has the same 
> optimization objective, but the method is permitted to remove a Droop 
> quota of votes to help minimize the penalty.
> So M says "what council displeases the most displeased voter the 
> least?", while M' says "what council displeases the most displeased 
> voter the least, if we can discard a Droop quota of voters from 
> consideration?"
> Then, are there any properties for p that makes M' satisfy Droop 
> proportionality? Can we in general turn consensus methods of this form 
> into PR methods by adding a "you can discard a Droop quota" rule?
> If we can, then we easily get a multiwinner version of Bucklin/MJ by 
> doing the following:
> Let g(c, v) be the grade voter v gives to the least preferred 
> candidate in c.
> Let the consensus method M be
> C = arg max min g(c, v)
>          c   v
> Let M' permit the method to remove a Droop quota, i.e. if |V| is the 
> number of voters, and V is the set of voters itself:
> C' = arg max c:
>     max x subset of V so that |x| = |V|/(seats+1):
>         min v in V \ x:
>             g(c, v)
> For a single-winner election, M' is (up to tiebreaker) just MJ, 
> because for each potential winner c, the removal step will remove the 
> voters who grade c the worst, and the Droop quota for single-winner is 
> a majority. Then the voter grading the c the worst after half of the 
> voters have been removed is just the median voter.
> Some thoughts about two-winner remove-voter minimax Approval follow. 
> Reasoning about what voter removal actually does can get kinda hairy, 
> thus I may very well be wrong:
> In minimax Approval, p(c, v) is the Hamming distance between c and 
> voter v's ballot, i.e. the number of candidates in c but not approved 
> by v plus the number of candidates approved by v not in c.
> Say we have an analogous Droop criterion for Approval: if more than k 
> Droop quotas approve of a set of j candidates (and nobody else), then 
> at least min(k, j) of these must be elected.
> For two winners, there are these possibilities:
>     1. no Droop constraints
>     2. k = 2, j >= 2
>     3. k = 2, j = 1
>     4. k = 1, j >= 1
>     5. k = 1, j = 1
> 1. is no problem, because we can elect anyone we want without running 
> afoul of the Approval DPC.
> 2. Since there can only be three Droop quotas in total, when we're 
> considering A = {C_1, C_2} with C_1 and C_2 in the set of j candidates 
> (call it J), we can eliminate all but the J-voters and the maximum 
> penalty is j-2.
> In contrast, for some B = {C_x, C_y} not a subset of j, the best it 
> can do is eliminate a Droop quota of the J-voters. In the best case 
> (for B), everybody but the J-voters approve of B alone. But there 
> still remains a Droop quota (plus one voter) of the J-voters, and each 
> of them gives penalty j. So A is preferred to B.
> If B = {C_1, C_x}, then even if everybody but the J-voters approve of 
> B alone, the J-voters give penalty j-1. So A is still preferred to B.
> 3. Same as in 2, but let A = {C_1, C_x}, J = {C_1}. With A, we 
> eliminate so that only the J-voters are left, and then max penalty is 
> 1 (for C_x). Furthermore, every remaining voter gives penalty 1. Let B 
> = {C_x, C_y}. In the best case for B, a Droop quota of J-voters are 
> eliminated and we have a Droop quota plus one left. These all give 
> penalty 2, which is worse than penalty 1. So A is preferred to B.
> 5. Let A = {C_1, C_x} and B = {C_x, C_y}. In the best case for B here, 
> two Droop quotas minus a voter approve only of B, and the remaining 
> Droop quota plus one voter approves of J = {C_1}. Eliminating all but 
> one of the J-voters gives a max penalty of 3 from that one J-voter: 
> one point for not having C_1, and two points for having C_x and C_y. A 
> eliminates one of the two B-approving Droop quotas and gets a penalty 
> of 1 from every remaining voter, which is better.
> Note that I assume that C_x is approved by the B-voters. If that were 
> not the case, then {C_x, C_y} would already be beaten by some {C_z, 
> C_y} where C_z is. Note also that I don't consider the case where the 
> B-voters also approve of a whole load of other candidates, with the 
> idea of raising the penalty under A. The problem is that because only 
> two candidates can be elected, this would also raise their penalty 
> under B.
> 4. Let A = {C_1, C_x} and B = {C_x, C_y}. The best case for B has 
> worst penalty j+2, since after a Droop quota of J-voters have been 
> eliminated, there remains a single voter who only approves of J. After 
> eliminating some of the B-voters, A gets penalty j from the J-voters 
> (j-1 for the members of J not part of {C_1, C_x} and one more for C_x 
> which is not approved by them), and one penalty point from the B-voters.
> Here it'd seem that adding loads of candidates to the B-voters would 
> make things hard. Can it be salvaged?
> Suppose there are J-voters and C-voters. B is a subset of C.
> When considering outcome B, before excluding a Droop quota, every 
> J-voter gives a penalty of j+2 and every C-voter gives a penalty of 
> c-2 where c=|C|.
> Under outcome A, before excluding, every J-voter gives j, and every 
> B-voter gives c (-1 for having C_x, +1 for having C_1).
> If j+2 > c, then we're in the domain above, and no problem.
> If c > j+2, then the excluded candidates under both A and B are C-voters.
> So under B we have a Droop quota of C-voters with penalty c-2, and a 
> Droop quota plus one of J-voters at j+2.
> Under A we have a Droop quota of C-voters with penalty c, and a Droop 
> quota plus one of J-voters at j.
> So unless I made a mistake, Hamming distance is not good enough. But I 
> might have made a mistake, because it seems strange that even in 
> ordinary minimax Approval, a coalition can increase its power by 
> approving a lot of clones. E.g. suppose in ordinary minimax Approval 
> that there are two coalitions of almost equal size:
> n+1: A B
> n: C1 C2 C3 ... Cq
> {A, B} gets worst penalty q+2 (there are n of these and n+1 zeroes)
> {A, C1} gets worst penalty q (n voters like C1 but not A)
> {C1, C2} gets worst penalty q-2 (n voters give this penalty, and then 
> n+1 give penalty 4).
> ... does that mean an arbitrarily small minority can force its own 
> council to win by just approving enough clones that they set the worst 
> penalty in every outcome? That feels rather wrong.
> ----
> Election-Methods mailing list - see http://electorama.com/em for list 
> info

Richard Lung.
Democracy Science series 3 free e-books in pdf:
E-books in epub format:

This email has been checked for viruses by Avast antivirus software.

More information about the Election-Methods mailing list