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

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.

That's exactly what it is HMC. We're driving on a rough road with lots of
potholes right now I will write more later

El mar., 25 de ene. de 2022 7:02 p. m., Daniel Carrera dcarrera@gmail.com
escribió:

On 26.01.2022 04:23, Forest Simmons wrote:

Right. I once wrote a fully differentiable genetic algorithm (I was
intending to use it for hyperparameter tuning). There were two problems.
First, local optima. Second, suppose that you have a plain statement like:

if (x>y) {
return z;
} else {
return f(z);
}

When smoothing, this turns into something like

return z * sig(x-y, k) + f(z) * sig(y-x, k)

where sig(x, k) is a sigmoid function that returns 1 if x>>0, 0 if x<<0,
and k is a steepness parameter controlling sig'(x) around 0.

If k is too high, then gradient descent fails because there's no
noticeable slope down to the optimum; it's flat almost everywhere and
then goes to zero exactly at the optimum (vanishing gradient problem).

So we need some smoothness, which means that both branch values come
into play. But this makes the function slow to evaluate as the program
must "go both ways" on every conditional.

This, I do agree with. There have been a lot of voting method proposals
lately, and we need some way to easily determine:

• what is its VSE (under what models)
• what is its voter-strategy susceptibility
• what is its candidate-strategy susceptibility (cloning)
• what criteria does it definitely fail

and it would be nice to also know what criteria it definitely passes,
though that requires formal verification, which is much harder than just
testing a bunch of cases.

(I remember using REDLOG to come up with BTV once, but I don't remember
the details. Perhaps I should look into the current state of the art for
provers, like Z3... so many things to do and so little time in which to
do them!)

-km

On 26.01.2022 00:10, Daniel Carrera wrote:

Yes, that's the one. My implementation is here:
https://github.com/kristomu/quadelect/tree/master/src/linear_model

I used it to sample pairs of elections where e.g. in the second
election, A is raised by one step (to check monotonicity failures), or A
is cloned (to check clone dependence). My idea at the time, I think, was
that sampling this constrained election space would cover all of that
space more quickly, so there would be a higher chance of getting a
failure example from a method that's e.g. only nonmonotone in some very
particular case.

That seems related to how you'd determine the Voronoi cells for a
continuous voter distribution. There's an algorithm to calculate a
Delaunay triangulation on c (number of candidates) points in R^d (number
of issues in issue space) in time O(c log c + c^floor(d/2)):
https://team.inria.fr/datashape/files/2017/01/alea.pdf p. 24. The
Delaunay triangulation is a dual of the Voronoi map, so I think
(although I'm not sure) that this means you can also get the latter in
the same time complexity.

So when figuring out the proportion who'd vote A>B>C in the continuous
(V->infty) case, you could first create a Voronoi map for all the
candidates. The volume of this region gives you how many voters would
vote A first. Then you'd take the region for A and calculate the Voronoi
map within it for every candidate but A excluded. The subregion that's
now closest to B gives you the number of voters who vote A>B>...; and so on.

For a finite number of voters, there's of course no need to deal with
continuous regions, just recursively partition the V voters. But in this
case, we can directly calculate the voters' rankings: a voter's ballot
is A>B>C if that voter is closest to A, next closest to B, and most
distant to C. This also takes V*C^2 time.

However, that doesn't solve the integral. My idea was to get the (as
close to exact as possible) probability that some random chosen voter
will vote A>B>C. Say that this is p(A>B>C).

Since the voters are independent, this then gives a probability that
some random election of V voters will be of a particular type; e.g. you
can figure out the probability that a three-candidate election will be
e_s = (A>B>C, A>B>C, B>C>A). Let the probability that we will encounter
election e be p(e). Then the probability of the example election is just
p(e_s) = p(A>B>C) * p(A>B>C) * p(B>C>A).

The exact manipulability of some method M is then

sum over all elections e of V voters: manip(M, e) * p(e)

where manip(M, e) is 1 if that election is manipulable, 0 otherwise.

If we set V finite before we calculate the probabilities p(A>B>C) etc.,
then I think the voters are no longer independent and the trick fails.
Either that or we get sampling error so that we could just as well just
directly infer what rank each voter votes.

The reason I'd like to get exact probabilities is that if I want to make
a method that minimizes manipulability for the spatial model, or
optimizes some linear combination of VSE and strategy resistance, then
I'd rather not want it to overfit. And if there's sampling noise, the
method is more likely to overfit.

Really, the fundamental problem is that I have no way to "regularize"
the manipulability optimization problem.

The most obvious measure of complexity is that the election method (for
a particular number of candidates and voters) is a union of convex
polytopes so that if an election falls inside this union, then A wins.
Then the more polytopes in that union, and the more vertices per
polytope, the more complex the method. (IRV would fare very poorly by
this metric.) But fitting a non-convex polytope (as the union would be)
to the smallest number of convex polytopes is NP-hard. So difficulty
abounds.

-km

El mié., 26 de ene. de 2022 3:12 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:

Here's a better way to get a smooth potential function V(x,y,z,) in the
present context:
First the potential V(x,y,z)for all voters concentrated at one point
(X,Y,Z):

V(r)=||r-R||, where r=(x,y,z) and R=(X,Y,Z).

To smooth, replace this with

V(r)=(epsilon+||r-R||^2)^(1/2)

This is more realistic anyway because you cannot truly have all voters
concentrated at one point. The epsilon smear factor would be a function of
the variance of the voters clustered around the point R.

That variance could be given exactly for a uniform distribution on a ball
of radius delta centered at R, for example.

Then for multiple factions...

V(r)=Sum(over R in Omega) of
f(R)*sqrt(epsilon(R)+||R-r||^.5),

