<div dir="auto"><div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">El mar., 25 de ene. de 2022 1:26 p. m., Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> escribió:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 25.01.2022 22:09, Forest Simmons wrote:<br>
> So we can approximate voter distributions with sums, products,<br>
> convolutions, etc of standard library distributions. And then get the<br>
> mean, variance, and other moments via MacLauren series coefficients<br>
> ...AND vice versa ... if we know the desired moments, we can construct<br>
> the MacLauren series for the transform of the distribution function, and<br>
> then inverse trans form back to the desired distribution function.<br>
> Classically this was called. "The problem of the moments."<br>
> <br>
> The biggest difficulty was dealing with  divergent or slowly convergent<br>
> MacLauren series ... the solution was to use continued fraction<br>
> expansions or other Pade approximants to get convergence. Nowadays<br>
> numerical inversion of these transforms is much more practical than it<br>
> was in those days.  <br>
> <br>
> Of course all of this is trivial in one dimension ... but not in two or<br>
> three dimensions.<br>
> <br>
> At least an answer to Colin's question about the proper or central<br>
> mathematical setting for voting methods is starting to take shape.<br>
<br>
I have been investigating the problem a bit myself. I was thinking that<br>
the best case is to have a black box numerical integration method where<br>
we evaluate the function to be integrated at a number of points and then<br>
get a reasonable approximation.<br>
<br>
Well, it turns out that even getting the exact volume of a convex<br>
polytope is hard. <a href="https://mathoverflow.net/questions/979" rel="noreferrer noreferrer" target="_blank">https://mathoverflow.net/questions/979</a><br>
<br>
So even in this idealized case, there would be trouble, unless Voronoi<br>
cells have some additional structure that make calculating the volume<br>
easy (unlike convex polytopes in full generality).<br>
<br>
I did implement an approximation algorithm called billiard sampling for<br>
quadelect for a different problem, but this is only approximate. I would<br>
also guess that, like most MIPs and NP-complete problems, this problem<br>
can be determined in practical time for low dimensions. However, the<br>
autodiff of the whole solver would be horrible: you'd have a number of<br>
step functions and attendant exploding or vanishing gradients (and<br>
slowdown having to take both paths). So the numerical differentiation<br>
method couldn't use derivatives; <br></blockquote></div></div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote></div></div><div dir="auto">The dirac delta is the convolution identity distribution ... convolving it with another distribution leaves it unchanged with cliffs and sharp corners intact. </div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">Electrical engineers have a vast library of standard test patterns to use as input signals for use in designing and testing circuits.</div><div dir="auto"><br></div><div dir="auto">We need a similar library of test distributions for use in designing and testing election methods.</div><div dir="auto"><br></div><div dir="auto">Election methods could even be profiled by their responses to these test patterns.</div><div dir="auto"><br></div><div dir="auto"><span style="font-family:sans-serif">"or the derivatives would also have to</span><br style="font-family:sans-serif"><span style="font-family:sans-serif">be found in some clever fashion."</span><br></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">That's part of the beauty of Parker-Sochaski ... clever ways of augmenting systems of ODE's for generating smooth power series approximations.</span></div><div dir="auto"><span style="font-family:sans-serif">Beyond that the library of test patterns should have the subroutines for generating the relevant power series.</span></div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Perhaps the better approach is to use MC or quasi MC. Or meet in the<br>
middle somehow, e.g. let f(A>B>C, A.x, A.y, B.x, B.y, C.x, C.y) be the<br>
fraction of voters who vote A>B>C when the candidates are at the given<br>
coordinates; then use billiard sampling to determine f, and sample using<br>
MC or a perturbed over the coordinates. This could perhaps be more<br>
accurate than using MC for both picking the candidate locations and<br>
counting voter proportions.<br>
<br>
-km<br>
</blockquote></div></div></div>