[EM] Exact spatial model probabilities?

[Forest Simmons]

El mar., 25 de ene. de 2022 1:26 p. m., Kristofer Munsterhjelm <
km_elmet at t-online.de> escribió:

> 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;
>

The dirac delta is the convolution identity distribution ... convolving it
with another distribution leaves it unchanged with cliffs and sharp corners
intact.

But if you convolve with a smooth approximation of Dirac,  like a gaussian
with tiny variance, you get an infinitely differentiable approximation of
the "horrible" function.

Electrical engineers have a vast library of standard test patterns to use
as input signals for use in designing and testing circuits.

We need a similar library of test distributions for use in designing and
testing election methods.

Election methods could even be profiled by their responses to these test
patterns.

"or the derivatives would also have to
be found in some clever fashion."

That's part of the beauty of Parker-Sochaski ... clever ways of augmenting
systems of ODE's for generating smooth power series approximations.
Beyond that the library of test patterns should have the subroutines for
generating the relevant power series.


> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220125/ee61a308/attachment-0001.html>