[EM] Nondeterminism in Multiwinner Methods

[Kristofer Munsterhjelm]

Greg Nisbet wrote:
> For the record, I am against nondeterminism in single winner methods,
> but that is another ball of wax that I want to keep separate.
> 
> Anyway, the single winner methods can be divided into a few basic types:
> 
> 1) slow (these take O(candidates!) time. They are non-iterative)
> 2) fast (these rely on iterations. Usually a kind of elect and punish
> cycle (think RRV or STV).)
> 3) party-based
> 4) nondeterministic (this includes your collusion-based methods (Asset
> Voting) and random ones (e.g. random ballot))
> 5) naive (without making any changes, use a single winner method)
> 6) plurality-based (CV, Block vote, Preferential Block etc...)
> 
> (1)s tend to become unwieldy.
> (2)s suffer bizarre paradoxes
> (3)s require parties
> (4)s produce lower quality winners on average
> (5)s do not produce proportional results...
> (6)s are kinda unimpressive
> 
> Just a bit of multiwinner voting theory: I suspect it would be
> relatively uncontroversial to declare (1) to be best if execution time
> weren't an issue. However, it is. What do you do about it?
> 
> There are various shortcuts to help a reasonable solution be found
> quickly. You could resort to iteration, randomness, parties, or give
> up.
> 
> Of course, various elements of these can be combined. It would be
> possible to have a party-based method with various other methods
> inside of it.
> 
> Nondeterministic elements do seem to be useful in the case of
> multiwinner methods.
> 
> It is unlikely that a nondeterminstic solution would be perfect, of course.
> 
> However, I suspect that it can deliver at least some of the benefits
> of group (1) without incurring factorial execution time.
> 
> Any thoughts on the matter?

Raph gave an explanation with multiple groups doing the optimization. 
Another option that would probably seem fair would be to find an initial 
council by using a type-2 method, then hill climb from there. The 
outcome may still have strange paradoxes (since the type-2 method may be 
nonmonotonic with the two outcomes being respective local minima), but 
it would be deterministic and may do better.

This would be a scale, where the nondeterministic "pure randomness" 
shortcut would be on one end, and this on the other. In the middle you 
would have something like genetic algorithm-based optimization, or 
simulated annealing.

If there's a PTAS for the problem in question, that could also be used. 
Of course, then one has to ask, a polynomial time approximation scheme 
of what? What variable does an election method approximate? That would 
have easier answers for PAV/LPV/etc methods, since those minimize or 
maximize some satisfaction number.

Also, one may ask if a strategyproof nondeterministic method exists for 
multiwinner elections (like Random Ballot for single-winner). That 
question may not be of much practical use, though, but could give some 
ideas of how multiwinner methods "should" be constructed. A multiwinner 
analog of random candidate would be vulnerable to cloning, and I don't 
think random ballot (pick n ballots) would be proportional either.