[EM] Exact spatial model probabilities?

[Kristofer Munsterhjelm]

On 27.01.2022 08:12, Daniel Carrera wrote:
> 
> 
> On Wed, Jan 26, 2022 at 6:53 AM Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
> 
>>     So when figuring out the proportion who'd vote A>B>C in the continuous
>>     (V->infty) case, you could first create a Voronoi map for all the
>>     candidates. The volume of this region gives you how many voters would
>>     vote A first. Then you'd take the region for A and calculate the Voronoi
>>     map within it for every candidate but A excluded. The subregion that's
>>     now closest to B gives you the number of voters who vote A>B>...;
>>     and so on.
> 
> You've convinced me that there's a lot of value in doing the exact
> geometric solution. I would be interested to see simulations with very
> large numbers of voters. Real elections can have 10^7 voters. I haven't
> figured out how to compute the volume of a Voronoi cell, but I did have
> a thought: What if we simplify the problem by reducing the number of
> candidates and issues?
> 
> For real elections, we don't really care about an arbitrary number of
> characters or an arbitrary number of issues. Political views are often
> described in just a two-dimensional space, with one "economic" axis
> (left <-> right) and one "social" axis (libertarian <-> authoritarian).
> That alone is enough to describe most of politics. The number of parties
> can be larger, but honestly, the countries that have >3 prominent
> parties are few and they probably use PR anyway. If all we do is find
> exact solutions for 3 parties (e.g. two major parties and a challenger)
> or 4 parties (e.g. two major parties + Green + Libertarian) and a
> 2-dimensional issue space, that would be a very relevant case that would
> tell us a lot about the real world elections we care about.
> 
> Finding the area of a Voronoi cell in a 2D space with just 3-4 cells
> doesn't sound difficult. I haven't done the math, but it feels like high
> school math problem.

It isn't very difficult. Fortune's algorithm can get the cells in O(c
log c) time, and then you can find the area of each (given its vertices)
by sorting the vertices in a particular order, in O(v log v) time. IIRC,
the number of vertices of a 2d Voronoi cell is bounded, so that is in
essence constant time.

A side note: I seem to recall that Patterns of Democracy (by Lijphart)
says that as a reasonable approximation, the number of dimensions in a
country's political realm is the number of effective parties, plus one.
(And anecdotally there definitely seems to be more than one dimension to
politics here.)

So if a good single-winner method can support multiparty democracy by
itself, then higher dimensions may be relevant eventually. Still, any
two-party system that's evolving to a higher party system will pass
through lower dimensionality spaces before getting to higher ones as
parties find out if it's safe to split and specialize.

(There's some evidence that single-member districts can support more
than two parties, e.g. the use of top two runoff in France.)

>>     However, that doesn't solve the integral. My idea was to get the (as
>>     close to exact as possible) probability that some random chosen voter
>>     will vote A>B>C. Say that this is p(A>B>C).
> 
>>     Since the voters are independent, this then gives a probability that
>>     some random election of V voters will be of a particular type; e.g. you
>>     can figure out the probability that a three-candidate election will be
>>     e_s = (A>B>C, A>B>C, B>C>A). Let the probability that we will encounter
>>     election e be p(e). Then the probability of the example election is just
>>     p(e_s) = p(A>B>C) * p(A>B>C) * p(B>C>A).
> 
> 
> 
> I'm a bit confused by the notation. If p(A>B>C) is the probability that
> a random voter picks A>B>C then what is p(A>B>C) * p(A>B>C) * p(B>C>A)?
> 
> I also don't get what you mean by "e_s = (A>B>C, A>B>C, B>C>A)" being an
> election.

The former is just a statement of statistical independence. Suppose that
we roll three ordinary dice, call them x, y, and z. Then the probability
of the result being all ones is p(x=1) * p(y=1) * p(z=1) due to
independence - the different outcomes don't constrain each other.

So in a similar way, if we let p(A>B>C) be the probability that a random
variable representing a given voter turns out to be A>B>C, then due to
statistical independence, the probability that the first voter votes
A>B>C, the second votes A>B>C, and the third votes B>C>A, is simply
p(A>B>C) * p(A>B>C) * p(B>C>A). And if the election is defined by this
particular voting pattern, then you have the probability that a randomly
chosen election will be this one.

e_s = (A>B>C, A>B>C, B>C>A) just means that the election e_s has these
ballots, in this order:

1: A>B>C
1: A>B>C
1: B>C>A.

(Again on a side note: since it doesn't matter in what order the voters
vote, you could save some computations by using a multinomial - e.g. if
you find out that method M is susceptible to manipulation with election
(x, y, z), you automatically know it's susceptible to manipulation with
election (x, z, y) too. But it would make the code more complex.)

-km