Exact spatial model probabilities?
My minimum-manipulability optimization system can find exact
probabilities that a voter will vote according to a particular ranking,
under impartial culture.
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
One benefit of the spatial model over impartial culture is that it's
much more clear how one may assign utilities to each ranking, so the
optimization system could also be used to investigate tradeoffs between
VSE and manipulability. (Durand suggested sampling on a sphere for
associating utilities with impartial culture, but I haven't read the
suggestion in detail. https://arxiv.org/pdf/1511.01303.pdf)
-km
These are fantastic questions.
The spherical geometry makes sense for Universal Domain methods because, as
Saari pointed out in his Geometry of Voting, the natural distance between
two permutations is the number of transpositions it takes to convert one
into the other... the Kemeny distance.
There are 12 permutations of three candidates ... which arrange themselves
naturally on the face of a clock. Any "Gray Code" where successive
permutations differ by only one transposition will match the twelve hours
with the twelve permutations:
For example, ABC, ACB, CAB, CBA, BCA, BAC, and back to ABC. Each
permutation will be diametrically opposite to its reverse order.
For permutations of four candidates you get 24 points on the surface of a
sphere.
Each permutation is adjacent to three others. For example, ABCD is next to
BACD, ACBD, and ABDC. When you arrange all 24 of these permutations
symmetrically on the surface of a sphere, so that the distance between any
two adjacent permutations is the same, you will find that reversed
permutations are polar opposites.
It's harder to visualize the arrangement of the 120 permutations of five
symbols, but topologically they reside symmetrically on the surface of a
4-dimensional ball. The surface of a four dimensional compact manifold is
in general a three dimensional manifold, in this case a 3-sphere, just as
the surface of a 3-dimensional ball is an ordinary 2-dimensional sphere ...
2D manifolds have area, while 3D manifolds have volume. A circle, the
boundary of a disc, is a "1-sphere" because it has length, namely its
circumference.
General Relativity (without black holes or worm holes) models the Big Bang
as a four dimensional space-time manifold whose temporal cross sections are
3-spheres ... precisely the kind of spheres on which the 120 distinct
complete rankings of five candidates must be arranged if you require
adjacent rankings to be the same distance apart.
So the space of permutations of n symbols consists of n factorial points
distributed evenly on the boundary of an (n-1) dimensional ball. A
Euclidean ball of radius R consists of all vectors v having L_2 norms ||v||
less than or equal to R.The set where equality holds is its boundary. If
the vector space has a basis of n vectors, the ball of radius R will be n
dimensional, and its boundary will be (n-1) dimensional.
These high dimensional vector spaces are ubiquitous in science, especially
in quantum mechanics and other applications of partial differential
equations ... the general mathematical setting being "Functional Analysis."
So Saari had the right idea topologically, but not metrically ...the same
topological space can have many different metrics that yield the same
topology, and the Kemeny metric is not quite right; by making all adjacent
permutations the exact same distance apart, the Kemeny metric introduces
clone dependence into methods based on it ... most notably the Kemeny-Young
method, and Borda as related to Saari's geometry of voting.
In my de-cloned Kemeny-Young posts, I have shown how to modify the Kemeny
metric to make it respect the natural clustering of clone sets, while
preserving the natural Kemeny generated topology.
Topology is all about local stretching and shrinking without ripping apart
or smashing together either the natural proximities or the large scale
connections.
Now we start to see the difficulty of trying to work within Universal
Domain rules: UD requires ballots that are permutations of the candidates,
so if we identify voters with their ballots, voters are distributed on
spheres. But issue spaces are products of line segments, like rectangles,
blocks, etc.
If there are two issues, then issue space is a rectangle. If there are four
candidates, then ballot space is a two dimensional sphere, so according to
UD rules, that only allow voter influence through their ballot rankings,
there is a topological mismatch of voter/ballot space and issue space.
For example, the Borsuk-Ulam theorem shows that any continuous map from an
n-sphere into a rectangle (or any other lower dimensional product of
intervals) must have a pair of polar opposite points that get mapped to the
same point; i.e. this requires that two polar opposite rankings correspond
to the exact same point in issue space.
That's one reason I take Universal Domain rules with a grain of salt, and
feel free to supplement rankings with ratings, approval cutoffs, etc.
I know that's not any help with your main question, but it may give some
insight into Durand's spherical distribution suggestion.
I'll try to give a practical suggestion next time!
El vie., 21 de ene. de 2022 7:02 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
My minimum-manipulability optimization system can find exact
probabilities that a voter will vote according to a particular ranking,
under impartial culture.
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
One benefit of the spatial model over impartial culture is that it's
much more clear how one may assign utilities to each ranking, so the
optimization system could also be used to investigate tradeoffs between
VSE and manipulability. (Durand suggested sampling on a sphere for
associating utilities with impartial culture, but I haven't read the
suggestion in detail. https://arxiv.org/pdf/1511.01303.pdf)
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
Roger Penrose did a proof of super-luminal connections, using "magic dodecahedra" popularised in his book, Shadows of the Mind. Previously, as in the Bell theorem, the proof had only been statistical. Penrose offered a deterministic proof.
I offered my own explanation of super-luminal connections, in my free e-book, Statistical Relativity Elections. Essentially, I argued it was a geometric mean of super-luminal connections and sub-luminal connections. This comes out of the special relativity situation, which allows, in theory, for tachyons, as well as tardyons. (Quantum theory does not allow for individual tachyons.)
I call myself a naive physicist (an amateur, I scarcely pretend that much).
Regards,
Richard Lung.
On 22 Jan 2022, at 5:53 am, Forest Simmons forest.simmons21@gmail.com wrote:
These are fantastic questions.
The spherical geometry makes sense for Universal Domain methods because, as Saari pointed out in his Geometry of Voting, the natural distance between two permutations is the number of transpositions it takes to convert one into the other... the Kemeny distance.
There are 12 permutations of three candidates ... which arrange themselves naturally on the face of a clock. Any "Gray Code" where successive permutations differ by only one transposition will match the twelve hours with the twelve permutations:
For example, ABC, ACB, CAB, CBA, BCA, BAC, and back to ABC. Each permutation will be diametrically opposite to its reverse order.
For permutations of four candidates you get 24 points on the surface of a sphere.
Each permutation is adjacent to three others. For example, ABCD is next to BACD, ACBD, and ABDC. When you arrange all 24 of these permutations symmetrically on the surface of a sphere, so that the distance between any two adjacent permutations is the same, you will find that reversed permutations are polar opposites.
It's harder to visualize the arrangement of the 120 permutations of five symbols, but topologically they reside symmetrically on the surface of a 4-dimensional ball. The surface of a four dimensional compact manifold is in general a three dimensional manifold, in this case a 3-sphere, just as the surface of a 3-dimensional ball is an ordinary 2-dimensional sphere ... 2D manifolds have area, while 3D manifolds have volume. A circle, the boundary of a disc, is a "1-sphere" because it has length, namely its circumference.
General Relativity (without black holes or worm holes) models the Big Bang as a four dimensional space-time manifold whose temporal cross sections are 3-spheres ... precisely the kind of spheres on which the 120 distinct complete rankings of five candidates must be arranged if you require adjacent rankings to be the same distance apart.
So the space of permutations of n symbols consists of n factorial points distributed evenly on the boundary of an (n-1) dimensional ball. A Euclidean ball of radius R consists of all vectors v having L_2 norms ||v|| less than or equal to R.The set where equality holds is its boundary. If the vector space has a basis of n vectors, the ball of radius R will be n dimensional, and its boundary will be (n-1) dimensional.
These high dimensional vector spaces are ubiquitous in science, especially in quantum mechanics and other applications of partial differential equations ... the general mathematical setting being "Functional Analysis."
So Saari had the right idea topologically, but not metrically ...the same topological space can have many different metrics that yield the same topology, and the Kemeny metric is not quite right; by making all adjacent permutations the exact same distance apart, the Kemeny metric introduces clone dependence into methods based on it ... most notably the Kemeny-Young method, and Borda as related to Saari's geometry of voting.
In my de-cloned Kemeny-Young posts, I have shown how to modify the Kemeny metric to make it respect the natural clustering of clone sets, while preserving the natural Kemeny generated topology.
Topology is all about local stretching and shrinking without ripping apart or smashing together either the natural proximities or the large scale connections.
Now we start to see the difficulty of trying to work within Universal Domain rules: UD requires ballots that are permutations of the candidates, so if we identify voters with their ballots, voters are distributed on spheres. But issue spaces are products of line segments, like rectangles, blocks, etc.
If there are two issues, then issue space is a rectangle. If there are four candidates, then ballot space is a two dimensional sphere, so according to UD rules, that only allow voter influence through their ballot rankings, there is a topological mismatch of voter/ballot space and issue space.
For example, the Borsuk-Ulam theorem shows that any continuous map from an n-sphere into a rectangle (or any other lower dimensional product of intervals) must have a pair of polar opposite points that get mapped to the same point; i.e. this requires that two polar opposite rankings correspond to the exact same point in issue space.
That's one reason I take Universal Domain rules with a grain of salt, and feel free to supplement rankings with ratings, approval cutoffs, etc.
I know that's not any help with your main question, but it may give some insight into Durand's spherical distribution suggestion.
I'll try to give a practical suggestion next time!
El vie., 21 de ene. de 2022 7:02 a. m., Kristofer Munsterhjelm km_elmet@t-online.de escribió:
My minimum-manipulability optimization system can find exact
probabilities that a voter will vote according to a particular ranking,
under impartial culture.
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
One benefit of the spatial model over impartial culture is that it's
much more clear how one may assign utilities to each ranking, so the
optimization system could also be used to investigate tradeoffs between
VSE and manipulability. (Durand suggested sampling on a sphere for
associating utilities with impartial culture, but I haven't read the
suggestion in detail. https://arxiv.org/pdf/1511.01303.pdf)
-km
Election-Methods mailing list - see https://electorama.com/em for list info
Election-Methods mailing list - see https://electorama.com/em for list info
Very interesting!
El sáb., 22 de ene. de 2022 1:45 a. m., Richard Lung <
voting@ukscientists.com> escribió:
Roger Penrose did a proof of super-luminal connections, using "magic
dodecahedra" popularised in his book, Shadows of the Mind. Previously, as
in the Bell theorem, the proof had only been statistical. Penrose offered a
deterministic proof.
I offered my own explanation of super-luminal connections, in my free
e-book, Statistical Relativity Elections. Essentially, I argued it was a
geometric mean of super-luminal connections and sub-luminal connections.
This comes out of the special relativity situation, which allows, in
theory, for tachyons, as well as tardyons. (Quantum theory does not allow
for individual tachyons.)
I call myself a naive physicist (an amateur, I scarcely pretend that much).
Regards,
Richard Lung.
On 22 Jan 2022, at 5:53 am, Forest Simmons forest.simmons21@gmail.com
wrote:
These are fantastic questions.
The spherical geometry makes sense for Universal Domain methods because,
as Saari pointed out in his Geometry of Voting, the natural distance
between two permutations is the number of transpositions it takes to
convert one into the other... the Kemeny distance.
There are 12 permutations of three candidates ... which arrange themselves
naturally on the face of a clock. Any "Gray Code" where successive
permutations differ by only one transposition will match the twelve hours
with the twelve permutations:
For example, ABC, ACB, CAB, CBA, BCA, BAC, and back to ABC. Each
permutation will be diametrically opposite to its reverse order.
For permutations of four candidates you get 24 points on the surface of a
sphere.
Each permutation is adjacent to three others. For example, ABCD is next to
BACD, ACBD, and ABDC. When you arrange all 24 of these permutations
symmetrically on the surface of a sphere, so that the distance between any
two adjacent permutations is the same, you will find that reversed
permutations are polar opposites.
It's harder to visualize the arrangement of the 120 permutations of five
symbols, but topologically they reside symmetrically on the surface of a
4-dimensional ball. The surface of a four dimensional compact manifold is
in general a three dimensional manifold, in this case a 3-sphere, just as
the surface of a 3-dimensional ball is an ordinary 2-dimensional sphere ...
2D manifolds have area, while 3D manifolds have volume. A circle, the
boundary of a disc, is a "1-sphere" because it has length, namely its
circumference.
General Relativity (without black holes or worm holes) models the Big Bang
as a four dimensional space-time manifold whose temporal cross sections are
3-spheres ... precisely the kind of spheres on which the 120 distinct
complete rankings of five candidates must be arranged if you require
adjacent rankings to be the same distance apart.
So the space of permutations of n symbols consists of n factorial points
distributed evenly on the boundary of an (n-1) dimensional ball. A
Euclidean ball of radius R consists of all vectors v having L_2 norms ||v||
less than or equal to R.The set where equality holds is its boundary. If
the vector space has a basis of n vectors, the ball of radius R will be n
dimensional, and its boundary will be (n-1) dimensional.
These high dimensional vector spaces are ubiquitous in science, especially
in quantum mechanics and other applications of partial differential
equations ... the general mathematical setting being "Functional Analysis."
So Saari had the right idea topologically, but not metrically ...the same
topological space can have many different metrics that yield the same
topology, and the Kemeny metric is not quite right; by making all adjacent
permutations the exact same distance apart, the Kemeny metric introduces
clone dependence into methods based on it ... most notably the Kemeny-Young
method, and Borda as related to Saari's geometry of voting.
In my de-cloned Kemeny-Young posts, I have shown how to modify the Kemeny
metric to make it respect the natural clustering of clone sets, while
preserving the natural Kemeny generated topology.
Topology is all about local stretching and shrinking without ripping apart
or smashing together either the natural proximities or the large scale
connections.
Now we start to see the difficulty of trying to work within Universal
Domain rules: UD requires ballots that are permutations of the candidates,
so if we identify voters with their ballots, voters are distributed on
spheres. But issue spaces are products of line segments, like rectangles,
blocks, etc.
If there are two issues, then issue space is a rectangle. If there are
four candidates, then ballot space is a two dimensional sphere, so
according to UD rules, that only allow voter influence through their ballot
rankings, there is a topological mismatch of voter/ballot space and issue
space.
For example, the Borsuk-Ulam theorem shows that any continuous map from an
n-sphere into a rectangle (or any other lower dimensional product of
intervals) must have a pair of polar opposite points that get mapped to the
same point; i.e. this requires that two polar opposite rankings correspond
to the exact same point in issue space.
That's one reason I take Universal Domain rules with a grain of salt, and
feel free to supplement rankings with ratings, approval cutoffs, etc.
I know that's not any help with your main question, but it may give some
insight into Durand's spherical distribution suggestion.
I'll try to give a practical suggestion next time!
El vie., 21 de ene. de 2022 7:02 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
My minimum-manipulability optimization system can find exact
probabilities that a voter will vote according to a particular ranking,
under impartial culture.
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
One benefit of the spatial model over impartial culture is that it's
much more clear how one may assign utilities to each ranking, so the
optimization system could also be used to investigate tradeoffs between
VSE and manipulability. (Durand suggested sampling on a sphere for
associating utilities with impartial culture, but I haven't read the
suggestion in detail. https://arxiv.org/pdf/1511.01303.pdf)
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
Election-Methods mailing list - see https://electorama.com/em for list
info
On Fri, Jan 21, 2022 at 9:02 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
I have been thinking about this. I don't have a clever solution for you,
but I have some thoughts that could be a stepping stone toward a solution.
What you are trying to do is compute an integral in a highly dimensional
space. Let's say that for a given set of candidates you have a function f()
that outputs a real value. That might be a utility, or a probability, or
whatever. I just want it to be a real number and not binary so that we can
hope that f() is smooth in the space spanned by the candidates.
The set of candidates can be thought of as a point in a C*D dimensional
space where C is the number of candidates and D is the dimension of your
D-cube. So you have a vector:
x_jk = position of candidate j on issue k
x = [ x11, x12, ... , x1N, x21, ... , xCD ]
When you ask:
"Do you know of any calculus tricks to get the probabilities over every
possible candidate position, or is this simply too hairy?"
You are asking, "how do I integrate f()"? Your default plan of drawing
random candidates and computing f() for each is integration by Monte Carlo
sampling. Now, I don't know how to integrate f() analytically, but
realizing that it is an integral allows us to consider other forms of
numerical integration (hence my request that f() be a smooth function). One
such example is Laplace's method:
https://en.wikipedia.org/wiki/Laplace%27s_method
Let us imagine that f() looks like a hill. If you can compute the gradient
of f(), you can climb the hill and get to the peak. Up there, if you can
compute the Hessian of f(), you can approximate f() with the Gaussian
function with the same height and Hessian. This method is approximate, but
it is very fast because you do not have to sample across the entire space.
Laplace's method is often used in highly dimensional problems, where the
cost of random sampling is prohibitive.
How do you compute the derivative and Hessian? Most often this is used with
an Autodiff package. Alternatively, you can use finite differences but at
the cost of reduced accuracy. What if f() isn't one hill but many? You can
integrate each hill separately and add them up.
Anyway, I don't know whether Laplace's method is a realistic solution, but
if it isn't, perhaps there is a different form of numerical integration
tool that is available to you that is more efficient than Monte Carlo
integration. For example, importance sampling doesn't require derivatives.
There is a long list of numerical integrators that have been devised over
the ages.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
This reminds me of the n-body problem. For n not too large, the
Parker-Sochaski method is the best numerical solution technique that I know
of so far.
But for many years they have been using statistical mechanics in the many
body problem ... from n=3 on up to n =infinity ... thermodynamics,
magneto-fluid dynamics, etc.
Those guys know how to do it.
When I did minuteman missile simulations back in the early1970's we had a
Spherical Harmonics gravitational model with hundreds of terms, which was
necessary to get a ballistic missile to within a few feet of an enemy
missile silo half way around the world.
The guys that came up with it used data from satellite tracking
observations to get a spherical harmonics mass density model of the earth.
Once they had that, it was a simple matter to express the gravitational
potential in spherical coordinates, and from that, gravitational force via
the gradient of the potential.
We need spherical harmonics expansions of the voter density function on the
surface of a sphere of the right dimension.
Now, I know why the suggestion of a spherical distribution ... you can have
a uniform probability density on a compact manifold like a sphere or a
cartesian product of circles, but not for an open manifold like an entire
plane .. for that, the best (closest to smooth & uniform) you can do is a
Gaussian.
[Somebody should start doing sphericalYee diagrams.]
We need to get one of those geodesical scientists from the 1970's who
solved this problem without super computers ... they could tell us how to
do it ... just like the astronomers of the nineteenth century could use the
"method of orbital elements", a clever perturbation technique to do all of
the numerical integration of all the high precision n-body celestial
mechanics problems of the solar system (planets, moons, comets asteroids,
etc) ... with nothing beyond mechanical adding machines and tables of trig
and log functions.
El dom., 23 de ene. de 2022 12:26 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Fri, Jan 21, 2022 at 9:02 AM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
I have been thinking about this. I don't have a clever solution for you,
but I have some thoughts that could be a stepping stone toward a solution.
What you are trying to do is compute an integral in a highly dimensional
space. Let's say that for a given set of candidates you have a function f()
that outputs a real value. That might be a utility, or a probability, or
whatever. I just want it to be a real number and not binary so that we can
hope that f() is smooth in the space spanned by the candidates.
The set of candidates can be thought of as a point in a C*D dimensional
space where C is the number of candidates and D is the dimension of your
D-cube. So you have a vector:
x_jk = position of candidate j on issue k
x = [ x11, x12, ... , x1N, x21, ... , xCD ]
When you ask:
"Do you know of any calculus tricks to get the probabilities over every
possible candidate position, or is this simply too hairy?"
You are asking, "how do I integrate f()"? Your default plan of drawing
random candidates and computing f() for each is integration by Monte Carlo
sampling. Now, I don't know how to integrate f() analytically, but
realizing that it is an integral allows us to consider other forms of
numerical integration (hence my request that f() be a smooth function). One
such example is Laplace's method:
https://en.wikipedia.org/wiki/Laplace%27s_method
Let us imagine that f() looks like a hill. If you can compute the gradient
of f(), you can climb the hill and get to the peak. Up there, if you can
compute the Hessian of f(), you can approximate f() with the Gaussian
function with the same height and Hessian. This method is approximate, but
it is very fast because you do not have to sample across the entire space.
Laplace's method is often used in highly dimensional problems, where the
cost of random sampling is prohibitive.
How do you compute the derivative and Hessian? Most often this is used
with an Autodiff package. Alternatively, you can use finite differences but
at the cost of reduced accuracy. What if f() isn't one hill but many? You
can integrate each hill separately and add them up.
Anyway, I don't know whether Laplace's method is a realistic solution, but
if it isn't, perhaps there is a different form of numerical integration
tool that is available to you that is more efficient than Monte Carlo
integration. For example, importance sampling doesn't require derivatives.
There is a long list of numerical integrators that have been devised over
the ages.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list
info
Hi Forest,
To digress from the topic a bit, there is an O(N) method for N-body
problems which has been around since the 1980s. It is called the Fast
Multiple Method.
The essence of the method is that the effect of a group of objects can be
approximated (outside a certain radius) as the effect of a single composite
object. These composite objects can further be combined into larger scale
composite objects. This is similar to Isaac Newton's approximation of
gravitational effect being due to a point mass.
If you just stop there, this reduces the order of operations to O(N logN).
That first stage of approximation is the effect of collections of masses on
everything else in the Universe. N-body simulations using this idea are
called Barnes-Hut methods.
The key to FMM is that you can do the same thing in the other direction,
finding the effect of everything outside a given radius on the objects
inside. That can also be described as a composite object -- a multipole.
Then there is a similar set of outer-inner nested collections to convey
information from the rest of the Universe to each individual particle.
This brings the number of operations to O(N).
https://en.wikipedia.org/wiki/Fast_multipole_method
On Sun, Jan 23, 2022 at 3:06 PM Forest Simmons forest.simmons21@gmail.com
wrote:
This reminds me of the n-body problem. For n not too large, the
Parker-Sochaski method is the best numerical solution technique that I know
of so far.
But for many years they have been using statistical mechanics in the many
body problem ... from n=3 on up to n =infinity ... thermodynamics,
magneto-fluid dynamics, etc.
Those guys know how to do it.
When I did minuteman missile simulations back in the early1970's we had a
Spherical Harmonics gravitational model with hundreds of terms, which was
necessary to get a ballistic missile to within a few feet of an enemy
missile silo half way around the world.
The guys that came up with it used data from satellite tracking
observations to get a spherical harmonics mass density model of the earth.
Once they had that, it was a simple matter to express the gravitational
potential in spherical coordinates, and from that, gravitational force via
the gradient of the potential.
We need spherical harmonics expansions of the voter density function on
the surface of a sphere of the right dimension.
Now, I know why the suggestion of a spherical distribution ... you can
have a uniform probability density on a compact manifold like a sphere or a
cartesian product of circles, but not for an open manifold like an entire
plane .. for that, the best (closest to smooth & uniform) you can do is a
Gaussian.
[Somebody should start doing sphericalYee diagrams.]
We need to get one of those geodesical scientists from the 1970's who
solved this problem without super computers ... they could tell us how to
do it ... just like the astronomers of the nineteenth century could use the
"method of orbital elements", a clever perturbation technique to do all of
the numerical integration of all the high precision n-body celestial
mechanics problems of the solar system (planets, moons, comets asteroids,
etc) ... with nothing beyond mechanical adding machines and tables of trig
and log functions.
El dom., 23 de ene. de 2022 12:26 p. m., Daniel Carrera <
dcarrera@gmail.com> escribió:
On Fri, Jan 21, 2022 at 9:02 AM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:
It's easy to approximately find such probabilities for spatial models as
well by just creating an instance and randomly placing voters on it to
determine what they vote, and hence in the limit of number of trials
going to infinity, get the probability.
But I was wondering, is it possible to do so exactly? Let's say that in
a spatial model, first c candidates are placed uniformly at random in an
unit d-cube. Then voters are also placed uniformly at random in this
cube and they prefer candidates closer to them to candidates further
away.
Now I would suppose that the probability that a voter votes A first is
equal to the volume of the Voronoi cell that belongs to A. (And the
probability that a voter will vote A>B>C is the volume of the
intersection of the closest-neighbor Voronoi cell for A with the
second-closest-neighbor for B and the third-closest-neighbor for C.)
Well, that eliminates one source of randomness -- assuming I can exactly
calculate the vertices of these regions. But there's still the second
source in the randomness of the candidates. Do you know of any calculus
tricks to get the probabilities over every possible candidate position,
or is this simply too hairy?
I have been thinking about this. I don't have a clever solution for you,
but I have some thoughts that could be a stepping stone toward a solution.
What you are trying to do is compute an integral in a highly dimensional
space. Let's say that for a given set of candidates you have a function f()
that outputs a real value. That might be a utility, or a probability, or
whatever. I just want it to be a real number and not binary so that we can
hope that f() is smooth in the space spanned by the candidates.
The set of candidates can be thought of as a point in a C*D dimensional
space where C is the number of candidates and D is the dimension of your
D-cube. So you have a vector:
x_jk = position of candidate j on issue k
x = [ x11, x12, ... , x1N, x21, ... , xCD ]
When you ask:
"Do you know of any calculus tricks to get the probabilities over every
possible candidate position, or is this simply too hairy?"
You are asking, "how do I integrate f()"? Your default plan of drawing
random candidates and computing f() for each is integration by Monte Carlo
sampling. Now, I don't know how to integrate f() analytically, but
realizing that it is an integral allows us to consider other forms of
numerical integration (hence my request that f() be a smooth function). One
such example is Laplace's method:
https://en.wikipedia.org/wiki/Laplace%27s_method
Let us imagine that f() looks like a hill. If you can compute the
gradient of f(), you can climb the hill and get to the peak. Up there, if
you can compute the Hessian of f(), you can approximate f() with the
Gaussian function with the same height and Hessian. This method is
approximate, but it is very fast because you do not have to sample across
the entire space. Laplace's method is often used in highly dimensional
problems, where the cost of random sampling is prohibitive.
How do you compute the derivative and Hessian? Most often this is used
with an Autodiff package. Alternatively, you can use finite differences but
at the cost of reduced accuracy. What if f() isn't one hill but many? You
can integrate each hill separately and add them up.
Anyway, I don't know whether Laplace's method is a realistic solution,
but if it isn't, perhaps there is a different form of numerical integration
tool that is available to you that is more efficient than Monte Carlo
integration. For example, importance sampling doesn't require derivatives.
There is a long list of numerical integrators that have been devised over
the ages.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list
info
Election-Methods mailing list - see https://electorama.com/em for list
info
On Mon, Jan 24, 2022 at 4:46 PM Ted Stern dodecatheon@gmail.com wrote:
Hi Forest,
To digress from the topic a bit, there is an O(N) method for N-body
problems which has been around since the 1980s. It is called the Fast
Multiple Method.
The essence of the method is that the effect of a group of objects can be
approximated (outside a certain radius) as the effect of a single composite
object. These composite objects can further be combined into larger scale
composite objects. This is similar to Isaac Newton's approximation of
gravitational effect being due to a point mass.
Not too similar though. Planets and stars are really well approximated by
spheres, and the Shell theorem tells you that the gravitational field from
a sphere is exactly identical to that of a point mass. The quadrupole
moments for a planet are not usually relevant except for problems that
require extremely high precision (most notably, studies of Saturnian
moons). Tree codes and the Shell theorem are more or less at opposite ends
in terms of levels of approximation. You wouldn't use a tree code for the
solar system, for example.
If you just stop there, this reduces the order of operations to O(N logN).
That first stage of approximation is the effect of collections of masses on
everything else in the Universe. N-body simulations using this idea are
called Barnes-Hut methods.
The key to FMM is that you can do the same thing in the other direction,
finding the effect of everything outside a given radius on the objects
inside. That can also be described as a composite object -- a multipole.
Then there is a similar set of outer-inner nested collections to convey
information from the rest of the Universe to each individual particle.
This brings the number of operations to O(N).
Fun fact, FMM only entered astronomy relatively recently, while it has been
dominant in particle physics for a very long time. The difference is that
the FMM methods from condensed physics are only faster than BH trees if the
N-body system is largely homogeneous. That's great for condensed matter
physics, but in astronomy we have ridiculously hierarchical systems and the
FMM that you'll find if you do a Google search will work poorly in
astronomy. It was only 8 years ago that someone developed a FMM that beats
BH for hierarchical systems (Dehnen 2014).
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Cool, thanks! I'll look up Dehnen.
I was in grad school when Greengard and Rokhlin was first published. It was
a big deal at the time in the applied math world. I knew the astro
community was continuing to use BH, but didn't know why.
On Mon, Jan 24, 2022 at 3:19 PM Daniel Carrera dcarrera@gmail.com wrote:
On Mon, Jan 24, 2022 at 4:46 PM Ted Stern dodecatheon@gmail.com wrote:
Hi Forest,
To digress from the topic a bit, there is an O(N) method for N-body
problems which has been around since the 1980s. It is called the Fast
Multiple Method.
The essence of the method is that the effect of a group of objects can be
approximated (outside a certain radius) as the effect of a single composite
object. These composite objects can further be combined into larger scale
composite objects. This is similar to Isaac Newton's approximation of
gravitational effect being due to a point mass.
Not too similar though. Planets and stars are really well approximated by
spheres, and the Shell theorem tells you that the gravitational field from
a sphere is exactly identical to that of a point mass. The quadrupole
moments for a planet are not usually relevant except for problems that
require extremely high precision (most notably, studies of Saturnian
moons). Tree codes and the Shell theorem are more or less at opposite ends
in terms of levels of approximation. You wouldn't use a tree code for the
solar system, for example.
If you just stop there, this reduces the order of operations to O(N
logN). That first stage of approximation is the effect of collections of
masses on everything else in the Universe. N-body simulations using this
idea are called Barnes-Hut methods.
The key to FMM is that you can do the same thing in the other direction,
finding the effect of everything outside a given radius on the objects
inside. That can also be described as a composite object -- a multipole.
Then there is a similar set of outer-inner nested collections to convey
information from the rest of the Universe to each individual particle.
This brings the number of operations to O(N).
Fun fact, FMM only entered astronomy relatively recently, while it has
been dominant in particle physics for a very long time. The difference is
that the FMM methods from condensed physics are only faster than BH trees
if the N-body system is largely homogeneous. That's great for condensed
matter physics, but in astronomy we have ridiculously hierarchical systems
and the FMM that you'll find if you do a Google search will work poorly in
astronomy. It was only 8 years ago that someone developed a FMM that beats
BH for hierarchical systems (Dehnen 2014).
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Thanks Ted and Daniel. Very interesting!
In the early 70's we did our minuteman missile simulations on a room size
mainframe IBM 360/65 computer with FORTRAN code, double precision
arithmetic ... punched cards interface.... and all. We got one turnaround
per night.... night because the Top Secret runs had to be totally isolated
from the daytime use of the computer. In 1974 our group got ahold of a
couple of the mini-computers that were just coming out ... TTY "ticker
tape" interface at first then (unreliable, but more convenient) floppy
discs. Very slow, single precision, but interactive BASIC for the spine of
the simulation. We employed pseudo-double precision for the numerical
integration, and modified BASIC so we could call on assembled bottle-neck
subroutines, etc.
The Top Secret, computationally high cost, high precision, spherical
harmonics gravity model "GRAV 74" (mylar tape in a secure safe) became the
main bottle- neck. Our project leader came up with the idea that cut the
run time from several hours to real time; our simulation had to be a
complete virtual reality operation with real time speed in order to fool
the D37 guidance and control computer that had been extracted from a MM2
missile to test the target tapes.
The idea was this ... start with a quick (fraction of a second)
approximate trajectory, and in another fraction of a second, fit a simpler
model "GRAVCHICO" to the precise GRAV 74 values at half a dozen points near
the approximate trajectory. So near that approximate trajectory GRAVCHICO
was accurate to seven significant figures. Then we transformed the
spherical coordinates to the Kustanheimo coordinates from Stiefel and
Scheifele's 1971 book, Linear and Regular Celestial Mechanics.
After that our simulation on the little dedicated, stand alone minicomputer
(32K bytes) system was good for real time use ... no trouble keeping up
with the D37 guidance and control computer.
Now here are some thoughts on our current problem. We need an
"electo-potential" scalar function V defined at every point in voter space,
such that the (opposite of) grad V gives rise to a force field that points
towards the (generalized) median voter.
It seems to me that a point partical located at point p0, should contribute
an amount ||p-p0||=distance(p, p0) to the potential V(p) at point p.
A test particle at p would experience a force of (p0-p)/||p0-p||, a force
of unit magnitude towards p0.
If the particles (voters) are distributed according to some probability
density P, and dP(r) is the probability in an infinitesimal volume centered
at r, then a test particle at p will experience a force of
F=Integral(over r)of (r-p)/|r-p|||dP(r)
or something like that.
Visualize the potential function V as a mountain range. The force field F
is represented by tiny arrows pointing in the direction of steepest descent
to (wet or dry) lake bottoms, local minima of V.
If there is only one drainage basin, the global minimum is the sink of that
basin, and is the generalized median of the probability distribution.
To find a local minimum start at a random point p0 and evolve the initial
value problem dp/dt=-gradV until two consecutive points in the numerical
solution are within some preset tolerance.
Which points would make good starting points?
How about the vertices of each of the Voronoi cells centered on the
candidate positions?
What do we do with the local minima?
For each of them, calculate the candidate preference order. Those will be
the stable orders that the voters of the respective drainage systems
gravitate towards.
How do we find the total probability of each drainage system?
Go back and find which Voronoi vertices end up in which sinks. If
necessary, triangulate the Voronoi cells with progressively finer mesh, and
continue following vertices to sinks.
I hope this stimulates some ideas.
We have all of the tools of force fields and numerical solutions of ODE's
at our disposal!
-Forest
El lun., 24 de ene. de 2022 3:19 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Mon, Jan 24, 2022 at 4:46 PM Ted Stern dodecatheon@gmail.com wrote:
Hi Forest,
To digress from the topic a bit, there is an O(N) method for N-body
problems which has been around since the 1980s. It is called the Fast
Multiple Method.
The essence of the method is that the effect of a group of objects can be
approximated (outside a certain radius) as the effect of a single composite
object. These composite objects can further be combined into larger scale
composite objects. This is similar to Isaac Newton's approximation of
gravitational effect being due to a point mass.
Not too similar though. Planets and stars are really well approximated by
spheres, and the Shell theorem tells you that the gravitational field from
a sphere is exactly identical to that of a point mass. The quadrupole
moments for a planet are not usually relevant except for problems that
require extremely high precision (most notably, studies of Saturnian
moons). Tree codes and the Shell theorem are more or less at opposite ends
in terms of levels of approximation. You wouldn't use a tree code for the
solar system, for example.
If you just stop there, this reduces the order of operations to O(N
logN). That first stage of approximation is the effect of collections of
masses on everything else in the Universe. N-body simulations using this
idea are called Barnes-Hut methods.
The key to FMM is that you can do the same thing in the other direction,
finding the effect of everything outside a given radius on the objects
inside. That can also be described as a composite object -- a multipole.
Then there is a similar set of outer-inner nested collections to convey
information from the rest of the Universe to each individual particle.
This brings the number of operations to O(N).
Fun fact, FMM only entered astronomy relatively recently, while it has
been dominant in particle physics for a very long time. The difference is
that the FMM methods from condensed physics are only faster than BH trees
if the N-body system is largely homogeneous. That's great for condensed
matter physics, but in astronomy we have ridiculously hierarchical systems
and the FMM that you'll find if you do a Google search will work poorly in
astronomy. It was only 8 years ago that someone developed a FMM that beats
BH for hierarchical systems (Dehnen 2014).
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University