[EM] A monotonic proportional multiwinner method

[Raph Frank]

On Thu, Mar 11, 2010 at 8:38 PM, Kristofer Munsterhjelm
<km-elmet at broadpark.no> wrote:
> 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").

If you set q = 2*voters + delta, then it meets this requirement, as
all constraints will round to 0.  It would mean that the first test
value for the binary search would be q = voters

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

So, each coalition will have a specific set of q values where it will
become less strict.  As q gets smaller, more constraints are added.
If C is a valid council for q = X, then C will be a valid council for
all q>X.

Thus, that number of valid councils is a monotonically increasing
(stepwise) function of q.

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

You could just define it as

 V_i/q - round(V_i/q) + 0.5

This would save you needing to add 1 to negative values.  I think it
gives the same answer for positive margins as your formula.  Also,
rather than having fractions of q's for your margins, you could use

V_i - round(V_i/q)*q+ q/2

This means that the margins count in votes, but that is purely aesthetic.

In any case, using round, you are just asking what is the difference
between the number of seats the coalition is entitled to have and the
number of seats that the actually have (plus half a seat).

Anyway, I wonder if the number of candidates in each coalition should
also be considered, when determining matches.

For example, assuming the ABC is the marginal coalition (lowest
margin) and the current constraint is that 1 candidate from that
coalition must be elected.

The 2 possible winning councils, due to other constraints are

AB and BD

Your margins would say that they both share at least 1 candidate, so
they should both be considered as a match.

Thus you would move to the next marginal coalition, as they would both
be able to claim ABC as their lowest margin match.

However, if ABC was to get more votes, it would shift from ABC>=1 to
ABC>=2.  This would actually eliminate BD, as it cannot meet the
ABC>=2 condition.

This means that the a better rule would be that, when considering
possible matches, a marginal coalition only matches a possible winner,
if the winner would meet the condition for the marginal coalition, if
the marginal coalition increased by 1 seat.  Also, completed
coalitions should not be considered as possible marginal coalitions.
A completed coalition means that the number of seats that it is
entitled to is greater or equal to the number of members of the
coalition.

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

I would say you should just redefine the constraints so that a
constraint is met if everyone in the coalition is elected, no matter
how many seats it is entitled to.  The various proportionality
criteria do that.  An alternative would be to assign that candidate 2
or more seats.

Clearly, if all the voters voted

A>B>C>D>E>....>Z

then the method should just elect the first N candidates on the ballot.