Advances in STV Margin Computation

Alexander Ek; Damjan Vukcevic; Michelle Blom; Peter J. Stuckey; Vanessa Teague

REVIEW 3 major objections 4 minor 4 references

This paper claims that an improved branch-and-bound algorithm, STV-26, computes exact or near-exact margins for many real STV elections and much tighter lower bounds for large ones, shrinking audit sample sizes from over a thousand ballots

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Tighter (often exact) STV election margins are computed with improved bound heuristics and pruning, making mismatch-based risk-limiting audits practical for real elections.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Real engineering improvements, but the new lower-bound heuristics are not proven to be lower bounds, and the quota-skip mechanism in WIGM gives a concrete reason to doubt them. the 3 major comments →

arxiv 2607.21178 v1 pith:SWBGBBG6 submitted 2026-07-23 cs.GT cs.CRcs.CY

Advances in STV Margin Computation

Michelle Blom , Alexander Ek , Peter J. Stuckey , Vanessa Teague , Damjan Vukcevic This is my paper

classification cs.GT cs.CRcs.CY

keywords single transferable votemargin of victoryrisk-limiting auditbranch and boundminimal manipulationlower boundspreferential votingsurplus transfer

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Single transferable vote (STV) elections are hard to audit because the margin—the fewest ballots that must be changed to flip the winner set—is hard to compute. This paper tries to establish that a new algorithm, STV-26, can compute exact margins for many smaller real-world STV elections and substantially tighter lower bounds for large ones, by extending an existing branch-and-bound search with a nonlinear minimal-manipulation solver, sharper tally and transfer-value bounds, and dominance pruning. The payoff is concrete: for the NT 2022 election, a mismatch-based risk-limiting audit would need about 55 ballots on average with the new lower bound, versus more than 1000 with the previous method. If correct, this makes risk-limiting audits of many STV contests practical for the first time.

Core claim

The paper's central claim is that the STV-26 algorithm obtains valid and much tighter lower bounds on the margin of real STV elections than the previous BST-19 approach. The algorithm searches a tree of partial election orders (prefixes), computing for each prefix a lower bound on the number of ballot changes needed to realise an outcome extending that prefix. The improvements are: solving the minimal-manipulation MINLP with its nonlinearities intact under a super-candidate relaxation; new minimum/maximum ballot-value bookkeeping (tails, piles, transfer-value bounds) that yields sharper elimination, quota, and displacement lower bounds; and a dominance rule that discards nodes whose relaxed

What carries the argument

The load-bearing machinery is the prefix-tree search with three lower-bounding heuristics—an elimination bound, a quota bound, and a new displacement bound—all built on min/max ballot-value bookkeeping (Equations 2–7) that tracks where each ballot could be and what value it could have at each round, including bounds on surplus transfer values. The MINLP that finds the minimal manipulation for a prefix is solved by keeping nonlinearities, with merged 'super candidate' elimination sequences to keep it tractable. A dominance rule prunes nodes sharing the same relaxed structure if a previously explored node has a lower bound no larger.

Load-bearing premise

The load-bearing premise is that the min/max pile and ballot-value bookkeeping always bracket the true tabulation for every reachable prefix, so that the elimination, quota, and displacement heuristics never overestimate the true minimal manipulation; this is shown on worked examples but not proven, and the floating-point implementation could in principle violate it.

What would settle it

Enumerate all possible manipulated profiles for a small STV election (e.g., 4–6 candidates, a few dozen ballots), compute the true margin by brute force, and compare with STV-26's reported lower bound; if any reported bound exceeds the true margin, the bookkeeping is unsound. Alternatively, instrument STV-26 to print the min/max tallies on a random profile and check against the actual tabulation of every nearby manipulated profile.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

