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

[Kristofer Munsterhjelm]

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?

=

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 :)