election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Single-winner to multi-winner by blowup

KM
Kristofer Munsterhjelm
Fri, Jul 9, 2021 5:45 PM

Here's a possible way to turn a single-winner method into a multiwinner
one. All that's required is some kind of quality metric (a total order
over elections, representing if the winner is a good fit to the
election). It's sort of a continuation of my cluster-based greedy
approximation method for Ranked Pairs (from January).

  1. Choose a Droop quota of voters[1] so that, when their voting weight
    is blown up to half the electorate's voting weight (the remaining voters
    getting the other half), the quality metric of the resulting election is
    maximized.

  2. Elect the winner of the post-blowup election that maximizes the
    quality metric. Eliminate the winner and remove the Droop quota of
    ballots that were blown up, from the original election.

  3. Repeat from step one until the full assembly has been elected.

If the base method passes mutual majority and elections with smaller
mutual majority sets have better quality metrics than elections with
large ones, then the blowup method passes Droop proportionality.

The approach is greedy and thus not optimal. If the base method is a
good single-winner method, the multiwinner method will tend to first
find very clear and strong factions (a Droop quota faction supporting a
few candidates, or even one candidate). As these are elected, the
electorate will eventually become more "mushy" and the quality of the
later winners may suffer.

I wouldn't expect monotonicity to survive the transformation - most
likely, monotone methods would suffer the same kind of lookahead
problems as BTV does.

However, there is an interesting quality when paired with Condorcet
methods like Ranked pairs: the most consensus-friendly single-winner
methods become the most partisan multiwinner methods. This because the
quality metric accurately identifies which candidates most clearly
represent a certain faction.

Using Droop instead of Hare should help with the partisanship, though;
e.g. with an odd number of seats and an even number of factions, Ranked
Pairs should choose a consensus candidate for the last seat.

Doing the quality metric optimization may be difficult. Two very easy
ones are Range (doesn't pass mutual majority) and MJ (is this just
BTV?). Plurality would produce a semiproportional method kind of (but
not entirely) like SNTV. Ranked Pairs can be done by linear programming
and perhaps more quickly with a multiplicative weights algorithm (I'm
not sure).

-km

[1] Properly speaking, this selection may choose a fraction of a number
of ballots; it's not restricted to picking whole ball

Here's a possible way to turn a single-winner method into a multiwinner one. All that's required is some kind of quality metric (a total order over elections, representing if the winner is a good fit to the election). It's sort of a continuation of my cluster-based greedy approximation method for Ranked Pairs (from January). 1. Choose a Droop quota of voters[1] so that, when their voting weight is blown up to half the electorate's voting weight (the remaining voters getting the other half), the quality metric of the resulting election is maximized. 2. Elect the winner of the post-blowup election that maximizes the quality metric. Eliminate the winner and remove the Droop quota of ballots that were blown up, from the original election. 3. Repeat from step one until the full assembly has been elected. If the base method passes mutual majority and elections with smaller mutual majority sets have better quality metrics than elections with large ones, then the blowup method passes Droop proportionality. The approach is greedy and thus not optimal. If the base method is a good single-winner method, the multiwinner method will tend to first find very clear and strong factions (a Droop quota faction supporting a few candidates, or even one candidate). As these are elected, the electorate will eventually become more "mushy" and the quality of the later winners may suffer. I wouldn't expect monotonicity to survive the transformation - most likely, monotone methods would suffer the same kind of lookahead problems as BTV does. However, there is an interesting quality when paired with Condorcet methods like Ranked pairs: the most consensus-friendly single-winner methods become the most partisan multiwinner methods. This because the quality metric accurately identifies which candidates most clearly represent a certain faction. Using Droop instead of Hare should help with the partisanship, though; e.g. with an odd number of seats and an even number of factions, Ranked Pairs should choose a consensus candidate for the last seat. Doing the quality metric optimization may be difficult. Two very easy ones are Range (doesn't pass mutual majority) and MJ (is this just BTV?). Plurality would produce a semiproportional method kind of (but not entirely) like SNTV. Ranked Pairs can be done by linear programming and perhaps more quickly with a multiplicative weights algorithm (I'm not sure). -km [1] Properly speaking, this selection may choose a fraction of a number of ballots; it's not restricted to picking whole ball