[EM] Consensus and PR methods

Jack Santucci jms346 at georgetown.edu
Wed Mar 7 11:19:11 PST 2018

Consensus in academia? Maybe that cigarettes cause cancer. Maybe.

I jest.

This paper may be helpful:

On Wed, Mar 7, 2018 at 2:14 PM, Richard Lung <voting at ukscientists.com>

> So, the academic world has no consensus or standard model of election
> method?
> 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.
> http://www.voting.ukscientists.com
> Democracy Science series 3 free e-books in pdf:
> https://plus.google.com/106191200795605365085
> E-books in epub format:
> https://www.smashwords.com/profile/view/democracyscience
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info

Jack Santucci, Ph.D.
Independent scholar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20180307/d2e675af/attachment-0001.html>

More information about the Election-Methods mailing list