[EM] More on manipulability in the limit

[Kristofer Munsterhjelm]

I had some thoughts about manipulability for methods in different 
models, and I think I understand why most methods have nontrivial 
manipulability values for IAC and spatial models, even when they tend to 
one for impartial culture.

When we're constructing an election for any of these models, we draw n 
ballots from a multivariate distribution with certain parameters (a 
parameter vector P). For instance, for the impartial culture, this 
distribution is a multinomial with p=1/c! for c candidates.

For some election, define the vote vector x as listing the number of 
voters who cast a ballot of each type. So without truncation and equal 
rank, the three-candidate vote vector is (ABC, ACB, BAC, BCA, CAB, CBA). 
Let the proportion x^ be x/||x||_1, i.e. the proportion of voters who 
voted each way.

For any given choice of distribution parameters[1], we have an "ideal 
proportion vector" Id_p(P) which is the limit of the proportion vector 
as the number of voters go to infinity. For impartial culture, that's 
just a vector with all elements equal to 1/c!.

If some conditions on variance hold (handwaving this, but it should be 
possible to formalize), then we can use these expectations to determine 
if a method is manipulable or not. Suppose that the method is definitely 
manipulable if A * Id_p(P) < b, for a constant matrix A and vector b, 
and definitely not manipulable if at least one element of A * Id_p(P) > 
b.[2]

Then, here's the point: for any given parameter vector P, we can have 
only one outcome: A * Id_p(P) < b, some element > b, some element = b. 
If it's not equality and the variance preconditions hold, the outcome is 
fixed as the number of voters approaches infinity. Thus, in the limit 
that particular election with that particular method is either 
manipulable or it isn't.

For impartial culture, we only have one possible parameter vector. So 
for impartial culture, either the method is almost surely manipulable, 
almost surely unmanipulable, or the preconditions don't hold. So that so 
many methods are almost always manipulable under IC is just a 
consequence of that inequality is much more likely than equality: you 
need a very particular method to force some element of A * Id_p(P) = b.

Now consider IAC. We uniformly pick a point p on the standard 
c!-dimensional simplex then draw n voters from a multinomial with 
probability parameters equal to p. This distribution has many asymptotic 
elections, not just one. We would expect most of these to give a 
decisive result (either the method is manipulable or not), but it would 
take a very carefully crafted method for all of them (or none of them) 
to be manipulable. Thus we get a nontrivial manipulability value: the 
proportion of points on the c!-simplex for which the associated 
asymptotic (ideal proportion) election is manipulable.[3]

The same logic holds for spatial models. In a spatial model, we first 
pick a number of candidate positions in d-dimensional space, then voter 
ballots are based on the distance between some preset distribution (e.g. 
the standard d-variate normal)  and the candidate positions. Different 
candidate positions give different elections in the limit of 
n->infinity. Some of these would be manipulable, and others would not; 
so again we get a nontrivial value.



So to summarize: IC is only "really" one election plus random variation. 
It's likely that this election is either manipulable or not, leading to 
a method's manipulability to be either zero or one for this model. Other 
models give multiple limit elections, so even if each such election is 
either definitively manipulable or not, the total proportion (over every 
possible election) is neither full manipulability nor no manipulability.

-km

[1] Some preconditions need to hold, e.g. each proportion vector element 
has a defined expectation, and that these expectations have a constant 
limit.

[2] If an element is equal, then variances again matter, which I think 
is what happens with IRV and Antiplurality under impartial culture. We 
can't simply "push" the proportion vector to one side of the inequality 
by drawing a large enough sample.

[3] We might have a nontrivial value for a single asymptotic election as 
well, if we have some elements of A * Id_p(P) equal to B. But this won't 
turn a nontrivial over-all result into a trivial one, so I haven't 
mentioned it.