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

[Warren Smith]

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