[EM] Idea: Gerrymandering/clustering-based Ranked Pairs multiwinner method

[Kristofer Munsterhjelm]

This is an idea I had the other day, of a multiwinner method that
generalizes Ranked Pairs.

Suppose you have s seats to elect. Imagine dividing the ballots into s
piles and running Ranked Pairs on each. Now divide the ballots so that
the maximum support of each pile/cluster's strongest pairwise preference
is maximized, and subject to this, that the maximum support of each
pile's next strongest preference is maximized, and so on.

The problem is that this is very hard to do. So I thought of a greedy
approximation.

Do the construction on a cluster by cluster basis, i.e. first do the
first cluster to get the candidate who should be elected to the first
seat. Then do the second, and so on.

Choosing the best pairwise preference to add to a cluster consists of
choosing the pairwise preference with the most support, subject to that
the cluster has to contain the voters that must by necessity be there
due to previous pairwise preferences that you've locked in for that cluster.

Or as a linear program to determine the strength of a pairwise
preference X>Y after having locked in A>B at support strength p:

maximize support[X>Y]

subject to:
	support[A>B] = p
	support[X>Y] = sum over voters v who rank X above Y: support_voter[v]
	support[A>B] = sum over voters v who rank A above B: support_voter[v]

	for each voter v: 0 <= support[v] <= support given by v to other clusters
	(sum over all voters: support[v]) = numvoters/seats

(I've used pairwise opposition and assumed no truncation or equal-rank.
Using e.g. margins should be easy enough: support[A>B] - support[B>A] =
p, etc.)

This linear program says, first, that within the cluster, the strength
of the pairwise preference A>B (that was determined earlier) must be p
(the maximum strength determined earlier).
Second, it defines what "strength of pairwise preference" means: it's
the sum of the support by the voters who rank according to that
preference, that the LP assigns to the cluster.
Third: no voter can give more than 100% of his voting weight to that
cluster, and the cluster holds exactly numvoters/seats voters (so it's
more Hare than Droop).

Try this for all possible pairwise preferences X>Y, then choose to admit
the preference that has maximum support. If there's a tie, choose the
preference with maximum over-all support (i.e. greatest number of voters
voting X>Y in total, not just within the cluster), as that constrains
later preferences the least.

Keep going like that until all pairwise preferences (even contradictory
ones) have been set for the cluster. Run ordinary Ranked Pairs to get a
winner using that pairwise preference order. Elect the highest ranked
candidate, according to the social ordering produced by Ranked Pairs,
that has not yet been elected.

When going on to the second cluster, "support given by v to other
clusters" has to be updated. E.g. if the first ballot contributes 30% of
its weight to cluster 1, the constraint on the first ballot for cluster
two would be 0 <= support[1] <= 0.30.
(I initially thought that the voters assigned to a cluster could be
ambiguous even after every pairwise preference has been admitted. But I
now think that it doesn't matter, because all n^2 pairwise preferences
are the same for every possible ordering consistent with the admitted
preferences to a cluster, so whichever you choose has the same effect on
who's available for later clusters.)

An example, with two-seat LCR:

40: L>C>R
35: R>C>L
25: C>L>R

First cluster (50 voters). The first maximization chooses the same
pairwise preference as ordinary Ranked Pairs, namely C>R. Both C>L and
C>R have support greater than the cluster size, so C>R wins the tiebreak
since 65 voters vote C>R while only 60 voters vote C>L.

The second maximization is constrained by that the voters assigned must
all have the preference C>R (since p=50 for C>R). So the maximum becomes
L>R because this can draw both upon the 40 L>C>R voters and the 25 C>L>R
voters.

The third maximization is constrained by the need to have 50 voters who
vote both C>R and L>R. The two options are C>L and L>C. C>L gives a
support of 25 (from the C>L>R voters) while L>C gives a support of 40
(from the L>C>R voters). So L>C is admitted.

Thus the first cluster has the social ranking L>C>R, so L is elected.
The voters assigned to the first cluster are 40 L>C>R voters and 10
C>L>R voters.

Second cluster: Since 40 L>C>R voters and 10 C>L>R voters are now
unavailable, we have the following election (in essence):

35: R>C>L
15: C>L>R

It's pretty easy to see that the Ranked Pairs ordering is R>C>L. (By the
definition above, the last cluster election is equivalent to an ordinary
Ranked Pairs election with some ballots removed.) So R wins the second seat.

And thus the method gives the intended result.

-

I am not sure how to make this Droop, or how to make it a divisor method
instead of a quota method. It should be possible to use the idea for
other methods than Ranked Pairs, though. River is trivial. Schulze, not
so much.

I have the feeling that making it Droop should use Ranked Pairs's mutual
majority compliance, somehow, to pass the DPC. If so, perhaps some kind
of "surplus transfer" would work: the clustering process chooses a Droop
quota's worth of voters who get amplified into a majority; the Ranked
Pairs election is done, and then that Droop quota's worth is removed. Or
when admitting a pairwise contest, the strength must be at least a Droop
quota. Something along those lines.

If I remember correctly from my playing with the clustering concept a
long time ago, these methods tend not to be monotone; but I don't see
how the particular greedy Ranked Pairs version would be nonmonotone. If
you raise your ranking of A, then that shouldn't push you out of the
first cluster if you were in it before. And if you're in it, you raising
A can't hurt A. Perhaps it could get you into a cluster where A didn't
win, so that A then loses support in some other cluster.