[EM] Nondeterminism in Multiwinner Methods

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On Wed, Oct 29, 2008 at 7:12 PM, Kristofer Munsterhjelm
> <km-elmet at broadpark.no> wrote:
>> 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.
> 
> Actually, pick n ballots would be proportional.  If there are N seats
> and you have 1/N support, then on average you will get one seat.
> 
> Ofc, there would be variation from the average.  An extremist faction
> could win all N seats, but that is not likely.
> 
> However, that is also true for single seat random ballot, a candidate
> with 1% support could win.

There's another problem. If you pick n ballots, with some probability 
more than one ballot is going to have the same first place candidate. 
This might be solvable by picking the first place candidate of the first 
of the n ballots, then eliminating it, and so on. Would that be cloneproof?

I think Woodall wrote that Clone-Winner is incompatible with Droop 
proportionality; but what of Clone-Loser? It should pass Clone loser, 
since adding a clone never splits the vote, since the worst thing that 
could happen is that one of the clones are eliminated, after which 
another clone may be in first place on the other ballots.

> Has anyone considered PR-STV with random ballot elimination?  It would
> work exactly like PR-STV except one ballot would be picked and the
> lowest ranked candidate on the ballot uneliminated candidate would be
> eliminated (excluding elected candidates).  Also, ballots that are
> being 'held' by elected candidates would not be included for
> selection.

It might be nonmonotonic. The monotonicity criterion for 
nondeterministic methods would be "raising A on a ballot shouldn't 
decrease A's probability of winning". The single-winner equivalent would 
be "IRV with random ballot elimination".