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

[Andy Jennings]

Kristofer Munsterhjelm wrote:

> Andy Jennings wrote:
>
>> Like Jameson and Toby, I have spent some time thinking about how to make a
>> median-based PR system.
>>
>> The system I came up with is similar to Jameson's, but simpler, and uses
>> the Hare quota!
>>
>
> How about clustering logic? Say you have an electorate of n voters, and you
> want k seats. The method would be combinatorial: you'd check a prospective
> slate. Say the slate is {ABC...}. Then that means you make a group of n/k
> voters and assign A to this gorup, another group of n/k other voters and
> assign B to that group, and so on.
> The score of each slate is equal to the sum of the median scores for each
> assigned candidate, when considering only the voters in the assigned
> candidate's group.


Kristofer,

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)

I consider it to be a very promising method.

If I recall, when you did your PR simulations and graphed them on two axes
(total satisfaction vs. proportionality), you said you weren't completely
happy with your metric for proportionality.  I think you should consider
using Monroe's metric.  That is, no matter how a given method chooses it's
slate, you run the algorithm on that slate to optimally assign the voters to
that slate and then you compute the sum of the voters' grades of their
assigned candidates.

Of course, to actually find the optimal slate is an NP problem.  People
often show this by embedding the "exact cover by 3-sets problem" in it.  But
that requires having one-third as many candidates as voters!  In fact,
finding the optimal slate is NP in the number of candidates and seats to
fill, not in the number of voters.  If there are not too many candidates or
not too many seats to fill, it should be tractable to iterate over all
possible winning sets of candidates.  In reality, I think an integer
programming algorithm should be able to find the optimal slate fairly
quickly.  Or you can always dodge the question by having a public contest to
find the best slate.

If we are choosing 15 winners from 30 candidates, there are 155 million
possible slates to try.  Seems tractable to me.

I do wonder if it will be underconstrained.  That is, there will be many
possible slates all tied for first.  If so, then we'll need to have some
tie-breaker method.

Monroe's method reduces to score voting in the one winner case, though his
original paper talked mostly about voters submitting ratings and generating
the scores from the ratings (which reduces to Borda Count).  His paper
mentioned an Approval Voting variant also, which Brams expounded on at one
point.

There is some free-rider incentive, I suppose.  If you know your favorite
candidate will get elected even without your vote, then you can rate him at
zero, making sure that your vote is not assigned to him, which will help you
have more influence on the rest of the election. I still don't think it can
help a faction get more than their fair share of seats, though.

- Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110725/ecb639f4/attachment-0003.htm>