[EM] MJ/Bucklin multiwinner method - monotone?

[Richard Lung]

Just to remind or introduce you all,
the key, to post-Impossibility of rational democratic voting method, is 
not to eliminate candidates during the stages of the count. Instead, an 
exclusion count does not have to exclude candidates before all the 
counting is done. An exclusion count (of unpreference or reverse 
preference) can, indeed must, be exactly as rational as a (preference) 
count.

https://www.smashwords.com/books/view/806030

FAB STV is not non-monotonic or preferentially perverse.

from
Richard Lung.


On 07/02/2019 21:51, Kristofer Munsterhjelm wrote:
> 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.
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>