[EM] Voronoi diagrams & convolutions

[David Cary]

A rather simple way to create Condorcet ambiguities in the Yee-BOlson
pictures is to use a distribution of voters that is a weighted
average, using unequal weights, of two Gaussian distributions with
different means.  Politically this represents a polarization of the
electorate along one of the dimensions.

This would work even if the two Gaussian distributions are each
spherically symmetric and/or have the same standard deviations.


--- Warren Smith <wds at math.temple.edu>, on Wed, 27 Dec 2006 17:08:14
-0500, wrote:
> 
> 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
> ----

When UTIL(distance) is spherically symmetric and radially decreasing,
being guaranteed a Condorcet winner, except for ties, is
characterized by the voter probability distribution's median envelop.
 In 2D, the median envelop is the curve whose tangent lines are
medians, i.e. the distribution has equal probabilities on each side. 
When the median envelop is degenerate to a point (all the median
lines intersect at a common point), the winner between any two
candidates is the one closest to that point.  Therefore, except for
ties, there will always be a Condorcet winner, which is the candidate
closest to that point, and the Yee-BOlson diagram is the Voronoi
diagram.

The equally weighted average of two spherically-symmetric Gaussian
distributions with different means and different standard deviations
has a median envelop that is degenerate to a point.  But it does not
meet the conditions of Warren's characterization, and so provides a
simple illustration that those conditions are sufficient, but not
necessary.

-- David Cary

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com