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

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
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.)
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Markus Schulze-3
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

Markus Schulze

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Markus Schulze-3
In reply to this post by Kristofer Munsterhjelm-3
Dear Kristofer,

your argumentation basically is: When some voters rank X higher,
then it is not possible that some other candidate Y becomes a
member of a solid coalition.

My argument basically is: When some voters rank X higher,
then it can happen that some other candidate Y who couldn't
be elected without violating Droop proportionality can now
be elected without violating Droop proportionality.
(In example 3 of my paper "On Dummett's 'Quota Borda System'" ,
X=B and Y=E.) Candidate Y can then kick candidate X out of
the winning set.

Markus Schulze


----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Toby Pereira
I feel compelled to point out that proportionality is not the same as Droop proportionality. Something can fail one particular "brand" of proportionality and still be proportional.

On Tuesday, 4 February 2020, 07:48:49 GMT, Markus Schulze <[hidden email]> wrote:


Dear Kristofer,

your argumentation basically is: When some voters rank X higher,
then it is not possible that some other candidate Y becomes a
member of a solid coalition.

My argument basically is: When some voters rank X higher,
then it can happen that some other candidate Y who couldn't
be elected without violating Droop proportionality can now
be elected without violating Droop proportionality.
(In example 3 of my paper "On Dummett's 'Quota Borda System'" ,
X=B and Y=E.) Candidate Y can then kick candidate X out of
the winning set.

Markus Schulze

----
Election-Methods mailing list - see https://electorama.com/em for list info

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
In reply to this post by Markus Schulze-3
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.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Markus Schulze-3
In reply to this post by Kristofer Munsterhjelm-3
Dear Kristofer,

> In other words, something like "Droop,X" won't retain the
> benefit of say, "Smith,X" of being automatically monotone
> whenever X is.

The Borda count is monotone.
But Smith//Borda violates monotonicity.

Markus Schulze


----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
In reply to this post by Toby Pereira
On 04/02/2020 11.25, Toby Pereira wrote:
> I feel compelled to point out that proportionality is not the same as
> Droop proportionality. Something can fail one particular "brand" of
> proportionality and still be proportional.

Yes, you're right :-)

What I like about Droop proportionality is that it implies that
proportional groups of voters (to some degree) don't have to coordinate
to get someone they prefer elected. That is also why something like
Warren's "racist"/"color proportionality" doesn't impress me as much,
because those proportionality criteria basically say that if everybody
who supports a certain party vote all the party members at max and
everybody else at min, then the party gets its share. That criterion
only tells you what happens if all the voters either coordinate or
compromise (give up their chance at deciding who gets to win within the
party in order to get the party as a whole to get its share of the seats).

Of course, methods that pass DPC might still have a serious coordination
or compromising incentive. (The criterion is stronger the more seats
there are.) But at least it reduces the need to employ such strategies.

Ideally I'd like to have a kind of proportionality that reduces to
Webster in the party list case, rather than reducing to LR-Droop, since
Webster is much better behaved as a party list method. The only such
criteria I've found so far are extraordinarily complex to state, though.

Perhaps also something that's to the Smith set what the DPC is to mutual
majority.

(And obviously, a method passing such a "Webster criterion" would
automatically fail the DPC, which is yet another indication of what you
say: proportionality isn't the same thing as Droop.)
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
In reply to this post by Markus Schulze-3
On 04/02/2020 13.01, Markus Schulze wrote:

> Dear Kristofer,
>
>
>> In other words, something like "Droop,X" won't retain the
>> benefit of say, "Smith,X" of being automatically monotone
>> whenever X is.
>
> The Borda count is monotone.
>
> But Smith//Borda violates monotonicity.

Does Smith,Borda violate monotonicity? (I.e. do Borda on the full set of
candidates, then elect the Smith set member that is ranked highest
according to the Borda outcome.)
----
Election-Methods mailing list - see https://electorama.com/em for list info