On Tue, Jul 26, 2011 at 12:03 AM, Kristofer Munsterhjelm wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">Andy Jennings wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
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: <a href="http://rangevoting.org/MonroeMW.html" target="_blank">http://rangevoting.org/<u></u>MonroeMW.html</a>)<br>

<br></blockquote></div>
I think this is the method I called CFC-Range, for "continuous forced clustering, Range".</blockquote><div><br></div><div>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.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> 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.<br>

</blockquote><div><br></div><div>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.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
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.<br>

</blockquote><div><br></div><div>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.</div>

<div><br></div><div>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.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
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.<br>


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...).<br>


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.</blockquote>

<div><br></div><div>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.</div>

<div><br></div><div>- Andy</div></div>