[EM] Voronoi diagrams & convolutions
Warren Smith
wds at math.temple.edu
Wed Dec 27 14:08:14 PST 2006
Sorry, I screwed up last post slightly.
Will correct that here.
Here are some properties that
continuous functions and probability densities in D-dimensional
space may or may not have:
CS: centrosymmetric: F(C+x) = F(C-x) where C is the centerpoint D-vector and
x is an arbitrary D-vector.
[Example: elliptical Gaussian density with elliptical hole, both same center,
the two ellipses need not be related.]
SS: spherically symmetric: F(x)=F(|x|).
RD: radially decreasing: along rays from the centerpoint, F(x) decreases.
CD: concave-down.
PR: probability density [integral is 1, and non-negative].
Now here is what results when you convolve a function with property set I,
with another function with property set II:
(I)&(II) = (III):
CS & SS = CS
CS & CS = CS
(PR, CS, RD) & (SS, RD) = (CS, RD)
PR & PR = PR
PR & CD = CD
(PR, CS) & (SS, CD) = (CS, CD, RD)
(PR, CS) & (CS, CD) = (CS, CD, RD)
SS & SS = SS
(There are probably some more interesting claims of the above nature, too.)
Now CLAIM:
If the voters & candidates are points in a D-dimensional space,
and the voters are distributed according to a probability density RHO,
and their utilities for candidates depend only on distance to the candidate
according to some function UTIL(distance),
THEN IF the convolution of the UTIL and RHO functions obeys
the properties (CS, RD) then in the large#voters limit
the Yee-like picture for any Condorcet method
will (almost surely) be the Voronoi diagram,
and there will be no cycles and there will be a
transitive social ordering almost
everywhere, and the Condorcet winner will just
be the closest candidate to RHO's centerpoint.
This claim evidently holds in a fairly wide class of circumstances.
wds
More information about the Election-Methods
mailing list