[EM] A wv question, and a general class of multiwinner methods

[Michael Ossipoff]

On Aug 3, 2016 12:25 PM, "Kristofer Munsterhjelm" <km_elmet at t-online.de>
wrote:
>
> In wv, suppose A>B and B>A are equally strong. What happens? Does A>B
> and B>A both go to 0 or do they both retain their pairwise strength?

(end quote)

That isn't a defeat.  It's a pair-tie. The wv measure of defeat-strength
only compares the strength of defeats.

That pair-tie merely does't give either candidate a defeat.

Of course in MMPO, it would count as pairwise opposition for both
candidates.

Michael Ossipoff
>
> =
>
> I've been trying to work a bit more on the MAM-Hare multiwinner method,
> but the inner function (the "magic" of the method) turned out to be very
> hard to construct.
>
> The idea of the MAM-Hare method is to sequentially find Hare-quota sized
> groups of voters so that the group has particularly strong affirmed
> majorities, then electing the candidate that this affirmed majority
> suggests and excluding the voters who contributed to the majorities.
>
> The problem lies in both finding a group of suitable voters and their
> affirmed majorities at the same time.
>
> For instance, if there are multiple candidate majorities supported by
> more than a Hare quota, then choosing just which majorities to affirm to
> get as many Hare-quota level majorities affirmed as possible can be
> pretty difficult. If more than a Hare quota prefers A>B, then we have to
> pick a Hare quota sized subset, but we want to choose a subset so that
> we can affirm as many other Hare-quota sized majorities as possible
> using only those voters. So the problem reduces to:
>
> "Given a number of sets (voters who have some given pairwise
> preference), determine which you can intersect (preferences you can
> affirm) so that you intersect as many sets as possible (affirm as many
> majorities as possible) while still keeping the intersection greater
> than or equal to a Hare quota".
>
> And that's apparently NP-complete (from clique).
>
> The whole point of the method is to scale reasonably - otherwise, why
> not just use Schulze STV? So if finding the right group of voters to
> assign to a candidate is NP-complete, that's kind of a disappointment.
>
> -
>
> However, it seems the general idea can be salvaged. That is:
>
> 1. Start with no winners
> 2. Find a quota-sized group who most strongly prefer some candidate to win
> 3. Elect that candidate and remove the voters from consideration
> 4. If it's candidate-based (not party list) or the party who won has had
> all its candidates elected (e.g. fielding 3 candidates and getting 3
> seats), eliminate the winner from all the ballots.
> 5. Repeat until all seats are full.
>
> If I replace 2. by:
>         2. For each remaining candidate:
>                 2.1. Measure how strong support we can get, from a Hare
>                 quota, in favor of this candidate being elected.
>            Return the candidate that maximizes this measure.
>
> then I basically get Monroe Algorithm A (if I've got it right), and it
> forms a class of greedy multiwinner methods based on how step 2.1. works.
>
> I don't know if it's possible to do this for more complex Condorcet
> methods, but it should be possible for simpler ones. I made a linear
> program for minmax(margins) for this purpose:
>
https://github.com/kristomu/voting-scripts/blob/master/linear_programming/sequential_minmax/multiwinner_minmax.mod
>
> Getting the best minmax(margins) score of a candidate A (with only a
> quota's worth of voters involved) can be phrased like this, in the
> "minimize worst defeat" formulation:
>
> Minimize max_defeat
>
> subject to:
>         for every candidate Y != A:
>                 max_defeat >= sum over all ballots b:
>                         ballot_weight_chosen[b] * {voter voted Y>A}
>                         - ballot_weight_chosen[b] * {voter voted A>Y}
>
>         for all ballots b:
>                 0 <= ballot_weight_chosen[b] <= ballot_weight[b]
>
>         (sum over all ballots b: ballot_weight_chosen[b]) = quota
>
> where for the bth ballot, ballot_weight_chosen[b] is 0 if the ballot was
> not made part of the group, otherwise it gives how much of the ballot
> was chosen. E.g. if the ballot weight is 9, ballot_weight_chosen could
> be anything between 0 and 9 inclusive.
>
> Solving the linear program will then provide a suitable function for
> step 2.1. above. The general method would, in each round, choose the
> candidate with minimal max_defeat over all candidates. Ties can be
> broken by random voter hierarchy based on the whole electorate (no
> voters eliminated).
>
> The "virtual constituencies" formed may contain fractional ballots, but
> that is required for the LP to work. If we demanded the group be
> assembled only from whole voters, the program would be an integer
> program and (presumably) much more difficult to solve. Besides, not
> permitting fractional vote assignment could lead to weird outcomes where
> multiplying all voter weights by 100 could change the result.
>
> Some other notes:
>
> - It's rather easy to make a Droop MJ method based on this (and it ends
> up looking a lot like STV).
>
> - It's rather hard to make a Hare MJ method based on this, because 50%
> of the voters in each Hare quota can vote for someone but your target
> candidate, and how you choose them makes a difference as to whom will
> get high scores later.
>
> - If I recall correctly, way back when I made the proportionality/BR
> simulator, I implemented something similar to this for Kemeny by brute
> force. It ended up being very proportional but having very bad
> (majoritarian) BR. So for party list, I'd suggest an ensemble-rule like
> system with relatively more centrist tiebreakers/kingmakers.
>
> - Minmax isn't that good a method as far as compliances go. It fails
> Smith, independence from clones, and Condorcet Loser, for instance.
>
> - Furthermore, any party list system based on quotas are subject to the
> Alabama paradox. So the system isn't all that good, but it's a proof of
> concept. Well, more of a sketch of a proof of concept :)
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20160916/6e2ef8e9/attachment.htm>