[EM] Spatial models -- Polytopes vs Sampling

[Daniel Carrera]

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 }

We have to do the integral by random sampling, but that's what the Polytope
library is doing anyway. Here is how Polytope computes volume:

a) Draw random points from the smallest box that contains the polytope.
b) Count the points that are inside the polytope (i.e. satisfy all the
half-space inequalities).
c) Volume = (Volume of box) * (Points inside) / (All points)

To compute the "Mass" of the polytope with variable density, we just need
to add two steps:

d) For each point x inside the polytope, compute Density(x).
c) Voters = Mass = Volume x (Mean Density)

Step (d) can be done in NumPy, so I *hope* that this wouldn't be vastly
more expensive than what the Polytope library already does. And as I noted
earlier, 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).

It might be several days before I have time to experiment with this, but I
wanted to put the ideas out there and see if any of you had any thoughts.

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220131/b88e05b2/attachment.html>