[EM] Multiwinner coalitional manipulability: the other end

[Kristofer Munsterhjelm]

So I tinkered a bit with multiwinner coalitional manipulability, and 
thought that a good place to start would be the other extreme from 
single-winner, namely electing n-1 out of n candidates.

It seems that in this case, both types of coalitional manipulability 
collapses to the same thing, so there's again only one manipulability 
measure.

Suppose that the honest set of winners is S and the one we're trying to 
manipulate to is Q. Since both situations have n-1 winners out of n 
candidates, there exists only one candidate in S that's replaced by 
another in Q. Say the one in the honest outcome's candidate is A and the 
desired manipulated outcome replaces A with B. Then the voters who 
benefit from the manipulation are those that rank B ahead of A.

I then more concretely looked at the three-candidate case, with the 
model being impartial culture, and the method electing two candidates of 
the three. In this situation, and in n-1 out of n in general, bottoms-up 
IRV is manipulable iff SNTV is: what the strategists have to do is turn 
the candidate they want to kick off the winner set into the Plurality loser.

For two out of three, SNTV and bottoms-up IRV are manipulable half of 
the time under impartial culture in the limit of number of voters going 
to infinity.

For STV, if I got my quick Gregory implementation right, its 
manipulability is also 1/2, though it's much harder to analyze in closed 
form (surplus redistribution makes the win regions nonlinear).

There's a nice connection between n-1 of n multiwinner methods and 
single-winner ones: suppose that the honest outcome is {A,B} and that 
voters who prefer C to B want to change this into {A,C}. Then we could 
consider the multiwinner's outcome to be A=B>C.

If we reverse every ballot in the election and also reverse the outcome, 
we get a "single-winner" method whose honest outcome is C>A=B. Since 
every ballot in the election was reversed, the C>B coalition in the 
original multiwinner case is now a B>C coalition, and they now desire to 
change the single-winner outcome into B>A=C.

So, what single-winner election corresponds to reversed SNTV? 
Antiplurality.[1] And Antiplurality has an impartial culture 
manipulability value of 1/2, which explains why SNTV (and thus 
bottoms-up IRV) also has a manipulability value of 1/2.[2]

So why not just reverse a resistant set method and enjoy very high 
resistance to manipulation? That *is* possible, e.g. for 2-of-3, reverse 
the ballots, find the IRV "winner", and then elect everybody but that 
winner. But it fails proportionality.

Consider an election eA of the form:
1/2 - epsilon: A>C>B
1/2 - epsilon: B>C>A
     2 epsilon: C>B>A

A weak quota-based proportionality measure would be: if A has more than 
a quota of the first preferences, then A has to be elected. The example 
above forces the election of A and B with a quota even slightly less 
than a majority. However, in the reversed election rev(eA):

1/2 - eps: B>C>A
1/2 - eps: A>C>B
     2 eps: A>B>C

A is the CW and has more than 1/3 of the first prefs, hence directly 
disqualifies everybody else. So requiring resistant set compliance for 
the "single-winner" method acting on reversed elections would mean that 
A must win for rev(eA). Hence in the hypothetical multiwinner method, 
the outcome must be {B, C} for eA. But that contradicts the 
proportionality criterion, which requires that A is a winner.[3]

To check if this problem would actually compromise the manipulability or 
just occur rarely, I wrote a method that elected what the DPC would 
mandate if the DPC mandated anything, and otherwise just elected 
everybody except for a resistant set member. The Monte Carlo simulation 
gave its impartial culture manipulability as around 47%, which does show 
(if I didn't make a mistake in my coding) that it's possible to do 
better than STV. But I wouldn't recommend this kind of stitched-together 
method for practical use.

-km

[1] Minimizing someone's first preferences on the original ballot set is 
the same as minimizing that candidate's last preferences on a reversed 
ballot set.

[2] Strictly speaking, we'd also have to prove that reversing every 
ballot doesn't change the ballot distribution. For impartial culture, 
that's true; I'm not sure about IAC or spatial distributions. (It might 
be true, e.g. imagine replacing just the candidate names, which 
shouldn't change the probability distribution if it has no privileged 
candidate order -- then replacing the candidates {A, B, C, ..., Z} with 
{Z, ..., C, B, A} would reverse the ballots. But maybe there's something 
sneaky that I'm forgetting.)

[3] Another way to consider this is that if the "single-winner" election 
passes Durand's InfMC criterion, then a majority can force its winner. 
This means that a majority could force the loser in a 2-of-3 election 
with a multiwinner method based on applying the single-winner method to 
the reversed ballot set. This violates proportionality because it allows 
a coordinated majority to block smaller groups who would otherwise get 
"their" winner. Hence "InfMC on reversed elections" is not a good 
criterion for proportional methods and Durand's theory doesn't apply.