[EM] 16.9%, or beware trying to brute-forcing strategic manipulability

[Kristofer Munsterhjelm]

Lately, I've been investigating why the resistant set does as well as it 
does against coalitional manipulation, at least when there aren't too 
many candidates. As part of this investigation, I wrote a program to try 
to find how often IRV is manipulable under impartial culture with three 
candidates.

I was surprised to find that my more mathematical approach was giving 
much higher manipulability values than my simulations, though, on 
checking with James Green-Armytage's values, they're not too far off his.

For 999 voters and three candidates, JGA reports IRV to be manipulable 
16.6% of the time[1]. My earlier simulations, with choosing elections at 
random and trying a given number of times to find a strategy, said 
13.4%. Tweaking the number of attempts at finding a strategy per 
election, I could get my simulator up to 15.8%, but it would be very slow.

With a bit more thought, I realized that it should be possible to 
directly determine when an IRV election is manipulable. I did that, used 
multinomials to generate impartial culture elections with a very large 
number of voters, and got this for the manipulability of IRV with three 
candidates:[2]
	With a billion voters (1e9): 16.88404(25)%
	With a quadrillion (1e18):   16.88699(25)%

I guess the lesson here is that random strategy tests may underestimate 
methods quite a bit, particularly when finding a strategy is hard. Since 
I'd imagine nonmonotone methods to be harder to manipulate than monotone 
ones, all else equal, this could make the former look better than the 
latter.

Or I made a mistake :-)


Since the values I found are rather different from the simulated ones, 
it'd be nice if someone could check my reasoning for determining when 
IRV is manipulable. Here it is:


Without loss of generality, relabel the candidates so that A and C 
advance to the second round of IRV, B is the Plurality loser, and A is 
the IRV winner. This can be done for every election that's not a tie, so 
assuming this labeling of candidates shouldn't distort anything.

Since we're taking very large values of n (number of voters), ties 
constitute a vanishingly small probability and shouldn't make a 
difference. Ties could be discounted even further by using some small 
epsilon instead of one vote when requiring the strategic voters to 
exceed a particular threshold.

Then the election is manipulable if:
	1. The voters who prefer B to A (B>A voters) can compromise for B, 
pushing C off the top two, and if then B beats A pairwise, B wins 
(compromising);
	2. The C>B>A voters can compromise for B to push A off the top two and 
make B win (compromising);
	3. If C beats B pairwise, then some of the C-first voters can vote B 
first, pushing A off the top two and making C win, if C still beats B 
pairwise after that's done (pushover).

I think those three scenarios cover every non-tie coalitional 
manipulation opportunity, but I could be wrong. The linear conditions are:

1. (fpB + CBA > fpC - CBA) and (B>A > A>B)
	fpB is the number of first preferences for B. CBA is the number of 
C>B>A voters, A>B is the number of voters preferring A to B.
The only B>A voters who could compromise for B are those who sincerely 
vote for C, hence C>B>A. So the statement says: if the CBA voters were 
to vote for B instead, then B would have more first prefs than C; 
furthermore, B beats A pairwise, so that B would defeat A in the second 
round.

For 2. and 3., the following common conditions must hold:
	(fpC > fpA) and (fpB + fpC > 2 * fpA + 1)

The first condition says that C is the Plurality winner. If not, then 
drawing votes from C to give to B would push C off before it would push 
A off.

The second condition says that the mean number of votes for B and C 
exceeds the number of votes for A plus one. Some or all of the C-first 
voters want to vote B first instead to push A off, and that's impossible 
if, even if they could completely equalize B and C's first preferences, 
A would still tie them or have a higher number of first prefs.

Then for 2., additionally:
	(C>B < 2 * (fpC - fpA - 1) + B>C) and (CBA >= (fpC - fpA - 1))

Here the point is to give fpC - fpA - 1 votes from C to B to push A off 
the top two. My program distinguishes between manipulation in favor of B 
and C, so the first condition states that B is the pairwise winner after 
the votes have been moved from C to B, because CBA voters changing to 
BCA would have an effect on whether C beats B pairwise. The second 
condition says that there are enough C>B>A voters to perform the 
strategy. (C>A>B voters would not be interested, because B would be the 
winner after manipulation and they prefer A to B.)

For 3., the additional condition is just:
	(C>B >= 2 * (fpC - fpA - 1) + B>C)

which says that the C-first voters shifting their votes to B won't make 
B win instead of C. Since fpC > fpA was checked by the common conditions 
above, fpC - fpA - 1 is positive, so the C-voters always have enough 
votes to shift.  If this condition holds, then manipulation in favor of 
C is possible.

-km

[1] "Strategic voting and nomination", table 2.

[2] Perhaps it's possible to find the exact value with infinite voters 
(in the limit) by doing something like Gehrlein did in 1997 with 
Condorcet cycles. But that'll take more math chops than I've got.