[EM] Webster-flavored multiwinner method
Kristofer Munsterhjelm
km-elmet at broadpark.no
Fri May 1 01:25:46 PDT 2009
I've been meaning to show this, but I haven't tested and implemented it
yet. Still, perhaps it would give good results.
The method is as follows. First, determine ranked votes' solid
coalitions, as in DSC and DAC. Then determine the divisor d. Each
coalition deserves the minimum of the number of members in the
coalition, and (number of voters fully supporting that coalition / d),
rounded off. Then go downwards (from the coalitions of greatest
support), reducing sets on the way until you know the composition of the
council. As you do so, there will be some contradictions (e.g a
coalition of one is supported by enough to deserve one seat, but a
larger coalition of three excluded the one in question); ignore these
contradictions, as you ignore cycle-forming in MAM. Also, remove any
coalitions "deserving" zero seats, so that one can't be punished by
raising a candidate from unranked into being supported by a set of size one.
Then pick d so that
- the number of contradictions is minimized,
and
- the number of seats the coalition consisting of all candidates
deserves is equal to the size of the council.
-
Let me show an example:
59: R1 > R2 > R3 > R4
34: R2 > R3 > R1 > R4
61: G1 > G2 > G3 > G4
20: B1 > B2 > B3 > B4
36: B4 > B3 > B2 > B1
The assembly size is 7. If the R*, G*, B* candidates were parties,
Webster would grant as follows:
R* supported by 93 out of 210: three seats
G* supported by 61 out of 210: two seats
B* supported by 56 out of 210: two seats
So let's set d=30 and generate the coalitions:
d = 30
max quotient min
210: <everybody> 16 7 7
93: {R1 R2 R3 R4} 4 3 3
93: {R1 R2 R3} 3 3 3
61: {G1 G2 G3 G4} 4 2 2
61: {G1 G2 G3} 3 2 2
61: {G1 G2} 2 2 2
61: {G1} 1 2 1
59: {R1 R2} 2 2 2
59: {R1} 1 2 1
56: {B1 B2 B3 B4} 4 2 2
36: {B2 B3 B4} 3 1 1
36: {B3 B4} 2 1 1
36: {B4} 1 1 1
34: {R2 R3} 2 1 1
34: {R2} 1 1 1
20: {B1 B2 B3} 3 1 1
20: {B1 B2} 2 1 1
20: {B1} 1 1 1
The "max" column is the maximum that can be given to the coalition
(because there aren't any more members). The "quotient" column is how
many seats are "deserved", and the "min" column is the minimum of the
two, which is how many we should try to elect from that set.
Simplifying,
group # to elect
210: <everybody> 1 7
93: {R1 R2 R3 R4} 2 3
93: {R1 R2 R3} 3 3
61: {G1 G2 G3 G4} 4 2
61: {G1 G2 G3} 5 2
61: {G1 G2} 6 2
61: {G1} 7 1
59: {R1 R2} 8 2
59: {R1} 9 1
56: {B1 B2 B3 B4} 10 2
36: {B2 B3 B4} 11 1
36: {B3 B4} 12 1
36: {B4} 13 1
34: {R2 R3} 14 1
34: {R2} 15 1
20: {B1 B2 B3} 16 1
20: {B1 B2} 17 1
20: {B1} 18 1
Let's narrow down. First, we check the <everybody> coalition. 7 to
elect, as it should be.
#2 says the R* group should get three of their four elected. #3 says
those three are {R1, R2, R3}. Now we have the R group.
#4 says the G* group should get two of their four elected. #5 says G4
should not be one of them, and #6 says G3 should not be one of them
either. Now we have the G group. #7 is consistent with this choice - the
G group includes G1.
#8 says R1 and R2 should be elected, which is consistent with what we've
decided so far. #9 says R1 must be elected, which is, again, consistent.
#10 says the B* group should get two of their four elected. #11 says one
of them should be B2, B3, B4. This forces the other to be B1. #12 says
one of them must be B3 or B4, and #13 says one of them must be B4. Thus,
the B group is {B1, B4}.
#14 is our first contradiction. Elect only one of {R2, R3}; but our
three are {R1, R2, R3}. Ignore the contradiction. #15 is consistent (we
did elect R2).
#16 is consistent (pick only one of {B1 B2 B3}). #17 is also consistent,
as is #18.
We're done - one contradiction. The council is R1 R2 R3 G1 G2 B1 B4. The
R group got three seats, the G group two, and the B group two.
-
The "disregard if below one seat" is kind of a hack, but could be
justified like this: consider all other members of the power set to have
zero support. Then these will give a fixed number of contradictions at
the very end. If some people add just a few votes to a set, it'll still
have a support of zero seats, and thus nothing changes with regards to
the number of contradictions.
If the method above is sufficiently alike Webster, it should be:
- House monotonic (the council for k=4 is made of the council for k=3
as well as a new member).
- Population pair monotonic (see my other post)
However, it does at some times break quota to do that. Thus, it doesn't
satisfy the DPC. Also, if it's house monotonic, it can't be Condorcet -
the standard Left-Right-Center example is good enough proof.
It obviously isn't summable, since the DSC/DAC information is a subset
of the power set, and thus can reach size 2^n, where n is the number of
candidates.
The method, as above, is also incomplete. I haven't mentioned how to
handle ties, e.g
10: A > B > C
10: C > A > B
10: B > C > A
In a true tie like the one above, the only real way is random ballot (or
random voter hierarchy). As in MAM, we can't "peek downwards" to see
which would lead to the least contradiction.
-
Finally, here's another example that isn't as clear cut along "party
lines". I'll use the PSC-CLE example:
33 A>D>B>C
33 B>D>A>C
32 C>D>A>B
2 D>A>B>C
Two to elect, so the upper bound on rounding is 41 and lower, 66.
d = 50
max quotient min effects
100: {A B C D} 4 2 2 <does nothing>
68: {A B D} 3 2 2 Don't elect C
34: {A D} 2 1 1 Elect A or D
33: {B D} 2 1 1 Elect B or D
33: {A} 1 1 1 Elect A --> elect A
33: {B} 1 1 1 Elect B --> elect A and B
32: {A C D} 3 1 1 consistent
32: {C D} 2 1 1 CONTRADICTION
32: {C} 1 1 1 CONTRADICTION
2: {D} 1 0 0 ignored because of 0 rule
The meaning of the max, quotient, and min columns should be self-evident
now. The "effects" column is just the explanation of each step of the
narrowing process.
The outcome is {A, B} with two contradictions.
More information about the Election-Methods
mailing list