[EM] Spatial models -- Polytopes vs Sampling

[Kristofer Munsterhjelm]

On 31.01.2022 21:39, Daniel Carrera wrote:
> Two types of spatial models:
> 
> 1) Traditional: Place individual voters randomly in an N-dimensional
> space, compute the distance between each voter and each candidate to
> compute that voter's ballot.
> 
> 2) Polytope: Kristofer's recent idea, implemented by me. Place
> candidates in space, compute their Voronoi cells, intersect them to get
> all the regions in space associated with each ballot, and compute their
> volumes.
> 
> The allure of (2) is the hope for higher precision at low cost because
> you are computing areas and volumes. Looking at their source codes,
> QHull seems to compute volumes exactly, but the Polytope library I'm
> using definitely computes volumes by random sampling. That might still
> be better than method (1) because the operations you do to compute a
> volume (linear inequalities) are simpler and easier to offload to a
> NumPy backend or even LAPACK than the sqrt() and if-branches that (1)
> requires. I want to benchmark this when I have time.
> 
> The downside of (2) is that it forces you to assume that voters are
> spread out uniformly across the space. Only method (1) allows you to
> distribute voters according to some reasonable distribution like a Gaussian.
> 
> I would like to present an idea for a third method that combines
> features of (1) and (2):
> 
> 3) Weighted Polytope: Compute Voronoi cells and their polytope
> intersections exactly as in (2). But instead of assuming that voters are
> uniformly distributed (i.e. Voters = Volumes), you also have a function
> like (1) that tells you the voter density in space. Your goal now is to
> integrate the voter density across the polytope associated with each ballot:
> 
> Voters = Mass = Integral{ Density x Volume }

This idea (restricted to 2D space) came up in an earlier thread in the
context of Yee diagrams, since the pixel at (x,y) in a Yee diagram is
given by the outcome of an election where the voters are represented by
a Gaussian centered at that point, and the Voronoi regions (as usual)
give the area within which voters vote A>B>C, etc.

So by evaluating a Gaussian integral over these regions, we could get a
v->inf Yee diagram. This could be interesting in particular for IRV due
to its chaotic behavior and tie amplification.

For 2D, it might be possible to do an exact integral of an approximate
erf. At least in that case, it would be more accurate than method 1
(assuming the erf is well-behaved). That approach won't easily scale to
higher dimensions, though.

> I don't yet know whether computing volumes is actually faster than
> method (1) for comparable accuracy. But if it is, then my method (3)
> could be the best of both worlds:
> 
> - The superior speed vs accuracy trade-off geometry (2).
> - The flexibility and realism of a dedicated voter-density function (1).

I'd imagine it would depend on how easy it is to do high dimensional
Gaussian integration. There may be more efficient methods than ordinary
MC (e.g. quasi-MC,
https://web.maths.unsw.edu.au/~josefdick/preprints/DKS2013_Acta_Num_Version.pdf)
or there may be special-case Gaussian integrals over simplices, and then
the polytope can be decomposed to simplices (like the approach for
determining the exact area) and the Gaussian integral applied to them.

Forest would probably know more about tricks of calculus; it's not my
area of speciality.

-km