Advances in STV Margin Computation

Tightening the Bounds on Electoral Integrity

In elections where voters rank candidates in order of preference, determining the security of the outcome is a computationally heavy task. To verify that a winner actually won, auditors use risk-limiting audits (RLAs)—statistical processes that provide evidence of correctness. A critical input for these audits is the "margin." This is the minimum number of ballots that would need to be manipulated to flip the result.

Until recently, calculating this margin for Single Transferable Vote (STV) systems was a massive bottleneck. While we have robust methods for simple plurality votes, STV involves complex rounds of transfers and eliminations. This makes the math explode. Previous algorithms struggled to provide tight enough lower bounds. Because of this, auditors often had to sample far more ballots than theoretically necessary to reach statistical confidence. This paper introduces STV-26. It is an improved algorithm that finally makes mismatch-based RLAs practical for real-world STV contests.

The bottleneck in STV auditing

The core problem is that the STV margin is difficult to bound. The margin is the smallest number of ballot manipulations required to change the set of winners. STV tabulation happens in sequential rounds. In each round, candidates are either seated or eliminated. Their votes are then transferred to others. A single change in a top-preference vote can ripple through the entire count. It can change the transfer values. It can even change which candidates are eliminated in later rounds.

The previous state-of-the-art was an algorithm called BST-19. It attempted to estimate the margin via a best-first branch-and-bound search (a method that systematically explores a tree of possibilities to find an optimal solution). This method explores a tree of possible "prefixes." These are sequences of seating and elimination events. The goal is to find a lower bound on the manipulation needed to realize those outcomes. However, BST-19 relied on heavy linear relaxations of Mixed-Integer Non-Linear Programs (MINLPs). An MINLP is a complex mathematical model used to find the best solution among discrete choices and non-linear relationships.

BST-19 simplified the math too aggressively. This produced "loose" lower bounds. In an auditing context, a loose bound is expensive. If your algorithm says the margin might be 10 votes when it is actually 1,000, your audit sample size will be unnecessarily massive.

Improving the branch-and-bound search

The authors propose STV-26. It retains the fundamental search structure shown in .

However, it replaces the weak components with more surgical optimizations. The goal is to navigate the tree of possible election prefixes more efficiently. It aims to maintain a tighter grip on the mathematical reality of the transfers.

The improvement rests on four main pillars:

1. Exact MINLP Solving: Instead of relying on linear relaxations, STV-26 solves the MINLPs directly. This ensures the lower bound for any specific prefix is as accurate as possible.
2. Super Candidate Relaxation: Long election sequences make MINLPs computationally intractable. To fix this, the authors use a "super candidate" approach. They group sequences of eliminated candidates into a single entity. This reduces the number of variables. It does not lose the essential logic of the elimination rounds.
3. Advanced Heuristics: The paper introduces three new ways to bound the margin for a given prefix:
4. Elimination Lower Bound: This calculates the cost to ensure an eliminated candidate actually has the lowest tally.
5. Quota Lower Bound: This ensures seated candidates actually meet the required threshold.
6. Displacement Lower Bound: This is a novel heuristic. It estimates the cost for a reported loser to "displace" a reported winner. This happens by reaching a quota or outlasting them in final rounds.
7. Dominance Checks: The algorithm uses super-candidate representations to identify redundant paths. If a new prefix is mathematically equivalent to one already explored, the algorithm prunes it. This prevents wasted cycles.

Results that justify the sample savings

The impact of these improvements is best seen in the delta between the old bounds and the new ones. The authors tested STV-26 against ten Australian Senate elections, several US-based contests, and various Irish and Scottish local elections.

The most striking results appear in the comparison of required audit samples. For the Northern Territory (NT) 2022 election, the authors note a massive difference in workload. If you assume a 0.1% mismatch rate (the rate at which humans err in reading ballots), a mismatch-based RLA would require sampling roughly 55 ballots using the STV-26 lower bound. In contrast, the older BST-19* method would require more than 1,000 ballots.

If the error rate rises to 1%, the discrepancy becomes even more extreme. STV-26 requires ~106 ballots. Meanwhile, BST-19* would require nearly 100,000. This demonstrates how much more efficient the new algorithm is for practical auditing.

On the computational side, STV-26 performs well on smaller contests. It can find exact margins or near-exact bounds significantly faster than previous implementations. Even for larger 2-seat Australian Senate elections, STV-26 finds substantially higher lower bounds. Earlier methods often hit computational limits without providing a useful answer.

Scaling and complexity limits

Despite the gains, STV-26 is not a silver bullet for all scales. The authors are honest about the remaining "frontier" of difficulty. Scaling the method to very large Australian Senate contests remains a challenge. These contests can involve hundreds of candidates and 6 to 12 seats.

There are two specific areas where a practitioner should exercise caution: * Complexity Growth: While the "super candidate" relaxation helps, the underlying problem is still NP-hard (meaning it becomes exponentially harder as more variables are added). As the number of seats and candidates grows, the branching factor increases. This could lead to exponential growth in runtime. * Rule Variants: The paper focuses on the Weighted Inclusive Gregory Method (WIGM). Users of different STV variants must be careful. They must ensure the MINLP formulation correctly captures their specific surplus transfer logic.

The verdict

If you are building or implementing systems for electoral auditing, STV-26 is a significant step forward. It transforms mismatch-based RLAs from a theoretical possibility into a practical tool. It does this by drastically reducing the required sample sizes. Moving from a 100,000-ballot requirement down to 100 is the difference between a viable audit and a logistical impossibility.

The implementation is available via the pymarginstv repository on GitHub. For engineers working on large-scale democratic infrastructure, this is a codebase worth prototyping. You should test it against your own datasets to see where your specific election profiles fall on the complexity curve.