[EM] Did someone say monotonicity? Or: Droop proportionality and monotonicity

[Kristofer Munsterhjelm]

I happened upon an old post by Markus Schulze where he said that no
proportional (non-party list) method has been proven to be monotone, and
I thought that it might be useful to determine if the DPC and
monotonicity criteria are incompatible. This is how far I've got - a
nondeterministic method that (I think) passes both:

Let o_x be a random ballot. Now choose the winning council W so that it
passes all Droop constraints, and the member in W that has the lowest
rank in o_x has the highest rank. Break ties by the member in W with the
next lowest rank, and so on (leximin). If there are ties, choose one of
the maximal councils at random.

Passing Droop constraints means that if the Droop proportionality
criterion requires that two of the winners come from a given solid
coalition, then at least two candidates from that coalition must be in W
(and so on for all solid coalitions).

Now, raising A can't make A drop out of a solid coalition he used to be
in. Furthermore, no non-A candidate can get into a solid coalition he
wasn't in before, by a voter raising A, unless that new solid coalition
also contains A.

If there's no equal-rank and no truncation, we can imagine the method as
one that assigns an optimal council to each voter (based on his ballot
as o_x). The random ballot modification then chooses a random voter's
optimal council. So for the sake of simplicity, say we have no
equal-rank or truncation. (If there is equal-rank or truncation, each
voter may have multiple optimal councils, so I don't want to deal with
that complexity.)

The method is nonmonotonic if either raising A lowers the unqualified
score of some council that has A in it (before Droop constraints are
applied), or Droop constraints shift so that councils that have A in
them and would be optimal are excluded and instead some other council
without A beats every now-allowed council that has A in it.

Let's take the two in turn. Suppose that a voter raises A by turning X>A
into A>X.

For a given unqualified council containing A, there are three
possibilities: the binding (lowest rank) candidate was A, the binding
candidate was X, or neither of these.

It can't be X, because by assumption, the council before A was raised
contained A, and A was ranked below X.

If A is the binding candidate, then the unqualified score of the council
either stays the same (if the new binder is X) or improves. If the
binding candidate is neither A nor X, then nothing happens. So raising A
can't decrease the minimum rank score of any council containing A.

For any council not containing A, raising A will either decrease that
council's score (if X is the binding candidate) or have no effect (if
someone else is). So raising A can't increase the minimum rank score of
any council not containing A.

To make this argument valid for leximin, just disregard the binding
candidate and look at the next-to-binding candidate, then the third
next-to-binding candidate, etc. The same logic holds.

However, one could imagine that it's still possible for the method to
fail monotonicity if it turns out that raising A changes the Droop
constraints so that they exclude some candidate Y. If some council not
containing A beats (has a greater score than) every council containing A
and not containing Y, then it doesn't matter if a council containing A
and Y is optimal, because everything containing Y gets disqualified and
then something that doesn't contain A wins. I need to show that scenario
to be impossible.

So consider the Droop coalitions (solid coalitions with "must elect at
least k candidates" with different k attached to each). Raising A can
only refine a Droop coalition containing A (i.e. create a new Droop
coalition with a smaller solid coalition containing A and the same
constraint that at least min(k, number of candidates in coalition) must
be elected from it).

Suppose that the winning council before raising A is W, and after
raising A is W', that A is in W, and (for contradiction) that A is not
in W'.

Consider the innermost Droop coalition that contributed to getting A
elected before A was raised. This coalition, though possibly no longer
the innermost coalition containing A, will still impose a constraint
after A has been raised. If everybody in that coalition is in W', then
W' contains A and we have a contradiction. Otherwise, there exists at
least one other candidate Y in W' who can be replaced by A, and where
doing this replacement will increase the council's score. This because
raising A can only create new constraints that have A in them, so if Y
can't be replaced by A in W', Y can't be replaced by A in W, either, and
thus Y, not A, would have been in W. Since replacing Y with A will
increase the score, W' can't be the optimum, and we also have a
contradiction.

Thus the method is monotone per voter. And thus the method is
monotone in expectation.

Does that sound right?

---

Now, of course, I'd prefer to have a deterministic method. Perhaps the
same trick can be used on all voters, e.g. something like: the council
that passes Droop constraints and where the voter who ranks someone in
that council lowest ranks him highest? Analogous reasoning should work:
if a voter raises A, then everybody else's binding candidate stays the
same but his binding candidate increases in rank if it was A and nothing
happens if it was neither A nor X. As usual, break ties recursively
(leximin).

Come to think of it, suppose f(v, S) is voter v's lowest rank of
candidates in S, then shouldn't the reasoning above work for *any* order
statistic of f over the whole electorate? If someone raises A, then
either he's part of the statistic or not (he can't drop out of the
statistic by improving his score). If he's not, then nothing changes,
and if he is, it only changes to the better. Hm...

(Then the most natural order statistic would be the leximin value of f
for all but a Droop quota of the electorate. Or you could flatten the
matrix A, A_ij = voter i's rank of the jth candidate in the council,
into a vector and eliminate a 1/(seats+1) fraction of the values, then
use the vector as a leximin score.)