[EM] Bolting proportionality onto the Kemeny method
Kristofer Munsterhjelm
kmelmet at broadpark.no
Thu Oct 8 11:04:26 PDT 2009
Here's a way of "bolting on" proportionality or PR behavior to the
multiwinner Kemeny method I described earlier. I call it "bolting on"
because it's fairly rudimentary and not very elegant, but it could in
principle be used for any type of proportionality:
As you may recall, the multiwinner Kemeny method works by finding k
geometric medians so that the sum of the distance between each ballot
ranking and the closest median is minimized, according to Kemeny
distance. Then the winner set is just those that are topranked on each
of the median rankings.
So that this will actually work, one imposes a constraint on the median
ranking sets (W in my other post) that no single candidate can be listed
top on more than one ballot. This constraint is simple, but it's
otherwise somewhat arbitrary.
That leads to the question: if we can have simple constraints like the
above, why not have complex ones? And thus, we have a generalized
multiwinner Kemeny method: construct median rankings as above, but
before checking each new ranking to see if the ballots' sum closest
distances are less, run it through a verification function and reject if
it doesn't pass.
To be proportional, one could simply pick as many candidates from the
first ranking as the DPC implies, according to the number of ballots
that that median ranking is closest to, and then as many from the second
as the DPC implies for that one, and so on. For instance, for the
PSCCLE example,
median ranking a.: C>D>A>B
median ranking b.: D>A>B>C
33 A>D>B>C, closest to b.
33 B>D>A>C, closest to b.
32 C>D>A>B, closest to a.
2 D>A>B>C closest to b.
Then a. is closest to 32 and b. is closest to 68, and with two to elect
and the Droop quota being 33.3^, the two winners should come from a. (C
and D).
However, relying on the DPC alone like that makes for, as I said in my
earlier reply to Jameson Quinn, a very abrupt and discontinuous rule,
and I suspect that discontinuities like that can break desirable
properties (such as monotonicity).
Therefore, why not use an apportionment rule on the rankings, with the
"support" for a ranking given by the number of ballots that ranking is
closest to? This would, in effect, make party list PR with "parties"
generated based on voters' rankings alone. The verification function
would "pass" if apportioning candidates that way leads to no one
candidate being added more than once.
For the method to pass the DPC, the apportionment method would have to
obey quota. Also, in the worst case, each geometric median is close to
equally many voters, and in that case, one would have to have k rankings
for the system to work, so one still needs to search for k median
rankings when doing a kwinner election.

Thus, the rule is: For each possible combination of rankings, check if
it's better (lower sum closest distances). If it is, check that, if
one adds candidates to the council according to some given apportionment
method, treating each median rank as a party list, no candidate is added
twice. If it is, admit that solution. Then run through all the
combinations until the best solution is found, which is the outcome.
Of course, now the method is even slower, and it's very hard to see how
to make it run quicker (since integer programming type tweaks would have
to take the complex constraint given by the apportionment method into
account). Finally, it might still be too discontinuous, since the
apportionment part is completely unrelated to the geometric minimization
idea of the Kemeny part.

"Bolting on" proportionality like shown above solves Jameson's example
in a satisfactory manner. Let's show that, using SainteLaguë:
99/1: A>B>C, closest to a. (itself)
1/1: C>B>A, closest to b. (itself)
two to elect. The first seat goes to (A > B > C), hence A, and now the
weights are
99/3: a. (A>B>C)
1/1: b. (C>B>A)
The first "party" still has greatest support, so add the second on its
"list" to the result.
Thus the outcome is {A, B}, as wanted.
More information about the ElectionMethods
mailing list