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. ---- Election-Methods mailing list - see https://electorama.com/em for list info |
Free forum by Nabble | Edit this page |