[EM] A monotonic proportional multiwinner method

[Kristofer Munsterhjelm]

Raph Frank wrote:
> 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

A list of solid coalitions always has the entry of the coalition of all 
the candidates, which is voted upon by all voters (even if they 
truncate). This entry, its support being equal to the number of voters, 
produce an ultimate limit.

On one end, you have 2 * voters, which will round everything to 0, 
meaning that every council will pass; on the other, for k seats, you 
have the point at which (voters / q) = k+0.5, i.e. the least point where 
the set of all coalitions demands one more than the number of seats, 
when the divisor is applied and the result rounded.

The valid interval is <voters/(k+0.5), 2*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.

That's what makes the binary search work. If the function were not 
monotonic, the binary search could possibly get lost. Doing better than 
binary search would probably involve looking at how the ranges interact, 
and that, I think, is related to the gcd function.

For instance, let's define f = 1/q, because linearity is much more 
managable when dealing with factors than divisors. If a coalition, call 
it cA, is supported by 2r voters, and the other coalition, call it cB, 
is supported by 3r voters, you would get a pattern like:

f-->

cA:  000011112222333344445555
cB:  000000111111222222333333

and the intersecting ranges change as follows (I use letters because 
it's not obvious which constraint would stick, and the caps is just a 
repeat):

cA:  000011112222333344445555
cB:  000000111111222222333333
int: aaaabbccddddAAAABBCCDDDD

and the pattern repeats after four changes: this is related only to the 
2 and 3, not to the common factor r.

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

Using other schemes for the negative values is possible - it doesn't 
break monotonicity - so I've left that open. It doesn't seem to make 
much difference in practice, however, so you still have a point.

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

The half seat is because 0.5 is the least you have to add to an integer 
value to make the rounding function round to the next integer. It would 
be possible to make a variant of this method for Jefferson's method 
(round downward) or Adams's (upward), but these would have the biases 
inherent to those methods.

It might be interesting to make the rounding parameter (0.5) free, and 
so experiment with the changes in multiwinner Yee diagrams as the 
parameter is changed from 0 to 1.

On a similar note, it might be possible to make a largest remainder 
version - first narrow down to those councils that give each group 
according to the quota in question (which we know is possible, at least 
with the Droop quota, otherwise the DPC would be worthless), then 
somehow prefer councils that reward coalitions with greatest remainders 
after the quota. Varying the quota would then be of interest in much the 
same way as varying the rounding parameter.

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

That's not a monotonicity problem, since raising one's preference for D 
can't increase the support of the ABC coalition, nor can lowering one's 
preference for A, B, or C do so.

It might make a useful tiebreak if the method finishes the margins phase 
with multiple councils, though that event is rare. I'll experiment more 
when I get time, see if it makes a difference.

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

It does that whether or not having too few members disqualifies the 
coalition. If it does, then the divisor is just readjusted until it's no 
longer a problem.

I have experimented a bit as to whether your suggestion improves things 
or not. By itself, the rule that a coalition that has too few members is 
nevertheless entitled as if it had enough, makes the results slightly 
worse. However, when I also remove completed coalitions' margins, the 
results improve compared to when I do neither. Also, a coalition 
shouldn't be punished for having too few members, so I think I'll leave 
in the change.