Advances in STV Margin Computation⋆ Michelle Blom1[0000−0002−0459−9917] , Alexander Ek⋆⋆2[0000−0002−8744−4805] , Peter J. Stuckey1[0000−0003−2186−0459] , Vanessa Teague3[0000−0003−2648−2565] , and Damjan Vukcevic4[0000−0001−7780−9586] 1
arXiv:2607.21178v1 [cs.GT] 23 Jul 2026
Department of Data Science and AI, Monash University, Clayton, Australia [email protected] 2 Department of Computer Science, KU Leuven, Belgium 3 Thinking Cybersecurity Pty Ltd. 4 Department of Econometrics and Business Statistics, Monash University, Clayton, Australia
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.
1
Introduction
The single transferable vote (STV), also called proportional ranked-choice voting, is an electoral system where voters rank candidates in order of preference and multiple candidates are elected in a manner reflecting voter preferences proportionally. STV is used for national, state, and local elections in Australia, for EU, national, and local elections in Ireland and Malta, and for some elections in Aotearoa/New Zealand, Northern Ireland, Scotland, and the USA. STV tabulation proceeds in rounds, with each round either electing or eliminating a candidate. In each case, every ballot sitting in the elected or eliminated candidate’s tally pile is transferred to the next-highest-ranked eligible candidate on that ballot. When ballots are transferred from an elected candidate’s tally, they are reduced in value according to a transfer value. ⋆
Accepted for E-Vote-ID 2026. This work was supported by the Australian Research Council (Discovery Project DP220101012, OPTIMA ITTC IC200100009). ⋆⋆ Funded by the European Union (ERC, CertiFOX, 101122653). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
2
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
A risk-limiting audit (RLA) is a process designed to efficiently provide affirmative statistical evidence that the reported winners really won, and correct the outcome (with a guaranteed high probability) if they did not win. The margin is the minimum number of ballots that need to be altered—by changing the marked preferences on the ballots—to change who wins.5 Determining the margin of an election informs us about how close it was, and allows us to conduct an RLA for the election using the mismatch-based method [3]. Mismatch-based audits require only a lower bound, not an exact value, for the margin. However, if this bound is not tight then such audits may require sampling far more ballots than truly necessary. In this paper we present significant improvements in STV margin lower bounding, which should substantially reduce required sample sizes for mismatch-based STV audits. Blom et al. [2] presented a best-first branch-and-bound algorithm, which we will call BST-19, for computing a lower bound on the margin of an STV election by searching over a tree of possible tabulation prefixes. Each prefix defines a sequence of seatings and eliminations over a number of tabulation rounds, starting with the first round r = 1 and ending at some round r = n which may or may not be the last round of tabulation. This tree captured outcomes that could occur if the cast ballots were manipulated. The algorithm used: a method for computing an upper bound on the margin; a linear relaxation of a mixed-integer non-linear program (MINLP) for computing a minimal manipulation to the ballots cast to realise an outcome that starts with a specific prefix; and heuristics for computing a lower bound on the number of ballots that would have to be altered to realise an outcome with a specific prefix. BST-19 is currently the only approach developed for computing lower bounds on the margin of an STV election, while several approaches exist for computing upper bounds [1, 4]. In this this paper, we improve BST-19 in several ways: – Solving of MINLPs without resorting to linear relaxation. – More sophisticated lower-bounding heuristics by considering future rounds and more sophisticated reasoning about transfer values. – Use of better margin upper bounds from recent work [1, 4]. – Dominance checks that allow us to discard prefixes from the search tree if something equivalent has been or is being explored. Our improved algorithm for STV margins, which we will call STV-26, is able to find exact or near-exact margins for many real-world STV elections. For large 2-seat Australian STV elections, we are able to find substantially higher lower bounds on the margin than previously possible. For STV elections of the size commonly conducted in the USA, and at the local council level in Scotland, we can find margins that would allow us to conduct mismatch-based RLAs [3]. An open source implementation is available in the following GitHub repository: https://github.com/michelleblom/pymarginstv 5
A more general definition also allows alterations where ballots can be removed or added. Here we only allow alterations that keep the total number of ballots fixed.
Advances in STV Margin Computation
2
Background
2.1
Single Transferable Vote
3
This paper considers the weighted inclusive Gregory method (WIGM) variant of STV. Voters rank candidates in order of preference, from first to last, in either a total order or leaving some candidates unranked, depending on the jurisdiction. Each ballot starts with a value of 1, which is subsequently reduced if used to elect a candidate to a seat. To be seated, a candidate’s tally must reach or exceed the quota Q (election threshold ). The Droop quota is typically used: # of validly cast ballots + 1. (1) Q = # of seats + 1 Each candidate has a pile of ballots, and each ballot a ballot value. A candidate’s tally V is the sum of the ballot values in their pile. If a candidate’s tally exceeds the quota, they are said to have a surplus, and this is equal to the number of votes by which they exceed the quota, V − Q. Initially, each candidate is given all ballots on which they are ranked first. Tabulation proceeds in rounds in which a single candidate is seated or eliminated, until all seats are filled. Ballots in a seated or eliminated candidate’s pile are moved to other candidates’ piles or discarded. If the number of unfilled seats equals the number of remaining candidates, we seat all remaining candidates. If no candidate has a quota at the start of a round, we eliminate the candidate with the lowest tally (breaking ties as defined by the jurisdiction), moving all ballots in their pile (at their current value) to the next most preferred eligible candidate on the ballot. If no such candidate exists, the ballot exhausts. A remaining candidate is one not yet seated or eliminated. An eligible candidate is a remaining candidate that does not have a quota at the start of the round. When seating a candidate, the ballots in their pile continue in the tabulation, but are reduced in value according to their transfer value τ , which is the proportion of the tally that is due to the surplus, τ = (V − Q)/V . The new value of each ballot is equal to its current value multiplied by the transfer value. Each of these ballots is then given to the next most preferred eligible candidate on the ballot, or discarded if no such candidate exists. Ballots will skip any remaining candidate that had a quota at the start of the round, even if they have not yet been seated. Where multiple candidates achieve a quota simultaneously, they are seated in order of their tally, highest to smallest. Example 1. Consider the 3-seat STV election between candidates A to E in Table 1, with 1230 validly cast ballots and a quota of 308 votes. The first preference tallies of A to E are 250, 120, 510, 0 and 350 votes. Candidates C and E have a quota. Candidate C has the largest surplus, at 202 votes, and is elected first. Their transfer value is τ1 = 202/510 = 0.396. The 400 [C, D] ballots are each given a weight of 0.396, and a total of 158.4 votes are added to D’s tally. The 110 [C, E, D] ballots are each given a weight of 0.396, and are also given to candidate D, skipping E as they already have a quota. Candidate D now has a
4
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
Table 1: The 3-seat STV election from Example 1 between candidates A–E and a quota of Q = ⌊1230/4⌋ + 1 = 308 votes. (a) Number of ballots of each type. (b) Tallies after each counting round, noting when quotas were reached (in bold). (b)
(a) Ranking
Count
[A] [B, A, C] [C, D] [E] [C, E, D]
250 120 400 350 110
Candidate
Round 1
Round 2
Round 3
Round 4
C elected E elected B eliminated A elected τ1 = 0.396 τ2 = 0.12 A B C D E
250 120 510 0 350
250 120 — 201.96 350
250 120 — 201.96 —
370 — — 201.96 —
tally of 201.96 votes. Candidate E is then elected. Their transfer value would be τ2 = 42/350 = 0.12, but all of the ballots in their tally exhaust. In the third round, no candidate has a quota’s worth of votes, so the candidate with the smallest tally, B, is eliminated. The 120 [B, A, C] ballots go to A, each retaining their current value of 1. At the start of the fourth round, candidate A has reached a quota, at 370 votes, and is elected to the third and final seat. 2.2
Notation
Definition 1 (STV Election). An STV election is defined as a tuple E = (C, B, N, Q, W) where C is the set of candidates up for election, B the multi-set of ballots cast in the election, N the number of seats to be filled, Q the election quota (Equation 1), and W the subset of candidates elected to a seat (the winners). Each ballot b ∈ B is a partial or complete ranking over the candidates C. Definition 2 (Margin). The margin, or margin of victory, for an STV election E = (C, B, N, Q, W) is defined as the smallest number of ballot manipulations required to ensure that candidates W ′ ̸= W are elected to a seat (i.e., at least one candidate in W ′ must not appear in W). A single manipulation changes the ranking on a single ballot b ∈ B to an alternate ranking. Definition 3 (Election order). Given an STV election E = (C, B, N, Q, W), we represent the outcome of E as an election order π, where π is a sequence of tuples (c, a) with c ∈ C, a ∈ {0, 1}, and each c ∈ C appears in at most one tuple. The tuple (c, 1) denotes that candidate c is elected to a seat, while (c, 0) that c has been eliminated. An order π is complete if it involves the election of N candidates, and partial if fewer than N candidates have been elected in π. For example, the order π = [(A, 0), (C, 1), (B, 0), (D, 1)] indicates that candidate A is eliminated in the first round of counting, C is next elected to a seat, B is then eliminated, and then D is elected to a seat.
Advances in STV Margin Computation
5
BST-19(E = (C, B, N, Q, W)) 1 rul ← ComputeUpperBound(E) ▷ Section 3.1 2 F ← InitialiseFrontier(E) 3 while F ̸= ∅ do 4 n, F ← Remove first node from F 5 F , rul ← Expand(n, F , rul, E) 6 done 7 return rul Expand(n = (l, π), F , rul, E = (C, B, N, Q, W)) 8 for each remaining candidate c do 9 for each action a ∈ {0, 1} do 10 π ′ ← π || [(c, a)] ▷ Add (c, a) to the end of π 11 l′ ← Apply lower bounding heuristics to π ′ ▷ Section 3.2 12 if π ′ is a complete outcome and l′ < rul then 13 rul ← l′ 14 else if π ′ is partial outcome and l′ < rul then 15 F ← Insert (l′ , π ′ ) into F 16 F ← Remove all nodes n′′ = (l′′ , π ′′ ) where l′′ ≥ rul 17 return F, rul
Fig. 1: Key components of the BST-19 STV margin lower bounding algorithm. Note that rul is a ‘running upper limit’ on the margin lower bound returned by the algorithm, as per Section 2.3, and not an upper bound on the margin itself.
An election E is tabulated in rounds. We use Sπ to denote the set of candidates that have not yet been elected or eliminated by the end of prefix π (i.e., the subset of candidates still standing at the end of π), and Sπ,r the subset of candidates still standing at the start of round r of π. 2.3
Margin Lower Bound Computation with BST-19
This section describes the overall structure of the STV margin lower bounding algorithm of Blom et al. [2]. We do not change this structure in this paper, but improve some of its components. The key components of the approach are: computation of an upper bound on the margin; exploration of a tree of alternate election outcome prefixes; heuristics for computing a lower bound on the manipulation required to realise outcomes that start with a specific prefix; and methods for pruning (ignoring) portions of this tree. Figure 1 shows how these components fit together. BST-19 used several heuristics to compute an upper bound on the STV margin (step 1). We replace these with a heuristic that produces tighter upper bounds (see Section 3.1). This upper bound is used to initialise a ‘running upper limit on the eventual lower bound’, rul, that the algorithm will return. BST-19 maintains a frontier of nodes, F , each node (l, π) ∈ F composed of a lower bound l and a prefix π. The prefix is a partial or complete election order, and l is a lower bound on the manipulation that would be required to realise an outcome that starts with π. The frontier is
6
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
initialised (step 2) by considering each candidate c ∈ C and creating two nodes: one where they are seated and one where they are eliminated in the first round. When a node is created with prefix π, we apply heuristics that compute a lower bound l on the manipulation required to realise an outcome starting with π (see Section 3.2). If this lower bound is equal to or higher than our ‘running upper limit’ (rul), we ignore the node, otherwise we add it to our frontier. Nodes on the frontier are sorted in order of their lower bound, smallest to largest. While our frontier is non-empty, we remove the first node n = (l, π) and expand it (steps 4–5). When expanding a node, we create two child nodes for each remaining candidate c (not yet seated or eliminated in π). One child seats c next and the other eliminates them (steps 9–10). If a child seats all of the reported winners of the election, we ignore it, as we are only interested in outcomes that change who wins. We apply our lower bounding heuristics (see Section 3.2) to compute an l for each child (steps 10–11). If the child is a complete outcome, filling all seats, and l < rul, we update rul to l (steps 12–13). If the child is a partial outcome and l < rul we add it to our frontier (steps 14–15). Otherwise it is ignored. All nodes n′′ = (l′′ , π ′′ ) on the frontier where l′′ ≥ rul are removed (step 16). Expansion updates the frontier and our ‘running upper limit’ rul. When we have explored or ignored all nodes on the frontier, we return rul as the computed lower bound on the election E’s margin (step 7). In the next section we describe how we have improved the computation of margin upper bounds (Section 3.1) and the lower bounding heuristics applied to partial/complete outcomes (Section 3.2). We also add a dominance check that improves efficiency by completely ignoring some nodes (Section 3.3).
3
Improvements
3.1
ConcreteSTV Upper Bounds
Blom et al. [1] and Teague and Conway [4] describe a method of computing upper bounds on STV margins that searches for, and tests, actual manipulations of ballots, looking for those that result in changed outcomes. This heuristic, implemented in ConcreteSTV, finds better (smaller) upper bounds than the heuristics used by BST-19.6 3.2
New Lower Bound Heuristics
In step 11 of Figure 1, BST-19 assigns to each prefix π the largest of several lower bounds: the lower bound assigned to the parent of π (if |π| > 1), an elimination lower bound; a quota lower bound; or a lower bound obtained by solving a relaxation of a MINLP. For a given π, an optimal solution to this MINLP was the smallest manipulation that could be made to the cast ballots to realise an outcome that started with π. The MINLP was relaxed in two ways: by merging sequences of eliminated candidates into a ‘super candidate’ that was eliminated 6
See Appendix A for more details.
Advances in STV Margin Computation
7
in a single round; and linearising all non-linearities. We use a similar MINLP in this paper, with the super-candidate relaxation, but retain all non-linearities and use the WIGM surplus transfer rules.7 Our MINLP now yields a lower bound on the manipulation required to realise outcomes starting with π.8 The remainder of this section is structured as follows. We first describe how relaxation is used to make the minimal manipulation MINLP tractable (Super candidate relaxation). We then outline how we improve the existing lower bounding heuristics used by BST-19. We first explain our new approach for computing tighter lower and upper bounds on candidate tallies in varying contexts (Minimum and maximum tallies), and then how these new bounds are used in BST-19’s elimination and quota lower bounds. Finally, we present our new lower bounding heuristic, the displacement lower bound, which is used together with the elimination and quota lower bounds, and the minimal manipulation MINLP, to assign lower bounds to prefixes in step 11 of Figure 1. Super candidate relaxation. Solving the minimal manipulation MINLP becomes intractable when dealing with long election orders. We instead solve the MINLP for a relaxation of a given prefix π, denoted π̃, in which some of the sequences of eliminations present in π are grouped or merged. By reducing the total number of candidates in the election, by merging some candidates into a single ‘super candidate’, the number of model variables is considerably reduced. Consider an election order π = [(A, 0), (C, 1), (B, 0), (E, 0), (F, 0) (D, 1)]. This order is relaxed by grouping candidates B and E into one ‘super candidate’ BE, producing π̃ = [(A, 0), (C, 1), (BE, 0), (F, 0), (D, 1)]. Where (BE, 0) appears in the order, it represents candidates B and E being eliminated in some sequence. Formally, we apply candidate merging to sequences of n ≥ 3 candidate eliminations c1 , . . . , cn−1 , cn by grouping candidates c1 to cn−1 into a ‘super candidate’, leaving cn out of the merge. When merging eliminated candidates, some constraints in the MINLP, concerned with ensuring those candidates have the lowest tally at the point of their elimination, are removed. We leave cn out of the merge because merging entire sequences of eliminated candidates produces a relaxation that is too aggressive, resulting in poor lower bounds on the margin. Minimum and Maximum Tallies. BST-19’s lower bounding heuristics rely on computing minimum and maximum possible tallies for candidates in each round of a given prefix. If a ballot might have been distributed as part of a surplus transfer before arriving in a candidate c’s pile, overly conservative assumptions were used: it was assumed to have a value of 1 when calculating c’s maximum tally, and 0 when computing their minimum tally. As a prefix does not stipulate the precise round that a seated candidate received their quota, and votes skip candidates that already have a quota during surplus distributions, there is some ambiguity as to which pile a vote belongs to 7 8
The original MINLP of Blom et al. [2] used Australian Senate surplus transfer rules. The formulation of this MINLP is provided in Appendix B.
8
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
Table 2: Example of how tails and piles evolve in Example 3 for different ballots b and rounds r of a prefix π, where ex denotes that a ballot has exhausted. prefix π = [(A,0), (B,1), (C,1), (D,0)] ballot b
r=1
r=2
r=3
r=4
[A, D]
tail: [A, D] pile: {A}
[D] {D}
[D] {D}
[D] {D}
[A, C, B]
tail: [A, C, B] pile: {A}
[C, B] {C}
[C] {C}
∅ {ex}
[A, B, C, D] tail: [A, B, C, D] [B, C, D] [C, D] [D] pile: {A} {B} {C, D, ex} {D}
in any given round. For prefix π and round r, we define the tail of ballot b = [x1 , . . . , xm ] as the order of remaining candidates that b can (but not necessarily will) be transferred through as the tabulation continues starting with round r. tailπ,b,r = [xi | 1 ≤ i ≤ m and xi ̸∈ {cπ,1 , . . . , cπ,r−1 }]
(2)
where cπ,i is the candidate being elected or eliminated in position i of order π. Example 2. Consider prefix π = [(A, 1), (B, 1), (C, 1)]. For the ballot b = [A, B, C], and round r = 2, tailπ,b,r = [B, C]. For the ballot b′ = [C, A, B], tailπ,b′ ,r = [C, B]. The pile that ballot b belongs to at the start of round r will be one of the candidates in tailπ,b,r or the exhausted pile (ex). The knowledge of what happens in round r (i.e., a candidate is seated or eliminated) gives extra context as to what pile a ballot b could be in. In particular, the only time piles become ambiguous is when two or more seatings occur in a row in π. We define pileπ,b,r as the set of possible piles a ballot b could be in at the start of round r of prefix π. In the following, aπ,i is 0 when a candidate is eliminated in round i of π and 1 if a candidate is elected. if tailπ,b,r = ∅ {ex} pileπ,b,r = {x1 , . . . , xm , ex} if aπ,r−1 = aπ,r = 1, where tailπ,b,r = [x1 , . . . , xm ] {x1 } otherwise, where tailπ,b,r = [x1 , . . . , xm ] (3) We can now define which ballots must be in a given candidate’s pile in a given round, and which ballots may be in their pile. must Bπ,c,r = {b | b ∈ B where {c} = pileπ,c,r } maybe Bπ,c,r
= {b | b ∈ B where c ∈ pileπ,c,r }
(4a) (4b)
Advances in STV Margin Computation
9
Example 3. Consider the prefix π = [(A,0),(B,1),(C,1),(D,0)]. Table 2 shows how tailπ,b,r and pileπ,b,r are computed for different ballots b and rounds r in π. For ballot [A, C, B] and round 2, for example, the tail is [C, B] while the ballot can only be in one pile, that of candidate C. The ballot [A, C, B] must be in candidate A’s pile in round 1, and then in C’s pile in rounds 2 and 3. The ballot [A, B, C, D] must be in candidate A’s pile in round 1, B’s pile in round 2, but then may be in C’s, D’s, or the exhausted pile in round 3. Our determination of which pile a ballot could be in at round r of π does not consider events at rounds r′ > r. We have not yet defined how much a ballot b contributes to the pile it is in. As finding the pile of a ballot b at the start of round r of a prefix π is sometimes ambiguous, the value of a ballot b is similarly sometimes ambiguous. We denote max min Bπ,b,r and Bπ,b,r as the maximum and minimum possible value (between 0 and 1) of ballot b at the start of round r in prefix π. Whenever a candidate c is seated in a round r of a prefix π, there is an associated transfer value Tπ,c,r . To compute the minimum and maximum value of a ballot b after it has passed through one or more surplus transfers, we need to establish lower and upper min bounds on the transfer value associated with each of those transfers. Let Tπ,c,r max and Tπ,c,r denote a lower and upper bound, respectively, on the transfer value for the seated candidate c in round r of π (defined in Equation 7). max min Bπ,b,1 = Bπ,b,1 = 1 ( max max Bπ,b,r−1 × Tπ,c,r−1 max Bπ,b,r = max Bπ,b,r−1 ( min min × Tπ,c,r−1 Bπ,b,r−1 min Bπ,b,r = min Bπ,b,r−1
(5a) must if b ∈ Bπ,c,r−1 and aπ,r−1 = 1 otherwise
(5b)
maybe if b ∈ Bπ,c,r−1 and aπ,r−1 = 1 otherwise
(5c)
When π contains no seatings, both the minimum and maximum value of a ballot in any round of π is 1. We compute minimum and maximum tallies as follows: X X max max min min Vπ,c,r = Bπ,b,r , Vπ,c,r = Bπ,b,r (6) maybe b∈Bπ,c,r
must b∈Bπ,c,r
We compute bounds on the transfer value for a candidate c, seated in round r of a prefix π, in Equation 7. min max max Q, Vπ,c,r −Q max Q, Vπ,c,r −Q min max , Tπ,c,r = (7) Tπ,c,r = max min max Q, Vπ,c,r max Q, Vπ,c,r As we are often computing bounds for prefixes that did not arise in practice, i.e., that do not follow from the cast ballots, candidates may be elected in positions without a quota. We take the max of quota and the actual tally in Equation 7 to arrive at sensible transfer values in these contexts. Example 4. Consider the example from Table 1 and now with the prefix π = [(C, 1), (E, 1), (A, 0)]. At the start of the first round, all ballots sit in the pile of
10
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
their highest ranked candidate, and have a value of 1. As there is no ambiguity maybe must min = Bπ,c,r=1 and Vπ,c,r=1 = around the location and value of ballots, Bπ,c,r=1 max Vπ,c,r=1 for all candidates c. Consequently, we can compute an exact transfer min max value for C, i.e., Tπ,C,r=1 = Tπ,C,r=1 = 0.396. At the start of the second round, min candidate E will have a minimum tally of Vπ,E,r=2 = 350 votes and a maximum max tally of Vπ,E,r=2 = 393.56. The difference arises as the 110 [C, E, D] votes sitting in C’s pile in round 1 may or may not skip over E, when transferred at a value of 0.396 each, depending on when E achieves their quota. We can compute lower and upper bounds on E’s transfer value in round 2 as follows. min Tπ,E,2 =
max(308, 393.56) − 308 max(308, 350) − 308 max = 0.12, Tπ,E,2 = = 0.22. max(308, 350) max(308, 393.56)
min Consider candidate D’s tally in r = 3 of π. Their minimum tally, Vπ,D,r=3 , is equal to the sum of the minimum values of the ballots that must be in their pile in round 3. These are the 400 [C, D] ballots, at 0.396 votes each, and the 110 min [C, E, D] ballots, at 0.396 × 0.12 = 0.04752 votes each. Thus, Vπ,D,r=3 = 163.627. The maximum tally of D in r = 3 of π is equal to the sum of the maximum values of the ballots that maybe in their pile in round 3 which, in this case, is the same set of ballots that must be in their pile. By Equation 6, the maximum total value of the 400 [C, D] and 110 [C, E, D] ballots in round 3 is 400 × 0.396 = 158.4 and must 110 × 0.396 = 43.56. Note that the latter set of ballots is not in Bπ,E,r=2 . min Vπ,D,r=3 = 163.627,
max Vπ,D,r=3 = 158.4 + 43.56 = 201.96
The minimum and maximum tallies of A and B in round 3 of π are simpler to compute, as the ballots that must and maybe in their piles across rounds 1 to 3 are the same, and none of these ballots participate in a surplus transfer. min max Vπ,A,r=3 = Vπ,A,r=3 = 250,
min max Vπ,B,r=3 = Vπ,B,r=3 = 120
Elimination lower bound. For prefix π, the elimination lower bound, lπelim , is a lower bound on the number of ballots we need to change to ensure that each eliminated candidate in π has the smallest tally in the round they are eliminated. For a candidate c ∈ C, eliminated in round r of π, we compute c’s minimum min tally at that point, Vπ,c,r , as per Equation 6. We also compute the maximum possible tally of each other remaining candidate c′ (i.e., that is still standing) at the start of round r, according to π, as per Equation 6. For c to be eliminated in r, we need their minimum tally at this point to be less than the maximum tally of all other candidates still standing. Otherwise, we need to take votes away from c to make this so. If c’s minimum tally is greater than the maximum tally of one of the candidates still standing, then they cannot possibly be eliminated in round r. Thus, we need to change at least the following number of votes: !+ min max Vπ,c,r − Vπ,c ′ ,r elim lπ,c = ′ max (8) 2 c ∈Sπ,r \{c}
Advances in STV Margin Computation
11
where (·)+ is the positive part function.9 For each c vs c′ comparison, the change involves giving some of the votes that would reside with c to c′ . elim This forms an elimination lower bound, lπ,c , with respect to candidate c. The overall elimination lower bound for π is obtained by taking the maximum candidate-based elimination lower bound across all candidates eliminated in π. Let Eπ ⊂ C denote the set of candidates eliminated in order π. This gives: elim lπelim = max lπ,c
(9)
c∈Eπ
Example 5. Consider prefixes π = [(C, 1), (E, 1), (A, 0)] and π ′ = [(C, 1), (B, 1)] for the STV election of Table 1. No candidate in the prefix π ′ has been eliminated, and so its elimination lower bound is 0. In π, A is eliminated in the third round. elim In this case, lπelim = lπ,A by Equation 9, and !+ min max Vπ,A,r=3 − Vπ,c ′ ,r=3 elim lπ,A = ′max 2 c ∈{B,D} min max max , Vπ,B,3 and Vπ,D,3 . by Equation 8. To compute lπelim , we need to compute: Vπ,A,3 min max max From Example 4, Vπ,A,3 = 250, Vπ,B,3 = 120 and Vπ,D,3 = 201.96. Conseelim quently, lπ,A is the maximum of 0.5×(250−120) = 65 and 0.5×(250−201.96) = 24.02 which is 65 votes. Thus, lπelim = 65.
Quota lower bound. For a prefix π, its quota lower bound considers all the candidates that are seated in π. Consider a candidate c that is seated in round r of π. If the maximum tally of c at that point is less than a quota, then c cannot possibly have been seated and we need to give extra votes to c to make it so. The quota lower bound with respect to candidate c in π, and the overall quota lower bound for π is given by: quota max + quota lπ,c = Q − Vπ,c,r (10) , lπquota = max lπ,c c∈Wπ
Example 6. Consider the prefix π = [(C, 1), (E, 1), (D, 1)] for the STV election of Table 1. Three candidates are elected: C in the first round, E in the second, and D in the third. In this example, Wπ = {C, E, D}. In this case, quota quota quota max + max + max + lπ,C = Q − Vπ,C,1 , lπ,E = Q − Vπ,E,2 , lπ,D = Q − Vπ,D,3 max max Vπ,C,1 is equal to C’s first preference tally, 510, while Vπ,E,2 is 393.56 as per Example 4. The prefix considered in Example 4 is that same as π here in rounds 1 and 2, but differs in round 3. To compute the maximum tally of D in round 3, we sum the maximum values of the ballots that may be in their pile: the 400 must [C, D] and 110 [C, E, D]. Note that the latter set of ballots are not in Bπ,E,r=2 . This max gives us Vπ,D,3 = 0.396 × 400 + 0.396 × 110 = 201.96. Given Q = 308, we have: quota lπ,C = 0,
quota lπ,E = 0,
+
quota lπ,D = (308 − 201.96) = 106.4
quota quota quota . By Equation 10, lπquota = 106.4, the maximum of lπ,C , lπ,E , and lπ,D 9
This is defined as (a)+ = max(a, 0), which has value a if a ⩾ 0 and value 0 if a < 0.
12
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
Displacement lower bound. The elimination and quota lower bounds consider only the eliminations and seatings present in a prefix π. If, by the end of π, no new candidate has been elected, we know that something must change in future rounds. Some reported loser must be elected in place of a reported winner. Consider a prefix π, concluding in round r − 1, where it is clear that at least one reported loser still standing has to displace one of the reported winners still standing. In this case, we need to ensure that at least one of the reported losers will not be eliminated before one of the reported winners. We compute the displacement lower bound for π, lπdisp , as follows. First, we check whether π already changes our reported outcome by seating a reported loser or eliminating a reported winner. In both cases, lπdisp is zero. We then check whether there is scope to change who is elected in subsequent rounds, beyond π. If the number of unfilled seats equals the number of subsequent rounds, all remaining candidates will be automatically seated, and lπdisp is again zero. We then consider each reported loser c that is still standing (not yet elected or eliminated) at the end of π. We denote the set of such candidates as Lπ . We compute for each c ∈ Lπ , the cheapest way that we could elect c in the future at disp . The displacement lower bound we assign the expense of a reported winner, lπ,c disp to π, lπ , is the smallest of those computed for each reported loser c ∈ Lπ . disp lπdisp = min lπ,c c∈Lπ
(11)
To compute the displacement lower bound for a candidate c ∈ Lπ , we compute three values: the cheapest way we can make sure c is not eliminated before some reported winner still standing (DispCostπ,c ); the cheapest way we can ensure c achieves a quota (QuotaCostπ,c ); and the cheapest way we can ensure c outlasts enough candidates to be automatically seated in the final round (LeftAtEndCostπ,c ). The displacement lower bound for c is then: disp lπ,c = max DispCostπ,c , min{QuotaCostπ,c , LeftAtEndCostπ,c } . (12) To compute DispCostπ,c , we consider each reported winner w still standing at the end of π, w ∈ W ∩Sπ , and compute the minimum cost required to displace w with c, DispCostπ,c,w . DispCostπ,c is the minimum of these displacement costs. DispCostπ,c ←
min
w∈W∩Sπ
DispCostπ,c,w
(13)
Recall that r is the next round of tabulation after π. We compute the maximum tally c could achieve from the end of π onward, in the context where w is still max standing, Vπ,c≺w,r (Equation 15), and the minimum tally of candidate w at the min end of π, Vπ,w,r (Equation 6). A lower bound on the cost of displacing w with c is equal to half the difference between these tallies. 1 min max Vπ,w,r − Vπ,c≺w,r DispCostπ,c,w ← max 0, 2 ( max X B if c ≺ w in tailπ,b,r max π,b,r Vπ,c≺w,r = 0 otherwise b∈B
(14) (15)
Advances in STV Margin Computation
13
where c ≺ w in a list is true if c appears before w or if only c appears. For a candidate c to be seated, they must either achieve a quota or must never be eliminated. To achieve a quota, their maximum possible tally from π max onward must reach a quota. Let Vπ,c≺∗,r denote this maximum tally. ( X B max if c ∈ tailπ,b,r max π,b,r (16) Vπ,c≺∗,r = 0 otherwise b∈B We compute the cheapest way for c to achieve a quota (QuotaCostπ,c ), and then for c to be automatically seated in the final round (LeftAtEndCostπ,c ). max QuotaCostπ,c ← max{0, Q − Vπ,c≺∗,r }
(17)
For an election E with N seats, and prefix π, candidate c needs to not be eliminated before LE,π = |Sπ | − (N − |Wπ |) other remaining candidates. We compute and sort the displacement costs between c and each remaining alternate candidate, both reported losers and winners, and take the maximum of the first LE,π of these displacement costs to form LeftAtEndCostπ,c . < denote the set of minimum costs required to displace each remaining Let Dπ,c < . candidate c′ ∈ Sπ \ {c} with c, in ascending order, and di the ith cost in Dπ,c < Dπ,c ← [DispCostπ,c,c′ | c′ ∈ Sπ \ {c}]
LeftAtEndCostπ,c = dLE,c
(18)
Example 7. Consider the prefix π = [(C, 1), (E, 1)] for the STV election of Table 1. This π reflects the start of the reported outcome in which C and E are elected. In the reported outcome, A is elected in round 4. We know that at some point after π we will need to elect some candidate other than A. The reported losers still standing at the end of π are B and D. To compute lπdisp we need to compute disp disp a displacement lower bound for each of these reported losers, lπ,B and lπ,D . disp lπ,B = max DispCostπ,B , min{QuotaCostπ,B , LeftAtEndCostπ,B } . 1 min max DispCostπ,B ← min max 0, V − Vπ,B≺w,r=3 2 π,w,r=3 w∈{A} min max To compute DispCostπ,B , we need to compute Vπ,A,r=3 and Vπ,B≺A,r=3 . The only ballots that A must have in their pile at the end of π are the 250 [A] ballots. The only ballots that mention B are the 120 [B, A, C] ballots. min Vπ,A,r=3 = 250,
max Vπ,B≺A,r=3 = 120,
1 DispCostπ,B = max{0, (250 − 120)} = 65 2
A lower bound on the cost required to give B a quota at some point after π is: max QuotaCostπ,B ← max{0, Q − Vπ,B≺∗,r=3 } = max{0, 308 − 120} = 188
To compute LeftAtEndCostπ,B , a lower bound on the manipulation required to make sure B is not eliminated before LE,π = 3−(3−2) = 2 other remaining candi min max = dates, we need to compute DispCostπ,B,A = max 0, 21 Vπ,A,r=3 − Vπ,B≺A,r=3
14
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
min max 65 and DispCostπ,B,D = max 0, 12 Vπ,D,r=3 −Vπ,B≺D,r=3 = max 0, 12 163.627− 120 = 43.627. If we sort these displacements costs in ascending order and take the 2nd element (LE,π = 2), we find that LeftAtEndCostπ,B = 65 and disp disp lπ,B = max{65, min{188, 65}} = 65. Repeating this process to compute lπ,D , we find that: DispCostπ,D = 24.02, QuotaCostπ,D = 106.04, and LeftAtEndCostπ,D = disp 24.02. Consequently, lπ,D = 24.02. The overall displacement lower bound for π disp disp is the minimum of lπ,B and lπ,D , by Equation 11. Thus, lπdisp = 24.02. 3.3
New Pruning Methods
We introduce a dominance rule to maximise the portion of the alternate-outcome search space STV-26 can ignore. We say that node (l, π) is dominated by node (l′ , π ′ ) if l′ ≤ l and the prefixes have the same super-candidate relaxed representations, π̃ ≡ π̃ ′ . When deciding whether to add an (l, π) to our frontier, F , we check whether (l, π) is dominated by another node already in F , or one that we have expanded before. If so, we do not add it to the frontier. If we have seen an order, π ′ , with a given relaxed structure, π̃ ′ , in the past, and we see that structure again in order π, and we know the lower bound we attached to π ′ , l′ , is smaller or equal to the lower bound we have attached to π, l, then we know that the smallest lower bound we could find for any descendent of π ′ will be less than or equal to the smallest lower bound we could find for any descendent of π. The MINLP that we create when we add a given sequence of events π ∗ to the end of either π or π ′ will be the same. Moreover, the contribution of each elimination or election event to the evaluation of the bound is not dependent on the precise order of prior elimination subsequences.
4
Results
We report the performance and margin lower bounds obtained by STV-26 across ten 2-seat Australian Senate elections, four US-based 2-seat STV elections, two Irish STV elections of 3 and 4 seats, and 21 3- or 4-seat Glasgow city county elections from 2007. We treated each Australian Senate election as a WIGM contest for the purposes of this evaluation. Our results are in Table 3. The 2013–16 Australian Senate, Irish and Scottish contests were used to evaluate BST-19 in Blom et al. [2]. We use BST-19 to denote the results published in that paper, and BST-19∗ for results obtained using our re-implementation of their algorithm. We must emphasise that the original implementation (BST-19) was designed for a slightly different variant of STV (Australian Senate rules) and not for WIGM. The difference lies in how the transfer value for ballots distributed as part of a winner’s surplus is computed. There is no difference in transfer value computation for the first elected candidate across rule sets. The differences arises in any subsequent surplus transfer. The two variants do not result in different outcomes on any of the contests in Table 3, with candidates elected and eliminated in the same order, or substantially different tallies per
Advances in STV Margin Computation
15
Table 3: For STV elections with N winners, |C| candidates, |B| validly cast votes, and quota Q, we report: margin upper bound (UB), lower bounds by various methods, and their run times. BST-19 refers to results published by [2], and BST19∗ to results obtained by STV-26 without the algorithmic improvements (i.e., a modern implementation of BST-19). The best margin and time between STV-26 and BST-19∗ are in bold. A ‘**’ indicates that the 10ks limit was reached; and ‘–’ that no result was computed for that method. Elections where we computed the exact margin only with STV-26 are shown in bold. Margin LB Election
N |C|
|B|
Q
Australian Senate ACT’13 2 27 246742 82248 13391 ACT’16 2 22 254767 84923 18835 ACT’19 2 17 95749 90078 12939 ACT’22 2 23 285217 95073 11078 ACT’25 2 14 293474 97825 23121 NT’13 2 24 102027 34494 2298 NT’16 2 19 102027 34010 11244 NT’19 2 18 37869 35010 15890 NT’22 2 17 103617 34540 11412 NT’25 2 17 106807 35603 13256 Minneapolis, USA MN BET’09 2 7 MN BET’13 2 5 MN BET’17 2 4 MN BET’21 2 5
Time (sec)
UB BST-19 BST-19∗ STV-26 BST-19∗ STV-26
16727 10696 2098 23949 16286 6713 48163 23232 16863 42672 31876 2703
32 224 – – – 96 3105 – – –
80 2155 343 9162 1635 9933 85 319 12358 16722 212 2298 3120 7438 3563 9322 474 5092 958 5870
** ** ** ** ** ** ** ** ** **
** ** ** ** ** 1.12 ** ** ** **
– – – –
2097 6712 16863 2703
2098 6713 16863 2703
1.38 0.62 0.31 0.4
0.67 0.21 0.10 0.17
2002 Irish General Election Dublin N. 4 13 43942 8789 Dublin W. 3 9 29988 7498
211 366
189 260
211 366
211 366
165 6
174 8
2007 Glasgow City Council Linn 4 11 9567 Newlands 3 9 8654 Greater P. 4 9 8682 Craigton 4 10 11052 Govan 4 11 9560 Pollock–s 3 9 9567 Langside 3 8 2334 Southside C. 4 9 8738 Calton 3 10 5199 Anderston 4 9 6900 Hillhead 4 10 8984 Partick W. 4 9 12744 Garscadden 4 10 10160 Drumchapel 4 10 8680 Maryhill 4 8 9901 Canal 4 11 8624 Springburn 3 10 5410 East Centre 4 13 9078 Shettleston 4 11 8803 Baillieston 4 11 10376 North East 4 10 8363
218 88 237 75 309 3 233 229 376 99 105 193 396 443 321 126 528 139 353 105 421
114 78 147 38 145 3 223 187 118 93 59 185 172 253 223 98 74 65 136 65 251
218 85 235 72 309 3 233 224 364 99 105 193 396 443 321 125 505 134 270 104 420
218 85 235 72 309 3 233 224 364 99 105 193 396 443 321 125 528 134 353 104 420
287 2 67 6 2609 1 10 625 881 8 25 5 2310 3222 62 11 ** 2027 ** 8 813
82 2 11 6 468 2 5 172 54 7 40 4 642 319 26 10 441 488 6170 7 119
1914 2164 1737 2211 1913 2392 9334 1748 1300 1381 1797 2549 2033 1737 1981 1725 1353 1816 1761 2076 1673
16
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
round (≤ 10 votes). We expect that the margins for each contest under Senate and WIGM rules would likely be similar. In fact, WIGM and Senate rules are equivalent for 2-seat STV elections as only one surplus distribution is made. This means that tabulation of the Australian Senate and Minneapolis (MN) contests under WIGM and Senate rules is equivalent. The original results are included to give a sense of progress due to advances in solving technology, modern computational power, and improvements to the algorithm itself. All experiments were run on a server with 32 virtual CPUs and 128 GB of RAM. A 10,000s time limit was applied for each run of BST-19∗ and STV-26. Blom et al. [2] applied a 12-hour time limit when generating their results (BST19). All runs of BST-19∗ and STV-26 use parallelisation when expanding nodes on the frontier, expanding up to 30 nodes simultaneously.
5
Concluding Remarks
The improvements we have made to the STV margin lower bounding method of Blom et al. [2] have resulted in substantially tighter lower bounds for large realworld STV elections than previously computable. For smaller contests, including many of the non-Australian cases in our dataset, we are able to compute exact margins or near-exact lower bounds in substantially less time. The lower bounds we compute in these cases are sufficient for use in mismatch-based RLAs [3]. For example, for the NT 2022 election assuming a mismatch rate of 0.1%, a mismatch-based audit would require sampling on average about 55 ballots based on the STV-26 lower bound, but more than 1000 ballots based on the BST-19* one. If the mismatch rate was 1% then these numbers jump to 106 and almost 100,000 respectively. Further work is required to scale the method for use on large Australian Senate contests with hundreds of candidates and 6 to 12 seats.
References [1] 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) [2] Blom, M., Stuckey, P.J., Teague, V.J.: Toward computing the margin of victory in single transferable vote elections. INFORMS Journal on Computing 31(4), 636–653 (2019), Preprint: arXiv:1703.03511 [3] 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 Science, vol. 15754, pp. 241–255. Springer (2026), Preprint: arXiv:2503.16104 [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
A
17
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 differences mean that the bounds found with one version are not guaranteed to be valid in a different version.10 The margin lower bounding algorithm that we present in this paper is not reliant on the correctness of provided upper bounds. If the provided upper bound is less than the true margin, the algorithm will return a lower bound that is less than or equal to it. This is still a valid lower bound on the margin, although the algorithm may have been able to find a better lower bound with a valid initial upper bound.
B
Minimal manipulations MINLP
We present a MINLP designed to find a minimal manipulation of an STV election such that a specific partial or complete election order π is realised. This model assumes the use of Weighted Inclusive Gregory STV. We define a ballot type as a specific ranking over candidates that may appear on a cast ballot. B.1
Indices, Sets, Parameters
B
Ballots cast in the original election profile.
c, C
Candidates.
s, S
Ballot types (or signatures).
Ns
Number of ballots of type s ∈ S cast in the original election profile.
r, R
Rounds of tabulation.
L
Last round in which a candidate is either eliminated or elected to a seat with a quota in π.
Q
Quota.
Ar
The subset of candidates still standing at round r of π
S
Number of available seats.
B.2
Variables
All non-binary variables are continuous in this model. This is a slight relaxation.
10
For example, the lower-bounding algorithm uses floating-point values; the ConcreteSTV implementation uses fixed-precision decimals with 6 decimal places. This is unlikely to make any practical difference, but in principle it could.
18
Blom M, Ek A, Stuckey PJ, Teague V, Vukcevic D
ps
Number of ballots that are modified so that their new type is s ∈ S.
ms
Number of ballots whose original type is s ∈ S but have now been changed to a different type.
ys
Number of ballots of type s ∈ S cast in the new election profile.
vc,r
Tally of candidate c at the start of round r.
qc,r
Binary variable with value 1 iff the tally of candidate c at the start of round r is at least a quota, and 0 otherwise.
nqc,r
For convenience, we define a binary nqc,r whose value is 1 iff the tally of candidate c at the start of round r is less than a quota.
tr
Transfer value applied to ballots leaving an elected candidates’ tally in round r. These variables are only defined for rounds where a candidate has been seated after achieving a quota, and their ballots distributed at a reduced value.
B.3
Functions
For each candidate c, and round r of π, we define f (π, c, r) as returning a list of tuples (s, v, Caveats) where s denotes a ballot type, v denotes the value of each ballot of that type to c, assuming the conditions in Caveats hold, and Caveats a list of binary qc′ ,r′ and nqc′ ,r′ variables whose values must equal 1 for c to be awarded ballots of type s, each with value v, in round r. If a ballot moves from eliminated candidate to eliminated candidate before it reaches c in r, it’s value will be 1 (v = 1) and Caveats empty. For example, consider the ranking s = (A, B, C) and the order π = [(A, 0), (D, 0), (B, 0)]. The function f (π, C, 2) will return a set of tuples that includes (s, 1, []). If we know that a ballot will have formed part of one or more surplus transfers before it reaches c in r, then its value will equal the product of these transfer values. For example, consider the ranking s = (A, B, C) and the order π = [(A, 1), (D, 0), (B, 0)], in which A’s transfer value was 0.125. The function f (π, C, 2) will return a set of tuples that includes (s, 0.125, []). For the ranking s = (A, F, C) and order π = [(A, 1), (D, 0), (F, 1), (B, 0)], with A and F’s transfer values being 0.125 and 0.05, respectively, the function f (π, C, 3) will return a set of tuples that includes (s, 0.00625, []). Caveats will be non-empty in situations where the ballot could have skipped over an elected candidate c′ on it’s way to c, due to c′ already having a quota. For s = (A, F, C) and order π = [(A, 1), (F, 1), (B, 0)], with A and F ’s transfer values being 0.125 and 0.05, respectively, the function f (π, C, 2) will return a set of tuples that includes both (s, 0.00625, [nqF,1 ]) and (s, 0.125, [qF,1 ]). B.4
Objective
We minimise the number of ballots modified: X min ps s
(19)
Advances in STV Margin Computation
B.5
19
Constraints
The number of ballots cast of type s ∈ S in the manipulated election profile is equal to the number of ballots originally cast of that type (Ns ) in addition to the number of ballots of other types modified to have type s (ps ), minus the ballots of type s in the original profile changed to a different type (ms ).
X
ys = Ns + ps − ms X ps = ms
s
(20) (21)
s
For candidates c that are elected to a seat in π at a round r′ ≤ L: ∀r < r′
vc,r ≥ Qqc,r
(22)
vc,r ≤ (1 − qc,r )(Q − ϵ) + |B|qc,r
(23)
q
(24)
c,r ′
=1
For rounds r < L in which a candidate c is elected to a seat in π: tr vc,r = vc,r − Q
(25)
For candidates c that are eliminated in π at a round r ≤ L: vc,r ≤ Q − ϵ
(26) ′
vc,r ≤ vc′ ,r
∀c ∈ Ar \ {c}
(27)
The following constraints define the number of votes in the tally piles of each candidate c ∈ C at the start of each round r (vc,r ) for all rounds r where c ∈ Dr . X vc,0 = ys ∀c ∈ C (28) s
vc,r = vc,r−1 +
X (s,v,C)∈f (π,c,r−1)
v ys
Y x∈C
x
∀r ∈ [1, L], c ∈ Ar
(29)