[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" 

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 

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 

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 
       - 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