where Omega is the set of faction centers, and f(R) is the fraction of
voters clustered near R, i.e. in a delta(R) [related to epsilon(R)]
neighborhood of R.

If we have a smooth (i.e. pre-smeared) pdf f(R), we can write the
"electo-potential" V(r) as an integral
V(r)=Integral(over R in Omega)of
||r-R||f(r)dxdydz

The hamiltonian for the wandering voter particle is the total energy,
kinetic + potential, E=T+V, where T =.5 ||dR/dt||^2.

The system (in vector form) of ODE's for the motion of the particle is

(d/dr)^2=-grad V(r)

I need to check the HMC link that Daniel gave me to see what notation they
are using.

Just one correction ****

El mié., 26 de ene. de 2022 10:02 a. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:

*** Should be
(d/dt)^2=-grad V(r)

I should probably give more of an explanation for the choice of the atomic
electo-potential, i.e. the scalar potential function V(r) for one voter
located at R:

V(r)=||r-R||

The force=-grad V(r) represents the influence of the voter pushing or
pulling in one direction or another. The true winner should be at a point
where the resultant force of the entire electorate is balanced at as close
to zero as possible.

So what is the force of one voter under this choice of potential V(r)?

It is -grad V(r) anchored at the voter position R.

-grad|r-R|||=-(r-R)/||r-R||, which is a unit vector pointing from r to R.

In other, words each voter exerts a pull of one dyne towards herself in the
tug of war to find the winning position.

One voter one vote translates to one voter one dyne. Each voter is allotted
the same amount of pull ... but different
voters pull in different directions. Sincere voters pull towards their own
location in in voter space.

If there exists a unique equilibrium point where all of the pulls balance,
that point is the geometric median of the voter distribution.

It is easy to see that in any distribution of voters along a straight line,
this balance occurs where r is at the ordinary median of the
didtribution,with half of the voters pulling with same strength in each
direction.

That's the heuristic for the choice of "electo-potential" ... one person,
one dyne of pull towards their own position.

El mié., 26 de ene. de 2022 10:23 a. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:

Now I want to point out how the HMC ergodic idea makes it simple,
efficient, and extremely precise to find the volume of each preference
order region:

Initialize an algebraic variable 'BallotProfile' with the value zero.

Then as you evolve numerically the wandering test point ODE,

(d/dt)^2 r= -grad V(r),

at each successive point r of the numerical solution, calculate all of the
distances from r to the respective candidate positions, and sort them to
find the ranked preference ballot for that position in the form of a
string, such as, "A>B=C>D". Before resuming the ODE evolution, add that
string into the variable 'BallotProfile', treating it as a variable name,
i.e.an algebraic monomial.

After a few billion steps, according to the ergodic theorem that applies to
this kind of energy conserving dynamical system, the 'BallotProfile'
collected over time along the trajectory of the wandering point r, will
also represent the spatial distribution of preference ballots.

Practical suggestions ... convert the second order vector differential
equations into a system of two first order vector ODE's ...

dr/dt=v,
dv/dt=-grad V(r)

Solve numerically using RK4 or even simple Euler's method ... after all
we're just using the path to sample the space. Try several initial
conditions ... nothing too far outside the support of the voter
distribution.

El mié., 26 de ene. de 2022 11:30 a. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:

Now that we have an efficient way (based on ergodicity) of estimating the
distribution of voter ballot rankings, based on the distribution of voters
and candidates, let's talk about how to find the 'correct' winner according
to "electo-potential" principles.

If some candidate R is positioned at a global minimum of V(r), ... i.e.

argmin V(r)=R,

then it will also be true that

||grad V(r)|| will vanish.

This suggests several possible ways to pick a winner when no candidate
resides at argmin V(r);

1. The candidate closest to argmin V(r).

2. The candidate argmin{V(k)|k is a candidate}.

3. The candidate argmin{||gradV of k||, k is a candidate}

Although (1) and (2) have obvious merit, I prefer (3), because the
magnitude of the gradient is an expression of the maximum force (over all
possible directions) trying to move k to a preferred position, i.e.
dissatisfaction tempting voters to connive and manipulate. In other words,
minimizing the magnitude of the gradient at the position of the winning
candidate will make that candidate more stable.

[This depends on the fact that the maximum directional derivative is the
magnitude of the gradient.]

El mié., 26 de ene. de 2022 8:18 p. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:

On Wed, Jan 26, 2022 at 6:53 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

You've convinced me that there's a lot of value in doing the exact
geometric solution. I would be interested to see simulations with very
large numbers of voters. Real elections can have 10^7 voters. I haven't
figured out how to compute the volume of a Voronoi cell, but I did have a
thought: What if we simplify the problem by reducing the number of
candidates and issues?

For real elections, we don't really care about an arbitrary number of
characters or an arbitrary number of issues. Political views are often
described in just a two-dimensional space, with one "economic" axis (left
<-> right) and one "social" axis (libertarian <-> authoritarian). That
alone is enough to describe most of politics. The number of parties can be
larger, but honestly, the countries that have >3 prominent parties are few
and they probably use PR anyway. If all we do is find exact solutions for 3
parties (e.g. two major parties and a challenger) or 4 parties (e.g. two
major parties + Green + Libertarian) and a 2-dimensional issue space, that
would be a very relevant case that would tell us a lot about the real world
elections we care about.

Finding the area of a Voronoi cell in a 2D space with just 3-4 cells
doesn't sound difficult. I haven't done the math, but it feels like high
school math problem.

However, that doesn't solve the integral. My idea was to get the (as

I'm a bit confused by the notation. If p(A>B>C) is the probability that a
random voter picks A>B>C then what is p(A>B>C) * p(A>B>C) * p(B>C>A)?

I also don't get what you mean by "e_s = (A>B>C, A>B>C, B>C>A)" being an
election.

Cheers,

Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University