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. Choose, among all possible such graphs, the graph with the greatest sum-of-edge-scores. 4. That tells us the W winners, and we are done. "But wait," you complain. "That's exponentially hard because binomial(C,W) could be exponentially huge, it could grow roughly like 2^C when C is large! And that's only the tip of the iceberg... the number of possible graphs is way huger than that!" But no, actually, finding the optimum possible graph is a polynomial(V*C)-time computation, because in the book L.Lovasz & M.Plummer: "Matching theory," it is explained how to reduce such "degree-constrained subgraph" optimization problems to the graph-matching optimization problem, which is known to be polynomial time. Now. Does this method exhibit "proportional representation" (PR)? If all chocolate voters score all chocolate candidates max, the vanilla voters score all vanilla candidates max, the peppery voters score all peppery candidates max, etc (and every candidate and every voter has exactly one flavor) then this method using K=1 plainly will elect the exact same winner-flavor-fractions as voter flavor fractions assuming enough candidates run from each flavor so that we do not run out, and assuming flavor fractions always are exact multiples of 1/W so we do not need to worry about "integer round off" effects. In fact, this method with K=1 is very similar to Andy Jennings' proposal: the graph matches each voter to "her personal representative" (whom she always scores max under our voter-behavior assumption). However it does not do the artificially "greedy" approach Andy Jennings was using which got him into trouble (as he noticed, on his last step) -- it instead finds the best among all configurations, rather than merely a greedy configuration. So, if K=1, then yes, there is a sense in which this method causes proportional representation. However, one could argue that K=2 (say) ought to be better than K=1, because voters' opinions about more than 1 candidates are taken into account. (It isn't clear what is the best value of K. Perhaps about W/2?) Can the method still be considered PR even with K=2? Suppose every voter has exactly TWO flavors she scores max (e.g. a "vanilla AND chocolate" voter). Under this assumption, the method plainly will elect a parliament that could be considered PR. Choosing K too large, however, should stop PR from happening: If K=W and we had 90% vanilla voters then after electing 90% vanilla winners, the vanilla voters would still have a huge say about the 10% remaining winners, having indeed more impact on that than the 10% chocolate voters. We'd get 100% vanilla winners. (Consider changing one chocolate winner to vanilla We gain 9 points for every 1 point we lose, so it changes, then continue for the next winner.) In fact with K=W this just reduces to "naive multiwinner range voting" which obviously is not a PR voting method. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) and math.temple.edu/~wds/homepage/works.html ---- Election-Methods mailing list - see http://electorama.com/em for list info
