Kristofer Munsterhjelm

2018-03-03 19:57:51 UTC

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

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