On Tue, Jul 26, 2011 at 7:21 PM, Warren Smith wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">This voting method will be for V voters, C candidates, and W winners, 0<W<C.<br>


There will also be an integer parameter K with 0<K<=W.<br>
For simplicity we shall assume W exactly divides V (although we do not<br>
really need to assume that, and it is easy to avoid assuming it, I<br>
just want to bother complicating things by explaining how).<br>
<br>
1. All voters supply scores in some fixed range (e.g. 0 to 9) for all candidates<br>
[as in "range voting"]<br>
<br>
2. Consider a bipartite graph whose V red vertices are the voters, and<br>
whose W blue<br>
vertices are the winners.   Associated with each voter-candidate edge<br>
is that voter's score for that candidate.  Assume each voter has<br>
valence K, that is,<br>
is joined by graph edges to exactly K winners for some constant K with 0<K<=W.<br>
Further, assume each candidate is joined to exactly V*K/W voters.<br></blockquote><div><br></div><div>Don't you mean "each candidate is joined to EITHER ZERO OR V*K/W voters"?</div><div><br></div><div>Then, I believe, the problem is no longer polytime.  Your own analysis is here: <a href="http://rangevoting.org/MonroeMW.html">http://rangevoting.org/MonroeMW.html</a></div>

<div><br></div><div>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.</div><div><br></div><div>With K=1, this is the same system I've been calling Monroe, and Kristofer calls "CFC-Range".</div>

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