On Sat, Jan 22, 2011 at 5:44 PM, Kristofer Munsterhjelm <[email protected]> wrote: > This leaves the first step. At first glance, that seems to be prohibitive. > If we have n candidates, there are n! possible ways to rank them, and so one > would think that the combinatorial explosion would make the algorithm > completely impractical. I thought so, too, but it seems that dimensionality > significantly limits the explosion. For instance, if there are regions > belonging to candidates A, B, and C, so that the distance from a given point > in A to the closest point in C is always greater than the distance from that > point to the closest point in B, then there can be no "A > C > B" voters in > the A region (or at all, for that matter). > Though I think it's possible to contrive examples where the number of > distinct ballots grow superpolynomially with respect to the number of > candidates, I think such examples will be unlikely in practice. I have no > proof either way, though, but if any of you have, go ahead and mention it > :-)
In the 2-d case, the number of distinct ballots is, at most, O(n^4) in the number of candidates. Given any pair of candidates, a voter will rank one over the other based on which side of the perpendicular bisector of the line segment between those two candidates. There are m = n * (n-1) / 2 such lines, which will split the plane into (at most) m * (m + 1) / 2 + 1 regions in which every voter will vote the same. http://oeis.org/A000124 Of course, this is with the standard voter model that everybody seems to be using; the numbers will change if you allow voters to rank candidates equal when the distance from each candidate is sufficiently similar. Best, Leon ---- Election-Methods mailing list - see http://electorama.com/em for list info
