[EM] Super Condorcet Winners, three-candidate IRV manipulability

[Kristofer Munsterhjelm]

François Durand published a paper, "Why Instant-Runoff Voting Is So 
Resilient to Coalitional Manipulation", in the beginning of June.[1] In 
it, he defines what he calls a "Super Condorcet Winner" or SCW, which is 
a candidate that not only beats everybody else pairwise, but also gets 
more than 1/k of the first preferences in any k-candidate matchup.

In resistant set terms, an SCW disqualifies everybody else directly.

The good news is that a method that always elects SCWs and has a certain 
structure (as IRV does, or every resistant set method does), is 
strategy-proof when an SCW wxists. (Simple explanation: suppose the 
method elects from the resistant set and A is the CW, so A~>X for all 
other X. Then voters whose honest preferences were B>A can never break 
A~>B. Therefore they can't introduce B into the resistant set, so they 
can't make B win.)

The bad news is that it's not enough to just elect an SCW when the SCW 
exists, the method must also handle strategy robustly. E.g. a composite 
method that elects the SCW when one exists, otherwise does Plurality, is 
not strategyproof when A is the SCW. B>A voters could break A~>C, making 
A no longer an SCW, and then if B is the Plurality winner, their 
strategy paid off.

With all of that considered, I thought I'd figure out how often SCWs 
exist in three-candidate impartial culture. A is an SCW in an election 
with n voters if:
(1)	ABC + ACB + CAB > n/2
(2)	ABC + ACB + BAC > n/2
(3)	ABC + ACB > n/3

(1) encodes that A beats B pairwise, (2) that A beats C pairwise, and 
(3) that A has more than a third of the first preferences.

Three-candidate impartial culture can be modeled as a multinomial with 
six categories (ways of ranking candidates), each with equal 
probability. As the number of trials (voters) goes to infinity, the 
Gaussian approximation becomes increasingly more accurate.

After some trivariate Gaussian manipulation, I find that the probability 
that A is an SCW is:
	SCW_A = (pi + arcsin(1/3))/(4 pi) ~= 0.27704336...

Since B and C can also be SCWs, and we want manipulability, which is 
bounded by when there's no CW, the maximum manipulability of methods 
that elect the SCW and have proper structure is
	1 - (3 * SCW_A) = (pi - 3 asin(1/3))/(4 pi) ~= 0.16886991...

Interestingly, this matches IRV's three-candidate impartial culture 
manipulability from my Monte Carlo simulations to the significant digits 
(for a quadrillion voters; I listed them in my post of 2025-03-08). My 
simulation to determine the manipulability of the most manipulable 
resistant set method also returns this value. So for three candidates 
and impartial culture, it's tight: in the limit of infinite voters, and 
disregarding elections that occur with probability zero, IRV/resistant 
set methods are manipulable iff the honest election doesn't have an SCW.

In his paper, Durand mentions that there exist unmanipulable IRV 
elections without an SCW. Presumably these have more than three 
candidates, or almost never occur under impartial culture in the 
infinite voter limit. My simulations also suggest that, with more 
candidates than three, the worst possible resistant set method is more 
manipulable than IRV.

-km

[1] The paper can be found here: 
https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p658.pdf