[EM] A multiwinner voting method based on graph-matching theory

[Andy Jennings]

On Tue, Jul 26, 2011 at 7:21 PM, Warren Smith wrote:

> This voting method will be for V voters, C candidates, and W winners,
> 0<W<C.
> There will also be an integer parameter K with 0<K<=W.
> For simplicity we shall assume W exactly divides V (although we do not
> really need to assume that, and it is easy to avoid assuming it, I
> just want to bother complicating things by explaining how).
>
> 1. All voters supply scores in some fixed range (e.g. 0 to 9) for all
> candidates
> [as in "range voting"]
>
> 2. Consider a bipartite graph whose V red vertices are the voters, and
> whose W blue
> vertices are the winners.   Associated with each voter-candidate edge
> is that voter's score for that candidate.  Assume each voter has
> valence K, that is,
> is joined by graph edges to exactly K winners for some constant K with
> 0<K<=W.
> Further, assume each candidate is joined to exactly V*K/W voters.
>

Don't you mean "each candidate is joined to EITHER ZERO OR V*K/W voters"?

Then, I believe, the problem is no longer polytime.  Your own analysis is
here: http://rangevoting.org/MonroeMW.html

I've decided that it's still tractable enough for my taste, but it is
NP-hard in the very worst case and that's a fatal flaw to some.

With K=1, this is the same system I've been calling Monroe, and Kristofer
calls "CFC-Range".

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