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 |
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 |
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 |
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 |
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 |
In reply to this post by Kristofer Munsterhjelm-3
Dear Kristofer,
The Borda count is monotone. But Smith//Borda violates monotonicity. Markus Schulze ---- Election-Methods mailing list - see https://electorama.com/em for list info |
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 |
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 |
Free forum by Nabble | Edit this page |