[EM] Nondeterminism in Multiwinner Methods

[Greg Nisbet]

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?