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

[Warren Smith]

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

--I meant each WINNER is joined to exactly V*K/W voters.

However you are correct -- the way to do this is to use the complete
bipartite graph
on all voters (red) & candidates (blue) and demand each candidate be joined
to either zero or V*K/W voters in the subgraph, and each voter is
joined to exactly
K candidates in the subgraph, then ask a degree-constrained-subgraph
computer algorithm for the optimum subgraph.

I warn you I may be confused, since I was recalling the results from
the book by Lovasz & Plummer from memory.  I will try to check this
out next time I go to the math library.   But anyhow, my
perhaps-confused memory, seems to think this kind of
degree-constraint, is in polynomial time?

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

--oh dear... hoisted by my own petard.   I did recall I'd thought of
this before, but the new twist now, which I had not thought of before,
is adding this parameter "K" to the picture.  On that web page, is
only the special case K=1 of the present picture, there called
"Monroe's voting system formulated in new way."

And... crap.  I proved it NP-complete on that web page.

OK, sorry:  my "wonderful new discovery" is bogus because the
algorithm does NOT run in polynomial time, contrary to my claim.
Sorry for my senility.

However, as I showed on that web page, this IS polynomial time if you
ALREADY ARE TOLD the set of winners, and there are only binomial(C,W)
possible sets of winners, so they can all be tried.   This is not too
bad if say, #candidates=C<=32.
As Andy remarked, this runtime is not too horrible for many applications.

And, my new contribution now can be viewed as just this: adding the
parameter "K" to the picture.  Then this is still soluble in
polynomial(V,W) * binomial(C,W)
time, even with K also in the picture.

What is the best value of K??

Perhaps one could try all possible K's and then somehow assess a
posteriori, which was the best one, then use it for that election.
Then you have to ask: what is the best assessment method?   (Some kind
of 2-stage Bayesian-regret?)

> 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.

--right.  Thanks for unconfusing me.

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


-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)