[EM] Consensus and PR methods

[Kristofer Munsterhjelm]

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.