DRMacIver's Notebook

There are no deterministic voting systems

There are no deterministic voting systems

As many of you are aware, one of my weird niche fandoms is random ballot, which I initially proposed using for parliamentary democracy but am also keen on for deciding where to eat and many other decisions.

One of the objections that I often hear to it is that people don't like nondeterminism in their voting systems. Well, I have bad news for you: There are no deterministic voting systems. The question is not whether you have nondeterminism, the question is how sharp the transitions between regions where the probability of an outcome is nearly deterministic are.

Lets take an easy example: Suppose you have a vote between two options, and the population of voters is largeish, say a thousand people for convenience. You want to choose between these two with a simple majority. Suppose, despite that large population, you somehow manage to get an exact tie. \(500\) people vote for the bikeshed to be blue, \(500\) for it to be orange.

What you do in this circumstance is flip a coin, right? This is a time honoured tradition for resolving ties.

So, even our simple, deterministic, majority system has at least one case where it's nondeterministic. However that seems fine: In practice that doesn't really happen, right?

Now suppose that the vote goes slightly differently and \(501\) people vote for orange and the other \(499\) vote for blue. This is a "clear" win for orange.

Does it seem vastly more fair than coin flipping though? It doesn't to me, but it's OK if it does to you, and it's indeed deterministic in these regions.

There's a problem though: The determinacy is an illusion. It's a deterministic function of votes cast, it's not a deterministic function of voters' actual beliefs, it just moves the nondeterminacy from the voting system and into the voters.

Suppose voters fail to vote with a dropout rate of \(1\%\). e.g. through getting lost on the way to the ballot box, misreading the instructions, spoiling their ballot, etc. What are the chances of orange winning now?

Here's some Python code for calculating these probabilities:

import numpy as np
import scipy.stats as st

def win_probability(a, b, dropout=0.01):
    """If there are ``a`` votes for orange and ``b`` votes
    for blue, and people drop out with a dropout rate of
    ``dropout```, what is the probability of orange winning?
    p_voted = 1 - dropout
    a_votes = st.binom(a, p_voted)
    b_votes = st.binom(b, p_voted)
    tie_possibilities = np.arange(min(a, b) + 1)

    # Probability of winning from a tie is the probability
    # of the two having the same number of votes exactly
    # times half for the coin flip.
    tie_wins = 0.5 * np.sum(
        a_votes.pmf(tie_possibilities) * b_votes.pmf(tie_possibilities)

    # A clear win happens when a has strictly more votes
    # than b.
    all_possibilities = np.arange(max(a, b) + 1)
    b_chances = b_votes.pmf(all_possibilities)
    a_exceeding = 1 - a_votes.cdf(all_possibilities)
    clear_wins = np.sum(a_exceeding * b_chances)
    return tie_wins + clear_wins

You can play with this a bit to get a feel for it, but the short version is that the result is nondeterministic but quite sharp. With the numbers above orange has a \(74\%\) chance of winning. If the dropout rate goes up to \(5\%\) orange has a \(61%\) chance of winnning.

In contrast if we raise the majority to \(510\) vs \(490\) the dropout rate has to go really very high before it becomes nondeterministic. A dropout rate of \(10\%\) gives orange a \(97\%\) chance of winning, a dropout rate of \(50\%\) gives it a \(74\%\).

Under this model simple majority voting is a nondeterministic system, but it's one where the curve between regions that are "morally" deterministic is very sharp. Exactly how sharp depends on the dropout rate.

How high is the dropout rate in practice? Hard to say, but given that voter turnout rates in the UK seem to hover in the \(60\% - 80\%\) region, \(5\%\) seems if anything optimistically low.

None of this is intended to suggest that because voting is intrinsically nondeterministic any nondeterminism is valid. What I want to do by pointing this out is to shift the argument from "Is nondeterministic voting acceptable?" to "How do we want to manage nondeterminism in voting?"