Mismatch-based risk-limiting audits of STV elections become practical at scale: for example, the NT 2022 election would require roughly 55 sampled ballots at 0.1% mismatch instead of over 1000.
For many smaller contests the algorithm computes the exact margin, not just a bound, giving precise closeness information.
The improvements carry over to Australian Senate rules for 2-seat races, since WIGM and Senate transfer rules coincide when only one surplus distribution occurs.
Large Australian Senate contests with hundreds of candidates and 6–12 seats remain out of reach, so further scaling work is needed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same prefix-based lower-bounding structure could likely be adapted to other sequential voting rules with transfers, such as variants that use the whole surplus, by replacing the transfer-value update equations.
A brute-force validation on small random profiles (comparing the returned lower bound to the true margin by exhaustive search) would empirically test the unproven bookkeeping bounds; this is cheap and could be done before deployment.
The combination of tighter upper bounds from constructive manipulation search and these tighter lower bounds could produce certified exact margins for contests that are currently too large for the MINLP to solve exactly.
One subtle risk: the implementation uses floating-point arithmetic, so formally verified or fixed-precision versions may be needed for legally binding audits.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Real engineering improvements, but the new lower-bound heuristics are not proven to be lower bounds, and the quota-skip mechanism in WIGM gives a concrete reason to doubt them.

read the letter

Short version: this is the best current attempt at practical STV margin lower bounds, and the engineering improvements are real. But the central safety property — the heuristics in §3.2 are always true lower bounds on the manipulation count — is not proven and, on the evidence of the equations, may be false. If that's right, the §5 audit sample sizes (55 ballots for NT'22, etc.) are not guaranteed to meet the risk limit.

What's genuinely good: the paper gives a controlled re-implementation baseline (BST-19*), full equations for the min/max tally bookkeeping, the displacement bound, and the MINLP formulation, plus worked examples. The performance gains are large and consistent: exact margins for many smaller contests, big improvements on Australian Senate contests. The authors are open about the ConcreteSTV upper bound caveat (Appendix A), which is a sign of care.

The major soft spot is the division-by-2 lower bound in Eqs. 8, 14, 18. It assumes one altered ballot changes the difference between two candidates' tallies by at most 2. In WIGM, that isn't true. A single ballot can push a candidate across the quota, changing the surplus transfer value and causing every subsequent ballot in that pile to be reweighted — or to skip the candidate entirely. Effects on a later candidate's tally can be far larger than 2 per changed ballot. The min/max tallies in Eqs. 5–7 are computed from the original ballot multiset; they do not bound tallies after manipulation. Worked Examples 4–7 show how the numbers come out; they do not establish the universal property. If any of these bounds overestimates, the final 'lower bound' can be above the true margin and the RLA sample sizes in §5 are too small.

Two smaller soft spots: the dominance rule in §3.3 rests on an unproven order-independence claim about the MINLP's relaxation; and the MINLP section never says which solver is used or whether the reported values are proven optima. That matters for the 'exact margin' claims. Also, no commit hash or solver version for the repo.

Bottom line: if I were running an RLA tomorrow, I wouldn't trust these numbers until the lower-bound heuristics carry proofs (or a small formal counterexample is found and fixed). But the MINLP alone is a sound method, and the empirical results might all be correct. The right path is a serious referee pass with a request for either a soundness proof or a re-scoped claim.

Referee Report

3 major / 4 minor

Summary. This paper improves the BST-19 branch-and-bound algorithm for computing lower bounds on the margin of STV (WIGM) elections. The contributions are a MINLP-based lower-bound solver, tighter margin upper bounds from ConcreteSTV, new lower-bounding heuristics (elimination, quota, displacement) built on min/max tally bookkeeping, and a dominance-based pruning rule. The authors report exact or near-exact margins for many real elections and argue that the resulting lower bounds make mismatch-based risk-limiting audits practical. The central claim is that the computed quantities are valid lower bounds on the number of ballot manipulations needed to change the winner set.

Significance. If the bounds are valid, the work is practically significant: it substantially reduces audit sample sizes for mid-sized STV elections and provides an open-source implementation. The controlled re-baselining on identical hardware (BST-19*) and the explicit statement that the lower-bound guarantee does not depend on upper-bound correctness are good methodological choices. However, the validity of the new lower-bounding heuristics is the linchpin of the paper, and no proof is supplied; on inspection, the 1/2-vote argument is inconsistent with WIGM's transfer and skip dynamics.

major comments (3)

