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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
