[EM] Bolting proportionality onto the Kemeny method

[Kristofer Munsterhjelm]

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 top-ranked 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 
PSC-CLE 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 k-winner 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 Sainte-Laguë:

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.