[EM] Monroe's Clustering Method (was PR methods and Quotas)

[Andy Jennings]

On Tue, Jul 26, 2011 at 12:03 AM, Kristofer Munsterhjelm wrote:

> Andy Jennings wrote:
>
>>
>> If you want a clustering PR method, then I would highly recommend Monroe.
>>  In Monroe, the score of each slate is equal to the sum of each voter's
>> score of his assigned candidate.  I think that, for a given slate, finding
>> the optimal way of assigning the voters to the winners is polynomial.  (See
>> Warren's page for more information: http://rangevoting.org/**
>> MonroeMW.html <http://rangevoting.org/MonroeMW.html>)
>>
>> I think this is the method I called CFC-Range, for "continuous forced
> clustering, Range".


Thanks for the clarification.  I remember looking through your list and not
having time to understand all of the methods you simulated.  I even wondered
if some of them were methods I knew by a different name.


> This method assigns voters, or fractional voters (so we can handle weighted
> votes) to one of a number of clusters, where each cluster is assigned to a
> candidate, so as to maximize the score that is the sum of scores to the
> assigned candidates in each cluster. This is done subject to the constraint
> that each cluster must have the same weight (sum of votes' weights), so one
> doesn't end up with one cluster representing 99% of the people and others
> less than 1%. Then it tries each possible slate to find the one that has a
> max sum, and that one wins.
>

Another option, instead of using fractional voters, is to make sure each
winner is assigned either floor(N/W) voters or ceil(N/W) voters, where N is
the number of voters and W is the number of winners.


> I do that assignment per slate by using linear programming, but I guess it
> could be done faster by more specialized algorithms, as Warren states. It
> might also be the case that Monroe's original integer programming
> formulation will relax easily to linear programming and so in practice be
> solvable quickly, similarly to how I usually can find the Kemeny and Dodgson
> winners quickly.
>

I think linear programming is fine for the fractional solution, but Warren
prefers the integral solution, so he prefers using the
constrained-degree-subgraph problem and solutions, though you can do the
same thing with integer programming.

I did some experiments at finding the optimal slate, for both the fractional
case and the integral case, using a general integer programming package.
 One thing I noticed was that the solution to the fractional case only
divided up as many voters as was necessary, no more.  Almost all of the
voters were assigned in whole to one of the candidates.  Did you notice
anything similar?  This makes it seem like the solution to the fractional
problem might be an excellent starting point for finding the integral
solution.


> I also made a Kemeny version of this - actually, the Kemeny version was the
> one I tried first. Here, one assigns orderings (rankings of candidates) to
> each cluster, and then allocates voters to the different clusters to
> maximize the Kemeny score of the assigned ordering wrt the cluster in
> question. The orderings are constrained so that there is a different first
> place candidate for each cluster's ordering, and then the candidates at
> first place of the orderings whose Kemeny scores' sums are maximum, win.
> However, this is *very* slow, because now one doesn't only have to find the
> right slate, but the right combination of orderings. Thus, it's impractical,
> though it seems to work to some degree as a multiwinner method (were it not
> so slow...).
> Therefore, I've been interested in Condorcet methods that give reasonable
> results under a variant of margins where the X against Y score is always
> (number of votes where X is above Y) - (number of voters where Y is above
> X), not either this or 0, whichever is more. If I could find such a method,
> it might be incorporable into linear programming and then I could make a
> clustering Condorcet method that would only be per-slate combinatorial
> instead of worse.


Is there some way in which the CFC-Kemeny method is better than
CFC-Range/Monroe?  It doesn't seem that useful to use the Kemeny scores that
the voters give to the ranking for the cluster they appear in only to
discard the entire ranking except for the first candidate.

- Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110726/028d3313/attachment-0004.htm>