[EM] A monotonic proportional multiwinner method
Kristofer Munsterhjelm
km-elmet at broadpark.no
Thu Mar 11 12:38:20 PST 2010
I think I have found a multiwinner method that is both monotonic and
proportional. I have, at least, found no counterexample.
The method achieves monotonicity by cheating about proportionality:
instead of strictly adhering to the quota, it determines a divisor and
sets up a number of constraints on the output. The idea is similar to
how Webster's method (and other divisor methods) maintain monotonicity
by, in certain cases, violating quota.
Note that I although I think it is likely that one can't have both Droop
proportionality and monotonicity, I have no proof of this.
How does the method work? It has two phases, which I'll call the
constraint phase and the margins phase.
For both phases, we'll need to transform the input set of ballots into a
list of solid coalitions. This list gives all the sets for which at
least one vote preferred the members of the set (in any order) to those
not in the set, and is the same data as is used to determine the outcome
in Descending Acquiescing/Solid Coalitions.
For example, consider the ballot set
13: ABC
1: ACB
11: BAC
10: BCA
17: CAB
18: CBA
The solid coalition list is
Coalition voters
ABC 70
AB 24
AC 18
BC 28
A 14
B 12
C 27
because 24 voters prefers A and B to everything else (thus voted either
A>B>C or B>A>C), 18 voters prefer A and C to everything else, and so on.
The first phase consists of setting up constraints to narrow down which
group of winners we are going to elect. The constraints on each
coalition is:
at least round(V_i / q) candidates from this coalition must be in
the outcome[1],
where round is the rounding-off function, V_i is the number of
voters supporting coalition i, and q is determined to be the least value
that doesn't lead to a contradiction. A particular choice for the value
of "q" leads to a contradiction if it's impossible to construct an
outcome that passes all the constraints.
In other words, determine the value of q so that at least one set can
pass the combined set of constraints ("at least round(V_i / q) of the
candidates from coalition i must be in the outcome"). Call this value,
the divisor. It can be found using binary search in conjunction with
trying all possible outcomes to find out how many pass the constraints,
or (probably) in some more sophisticated manner.
Returning to our example, let's say we're going to elect a council of
size 2.
Our initial options are: elect {AB}, {AC}, or {BC}. The value of q that
satisfies our desiderata is slightly greater than 28, let's say 28.0034.
That value gives the following constraints:
Coalition voters =======elect at least
ABC 70 round(70/28.0034) = 2
AB 24 round(24/28.0034) = 1
AC 18 round(18/28.0034) = 1
BC 28 round(28/28.0034) = 1
A 14 round(14/28.0034) = 0
B 12 round(12/28.0034) = 0
C 27 round(27/28.0034) = 1
(Note here that A is *very* close to getting a seat, as 14/28.0034 =
0.49994. That will become important later.)
Can AB pass? No, because it violates the "must have at least 1 of the
{C} coalition" criterion. Can AC pass? Yes. Can BC pass? Yes.
So in this example, the constraint phase has narrowed down our choice of
outcomes to AC and BC. But which should we pick? That's where the
margins phase comes into play, and herein lies the trick that makes the
method monotonic:
For some coalition i, define i's /margin/ equal to:
floor(V_i / q) + 0.5 - V_i / q.
Calculate these. For our example:
Coalition voters margin
ABC 70 0.000307
AB 24 -0.357038
AC 18 -0.142778
BC 28 -0.499877
A 14 0.000060
B 12 0.071481
C 27 -0.464167
Assign to each possible outcome, the margins of those coalitions with
which it shares at least one candidate, then sort the margins, lesser
first. Negative margins have to be altered somehow, but it usually
doesn't matter how you do it - I just add one to them as that seems to
be the most natural. Margins for coalitions that don't match are set to
infinity, so that any margin against a coalition that actually matches
(shares at least a candidate in common) is better than no match, which
makes sense.
AC shares at least one candidate with {ABC, AB, AC, BC, A, C}.
BC shares at least one candidate with {ABC, AB, AC, BC, B, C}.
Thus the sorted margins lists are:
positive margins negative margins, adjusted n/a
AC: 0.0000607 0.000307 | 0.500123 0.535833 0.642962 0.857222 | infinity
BC: 0.0003066 0.071481 | 0.500123 0.535833 0.642962 0.857222 | infinity
The infinities are, for AC, the "B" coalition, and for AB, the "C"
coalition.
Once that has been done, process the list from the left to the right.
First, throw out those candidate sets that don't have the least first
value. If more than one remain, throw out the remaining candidate sets
that don't have the least second value, and so on. This is (I think) a
leximax comparison: a comparison where the tiebreaker is a further
comparison.
In the case above, we first compare the first entry:
0.0000607 vs 0.0003066. AC wins, BC is disqualified. If they had had
the same first value, then we would have compared the second values
(0.000307 vs 0.071481) and AC would still have won. If we exhaust the
margins lists, then all remaining candidates are part of a true tie, so
break it randomly.
The outcome for the example is therefore: AC wins.
-
But what's the point of the margins phase? To answer that, we'll have to
look at the constraints phase again. When the constraints phase settles
on a particular divisor, that's because one of the coalitions "stick":
there's a coalition that, if given just a slightly lower divisor, will
cause a contradiction. This coalition has a very low margin.
To maintain monotonicity, we must be aware of the sticking coalition. If
some voters shift their votes to prefer this coalition, then it might
increase its support without increasing the support of the other
coalitions: that means that it will no longer stick, and that it can
cause an additional constraint by lowering the divisor. Such a
constraint can only be to the benefit of the coalition in question,
because the constraints are of the form "elect at least k from this
coalition", and increased support can only increase k (unless the
divisor also increases).
Because of that, when we're uncertain about which set to pick, we should
lean towards those that may force our hand in the future (should more
voters support that set). For instance, if some voters raise A, it might
cause the set {AB} to present another constraint, and so could possibly
drive out A (say, if only {BC} is possible). The way the margins phase
handles this is that it elects {BC} before that becomes a problem.
Let's provide an example of what happens if we don't. Here I'll break
"randomly" (first set among all listed) without any margins phase, and
give a monotonicity failure example:
0: A>B>C
3: A>C>B
2: B>A>C
2: B>C>A
2: C>A>B
3: C>B>A
and the divisor is 10.0018 (for electing a single candidate), and thus:
Coalition voters constraint margin
ABC 12 1 0.30022
AB 2 0 0.300037
AC 5 0 0.000092
BC 5 0 0.000092
A 3 0 0.200055
B 5 0 0.000092
C 4 0 0.100073
Going lower will trigger the AC, BC, and B constraints, and the
intersection of those sets is empty, so that's a contradiction.
Since we're disregarding margins, the result is a tie between A, B, and
C. By my tiebreak, A wins (i.e. A wins with probability > 0). Then say a
BAC voter changes his mind and decides to vote ABC instead. The result is
1: A>B>C
3: A>C>B
1: B>A>C
2: B>C>A
2: C>A>B
3: C>B>A
and the divisor is 8.00238 (it's now possible to go lower without
contradiction because the B constraint no longer blocks), giving:
Coalition voters constraint margin
ABC 12 1 0.000446
AB 2 0 0.250074
AC 5 1 -0.124814
BC 5 1 -0.124814
A 4 0 0.000149
B 4 0 0.000149
C 4 0 0.000149
The AC and BC constraints force the election of C, so C wins. This means
A's probability of winning is zero, hence monotonicity failure.
If we make use of the margins phase, then the first election's
candidates have the margins:
A 0.000092 0.200055 0.300037 0.30022 inf inf inf
B 0.000092 0.000092 0.300037 0.30022 inf inf inf
C 0.000092 0.000092 0.100073 0.30022 inf inf inf
The first comparison retains all candidates. The second eliminates A.
The third eliminates B, and so C wins, heading off the problem.
-
How well does this method do? My tests, although I know not all think
they're much worth, seems to indicate that it's somewhat better than STV
with a council of multiple members, and about STV (IRV) as a
single-winner method. More precisely, with:
number of voters = 3 + random() % 400
number of binary issues = 1 + random() % 6
number of candidates = 2+random() % min((number of voters)/2, 9)
council size = 1 + random() % (number of candidates)
and normalized RMSE as the error measure:
Mean error Name
0.12669 STV
0.12573 Meek STV
0.12426 Warren STV
0.11866 Schulze STV
0.1065 M-Set Webster (unnamed method)
0.09583 QPQ(Sainte-Lague, sequential)
0.09544 QPQ(Sainte-Lague, multiround)
When there's only a single seat, the results change significantly:
Mean error Name
0.13723 QPQ(Sainte-Lague, multiround) (these suck at k=1)
0.13707 QPQ(Sainte-Lague, sequential)
0.01379 M-Set Webster
0.01283 Warren STV (they all reduce to IRV)
0.01283 STV
0.01283 Meek STV
0.00537 Schulze STV
In short, it is at the level of STV: somewhat better in multiwinner,
somewhat worse in single-winner. Thus, it wouldn't make a good method
for a combined single-winner/multiwinner proposal (as by FairVote's
strategy).
But it is monotonic.
-
What did I find out or make use of when constructing this method? These
points may be useful to remember:
- Divisor-type methods deal with ranges, like the range of
divisors in ordinary Webster's or the intersecting ranges that produce
the output sets in the unnamed method.
- Therefore, you can't design such a method using DSV. DSV would
try to maximize the impact of every single vote, and so would move to
the edge of each range, turning the "range" into a hard point - a quota.
- The methods don't seem to use elect-and-punish either. As such,
they avoid the chaos or sensitivity to initial conditions that make it
very hard (if not impossible) to patch up STV to be monotonic. (That may
not be exclusive to divisor-based methods, though; none of the classical
apportionment methods "elect and punish")
And further, and this was somewhat of a revelation, although obvious in
hindsight:
- Any case of monotonicity failure can be reduced to one or more
where a single voter raises A a single rank. The proof is rather simple:
first relabel all the candidates so A is the candidate to raise. Then
say there are n steps between the two ballots. Perform each step
separately. Either going one step will cause a monotonicity failure, in
which case you're done, or it won't, in which case loop back and do the
next step. If it's a situation where A is lowered, just raise every
candidate, one by one.
That alone made it much easier to patch monotonicity failure: knowing
that if all single candidate swaps can be handled, the method is
monotonic. It's not *quite* as easy as it seems (since obvious
heavy-handed methods will just move the point at which failure does
happen), but it helps a lot.
-
[1] Note that this leaves open what happens if a coalition has fewer
members than what the constraint comes out as. Say, for instance, 100 of
101 voters vote for A alone (have a random order beyond A), and the
divisor is 35. Should that disqualify all sets (because they can't get
more than one member of the "A only" coalition in the outcome anyway),
or should it pass sets that contain A? I am not sure - in practice, it
seems to make little difference.
More information about the Election-Methods
mailing list