[§3.2, Eqs (8), (14), (18)] The factor 1/2 is load-bearing and unproved, and it is false under WIGM. These equations implicitly assume that changing one ballot changes the difference between two candidates' tallies at a round by at most 2 votes. In WIGM a single changed ballot can flip a candidate across the quota threshold, changing the eligibility/skip status of an entire transfer. Concretely, with Q=308, let E have 307 first preferences and C have 510, of which 110 are [C,E,D]. If E receives C's surplus, E's tally is 307+110·(202/510)=350.57. Changing one ballot so that E has 308 first preferences at the start of round 1 makes E ineligible for C's transfer, so E's tally is 308: a swing of about 42.6 votes from one ballot. Hence the heuristics can overestimate the true minimal manipulation. Examples 4–7 are arithmetic demonstrations, not proofs; no theorem establishes the required lower-bound property.
[§2.1 vs §3.2, Example 4] The min/max pile bookkeeping contradicts the stated WIGM skip rule. Section 2.1 says ballots skip any remaining candidate that had a quota at the start of the round, even if not yet seated. In Example 1/4, E has 350 first preferences, so E has a quota at the start of round 1; the 110 [C,E,D] ballots must skip E. Thus Vmax_{E,2}=393.56 in Example 4 is inconsistent with the paper's own rules; the value should be 350. This error propagates into Examples 5–7 and into the definitions of Bmaybe/Bmust (Eqs 3–6). The ambiguity the model tries to capture ('depending on when E achieves their quota') does not exist for a candidate that starts the round with a quota.
[Table 3 and §5] The empirical claims of exact or near-exact margins rest on the unsound lower bounds. The 'exact' entries are those where the STV-26 lower bound equals the ConcreteSTV upper bound; if the lower bound can overestimate, equality is not exactness. The paper should validate the bounds against independently computed exact margins for the small contests (e.g., the MN and Glasgow cases) and should report MINLP-only lower bounds separately from the heuristic bounds. Without such validation, the RLA sample-size statements (e.g., 'about 55 ballots' for NT 2022) are not supported.

minor comments (4)

[§1] Typo: 'In this this paper' should be 'In this paper'.
[Table 3, Langside row] The reported quota 9334 for |B|=2334 and N=3 is inconsistent; the Droop quota should be 584. Please check the data entry.
[Table 3] The notes state that bold marks the best value between STV-26 and BST-19*, and also that bold marks elections with an exact margin only with STV-26. These two conventions overlap and make the table hard to read; please distinguish them.
[Algorithm 1] The variable 'rul' is called a 'running upper limit' but it is an upper bound on the returned lower bound. Consider renaming it to 'incumbent' or 'best lower bound found' to avoid confusion.

Circularity Check

0 steps flagged

No circular derivation: STV-26's lower bounds are computed from ballot data and WIGM tabulation rules, not from the claimed margins; self-citations are contextual and not load-bearing.

full rationale

The paper's central claim is that STV-26 computes valid lower bounds on the STV margin. The derivation is self-contained: the min/max tally machinery (Eqs. 2–7) is defined directly from the cast ballot multiset and the WIGM transfer rules, and the elimination, quota, and displacement bounds (Eqs. 8–18) are constructed from those tally bounds. No parameter is fitted to a known margin, and no reported margin value is fed back into any bound. The final lower bound is the minimum over explored complete alternative outcomes, which is a direct computation rather than an inverse fit. The MINLP in Appendix B also encodes the tabulation rules explicitly and minimizes the number of modified ballot types subject to constraints that the desired prefix occurs. The 'super candidate' relaxation is explicitly described as a relaxation, so the resulting objective is a lower bound by construction, not a renamed version of the target margin. The upper bound from ConcreteSTV is used only to initialize the running limit and to recognize exactness when it coincides with a lower bound. The paper explicitly states that the lower-bounding algorithm is not reliant on the correctness of provided upper bounds: if the upper bound is too low, the returned value is still a valid lower bound. Thus the upper bound is not a fitted input disguised as a prediction. The references [1]–[4] do share authors with the present paper, but the load-bearing argument is restated in this paper: the algorithm, equations, and MINLP formulation are given in full, so the result does not reduce to an unverified self-citation. No uniqueness theorem is imported to force a choice, and no ansatz is smuggled in via citation; the WIGM model and heuristics are defined in the present text. Comparisons to BST-19 are benchmark comparisons to the authors' prior work, which is a normal and non-circular way to demonstrate improvement. The manuscript does flag limitations: the lower-bound heuristics are demonstrated on Examples 4–7 rather than proven, Appendix A notes that floating-point versus fixed-precision differences could in principle affect validity, and the concluding remarks state that scaling to very large contests remains future work. These are correctness and completeness risks, not circularity. Even if a heuristic were later shown to overestimate a true minimum manipulation, that would be a soundness bug, not a case of the derivation being equivalent to its own inputs. For these reasons, the derivation

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 1 invented entities

