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