[EM] Setwise Highest Average: A simple Sainte-Laguë based multiwinner system that reduces to DAC/DSC
Kristofer Munsterhjelm
km-elmet at broadpark.no
Sat May 30 15:16:39 PDT 2009
While trying to make Set Webster into something better (an less
underdetermined), I've been making various experimental multiwinner
methods. Most of these are no good - for instance, trying to optimize
the pairwise properties mentioned on Warren's apportionment page, only
with regards to sets rather than parties - but I did find one very
simple generalization of Sainte-Laguë, and it seems to be at least as
good as STV.
The method is merely this: First, construct a set of acquiescing, solid,
or half-solid coalitions. Then, the process consists of consecutively
adding a new viable candidate to the assembly until you have as large an
assembly as you want.
Call the set of candidates in the assembly, S_assembly, and the set of
candidates remaining unelected, S_unelected. Then, the core process
involves moving a candidate in S_unelected to S_assembly. This is done
by, for each of the coalitions, dividing the support for that coalition
by (2 * v + 1), where v is equal to the number of candidates that are
both in that coalition and in S_assembly. After this is done, sort the
coalitions from greatest support to least, then run the DAC procedure on
them, starting with S_unelected. The result will be a candidate in
S_unelected. Deem that candidate elected - move it from S_unelected to
S_assembly.
If everybody votes only for candidates within their favorite party, then
each party gets the number of seats expected by Sainte-Laguë. In the
case of a single winner, the method reduces to DAC/DSC/DHSC.
Since the method consists of moving candidates from S_unelected to
S_assembly one by one, it's clearly house monotone. A neat property of
house monotonicity is that one can force certain members to be elected,
and the method will adjust automatically, although, as I have said
before, house monotonicity has its limits, because it either forces the
method to elect a winner with narrow rather than broad support in a
single-winner case, or to be less than optimally proportional (electing
Center in the Center-Left-Right case, which then leads to the 2-seat
council being biased towards either the left or the right).
The method should also be population monotone, since both DAC/DSC/DHSC
and Sainte-Laguë is, but I have not checked this.
To demonstrate how the method works, I will give an example. After the
example, I'll give scores for the method compared to STV, according to
my election testing program, and also give some ideas of how to improve
them.
-
Consider a group of ballots that produces this acquiescing coalition set:
75 ABCD
36 ABD
34 D
33 BCD
25 BD
24 B
24 AB
17 CD
10 A
6 AD
6 C
3 ACD
3 ABC
2 BC
We want to elect three candidates.
The first candidate is straightforward DAC. S_unelected is full and
S_assembly is empty, so we start with S_unelected as the set of all
candidates. This gets narrowed down to ABD, then D. So D wins.
Now S_unelected is ABC, and S_assembly is D. Thus, for the second
round, we have
support set # already in assembly divisor round 2
75 ABCD 1 3 25.00
36 ABD 1 3 12.00
34 D 1 3 11.33
33 BCD 1 3 11.00
25 BD 1 3 8.33
25 B 0 1 25.00
24 AB 0 1 24.00
17 CD 1 3 5.66
10 A 0 1 10.00
6 AD 1 3 2.00
6 C 0 1 6.00
3 ACD 1 3 1.00
3 ABC 0 1 3.00
2 BC 0 1 2.00
which gives the new DAC order:
25 ABCD
24 AB
24 B
12 ABD
11.33 D
11 BCD
10 A
8.33 BD
6 C
5.66 CD
3 ABC
2 AD
2 BC
1 ACD
and so, B is elected. Now S_unelected is AC and S_assembly is BD. Thus,
for the third round, we have
support set # already in assembly divisor round 3
75 ABCD 2 5 15.00
36 ABD 2 5 7.20
34 D 1 3 11.33
33 BCD 2 5 6.60
25 BD 2 5 5.00
25 B 1 3 8.33
24 AB 1 3 8.00
17 CD 1 3 5.67
10 A 0 1 10.00
6 AD 1 3 2.00
6 C 0 1 6.00
3 ACD 1 3 1.00
3 ABC 1 3 1.00
2 BC 1 3 0.67
which gives the new DAC order:
15.00 ABCD
11.33 D
10 A
8.33 B
8.00 AB
7.20 ABD
6.60 BCD
6.00 C
5.66 CD
5.00 BD
2.00 AD
1.00 ACD
1.00 ABC
0.67 BC
which elects A. Thus the outcome is {A, B, D}. If it had been a two-seat
election, the outcome would have been {B, D}, and if single-winner, D.
-
In my tests, I named the new method class Setwise Highest, for Setwise
Highest Average. My election method test program scores Sainte-Laguë
method at about the level of STV on average, though considerably better
at the median. The other analogous methods (with other divisors) don't
do as well:
For a council (assembly) size of 24:
Sorted by mean:
mean median name
0.07532 0 QPQ(div Sainte-Laguë, multiround)
0.11325 0.013 Setwise Highest [Sainte-Laguë]
0.11654 0.06908 Maj[Eliminate-Plurality] (IRV-SNTV)
0.11895 0.04885 STV
0.12188 0.04656 Meek STV
0.13523 0.0584 STV-ME (Plurality)
0.14157 0.11533 Setwise Highest [Dean]
0.14165 0.11592 Setwise Highest [Huntington-Hill]
0.14168 0.11533 Setwise Highest [Adams]
0.15463 0.12917 Maj[Plurality] (SNTV)
0.17171 0.08148 Setwise Highest [D'Hondt]
smaller numbers are better.
Sorted by median:
0.07532 0 QPQ(div Sainte-Laguë, multiround)
0.07415 0.00257 QPQ(div Sainte-Laguë, sequential)
0.11325 0.013 Setwise Highest [Sainte-Laguë]
0.12188 0.04656 Meek STV
0.11895 0.04885 STV
0.12148 0.04885 Warren STV
0.13523 0.0584 STV-ME (Plurality)
0.11654 0.06908 Maj[Eliminate-Plurality] (IRV-SNTV)
0.17171 0.08148 Setwise Highest [D'Hondt]
0.14157 0.11533 Setwise Highest [Dean]
0.14168 0.11533 Setwise Highest [Adams]
0.14165 0.11592 Setwise Highest [Huntington-Hill]
0.15463 0.12917 Maj[Plurality] (SNTV)
0.28428 0.2224 PSC-CLE
0.59889 0.69084 Maj[Cardinal-20(norm)] (ditto, normalized)
0.59904 0.69447 Maj[Cardinal-20] (Majoritarian Range)
For a council (assembly) size of 5:
Sorted by mean:
mean median name
0.13333 0.09979 QPQ(div Sainte-Laguë, multiround)
0.13605 0.10455 QPQ(div Sainte-Laguë, sequential)
0.17748 0.15664 Maj[Eliminate-Plurality]
0.18409 0.16494 Setwise Highest [Sainte-Laguë]
0.19477 0.1779 STV
0.19518 0.1793 Warren STV
0.19638 0.1811 Meek STV
0.20837 0.19454 STV-ME (Plurality)
0.21469 0.19688 Setwise Highest [Dean]
0.21505 0.19681 Setwise Highest [H-Hill]
0.21558 0.19742 Setwise Highest [Adams]
0.21694 0.20511 Setwise Highest [D'Hondt]
0.25256 0.2427 Maj[Plurality]
0.31835 0.31636 PSC-CLE
0.51482 0.51203 Maj[Cardinal-20(norm)]
0.52317 0.52273 Maj[Cardinal-20]
and by median:
0.13333 0.09979 QPQ(div Sainte-Laguë, multiround)
0.13605 0.10455 QPQ(div Sainte-Laguë, sequential)
0.17748 0.15664 Maj[Eliminate-Plurality]
0.18409 0.16494 Setwise Highest [Sainte-L]
0.19477 0.1779 STV
0.19518 0.1793 Warren STV
0.19638 0.1811 Meek STV
0.20837 0.19454 STV-ME (Plurality)
0.21505 0.19681 Setwise Highest [H-Hill]
0.21469 0.19688 Setwise Highest [Dean]
0.21558 0.19742 Setwise Highest [Adams]
0.21694 0.20511 Setwise Highest [D'Hondt]
0.25256 0.2427 Maj[Plurality]
0.31835 0.31636 PSC-CLE
0.51482 0.51203 Maj[Cardinal-20(norm)]
0.52317 0.52273 Maj[Cardinal-20]
-
One possible way of making this method better might be to somehow
incorporate the sets that include already elected candidates. In other
words, if you have something like:
91: D
90: A B C
65: A B
and C has been elected, perhaps one should act as if C doesn't exist,
after having reweighted. If C's already elected (and is the only one
elected so far), the 90 are divided by 3, so we get
91: D
30: A B C
65: A B
But C isn't among the unelected anymore, so should having a preference
for C count against the A B C coalition? They already paid by having
their support downweighted, so one could remove C, thus giving
91: D
30: A B
65: A B
and hence
95: A B
91: D
meaning that one of {A, B} should be elected next, not D. I haven't
tested this approach, but it seems reasonable and might make the method
less vulnerable to vote splitting.
More information about the Election-Methods
mailing list