[EM] Theorems about Yee/Bolson pictures

[Warren Smith]

Theorems about Yee/Bolson pictures
Well, I wrote about 20 emails to Ka-Ping Yee and he hasn't responded...

so anyway, let me here say a few of the things I said to him.
(I made a web page with combined Yee+WDS thoughts on it, but that web page is currently secret
since KPY has not yet given approval to release.)


* In any #dimensions (Yee used 2 for pictorial purposes),
* with any centro-symmetric probability density in place of Yee's Gaussian
  to govern the voter distribution about a pixel
* In the limit of large #voters (to avoid issues of "random noise")
* with any utility function that is a decreasing function of distance to the candidate:
THEOREM:
For any Condorcet voting method, and the the max-utility-sum "best" method,
the picture will be exactly the Voronoi diagram of the candidates.

THEOREM:
For Approval voting using an "oblivious randomized approval threshold"
[that is, the distance within which you approve, is chosen randomly from
any probability density whatever, as long as its support set is universal]
the picture will be exactly the Voronoi diagram of the candidates.

But this is false if the approval threshold instead is chosen
in some strategic ways (such as, mean utility).
And indeed this approval method
can yield win regions not containing their candidates,
[example 0, 3, 4 = locations of 3 candidates on line, utility=-distance].

THEOREM:
For Approval or Range with strategic voters using an approval threshold chosen strategically
using the method in   http://rangevoting.org/AppCW.html
the honest-voter Condorcet winner wins so we get the Voronoi diagram.

THEOREM:
Range voting with honest (renormalizing best=max, worst=min) voters,
we will in general NOT get the Voronoi diagram, but
if we can assume that wherever you are,
there is always some "bad guy" candidate very far away,
then we WILL get the Voronoi diagram.

THEOREM:
Condorcet voting with strategic voters who strategically rank the two "most likely to win"
candidates top & bottom, will NOT yield the Voronoi diagram.

DISPROOF OF CONJECTURES:
* Here we use 2-dimensions and Yee's gaussian:
Yee had conjectured monotonic voting methods ==> convex winning regions.
Yee then conjectured (more weakly) monotonic voting methods ==> star-shaped winning regions.
We could conjecture even more weakly that win-regions would be connected,
or would contain their candidates.
All of these conjectures are false - I have counterexamples.

Warren D Smith
http://rangevoting.org