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