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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
