[EM] Exact spatial model probabilities?

[Kristofer Munsterhjelm]

On 25.01.2022 22:09, Forest Simmons wrote:
> So we can approximate voter distributions with sums, products,
> convolutions, etc of standard library distributions. And then get the
> mean, variance, and other moments via MacLauren series coefficients
> ...AND vice versa ... if we know the desired moments, we can construct
> the MacLauren series for the transform of the distribution function, and
> then inverse trans form back to the desired distribution function.
> Classically this was called. "The problem of the moments."
> 
> The biggest difficulty was dealing with  divergent or slowly convergent
> MacLauren series ... the solution was to use continued fraction
> expansions or other Pade approximants to get convergence. Nowadays
> numerical inversion of these transforms is much more practical than it
> was in those days.  
> 
> Of course all of this is trivial in one dimension ... but not in two or
> three dimensions.
> 
> At least an answer to Colin's question about the proper or central
> mathematical setting for voting methods is starting to take shape.

I have been investigating the problem a bit myself. I was thinking that
the best case is to have a black box numerical integration method where
we evaluate the function to be integrated at a number of points and then
get a reasonable approximation.

Well, it turns out that even getting the exact volume of a convex
polytope is hard. https://mathoverflow.net/questions/979

So even in this idealized case, there would be trouble, unless Voronoi
cells have some additional structure that make calculating the volume
easy (unlike convex polytopes in full generality).

I did implement an approximation algorithm called billiard sampling for
quadelect for a different problem, but this is only approximate. I would
also guess that, like most MIPs and NP-complete problems, this problem
can be determined in practical time for low dimensions. However, the
autodiff of the whole solver would be horrible: you'd have a number of
step functions and attendant exploding or vanishing gradients (and
slowdown having to take both paths). So the numerical differentiation
method couldn't use derivatives; or the derivatives would also have to
be found in some clever fashion.

Perhaps the better approach is to use MC or quasi MC. Or meet in the
middle somehow, e.g. let f(A>B>C, A.x, A.y, B.x, B.y, C.x, C.y) be the
fraction of voters who vote A>B>C when the candidates are at the given
coordinates; then use billiard sampling to determine f, and sample using
MC or a perturbed over the coordinates. This could perhaps be more
accurate than using MC for both picking the candidate locations and
counting voter proportions.

-km