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

[Kristofer Munsterhjelm]

Andy Jennings wrote:
> 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.

Most likely :-) If there are any you wonder what means, just ask.

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

It seems reasonable to me that if you multiply the number of voters (or 
the weight of every ballot) by some positive value p, the outcome should 
not change. That is the case for a fractional system, but not for an 
integer one, since when you multiply the weights, the ballots can then 
be divided more finely.

Of course, others disagree. If I remember correctly, the whole thing 
that makes Young (not Kemeny, but the "remove as few as possible to make 
a CW" method) is the integrality constraint.

>     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 haven't checked the two, but I know that for the Young and Kemeny 
methods, the linear programming solution is often exact. The same thing 
has been seen with other problems as well: there are "easy" instances of 
NP-complete problems. I think some integer programming libraries solve 
the linear programming relaxation first, and then uses this as a basis 
for branch-and-bound/etc.

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

It's a bit more "compromise friendly", although both put rather more 
weight on proportionality (vs total satisfaction) than does, say, STV. I 
just did another run with the same parameters as on 
http://munsterhjelm.no/km/elections/multiwinner_tradeoffs/ , and I got:

Name                                          Disprop      Regret
==================================================================
CFC-Kemeny                                    0.06997      0.18483
CFC-Range (exhaustive)                        0.05809      0.23319
CFC-Range (greedy)                            0.06219      0.22914

Meek STV                                      0.12078      0.09371
Schulze STV                                   0.1165       0.09591

Since CFC-Kemeny only has ranked ballots to work with, while CFC-Range 
(Munroe) uses ratings as well, I think that is a pretty good result. 
CFC-Kemeny is completely intractable for large numbers of candidates and 
winners, though.