The method is parameter-free in the sense that no constant is fitted to the target margin. The hand-chosen algorithmic choices (when to merge eliminated candidates into a super candidate; leaving the last merged candidate out) affect bound tightness, not validity. The heavy lifting is done by domain assumptions: the WIGM model with Droop quota and jurisdiction tie-breaking, the relax-then-bound discipline of the MINLP, and — for the 'exact margin' readings — the validity of ConcreteSTV's upper bounds. The 'super candidate' is a computational relaxation device, not an evidential entity. The main unstated burden is that every bound is a true lower bound; the paper illustrates this on examples rather than proving it.

free parameters (2)

super-candidate merge threshold = n ≥ 3 eliminated candidates merged
Hand-chosen in §3.2 'Super candidate relaxation': sequences of eliminations of length ≥ 3 are merged into a super candidate, shorter sequences are not. It affects the tightness of the resulting lower bounds, not their validity, and is not fitted to data.
exclusion of trailing candidate c_n from merge = c_n left unmerged
Hand-chosen: 'leaving c_n out of the merge because merging entire sequences of eliminated candidates produces a relaxation that is too aggressive'. Affects bound quality only; not fitted to data.

axioms (5)

domain assumption The WIGM STV tabulation model (Droop quota, surplus transfer values, jurisdiction tie-breaking) faithfully represents the tested real-world elections.
Section 2.1 defines the counting rules; all margin calculations assume this model and tie-breaking per jurisdiction. If the real rules differ (e.g., surplus transfer variants), the computed margins do not correspond to actual manipulability.
standard math Enumerating all prefixes in best-first branch-and-bound covers every outcome that differs in winners from the reported one.
Section 2.3: the frontier search over seat/eliminate decisions is the standard completeness argument for this state space; assumes no outcome is missed by the prefix representation.
domain assumption A margin lower bound under the fixed-ballot-count alteration model transfers to the mismatch-based RLA framework of [3].
Sections 1 and 5: audit sample-size statements (e.g., ~55 ballots for NT 2022) inherit the theory of Ek et al. [3], co-authored by this group; the paper does not re-derive that connection.
domain assumption The MINLP relaxation (continuous non-binary variables, super-candidate merging, dropped lowest-tally constraints) yields a value that is a true lower bound on the minimal manipulation.
Section 3.2 and Appendix B: the 'slight relaxation' claim and the removal of elimination constraints are asserted, and the solver's returned value is assumed to be a proven bound; no proof or solver optimality statement is given.
domain assumption ConcreteSTV manipulations are valid manipulations under WIGM, so the reported upper bounds are true upper bounds.
Appendix A: the paper itself notes bounds found by ConcreteSTV 'are not guaranteed to be valid' in a different version; the exact-margin (LB=UB) results depend on this.

invented entities (1)

super candidate no independent evidence
purpose: Groups sequences of eliminated candidates in a relaxed prefix so the minimal-manipulation MINLP has fewer variables and is tractable.
A relaxation device within the algorithm (§3.2), not a claim about the world. It is introduced to make computation feasible and carries no falsifiable external handle; it does not load the evidential burden the way a new physical entity would.

reviewed 2026-08-01 · how reviews work

0 comments

Cite this review

Pith. "Pith review of Advances in STV Margin Computation." pith.science (2026). https://pith.science/paper/SWBGBBG6

@misc{pith2026260721178,
  author       = {Pith},
  title        = {Pith review of: Advances in STV Margin Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SWBGBBG6}},
  note         = {Machine review of arXiv:2607.21178}
}

