[EM] Survey of Multiwinner Methods

[Kristofer Munsterhjelm]

On 01/08/2013 04:30 AM, Jameson Quinn wrote:
>
>
> 2013/1/7 Greg Nisbet <gregory.nisbet at gmail.com
> <mailto:gregory.nisbet at gmail.com>>
>
>     Hey, I'd like to get a sense of what sorts of multiwinner methods
>     are currently known that are reasonably good and don't require
>     districts, parties, or candidates that are capable of making
>     decisions (I'm looking at you, asset voting).
>
>
> Like Abd, I wonder at the basis for your criteria. I think that for
> reform in most English-speaking countries, districts are usually an
> advantage, parties arguably so, and intelligent candidates always.

Perhaps he's looking for some kind of multiwinner method for the pizza 
election. E.g. "n people go out for pizza and decide to split the costs 
of four pizzas. Which pizzas should they get?" Then you can't use asset, 
and districts and parties are out.

However, for a pizza election, usually n is small (definitely less than 
a hundred), so discussion/negotiation works much better than election.

Perhaps the method is to be used for a computer program that has to 
choose between different predictors of some event (e.g. a robot modeling 
reality). Then, again, asset is out (the predictors don't campaign) and 
districts and parties are not applicable. But in this case, there are 
lots of methods that work based on feedback so as to increase the weight 
of the successful predictors and attenuate those that are not. The 
weighted majority algorithm is one such, and probably the simplest. If 
testing the alternative predictors is too hard, one instead could use 
some form of multi-armed bandit testing, e.g. UCB1.

It would be amusing to consider a society that would do its political 
elections like this. These would initially elect randomly, then voters 
would be asked how well the candidate did, and then that would be fed 
back into the process. It would be elections based on what actually 
happened rather than what the candidates promise. However, the 
candidates would have incentives to game the system, and the dynamic 
nature of the thing (performance changing with time) would violate some 
assumptions in the multi-armed bandit framework, requiring restless 
bandit algorithms, which are, to my knowledge, PSPACE-hard.

In any event: Greg, I think we need more information about what the 
multiwinner method is to be used for. Why aren't districts, parties, and 
candidates that are capable of making decisions permitted?