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

[Kristofer Munsterhjelm]

On 03/02/2020 20.48, Markus Schulze wrote:
> Hallo,
> 
>> 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.
> 
> My paper "On Dummett's 'Quota Borda System'" contains
> an example showing this method violating monotonicity:
> 
> http://www.votingmatters.org.uk/ISSUE15/P3.HTM
> 
> In example 3 (original), the following sets can be
> chosen according to Droop proportionality:
> 
> AD
> BD
> CD
> 
> Suppose one voter ranks B higher then, in example
> 3 (modified), the following sets can be chosen
> according to Droop proportionality:
> 
> AC
> AD
> BC
> BD
> CD
> CE

Your brief response was a bit hard to decipher because it didn't specify
who that voter was, or what the transformation was, but I think I see
the problem.

The problem is that although I'm technically right about what I meant
(that raising A can't increase the support of any solid coalition that
doesn't have A in it and can never increase the support of a solid
coalition that does have A in it), that's incomplete. I didn't consider
the possibility that, through decreasing the support of a solid
coalition A is not in, it may increase the number of sets that are
admissible and so make the optimal council no longer contain A.

It seems that the solution is that the base method must also, in
addition to being monotone, be consistent with solid coalitions of
exactly a Droop quota of support. But this means that the base method
itself must have some awareness of the Droop constraint structure, which
means that dividing a method into a base method and a Droop constraint
stage is going to have limited use. In other words, something like
"Droop,X" won't retain the benefit of say, "Smith,X" of being
automatically monotone whenever X is.

I already have a thought of a method that could work, though I haven't
proven it. A generalization of DSC that goes like this:

Let W be the set of all sets of councils that can be chosen according to
Droop proportionality, and let Y be the set of all solid coalitions
sorted from maximum support to minimum support, with ties broken
according to random ballot (or random voter hierarchy).

Start with the quota being the Droop quota. As long as Ws is nonempty,
decrease the quota by some epsilon. Go down the solid coalition list
from maximum support to minimum support, and apply the constraint with
the new quota to W unless this would lead to W becoming empty (in which
case ignore this constraint). When W is reduced to a single set, elect
that set as the winning council. If you get to the bottom of the list
and W still has more than one set, loop back to where you decrease the
quota by some epsilon.

That might work because rasing A can't increase the support of a
coalition not containing A and can't decrease the support of a coalition
containing A. Thus no coalition constraint that has A in it will bind
later, and no coalition that doesn't have A in it will bind sooner, so
whatever constrains the sets to have A in them will happen no later than
before raising. Furthermore, without equal-rank and truncation, the
algorithm will terminate at some point, so it'll always give a definite
answer.

However, there might be a problem if raising A affects one coalition not
containing A more severely than it does another, and then some potential
butterfly effect could lead to an entirely different council being the
winner. This new council could be formed by skipping A as an infeasible
constraint, and thus not contain A after all. I would have to check that
if I were to make a proof.

If you can think of another possible problem of that method, do tell.