Share X Bluesky LinkedIn Reddit HN

read the original abstract

Single transferable vote (STV) is a multi-winner preferential proportional electoral system. The margin is the smallest number of ballots that need to be manipulated to alter the set of winners. If we can compute the margin of an STV election, or a reasonable lower bound on the margin, we can use recent advances in auditing research to conduct a risk-limiting audit of the election's winners. Knowledge of the margin also provides insight into whether uncovered mistakes, or a known error rate in ballot interpretation, could have influenced the outcome. This paper presents substantial improvements on an existing algorithm for computing lower bounds on the margin of an STV election. These improvements allow us to compute higher lower bounds for real STV elections, making mismatch-based risk-limiting audits more practical.

Figures

Figures reproduced from arXiv: 2607.21178 by Alexander Ek, Damjan Vukcevic, Michelle Blom, Peter J. Stuckey, Vanessa Teague.

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 1 linked inside Pith

[1]

In: AAAI

Blom, M., Conway, A., Stuckey, P.J., Teague, V.J.: Did that lost ballot box cost me a seat? Computing manipulations of STV elections. In: AAAI. vol. 34, pp. 13235–13240 (2020)

2020
[2]

INFORMS Journal on Computing 31(4), 636–653 (2019), Preprint: arXiv:1703.03511

Blom, M., Stuckey, P.J., Teague, V.J.: Toward computing the margin of vic- tory in single transferable vote elections. INFORMS Journal on Computing 31(4), 636–653 (2019), Preprint: arXiv:1703.03511

Pith/arXiv arXiv 2019
[3]

In: Financial Cryptography and Data Security

Ek, A., Blom, M., Stark, P.B., Stuckey, P.J., Teague, V.J., Vukcevic, D.: Doing more with less: Mismatch-based risk-limiting audits. In: Financial Cryptography and Data Security. FC 2025. Lecture Notes in Computer Sci- ence, vol. 15754, pp. 241–255. Springer (2026), Preprint: arXiv:2503.16104

arXiv 2025
[4]

Teague, V.J., Conway, A.: iVote issues: Assessment of potential impacts on the 2021 NSW local government elections. In: E-Vote-ID (2022) Advances in STV Margin Computation 17 A ConcreteSTV Upper Bounds Details We ran ConcreteSTV with settings that matched, as closely as possible, the variant chosen in this paper. However, it is always possible that slight...

2021

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.

[1] [1]

In: AAAI

Blom, M., Conway, A., Stuckey, P.J., Teague, V.J.: Did that lost ballot box cost me a seat? Computing manipulations of STV elections. In: AAAI. vol. 34, pp. 13235–13240 (2020)

2020

[2] [2]

INFORMS Journal on Computing 31(4), 636–653 (2019), Preprint: arXiv:1703.03511

Blom, M., Stuckey, P.J., Teague, V.J.: Toward computing the margin of vic- tory in single transferable vote elections. INFORMS Journal on Computing 31(4), 636–653 (2019), Preprint: arXiv:1703.03511

Pith/arXiv arXiv 2019

[3] [3]

In: Financial Cryptography and Data Security

Ek, A., Blom, M., Stark, P.B., Stuckey, P.J., Teague, V.J., Vukcevic, D.: Doing more with less: Mismatch-based risk-limiting audits. In: Financial Cryptography and Data Security. FC 2025. Lecture Notes in Computer Sci- ence, vol. 15754, pp. 241–255. Springer (2026), Preprint: arXiv:2503.16104

arXiv 2025

[4] [4]

Teague, V.J., Conway, A.: iVote issues: Assessment of potential impacts on the 2021 NSW local government elections. In: E-Vote-ID (2022) Advances in STV Margin Computation 17 A ConcreteSTV Upper Bounds Details We ran ConcreteSTV with settings that matched, as closely as possible, the variant chosen in this paper. However, it is always possible that slight...

2021

Advances in STV Margin Computation

The reading

Core claim §

What carries the argument

Load-bearing premise §

What would settle it §

If this is right

Where Pith is reading between the lines

discussion (0)

Core claim

Load-bearing premise

What would settle it