In my previous post I wrote about resampling the results of voting systems. I defined a function \(S(n)\) which was the probability of the result changing when you sampled N voters from the population with replacement.
One of the questions I asked was what happens as \(N \to \infty\). I now have a partial answer to that.
This solution only addresses voting systems where you can get the answer by looking at the proportions of votes. Such voting systems can be regarded as functions
\[ \nu : \mathbb{P}(V) \to \mathbb{P}(C) \]
Where \(\mathbb{P}(X)\) is the set of probability distributions on \(X\), \(V\) is the set of possible votes and \(C\) is the set of possible candidates.
I’m pretty sure most conventional voting systems can be viewed in this way, or can be modified to be viewed this way. My only slight concern is that most of them are concerned with integer tallies. However I think they mostly have scaling properties that mean they can be viewed this way anyway (I haven’t checked this properly and I’m pre-coffee at time of writing this post, so this may be an obviously stupid belief).
At the very least however my two examples in the previous post can definitely be viewed this way: First past the post is the function that takes the highest element and produces a probability distribution that returns that with probability 1 (it needs a tie breaking rule. A reasonable one might be a uniform distribution across the highest values). Random ballot we have \(V = C\) and the function is just the identity function. Picking a random Condorcet winner and alternative vote can both be converted with only slightly more effort, so I think there’s at least a reasonably large subset of voting systems which can adopt this formalism.
Anyway, this formalism done, we can answer the question for most such voting systems about what the limiting behaviour of \(S(n)\) is:
Given a voting system \(\nu\) and a point \(x \in \mathbb{P}(V)\), if \(\nu\) is continuous (when regarding \(\mathbb{P}(V)\) as a subset of \(\mathbb{R}^{|V|}\)) at \(x\) (the original distribution of votes in our population) then \(S(n) \to \sum_{c \in C} \nu(x)(c)^2 \), the probability that running the election twice will produce the same result.
Why? Well, basically because by continuity we can find a neighbourhood of \(x\) which makes the distribution of running the voting system on anything in that neighbourhood arbitrarily close to the distribution of \(\nu(x)\). We can then make \(n\) sufficiently arbitrarily large that by the law of large numbers the distribution of the population is going to be within that neighbourhood with probability arbitrarily close to 1. So we can make the distribution of the vote outcomes arbitrarily close to the distribution of the original outcome by making \(n\) large enough, and hence the result follows.
When is this continuity assumption satisfied?
Well, deterministic voting systems are never continuous for all \(x\). Why? Topology! The input space is a connected set, the output space is a discrete set (it’s the set of vectors which have one coordinate set to 1 and all others set to 0). However most of them are continuous away from the boundaries I think – that is, if you’ve not had to invoke some tie breaker mechanism you’re probably continuous at that point (I saw some good visualisations of this a while ago but I can’t find them right now). First past the post in particular is continuous if you don’t have a tie.
Anyway, given this result, I’m largely satisfied as to what the large \(n\) behaviour of \(S(n)\) is.
I’m still interested in the small \(N\) question. I think it’s fairly clear that \(S(1)\) may be quite far from 1 indeed. For example in alternative vote, \(S(1)\) will give you the probability of having the highest number of first votes and will completely ignore the crucial secondary and higher votes. I suspect \(S(3)\) is an interesting number, as it’s the first point at which you can have interesting majority behaviours starting to take effect.