[EM] Coalitional manipulation ideas for multiwinner

[Kristofer Munsterhjelm]

Since I've been thinking about coalitional manipulation (and 
strategy-resistant methods) lately, I got to think about how it might 
generalize to multiwinner without needing to assume anything about voter 
utilities. This is a tough thing to do because a strategy could 
theoretically be "partially succcessful", i.e. an attempt to replace 
three winners could end up replacing only two of them. It's not like 
single-winner where you either accomplish your goal (increase 
probability that X wins) or don't.

Well, I think I found two approaches:

Suppose that the winners prior to manipulation are W_1, ..., W_n, and 
call the winner set W. Say that a voter prefers a winning set X = {X_1, 
..., X_n} to W if his kth highest ranked candidate in X is no lower 
ranked than the kth highest ranked candidate in W, for all k, and at 
least one of them is strict (the voter ranks the kth highest candidate 
in X higher than the kth highest candidate in W).

As an example, consider a voter whose ballot is
	B>C>A>D>E
and another whose ballot is
	A>C>B>E>D.

Suppose that W = {C,E}, and X = {A, B}.
The first voter prefers A to E and B to C, and thus prefers the winning 
set X to W.
The second voter prefers B to E and A to C, and thus also prefers the 
winning set X to W.

Then, if the honest outcome for a multiwinner method is W, and there 
exists a coalition or group of voters who all prefer a winning set X to 
W, and they can get all of X elected by altering their ballots...

... then that method is manipulable for that election.

The idea is that any voter who prefers X to W can say that he's better 
off participating in the strategy because, for any winner in W, he 
prefers or is indifferent to someone in X. For instance, for the first 
voter above, he prefers X to W because if A and B win, then he can say:
	I'm not worse off due to A being elected, because E is no longer
		elected and I prefer A to E.
	and I'm not worse off due to B being elected, because C is no
		longer elected and I prefer B to C.

For the second approach, note that the former doesn't capture all 
coalitional manipulation that would make sense if we knew the voters' 
utilities. If we did, a voter might accept losing one good candidate if 
it led other better candidates to be elected, e.g. consider

	W = {C, E}
	X = {A, B}

with a voter whose honest ballot is

	C>A>B>E.

This voter does not prefer X to W by the definition above, but if the 
utilities were

	C = 100,
	A = 99,
	B = 98,
	E = 0

and there are no interaction effects (e.g. no desire for the voter to 
not see the reps obstruct each other, etc.); then the voter would 
benefit from manipulating the winners to {A,B}.

So we could also define a "worst-case" coalitional manipulation concept: 
voter V is part of a valid coalition for manipulating W to X if there 
exists an assignment of utilities consistent with V's ranking, so that 
V's expected utility given X is greater than V's expected utility given W.

Then the method is worst-case manipulable in an election if there exists 
a set of winners X and a valid coalition for manipulating W to X, so 
that if the members of that coalition manipulates, then the outcome 
changes from W to X.

(Whether such an assigment is possible can be determined by trying to 
set a dividing rank so that more candidates of X than of W are ranked at 
or above the dividing rank. Then set utilities very high on the high 
side of the divider and low on the low side. For instance, for the 
C>A>B>E example, if the divider is at third rank, then assigning C, A, 
and B approximately one, and E approximately zero, works.)


Whatever concept one uses, it would be interesting to see actual figures 
for, say, STV vs Schulze STV. Would the latter's resistance to vote 
management show up as reduced general coalitional manipulability? Or 
does IRV's resistant set property generalize enough to STV that it would 
outdo Schulze STV in manipulation resistance?

-km