[EM] MJ/Bucklin multiwinner method - monotone?

[Kristofer Munsterhjelm]

Here's a mulitwinner method that I think passes both mono-raise and the
DPC. I'd like to have someone check my reasoning, though; if I'm right,
it's the first method I know of that passes both, but I've had little
luck proving the combination of the two before, so I could be wrong.

----

Let f(b, C, k) be the k highest grades of ballot b (in sorted order,
highest first) if we only look at the grades for candidates in set C.

Let g(B, C, k) be leximin b in B: f(b, C, k), where B is a set of
ballots. In other words, g(B, C, k) is the k highest grades of the voter
who graded the candidates in C the worst.

If C is a council, then f(b, C, k) is a measure of how much a voter
likes the best k candidates on that council, and g(B, C, k) is a measure
of how much the worst-off voter likes the best k candidates on that council.

Now, up to tiebreaks, MJ can be considered to work like this:

1. For each candidate X:
1.1. Eliminate half the ballots from the input election B to get B_elim.
Choose the ballots to eliminate is in such a way as to maximize
g(B_elim, {X}, 1).
1.2. Let X's grade be g(B_elim, {X}, 1).
2. The winner is the candidate with the greatest grade as above (apply
whatever tiebreak you'd like).

This is just a fancy roundabout way of saying that if you eliminate the
half of the voters who graded X the worst, and then look at what the
worst-off remaining voter thinks of X, then you get the median grade.

So let h(B, C, k, m) be leximax g(B \ E, C, k), with |E| = m. That is,
how well the worst-off remaining voter is after you eliminate m ballots
in such a way as to make the worst-off remaining voter best off. And let
V=|B| be the number of voters. Then X's grade by 1.1 and 1.2 above can
be written as h(B, {X}, 1, V/2).

MJ passes mutual majority by grades: If more than a majority grades
every candidate in some set M at or above some grade k, then the winner
must come from M.

(Note that mutual majority sets can be nested by grade. Trivially, every
voter grades every candidate at or above bottom grade, but only some may
rank a group of candidates at or above a given higher grade.)

The reason it does that is because MJ's h(B, {X}, 1, V/2) can only
eliminate half the voters.
Suppose that a majority of the voters grade X at Good or above, while a
majority grades Y at Poor or above, but not at Good or above. Then h(B,
{X}, 1, V/2) must be better than h(B, {Y}, 1, V/2), because the
worst-off voter for h(B, {Y}, 1, V/2) includes someone who grades Y at
Poor or Fair, whereas h(B, {X}, 1, V/2) can eliminate everybody who
grades X below Good, by our assumption.

Furthermore, MJ is monotone both in grades and ranks. If you increase
A's grade (without altering any other candidate's grade), that either
won't affect h(B, {A}, 1, V/2) (if you're not the worst-off remaining
voter), or it will improve A's situation (if you are, and there are
nobody else who will become the new worst-off voter who graded A lower
than you did). It won't affect h(B, {X}, 1, V/2) for any other X because
you didn't change anyone else's grade.
Similarly, lowering A's grade without altering any other candidate's
grade will either not affect h(B, {A}, 1, V/2) or will lower it.
And raising A above X ranking-wise (i.e. going from ...>X>A>... to
...>A>X>...)can be considered first raising A grade-wise and then
lowering X, neither of which can harm A. So MJ is monotone in the
ranking sense too.

All of this suggests a multiwinner generalization, hopefully
generalizing mutual majority to Droop proportionality, and preserving
monotonicity. Here it is:

For both seat-discrete and continuous versions, start with PC being the
set of all possible councils (every possible way to assign candidates to
the number of seats). Let DQ be a Droop quota.

The seat-discrete version goes like this:

For k = 1..seats:
	- Eliminate every council C from PC for which h(B, C, k, k*DQ) is not
leximax.

The seat-continuous (voter-discrete) version is like this:

For k = DQ...V:
	- Eliminate every council C from PC for which h(B, C, floor(k/DQ), k)
is not leximax.

I'm reasonably sure that the method is monotone, because the
monotonicity argument above holds no matter what the final two
parameters of h are: Either you're the worst-off voter, in which case
you improve the outcome for A but not for councils not having A; or
you're not, in which case you have no effect.

DPC is trickier, but I think it passes that one too.

Start by considering that groups of more than one Droop quota have the
right to have a candidate of their choice elected.

The k=1 stage of the seat-discrete version makes sure that any council
containing the preferred candidates of a group of more than one Droop
quota have higher values of h than any not containing such (the
reasoning is similar to that for MJ: since the elimination quota is set
to a Droop quota, it can't eliminate any group of more than a Droop
quota of voters). k=1 ensures that these groups of more than one Droop
quota don't get to decide more than one candidate each, since the
worst-off calculation doesn't go deeper than one candidate.

Then the same happens for k=2. Since all remaining councils satisfy
one-Droop-quota constraints, the work that was done with k=1 is not
undone, and since the elimination can only eliminate up to two Droop
quotas, it can't contradict any two-Droop-quota constraints.

Lower k can't contradict higher-Droop constraints either, because the
same logic that goes for single-Droop constraints go for higher
constraints. If the elimination stage can't eliminate more than a Droop
quota's worth of voters, it definitely can't eliminate more than two
Droop quotas' worth.

As for the seat-continuous method, the point is just to perform some
tiebreaks, and to reduce to the MJ method above in the case of seats=1.

Implementing this method is not going to be fun. The naive approach is
definitely not polytime since it keeps a set of every possible council.
However, the fact that h(B, C, k, m) only looks at k candidates of the
council might make it possible to cheat the complexity devil by building
the council from the bottom up.