[EM] Yee Diagrams for Bucklin Voting

[Kristofer Munsterhjelm]

Leon Smith wrote:
> Ka-Ping Yee's code has weaknesses,  but it is straightforward.
> Sadly,  it only supports 4 candidates.  I implemented 4-candidate
> Bucklin ranked 1 through 4.    Honestly I'd rewrite the whole thing,
> but this was a quick and easy way to see how Bucklin behaves.   I
> included the four scenarios that Yee has on his page in the zip file I
> sent,  although with 20,000 voters and not 200,000.
> 
> Out of curiosity,  has anybody contemplated algorithmic improvements
> for generating Yee diagrams more quickly?   For example,  moving the
> distribution a small delta would typically change the votes of a small
> number of voters,   so it should be worthwhile to intelligently update
> votes and totals.   Although I imagine this kind of improvement would
> benefit some methods  (such as Condorcet and Bucklin) moreso than
> others,  (such as IRV).

For ranked methods, see my post, "High precision Yee diagrams". I think 
that it might be possible to do the same for certain types of rated 
methods, but that would involve complex mathematics. In essence, one 
would find the "center of mass" for each region (taking into account the 
Gaussian density within the region) and calculate the rating at that 
point, which would be the mean rating.

Another option, but only for methods that pass monotonicity, is to 
travel along the edge. If a method passes monotonicity, all regions are 
connected. The method would have to have a way of signaling whether the 
result was due to a tiebreaker or not, however, because the strategy 
doesn't work where there are ties (since those can go either way).

To "travel along the edge", you would start with a pixel, then calculate 
it and its neighbors. Go to a pixel that borders a pixel of a different 
color and do the same. In that way, you'd trace the edge (clockwise or 
counterclockwise depending on the method) of the region, and you could 
simply flood-fill afterwards.

If you have a criterion compliance structure, you could automatically 
return the Voronoi diagram for methods that pass Condorcet. The Voronoi 
diagram can be calculated in n log n time for n candidates, although the 
algorithm to do so is a bit tricky. Note that this wouldn't be the case 
for arbitrary distributions; if the distribution isn't 
centrosymmetrical, Condorcet may not give the Voronoi diagram.

Going further with that idea, you could calculate regions that any 
method passing, say, Majority, must have. The majority test would return 
a candidate if that candidate is ranked above top by a majority of the 
voters, otherwise -1 (for uncertain). Then, when drawing an individual 
method's Yee diagram, if that method passes Majority, you already know 
which candidate wins for certain pixels of the regions. This speedup 
would only be advantageous if you're calculating the Yee diagrams for 
many methods at once, however.

Drawing a single Yee diagram should also be extremely easy to make 
parallel. If you have a quad-core CPU, spawn off four threads and have 
them check a fourth of the pixels each. If you're drawing many at once, 
it would be slightly faster to do "per method" parallel (same pixel 
checked with many methods) instead of "per pixel" parallel, since in the 
former case, you'd have to calculate the ballots for that pixel only once.

If you want to get very clever, the extreme parallel nature of Yee 
diagrams would make it amenable to GPGPU acceleration. I have no idea 
how to actually do that, though.

You could also draw the Gaussian separately in something like a quadtree 
(only once). Then, to get the ranks, you simply intersect the Gaussian 
(centered on the pixel) with the region in question. This would be like 
my "high precision Yee diagrams" idea, only without explicit integration.

Finally, although that would be extremely hard, you could take sampling 
to its conclusion. Have all comparison operators within the method check 
how sure one can be that x (some value derived from the sampling) is 
greater than y. If the confidence is below a certain value, sample 
further. Thus you'd start with a very small sample and only increase the 
sample where it's actually needed, so you wouldn't waste time sampling a 
lot of voters where a few would be required.