[EM] Intuitive argument that FPTP manipulability approaches certainty in impartial culture

[Kristofer Munsterhjelm]

On 2025-04-20 18:36, Joshua Boehme via Election-Methods wrote:
> I think you've hit on an even more general result than you realized. It 
> looks like it applies much more broadly than impartial culture. If my 
> intuition is right, we can sacrifice a lot of the assumptions of 
> impartial culture and still prove the result.
> 
> If we have something like the following, with O() meaning order notation...
> 
> 1. P(fpA = fpB)->0 as n->infinity
> 2. O(sqrt(Var(B>A - fpA))) < O(E[B>A - fpA])
> 3. O(sqrt(Var(A>B - fpB))) < O(E[A>B - fpB])
> 4. E[B>A - fpA] > 0
> 5. E[A>B - fpB] > 0
> 
> then I think you get there regardless of the underlying distribution, 
> and even if voters aren't all independent. #1 provides your first 
> inequality and Chebyshev's inequality plus the rest gives you the second 
> (possibly with A and B flipped consistently throughout for a particular 
> realization).
> 
> Note: when writing out the exact variances for a particular case, B>A 
> and fpA usually covary negatively, and likewise for A>B and fpB.
> 
> You can construct voting models where voters anti-coordinate in weird 
> ways that violate these conditions, but my guess is that realistic 
> models are generally going to meet them.
> 
> The above isn't a rigorous argument, but it gestures at the intuition. 
> You can probably weaken the assumptions further, too -- you don't need 
> #3 and #5 if fpA > fpB with probability going to 1, for example.

Very nice. I think you're right. (Strictly speaking, we can probably 
remove the first condition, because if fpA=fpB, then as long as B>A > 
fpA in expectation, we can still change a tie between fpA and fpB into a 
decisive victory for B, which is an improvement for B.)

However, other obvious voting model - impartial anonymous culture or IAC 
- fails the criteria above. As a result, most of the methods I've been 
looking at converge to a fractional manipulability value for three 
candidates for IAC.

The reason IAC has fractional values is that it's essentially a 
Dirichlet model, so the manipulability is the volume of the polytope 
where the conditions hold, divided by the total volume of the polytope 
(under constraints that the number of voters sum to some given n).

Suppose spatial is the most realistic model. Then IC (apart from its 
soft spot for Antiplurality) seems to generally be more punishing than 
spatial, while IAC is less punishing. Here are IAC n->infty values for 
some methods, from https://www.jstor.org/stable/41106091:

Plurality:      7/24 ~= 0.2917
Antiplurality: 14/27 ~= 0.5185
IRV/runoff:     1/9  ~= 0.1111
Coombs:        31/72 ~= 0.4306

I've verified this with Monte-Carlo for Plurality. Since it's no longer 
almost surely manipulable, one needs to check B and C separately.

I'm not sure if spatial converges to edge values (0 or 1). JGA's results 
(https://mpra.ub.uni-muenchen.de/32200/1/MPRA_paper_32200.pdf table 4) 
at first seems to indicate the manipulability converging (e.g. to 0.46 
for approval), but the step from 639 voters to 2559 voters doesn't seem 
to fit the pattern. So I'm unsure.

For spatial, the easiest way to start is probably by fixing the 
candidate locations in opinion space and then looking at the 
distribution of Euclidean distances from random multivariate normals to 
each of these fixed points. But converting that to something like E[ABC] 
is still going to be tough (e.g. https://stats.stackexchange.com/q/167133).

Alternatively, perhaps something around: suppose that the candidate 
positions are fixed, then we have polytopal sets in opinion space for 
each ordering. S_{A>B>C} would contain the points in opinion space 
closest to A, second closest to B, and furthest away from C. Then the 
fraction of the voters who vote ABC would be the integral of the normal 
distribution within S_{A>B>C} - call this the Gaussian volume of 
S_{A>B>C}, or Vol(ABC) with E[ABC] = n * Vol(ABC). Then there's nothing 
special about each such set (in the expectation of every arrangement of 
candidates), so that one would expect volumes of more regions in total 
(e.g. B>A = BAC + BCA + CBA) to be greater than those of fewer (e.g. fpA 
= ABC + ACB), which would suggest it's likely for Plurality to almost 
always be manipulable. But this is very handwavy and I don't feel like I 
could justify it formally. We don't get the variances this way, so it 
could well be wrong.


On an aside, I think I've also managed to determine that minmax is 
almost always manipulable under impartial culture with three candidates.

-km