Graph-Based Audits for Meek Single Transferable Vote Elections Edouard Heitzmann 1 Abstract In the context of election security, a Risk-Limiting Audit (RLA) is a statistical framework that uses a minimal partial recount of the ballots to guarantee that the results of the election were correctly reported. A generalized RLA framework has remained elusive for algorithmic election rules such as the Single Transferable Vote (STV) rule, because of the dependence of these rules on the chronology of eliminations and elections leading to the outcome of the election. This paper proposes a new graph-based approach to audit these algorithmic election rules, by considering the space of all possible sequences of elections and eliminations. If we fix a subgraph of this universal space ahead of the audit, a sufficient strategy is to verify statistically that the true election sequence does not leave the fixed subgraph. This makes for a flexible framework to audit these elections in a chronology-agnostic way. 1 1 footnotetext: Department of Mathematics, University of Colorado, Boulder edouard.heitzmann@colorado.edu 1 Introduction. Single Transferable Vote (STV) methods are a family of algorithmic tabulation rules used to run multi-winner elections. They are currently used for political elections at the City Council level in Scotland, Northern Ireland, some US cities, and some regions of New Zealand. They are further used for state- or national-level elections in Australia, Malta, and Ireland. There are many variants of STV, but all of them share the same underlying principle. They ask voters to fill out a full ranking over all candidates running for the m seats to fill. During tabulation, candidates are eliminated or elected one-by-one. At each stage in this tabulation, each vote counts for its highest-ranked candidate still in the running (so-called ‘hopeful’ candidates). Candidates are elected if they receive more than a pre-determined ‘quota’ of votes, in which case some weight of the votes that got them quota is removed (or ‘exhausted’) from the election. If no candidate makes quota, we eliminate the candidate with the fewest votes and transfer their votes onwards. STV has many desirable properties. It achieves proportional representation, in the sense that cohesive blocs of voters tend to be awarded a number of the m seats proportional to their bloc’s weight in the electorate. Unlike other proportional election rules, STV achieves this without requiring candidates to run with a partisan affiliation, which makes it suitable for non-partisan elections. As a multiwinner election method, it also has some natural insulation to gerrymandering. Finally, the turbulence of STV elections decreases the viability of strategic voting and incentivizes voters to represent their honest preferences. STV also has some drawbacks. Most of these drawbacks stem from its algorithmic nature, which makes it more complicated than other typical voting methods. This increases voter burden and makes election outcomes difficult to communicate, which can in turn lower trust in election outcomes. Algorithmic complexity also makes STV susceptible to pathologies like the so-called monotonicity, reinforcement, or no-show paradoxes – see for example 8 . These pathologies all point to the higher fragility of outcomes under STV: perturbing a small number of votes can have a big impact in an STV election. This is also what makes STV harder to audit than other election rules. A Risk Limiting Audit (RLA) of an election is, informally, a randomized partial recount of the physical ballots that gives some statistical guarantee that the outcome of the election was correctly reported. They are a way to make elections more secure while avoiding the high cost of doing a full hand recount of the election. Typically this is done by comparing the sampled ballots against their digital Cast Vote Records (CVRs), and checking that the discrepancy levels among sampled ballots would not be sufficient to overturn the reported margins of the election. The common wisdom is that audits are harder for STV because more rounds means more margins to audit. If we seek confidence about the exact chronology of the election – every elimination and election from start to finish, as well as their timing – there are more opportunities for decisions to hinge on razor-sharp margins, making the election unauditable. However, if we only seek confidence about the outcome of the election – who won and who lost, without any details about the specific sequence that led to this outcome – we find that much of this chronology can be overlooked, as it bears no impact on the outcome. To illustrate this point, consider District 1 of the 2024 Portland City Council election, which was a 3-seat STV contest 2 2 2 The tabulation for this election is available here . . In Round 6 of this election, candidates David Linn and Peggy Sue Owens were tied for last place with 1,141 first-place votes each, or 3.36% of the ballots cast. If we wished to certify the exact chronology of this election, we would certainly have to perform a full recount to audit this margin of 0 votes. However, we find that which of these two candidates we choose to eliminate first has no bearing on the big picture of this election, since the second candidate is certain to be eliminated next (or, as we will find, before Round 9 of the election – cf. Appendix A ). But formalizing this insight mathematically is tricky. A further complication for these chronology-agnostic audits comes from the fact that in most variants of STV, the timing of a winner’s election has an impact on subsequent Rounds of the election. If it does not matter whether we eliminate candidate A or B first, it does usually matter which of them is eliminated by the time C gets elected. This explains why a generalized STV auditing framework remains elusive, despite the success of the RAIRE framework for auditing single-winner STV contests in a chronology-agnostic way – see 4 . In developing this generalization, we show that not all variants of STV are equally suited to the task. We find that the Meek variant, being chronology-independent by definition, is more naturally auditable than the more commonly-used Weighted Inclusive Gregory Method (WIGM). That being said, the graph-based approach we develop for Meek STV can and should also be applied to more traditional variants of STV. The high-level picture of the graph-based approach we propose is to consider the space \Omega of all possible sequences of elections and eliminations the election could follow. We pre-emptively carve out a subgraph G\subseteq\Omega , and we statistically verify that the true election path never leaves this subgraph G . As long as all the winner sets contained in the ‘bottom-line’ of G are the same as the reported one, this verifies the election result. We formalize the Experimental Design of this framework in Section 2.1 , after justifying our comparison between Meek and WIGM STV below. 1.1 A Helpful Case Study. Meek and WIGM STV most often produce the same winner set given a fixed set of ballots – they are, after all, variants of the same rule. To illustrate the difference between the two, we will focus on an example where this is not the case, to understand the root causes of their disagreement. We emphasize that such a disagreement is the exception, not the rule, for these two variants. One such example is the 2012 election in Ward 9 (Almond and Earn) of the Perth Kinross Councilmember election in Scotland. In this election, N=3,689 voters cast ballots to elect m=3 City Councilors using the WIGM variant of STV. In this variant, the quota of votes a candidate must receive to get elected is calculated using the Droop formula: q=\left\lfloor\frac{N}{m+1}\right\rfloor+1=923. When a candidate’s tally T does exceed quota, the votes that got them there are re-weighted using a fractional transfer value \tau , which is calculated so as to make sure a quota’s worth of votes is removed from the election, as follows: \tau=\frac{T-q}{T}. For example, in Round 1 of our case study election, Alan Livingstone received T=1,112 first-place votes, so his transfer value was \tau=189/1,112\approx 0.17 . Of the ballots that listed Livingstone as their first preference, 290 listed Alan Jack as their next preference, so Jack received a weight of around 290\cdot 0.17=49.3 ballots as a result of Livingstone’s election. Crucially, in WIGM STV, this transfer process happens exactly once, and the transfer value is fixed for the rest of the election. In future rounds, if a ballot would transfer from another candidate to Livingstone, it instead goes straight to its next preference, or it is exhausted if none are specified, but Livingstone’s transfer value is not recalculated. This is what we mean when we say WIGM STV is chronology-dependent: it matters which candidates were still in the running when Livingstone was elected. The full tabulation for the rest of the election is below: Round 1 Round 2 Round 3 Round 4 Round 5 Round 6 Alan Livingstone 1112 Elected Elected Elected Elected Elected Henry Anderson 892 900.67 923.37 Elected Elected Elected Alan Jack 444 493.29 596.93 596.96 770.62 986.97 Wilma Lumsden 628 640.41 670.96 671.23 756.43 Eliminated Andrew Dundas 369 381.24 450.7 450.73 Eliminated Eliminated George Hayton 244 284.28 Eliminated Eliminated Eliminated Eliminated Quota 923 923 923 923 923 923 Table 1 : The tally breakdown in the 2012 Perth Kinross Ward 9 election, as it occurred in reality. This election is peculiar in two ways: firstly, Henry Anderson is elected by a razor sharp margin of 0.37 votes in Round 3, and secondly, Wilma Lumsden narrowly loses to Alan Jack in Round 5 by a margin of 14.19 votes. As it turns out, Anderson and Lumsden were both candidates from the Scottish National Party (SNP), meaning that many voters who listed one candidate also listed the other. Of Anderson’s surplus of 0.37 votes, 0.27 transfers to Lumsden – around 73%! In Round 4, Andrew Dundas is eliminated. Of the votes he transfers onwards, 85.2 transfer to Lumsden, and 173.65 go to Jack. Of the remaining weight of 191.87 votes in Dundas’ pile, an additional 39.51 would have listed Anderson as their next preference, but do not mention Lumsden. According to the WIGM rules of STV, those votes are exhausted from the election, since Anderson is already elected, and his transfer value does not change. This makes the election very unstable – if Anderson’s tally had 0.37 fewer votes in Round 3, those 39.51 votes would have transferred through Anderson before exhausting (along with an additional 35.34 votes that listed Anderson and then Lumsden), pushing Anderson’s transfer value high enough that Lumsden would now edge out Jack in Round 5 of the election. This can be realized in a number of ways: 1. As a monotonicity paradox: by replacing one vote (\text{Henry Anderson},\text{Alan Jack})\rightarrow(\text{Alan Jack},\text{Henry Anderson}), we would be increasing the strength of the profile’s support for Jack in a way that loses him the election. 2. As a failure of the Independence of Irrelevant Alternatives axiom: by replacing a single bullet vote (\text{Henry Anderson})\rightarrow(\text{George Hayton}), we would not be changing any of the profile’s comparisons between Lumsden and Jack, yet the outcome’s comparison between these candidates would change (Lumsden would now beat Jack). 3. As a no-show paradox: if a single voter (\text{Henry Anderson},\text{Wilma Lumsden}) had decided not to cast her vote in the election, Lumsden (one of her preferred candidates) would have been elected. Indeed, up to 18 such voters (out of 646 recorded) could have abstained while still preserving that outcome. The change caused by these three perturbations is the same – even though fewer votes transfer from Dundas to the Anderson-Lumsden slate than to Jack, the “lost” weight of 39.51 gets to transfer into the slate with this new elimination order; and even though these votes only listed Anderson and not Lumsden (indicating a non-solid coalition), this difference is enough to overcome the 14.19 vote margin that Lumsden was losing by. It is normatively nebulous to say that Lumsden “deserved” to win more than Jack in this election. Both candidates were competitive, and the election was sharp – in most of the alternate elimination orders that lead to Lumsden winning under WIGM rules, she only beats Jack by a margin of \sim 9.5 votes. But it is fair to say that the timing of his election was cruel to Anderson in this case: through no fault of his own, Anderson was elected with a minuscule surplus, which disenfranchised over 39.51 voters who would have ranked him later on, and diminished the next preferences of the votes that got him quota. The rules of Meek STV were designed to address exactly this scenario. At a high level, Meek changes two rules compared to WIGM: it allows winners to receive votes even after the Round of their election, in which case they increase their transfer value, and it re-calculates quota every round, lowering it when votes are exhausted because they list no further preference in the election. Because of the former difference, the 39.51 votes we mentioned still get added to Anderson’s pile, even after he has attained quota, and Anderson gets to increase his transfer value. Even though the new 39.51 votes do not list Lumsden as their next preference, a rising tide lifts all boats, and the rest of Anderson’s pile gets to transfer with an increased weight to Lumsden. The result of re-tabulating the same election using the Meek rule is shown in Table 2 . Round 1 Round 2 Round 3 Round 4 Round 5 Alan Livingstone 1112.00 ✓ 904.07 ✓ 885.12 ✓ 884.13 ✓ 833.50 ✓ Henry Anderson 892.00 901.54 926.30 ✓ 884.13 ✓ 833.50 ✓ Alan Jack 444.00 498.23 608.11 612.87 810.07 Wilma Lumsden 628.00 641.65 674.34 705.24 856.94 ✓ Andrew Dundas 369.00 382.46 446.60 450.16 Eliminated George Hayton 244.00 288.32 Eliminated Eliminated Eliminated Quota 922.25 904.07 885.12 884.13 833.50 Table 2 : The Ward 9 election tally breakdown under Meek STV. A happy side-effect is that the Meek election is a lot more resilient to perturbation: if we allow perturbations of less than 40 votes’ worth of weight, the only real point of uncertainty is whether Anderson should have been elected in Round 2 or Round 3 – but whichever round the election occurs in, the other round will result in the elimination of George Hayton, such that both branches converge back to the same election state before Round 4 . We begin to formalize this notion of stability with the construction of ‘audit graphs’ in Figure 1 . 1 2 3a 3b 4 5 6 Elect Alan Livingstone Elect Henry Anderson Eliminate George Hayton Eliminate George Hayton Elect Henry Anderson Eliminate Andrew Dundas Elect Wilma Lumsden (a) The audit graph using Meek rules. 1 2 3a 3b 4a 4b 5a 5b 6a 6b Elect Alan Livingstone Elect Henry Anderson Eliminate George Hayton Eliminate George Hayton Elect Henry Anderson Eliminate Andrew Dundas Eliminate Andrew Dundas Elect Alan Jack Elect Wilma Lumsden (b) The audit graph using WIGM rules. Figure 1 : The audit graphs for an auditable margin of 40 votes in Ward 9. Starting with the ‘election state’ (H,W)=(C,\varnothing) in vertex 1 , we draw an edge to every election state (H,W) we might plausibly encounter in the next round of the election if the recorded tallies (the so-called ‘Cast Vote Records,’ or CVRs) were off by at most 40 votes, repeating this process until we end up at nodes with complete winner sets. If all vertices in the last layer of the resulting graph G have the same winner set, then a valid strategy to audit the election would be to reject the global null hypothesis \mathcal{H}_{\star}= “The true election order leaves the graph G .” If we can reject \mathcal{H}_{\star} , we might not know exactly which path the true election takes from node to the last layer of the graph, but we know that every such path leads to the same winner set, confirming the result of the election. The audit graphs in Figure 1 demonstrate that the Meek rule is more stable than WIGM in this case. Despite having the same sets of elected winners and hopeful candidates, the election states represented by nodes and in Figure 1(b) must be considered distinct, since Anderson has a lower transfer value in the former than the latter. By contrast, the edges leaving nodes and in Figure 1(a) can truly be considered to lead to the same election state, since whichever path we take to node will result in the same calibrated transfer values. Hence this is an example of an election which is unauditable under WIGM rules (since 0.37 of a vote can change the outcome of the election, a full recount will surely be necessary), but which is auditable under Meek rules, where the sharpest margin to audit is the 46.87 vote margin between Lumsden and Jack in the last round of the election. Of course, there are other profiles where Meek will be unauditable for other reasons (and WIGM might be auditable in some of these profiles); but this example illustrates that uncertain election chronology poses a problem in WIGM audits, whereas it does not in Meek. 1.2 Mathematical Formalism. The STV rules are algorithmic processes to determine a committee of m winners from a set of C=[M]=\{0,1,\ldots,M-1\} candidates, by consulting a preference profile P containing the ranked choice votes (or just rankings ) of a set of voters [N]=\{0,1,\ldots,N-1\} . We define these mathematically as follows: Definition 1.1 . (Rankings, Profiles.) • Given L\in\mathbb{N} and a subset of “hopeful” candidates H\subseteq C , an \boldsymbol{L}\textbf{-ranking} of candidates H is an injective map r\colon[L]\hookrightarrow H. We allow L=0 , in which case [L]=\varnothing , and the only ranking r:\varnothing\to H is the empty ranking r=\varnothing ; this corresponds to a vote which indicated no preferences in H . • We denote the set of all rankings of candidates H\subseteq C by R_{H} : R_{H}\vcentcolon=\{r\colon[L]\hookrightarrow H\mid 0\leq L\leq|H|\}. • For H\subseteq C , the length map \mathsf{len}\colon R_{H}\to[|H|+1] maps each r to the integer L such that r is an L- ranking; formally, \mathsf{len}(r)=|r|. • A profile P on candidates H can be thought of as a multiset of rankings, or as a map P\colon R_{H}\to\mathbb{N} , or as a point in an |R_{H}|- dimensional simplex. In the context of auditing, it will be useful for these profiles to be ordered, so we formally define a profile on candidates H\subseteq C as a map P\colon[N]\to R_{H}. • When the number of voters N>0 is clear, we denote the set of all profiles on candidates H by \mathscr{P}_{H}=\{P\colon[N]\to R_{H}\} , or just \mathscr{P} when H is also clear. Given a ranking r\in R_{C} , we think of r(0) as the most preferred candidate of r , then r(1) as its second-most preferred, etc. In this formalism, the STV rules can be thought of as maps \mathscr{P}_{C}\to\{W\subseteq C:|W|=m\} . These rules are algorithmic: starting from the full candidate set C , it iteratively elects or eliminates one candidate at a time, until m candidates have been elected. One advantage of the Meek rule is that it can be described using elimination rounds only – election rounds are not necessary. In this framework, given a fixed profile P , we can view the Meek rule as a monotone decreasing map \mathcal{R}_{P}\colon\{H\subseteq C:|H|>m\}\to\mathcal{P}(C)\;\text{ such that }\;\mathcal{R}_{P}(H)\subseteq H\;\text{ and }\;|\mathcal{R}_{P}(H)|=|H|-1, where \mathcal{P}(C) is the power set of C . Then the winner set under a profile P on candidates C=[M] is defined as W=\mathcal{R}_{P}^{M-m}(C). Before we can describe the STV rules mathematically, we need to establish how to project a profile of rankings onto a set of remaining hopeful candidates H\subseteq C . This works as one might expect: to project a ranking r\in R_{H} onto H^{\prime} , we ‘erase’ the positions in r that list candidates not in H^{\prime} , and ‘shift’ all the remaining positions to fill any empty positions. Definition 1.2 . (Projection onto hopeful candidates, first-place vote map.) For fixed sets of hopeful candidates H^{\prime}\subseteq H\subseteq C , given an L -ranking r\in R_{H} such that |r([L])\cap H^{\prime}|=L^{\prime} , we define the shift map of r as the unique increasing injection J_{r}\colon[L^{\prime}]\hookrightarrow[L]\;\text{ such that }\;r\circ J_{r}([L^{\prime}])\subseteq H^{\prime}. In the same setting, we define the ranking projection map \pi_{H^{\prime}}\colon R_{H}\to R_{H^{\prime}} by \pi_{H^{\prime}}(r)=r\circ J_{r}. Further, the projection onto \boldsymbol{H^{\prime}} of a profile P\in\mathscr{P}_{H} is defined as \pi_{H^{\prime}}\circ P\in\mathscr{P}_{H^{\prime}}. Finally, it will be useful to define the first place vote map \mathsf{fpv}_{H}\colon R_{C}\to H\cup\{-1\} as \mathsf{fpv}_{H}(r)=\begin{cases}\big(\pi_{H}(r)\big)(0)&\;\text{ if }\;\pi_{H}(r)\neq\varnothing\\ -1&\;\text{ if }\;\pi_{H}(r)=\varnothing.\end{cases} We are presently equipped to describe the STV rules. The WIGM (again, Weighted Inclusive Gregory Method) Rule has seen wide enough use to be considered a piece of folklore; its genealogy seems to go back to 1880, although the first record of it appears in 10 , where it is attributed to one ‘Mr. J. B. Gregory of Melbourne.’ WIGM is notorious for having as many variants as there are governments that use it – some calculate transfer values differently, or handle simultaneous elections differently, or calculate quota differently, etc. We formalize the version of WIGM we will henceforth refer to below. Algorithm 1.3 . (The WIGM Rule.) Given a profile P\in\mathscr{P}_{C} of N voters with the additional constraint that P(i)\neq\varnothing\;\forall\;0\leq i\leq N-1 (i.e. each voter indicates a preference among the initial candidates C ), the WIGM rule for \boldsymbol{m} seats iterates through the following steps to find a winner set W\subseteq C : 0 Calculate the so-called Droop quota q for this election as q=\left\lfloor\frac{N}{m+1}\right\rfloor+1. Further initialize the set of winners as W=\varnothing , the set of hopeful candidates as H=C , and define the initial voter weight map w_{0}\colon[N]\to[0,1] as the constant map w_{0}(i)=1\;\forall\;i\in[N] . Then, start iterating the following steps with j=0 . 1 If |H\cup W|=m , the algorithm is complete, and the winner set is H\cup W . 2 For each c\in H , define S_{c}=\{i\in[N]:\mathsf{fpv}_{H}(P(i))=c\} . Calculate this round’s tallies T_{j}\colon H\to\mathbb{R}^{+} as T_{j}(c)=\sum_{i\in S_{c}}w_{j}(i). 3 If any of the hopeful tallies are at or above quota, this is an election round: go to step 3a . Otherwise, this is an elimination round: go to step 3b . 3a let c be the candidate with the highest 2 2 footnotemark: 2 tally above quota, i.e. c is such that T_{j}(c)\geq T_{j}(i)\;\forall\;i\in H\;\text{ and }\;T_{j}(c)\geq q. Calculate the transfer value \tau_{c} of this winner as \tau_{c}=\frac{T_{j}(c)-q}{T_{j}(c)}. Use this transfer value to update the voter weight map for the next round: w_{j+1}(i)=\begin{cases}\tau_{c}\cdot w_{j}(i)&\;\text{ if }\;i\in S_{c};\\ w_{j}(i)&\;\text{ otherwise. }\end{cases} Finally, remove c from H and add her to W , then increment j and return to step 1 . 3b let \ell be the hopeful candidate with the lowest 3 3 3 If there are multiple such \ell , break the tie in a reproducible way, e.g. by picking the smallest such index (a so-called ‘lexicographic’ tiebreak). tally, i.e. \ell\in H is such that T_{j}(\ell)\leq T_{j}(i)\;\forall\;i\in H. Finally remove \ell from H , increment j , and return to step 1 , using the same voter weight map w_{j+1}=w_{j}. Before we formally define the Meek Rule, let us highlight its main differences compared to WIGM, to draw a contrast: • Meek uses so-called ‘keep factors’ k instead of transfer values \tau . If nothing else was different about Meek, we could think of these as just the complement of the transfer values: k=1-\tau . • In Meek, winners are allowed to receive transfers, even after the round of their election. When this happens, the winner re-calculates her keep factor from scratch, lowering it to adjust her tally (including the new votes she received) at exactly the current value of quota. • We also re-calculate quota every round in Meek – unlike WIGM, this value is not fixed at the start of the election. When ballots exhaust from the election (i.e. all preferences on the ballot are either elected or eliminated, but the vote still carries the weight), we treat the remaining weight of the ballot as though it did not figure in the total ballot weight used to calculate Droop quota, hence quota lowers. • Because of situations where multiple seated winners transfer ballots to each other, or situations where decreasing the value of quota causes new votes to exhaust, the first round of keep factor calculations often does not calibrate the tallies of all winners at the value of current quota – quota either lowers after new votes are exhausted from winner tallies, or winner tallies increase above quota after receiving votes from other winners. Because of this, we use a recursive process which re-calculates keep factors iteratively until winner tallies have ‘converged’ to quota in a well-defined sense. Algorithm 1.4 . (The Meek rule.) Given a profile P\in\mathscr{P}_{C} of N voters, a minimum surplus \varepsilon , and a tolerance \omega (usually both set to \varepsilon,\omega=10^{-6} ), the Meek rule for \boldsymbol{m} seats iterates through the following steps to find a winner set W\subseteq C : 0 Start by setting H=C . 1 Let P_{H}=\pi_{H}\circ P . 2 Initialize the first set of keep factors k_{0}\colon H\to(0,1] as the constant map k_{0}(c)=1,\>\forall\>c\in H . Then, iterate through the following steps (starting with j=0 ) to calibrate the keep factors: 2a Let V be the |H| -dimensional real vector space with basis \{{\vec{e}}_{c}\}_{c\in H} . Define this iteration’s weight vector map w_{j}\colon R_{H}\to V by w_{j}(r)=\sum_{i=0}^{\mathsf{len}(r)-1}k_{j}(r(i))\left(\prod_{l=0}^{i-1}\big(1-k_{j}(r(l)\big)\right){\vec{e}}_{r(i)}. N.b.: depending on the keep factors k_{j} and the ranking r , the total weight \sum_{i\in H}\big(w(r)\big)(i) may be smaller than 1 ! Some or all of the weight of r might be exhausted ; e.g., if r=\varnothing has no preferences, then w(r)=\vec{0} . 2b Define this iteration’s tallies T_{j}\in V as T_{j}=\sum_{i=0}^{N-1}w_{j}\circ P(i). 2c Calculate this iteration’s quota q_{j}\in\mathbb{R} as q_{j}=\frac{\sum_{i\in H}T_{j}(i)}{m+1}+\varepsilon. 2d Break out of this loop if all of the tallies in T_{j} are less than tolerance \omega above quota, i.e. if \max_{i\in H}(T_{j}(i)-q_{j})<\omega. In this case, go to step 3 ; otherwise, proceed with step 2e . 2e Calculate the next iteration’s keep factors k_{j+1}\colon H\to(0,1] as follows: k_{j+1}(i)=k_{j}(i)\cdot\min\left(1,\frac{q_{j}}{T_{j}(i)}\right). Then, increment j and return to step 2a . 3 Let \ell\in H be the index of the lowest 4 4 4 Again, breaking ties in a consistent way, e.g. lexicographically. tally in the last iteration of tallies T_{j} from the loop in 2 ; i.e. \ell is such that T_{j}(\ell)\leq T_{j}(i)\;\forall\;i\in H. Define H^{\prime}=\mathcal{R}_{P}(H)=H\backslash\{\ell\} . If |H^{\prime}|=m , the algorithm is complete and W=H^{\prime} are the winners of the election. Otherwise, return to step 1 , setting H=H^{\prime} . It is worth noting that when Meek is used in actual elections, it is typical to distinguish candidates c as winners the first time their keep factor k(c) dips below 1 , unlike the version of the algorithm we describe. In such an election round it is common to break out of the loop in step 2 as soon as a new candidate is detected above quota. This has the effect of making the tallies T(i) look like they weren’t fully calibrated at quota (since we ended the iteration before the keep factors converged); but mathematically speaking this will always produce the same effect as our version of the algorithm, because in the next round of the election we would begin calibrating the keep factors from scratch at 1 . The Meek rule was originally outlined in 12 , and its algorithmic properties – in particular, the convergence of step 2 – were further studied in 9 . The last notion we should formalize is that of a Ballot-Comparison Risk-Limiting Audit (RLA) . In the real-world setting, elections are often tabulated by applying the election rule to a digital Cast Vote Record (CVR) of the paper ballots. We consider this profile to be a noisy approximation of the true preference profile, which is recorded in the paper ballots cast by the voters in the election; noise can be introduced by scanning or transcription errors, by interference, or by miscommunication of intent. Usually, doing a full recount of this true profile is expensive, so it is preferable instead to construct a series of statistical assertions about it that can be verified by looking at a small sample of paper ballots to confirm the result of the election. Definition 1.5 . (Risk-Limiting Audits.) We define an election as a pair of profiles on candidates C with the same number N of voters, \text{BAL},\text{CVR}\in\mathscr{P} . The noise level of this election is defined as \eta=\frac{|\{0\leq ii\} , then the true process should end in vertex 10b (i.e. H_{\star} would be true), but each of the dashed edges along the path to 10b gets rejected by the RLA with probability 0.039 . Therefore \mathbb{P}(R_{\star}\mid P\in\mathscr{P}_{0})\approx 1-(1-0.039)^{9}\approx 0.3\leq 9\alpha=0.351. This is verified computationally in the second row of Table 3 , under the ‘Naive Design’ entry. There are several ways that we could fix this experimental design to test H_{\star} at level \alpha : 1. We could set lower risk levels \alpha_{i} for each of the H_{i} , such that \sum_{1\leq i\leq 9}\alpha_{i}=\alpha . In the above setting, we might raise the bar to reject H_{i} as long as \pi_{i}\leq 10 , which happens with probability 0.004 when P_{i}=200 . The cost of this is a more conservative test: we end up failing to reject H_{\star} more often, even when it is false. The results of this test when P is taken from \mathscr{P}_{0} are also in Table 3 , under ‘Risk-Budgeted Design.’ 2. We could also choose to audit a single one of the 9 edges on the path from node 1b to 10b at level \alpha . This amounts to the same idea as solution 1., where we set all but one of the \alpha_{i} equal to 0 ; if we do not audit an edge, we also do not introduce a risk of making a Type I error. For example, if the only edge we choose to audit is the one connecting 1b to 2b , then we are back in the setting where we can apply Proposition 2.1 , with the subgraph G made up of nodes 1 b, 2 a, \ldots , 10 a, and \partial G=\{(1\text{b},2\text{b})\} . We show the result of this approach in the last row of table 3 . 3. Alternatively, we could flip the script, and define H_{\star} as the statement “The process ends at vertex 10a ” instead. In this setting we could apply Proposition 2.1 with the subgraph G made up of nodes 1 b, \ldots , 10 b, and our set of local nulls to reject would contain one assertion for each of the edges that aren’t dashed in Figure 3 . This is statistically equivalent, for this example, to the approach in 2. Example Design Used Trials Number of Type I Errors Empirical Risk Level 2.3 Proposition 2.1 50000 0 0.000000 2.4 Naive Design 50000 15035 0.300700 2.4 Risk-Budgeted Design 50000 1757 0.035140 2.4 Proposition 2.1 50000 1959 0.039180 Table 3 : Computational Verification of the Risk Level for Examples 2.3 and 2.4 Examples 2.3 and 2.4 suggest the following rule of thumb to determine when a rejection rule R_{\star} for H_{\star} is designed correctly. If H_{\star} was true but R_{\star} rejected it, then the true process corresponding to P must have followed a deterministic path leaving G . If we can point to at least one single edge {\vec{e}} along this path whose local hypothesis H_{\vec{e}} was definitely rejected at level \alpha as a part of R_{\star} , then the audit was correctly constructed, and we just made a legitimate Type-I error. Otherwise, if there are multiple such edges along the path, and it is not clear which of their local hypotheses was rejected at level \alpha as a part of R_{\star} , then we have failed to adequately allocate our risk level \alpha . 2.2 Variance Bounds for Sparse Samples. The actual parameters we end up sampling for our audits, when we project them onto our local nulls, end up looking a lot like the previous examples; they are functions of the means of (almost) coin flips with a low success rate p . When the sample size n and the success rate p are both small, we will see sparse samples where the sample variance may not be an accurate approximation of the true variance. The common rule of thumb for such a case is to require np(1-p)\gg 1 ; in our implementations we will stay on the safer side and only use the sample variance when our sample shows more than 20 non-zero entries (which rarely happens). When we run into sparse samples, we will fall back on a hypergeometric bound for variance. In the hypergeometric setting, we have a population of N items, K of which record a ‘success event’ – in our setting, a ballot comparison discrepancy. We sample n of these items without replacement, and we let X be the number of successes in our sample. The hypergeometric distribution tells us \mathbb{P}(X=k)=\frac{{K\choose k}{{N-K}\choose{n-k}}}{{{N}\choose{n}}}. (1) When K is unknown but we have recorded a sample of size n with k successes, we can use this distribution function to build a one-sided confidence interval for K ; we will follow a procedure called ‘pivoting the cdf,’ stated generally in Theorem 9.2.2 of 5 . 1 also explores this method as applied to hypergeometric variables specifically; the exact method we use is outlined at the start of their Section 6. We re-state a version of this Theorem 9.2.2 below, then apply it in our previous context: Theorem 2.5. (Casella and Berger.) For each \theta_{0}\in\Theta , let A(\theta_{0}) be the acceptance region of a level \alpha test of \mathcal{H}_{0}\colon\theta=\theta_{0} . For each x\in\mathcal{X} , define a set C(x) in the parameter space by C(x)=\{\theta_{0}\colon x\in A(\theta_{0})\}. Then the random set C(x) is a 1-\alpha confidence set. In our case, the parameter space \Theta=[N+1] corresponds to the possible values of \theta=K , the sample space \mathcal{X}=[n+1] corresponds to our recorded number of successes X in our sample of size n , our null hypotheses are \mathcal{H}_{0}\colon K=K_{0} , our alternative hypotheses are \mathcal{H}_{1}\colon K0 ” is a success, and find a hypergeometric bound K on the number of successes for Y , using all of the allocated risk \alpha_{K} . Then, use the same bound on variance it induces for each of the X_{i} . That is to say, in the worst case, the number of successes in the population for each individual X_{i} is bounded above by the number of successes in the population for any of the compilers at all, and the variance bound follows. 3. We could also do something similar to 2., but with Y corresponding to the event “there is a ballot-comparison discrepancy (not necessarily detected by the assorters X_{i} ).” This would make for worst bounds on variance, but it has the advantage of being re-useable across every local null we have to reject. In practice, we end up using option 2. for our implementation. This avoids further breaking \alpha_{K} into small pieces, at a cost for the sharpness of the resulting bound. In some cases, the sampled X_{i} might be 0 , whereas Y can be greater than 20 . It is very plausible that option 1. will be more competitive in the long run, but deciding how to budget the risk \alpha_{K} among all of the X_{i} will be a problem of some complexity. To be optimal, a solution would have to look at the expected scales of the X_{i} and their impact on the overall margin. A good reference for this approach of budgeting risk as a function of the expected outcome is 6 . 2.3 Audit Graphs. In view of the approach we outline to audit algorithmic election rules in Section 2.1 , we had better formalize the graph \Omega and the Meek rule \mathcal{R}_{P} we will use to traverse it. Let the set of candidates C=[M] and the number of seats to fill m\in\mathbb{N} be fixed. Definition 2.6 . A depth- \boldsymbol{t} election state is an ordered pair of subsets (H,W)\in\mathcal{P}(C)^{2} such that H\cap W=\varnothing , |W|\leq m , and |C-H|=t . We call H the set of hopeful candidates in the state, and we call W the set of elected winners . The degree of an election state is \mathsf{deg}(H,W)=|W| . The projection map onto an election state S=(H,W) is \pi_{S}\colon R_{C}\to R_{H\cup W} defined as \pi_{S}=\pi_{H\cup W} . The universal audit graph \Omega is a directed layered graph whose vertex set is the set of all depth- t election states, for 0\leq t\leq M-m . The root of \Omega is the election state (C,\varnothing) . Layer t of \Omega contains all possible election states of depth t . We draw an edge from vertex S=(H,W) to S^{\prime}=(H^{\prime},W^{\prime}) when: • H^{\prime}\subseteq H , • W\subseteq W^{\prime}\subseteq W\cup H , and • |(W^{\prime}-W)\cup(H-H^{\prime})|=1 . When the single element c in this set is an element of W^{\prime}-W , we call the edge (S,S^{\prime}) a winner edge ; note in this case that c\notin H^{\prime} , by the definition of election states. Otherwise, when c\notin W^{\prime} , we must therefore have c\in H-H^{\prime} , and we call the edge (S,S^{\prime}) a loser edge . When it is known whether the edge {\vec{e}}=(S,S^{\prime}) is a winner or loser edge, we sometimes use the notation {\vec{e}}=(S,c) to emphasize the candidate c that gets elected/eliminated in this edge. Finally, we define an audit graph as any connected subgraph G\subseteq\Omega which contains the root of \Omega , as well as at least one depth M-m election state S . We call the graph coherent when any two election states in G coming from that layer have the same winner set. In view of the discussion under Algorithm 1.4 , we might question the decision to include winner edges in the construction of audit graphs at all. There is one convenient reason to do so, and another more necessary. First, including winner edges makes this construction more general – we will need fewer modificiations to apply this framework to the WIGM rule, where election rounds are truly necessary. The second, more serious reason to track winners as part of the election states is that we need to generalize the Meek rule to apply to every vertex in \Omega in such a way that the keep factors k(i) are auditable in every round. In order to calculate variances for the magins between candidates, we will want exact mathematical formulas for the limiting keep factors that the iterative process in step 2 of Algorithm 1.4 converges to. This is possible, but only as long as the set of current winners is known. So, we will define a generalized Meek rule that takes in a prescribed set of winners W\subseteq C as part of its input, and calculates keep factors only for those candidates using the exact formulas. One awkward consequence of this approach is that occasionally the audit graph will contain election states S=(H,W) where some of the winners in W don’t actually make quota in state S according to the CVR. For example, vertex 3a of the audit graph in Figure 1(a) of our case study represents an election state where Henry Anderson is in the winner set W , despite the CVR recording his final tally as 901.54 in that round, whereas quota was 904.07 . The prescription of Meek rule as defined in 1.4 in such a case would simply be to truncate the keep factor of Anderson at 1 . But again, this is not a statistically viable option for us, because the variances we obtain by using the exact keep factor formulas only apply at the actual solution of those polynomials. Instead, we opt to use an ‘extended Meek rule’ which uses the exact formulas to calculate keep factors no matter what – even when the solved keep factors end up above 1 (which happens in so-called ‘irregular’ election states). This can look quite irregular indeed! When a winner has a keep factor above 1 , they effectively ‘steal’ votes out of the tallies of candidates down-ballot from their \mathsf{fpv} (‘first place vote’) ballots. If those \mathsf{fpv} votes exhaust after ranking the winner, they exhaust with a negative weight, thus artificially inflating the number of votes in the election, and quota by extension. In some particularly pathological election states with multiple ‘fake winners,’ the keep factors can blow up to +\infty ! Although in practice our audit graphs will usually stay quite far away from the parts of \Omega where this can happen. The keep factors we will run across only occasionally go above 1.05 , and rarely above 1.1 . Our mathematical argument in this case is the following: such a state is irregular according to the CVR, and may or may not be so according to the true profile BAL. If it was also irregular according to BAL, then we know for sure that the true Meek process will never visit that state in the audit graph, so whatever edges our auditing process allow to leave from that irregular state just make the audit more conservative; we are giving ourselves more work, not less, by considering this irregular state. If the state was not irregular according to BAL, then the solutions to the exact keep factor equations should be non-singular in a neighborhood of BAL, which our sampled parameters will get us into, so that our estimates of margin variances should hold. We should spare a word as well for how we construct the audit graphs G we end up using for our audits; even if this process is of no importance for the actual statistical framework we apply to it (we might as well treat G as provided by a third party), it might still be of interest as a general-purpose construction. What we do is that we fix a ‘Least Auditable Margin’ \text{LAM}\in\mathbb{N} , which we think of as the smallest margin we feel confident we would be able to audit with the sample size we are planning. Then, starting at the root of \Omega , we calculate the tallies in each election state, and we allow every outcome which could be possible if margins of fewer than LAM votes were allowed to flip. This is similar to giving an adversary a budget of \text{LAM}/2 votes they are allowed to flip (whichever way they want) and telling them to try their worst; any outcome they might be able to achieve will be included in our graph G . Crucially, we reset the adversary’s budget in every new election state we reach. They might flip one set of \text{LAM}/2 votes to get from the root to a state in the first layer of G , at which point we would reset the CVR and they would be allowed to pick a new (possibly different) set of \text{LAM}/2 votes to flip. 2.4 Instant Keep Factors. To write down the formulas for the instant keep factors, we will need to track some quantities of interest in each projected profile P_{H}=\pi_{H}\circ P . Definition 2.7 . (Profile Projections.) Given a profile P on candidates H\subseteq C , a distinguished L -ranking s\in R_{C} , and a distinguished candidate c\in H : • We define the first- \boldsymbol{L} restriction map \mathsf{first}_{L}\colon R_{H}\to R_{H} as the map that truncates each ranking to its first L positions: \mathsf{first}_{L}(r)=\begin{cases}r\Big|_{[L]}&\;\text{ if }\;\mathsf{len}(r)>L;\\ r&\;\text{ if }\;\mathsf{len}(r)\leq L.\end{cases} • We define the initially-like- \boldsymbol{s} tally T_{s}(P) as the number of rankings r ‘inside of’ P whose first- L restriction is s : T_{s}(P)=|(\mathsf{first}_{L}\circ P)^{-1}[s]|. N.b.: if s ranks a candidate not in H , this is automatically 0 . • We define the exactly-like- \boldsymbol{s} tally t_{s}(P) as the number of times a ranking r in P is s : t_{s}(P)=|P^{-1}[s]|. • We distinguish t_{\varnothing}(P) by giving it the notation g(P) (or just g , when P is clear) and calling it the ghost number of P : this is the number of rankings in P that indicate no preference in H . • We use the following shorthand to represent rankings r in the subscript of these tallies: when \mathsf{len}(r)=L , and the positions in r are r(0)=r_{0},\ldots,r(L-1)=r_{L-1} , we use the notation T_{r_{0},\ldots,r_{L-1}}\;\text{ and }\;t_{r_{0},\ldots,r_{L-1}}\;\text{ to represent }\;T_{r}\;\text{ and }\;t_{r}. For example, T_{5,3,12} represents the number times a vote r=P(i) has r(0)=5 , r(1)=3 , and r(2)=12 . We will occasionally drop the commas if all numbers involved are small. • Finally it will be helpful to distinguish the ending-in- \boldsymbol{c} rankings R_{H;c}\subseteq R_{H} as R_{H,c}=\{r\in R_{H}:r(\mathsf{len}(r)-1)=c\}. N.b. that R_{H;c} contains the singleton ranking r=\{(0,c)\} , among others; a vote that lists only c is still a vote ending in c . Given a profile P\colon[N]\to R_{C} on candidates C and an election state (H,W) , we set P_{S}=\pi_{S}(P) , and define the number of active votes N^{\prime} in the election state is: N^{\prime}=N-\sum_{r\in R_{W}}\left(\prod_{i=0}^{\mathsf{len}(r)-1}\Big(1-k(r(i))\Big)\right)t_{r}(P_{S}), (4) where the keep factors k\colon W\to(0,+\infty] are the least positive solutions to the system of equations: \forall\;w\in W:\frac{N^{\prime}}{m+1}+\varepsilon=k(w)\sum_{r\in R_{W;w}}\left(\prod_{i=0}^{\mathsf{len}(r)-2}\Big(1-k\big(r(i)\big)\Big)\right)T_{r}(P_{S}). (5) This system of equations might have no such solution in general; we will have to worry about this when designing our extended Meek rule. This is also not the first time someone solves for the convergent value of keep factors directly – Meek himself did this for degree \leq 4 election states in Section 7 of his original paper ( 12 ) . Presently we confirm that when the solution exists, it agrees with the solution found by Algorithm 1.4 : Proposition 2.8. For a fixed profile P\in\mathscr{P}_{H} , let k\colon H\to(0,1] be the convergent keep factors obtained by applying step of Algorithm 1.4 with a tolerance \omega , and define W\vcentcolon=\{c\in H:k(c)<1\} . If there exists a solution k^{\prime} to Equations ( 4 ) and ( 5 ) applied to equation state S=(H\backslash W,W) , then this solution is unique, and it agrees with k up to a factor of \omega , in the sense that for all c\in W , |k(c)-k^{\prime}(c)|<\frac{\omega}{q}<\omega. Proof. It suffices to note that such a solution k is by design a fixed point of the Meek algorithm; in such a case Theorem 1 of 9 already shows it is unique, and Theorem 2 of that same paper proves it is ‘within tolerance’ of the iterative solution from the algorithm. ∎ With the instant keep factors defined, the ‘extended Meek rule’ we described in Section 2.3 is just to use the instant formulas (when possible) rather than the iterative process described in step 2 of Algorithm 1.4 to calibrate the keep factors. Given that the rest of the algorithm – including how the keep factors are used to elect/eliminate candidates – remains the same, this extended Meek rule is guaranteed to produce the same winner set as the original rule, for any fixed profile. However, when we apply this instant keep factor formula to election states that would not be naturally be visited by the Meek rule, it is possible to see keep factors greater than 1 – we call such states ‘irregular,’ in the following sense: Definition 2.9 . We call an election state S=(H,W) regular if the system in ( 5 ) has a solution k\colon W\to[0,1] where all the keep factors are between 0 and 1 . We call it degenerate if there is no finite positive solution k\colon W\to[0,+\infty) . There is reason to fear that, when we solve the keep factors for election states not visited by the true Meek rule in our audit graph, the instant keep factor solutions for that state might vary discontinuously with respect to the profile projections T_{r} and t_{r} used to solve them. In such a case, the confidence intervals we build for the margins between candidates in this election state, which depend on this variation of the keep factors with respect to these projections, would not be valid. On the one hand, we can offer at least a modicum of comfort here: this can not happen as long as the election state is regular. Theorem 2.10. The (unique) solution k\colon W\to[0,1] for a regular election state is continuous with respect to the profile projections T_{r} and t_{r} used to construct it. Proof. Fix a degree- j election state S=(H,W) , call C=H\cup W , and consider the profiles P\in\mathscr{P} on candidates C . Let d=|R_{C}| and define \mathcal{T}=\mathbb{R}^{d} , so that the Equations in ( 5 ) can be thought of as describing a system of polynomial equations \vec{F} : \vec{F}\left(\vec{k},\vec{t}\right)=\vec{0}\;\text{ for }\;\vec{t}\in\mathcal{T}\;\text{ and }\;\vec{k}\in\mathbb{R}^{j}. (6) Finally let \mathcal{T}_{\mathsf{reg}}\subseteq\mathcal{T} correspond to the set of profile projections that make S regular; by definition, for every \vec{t}\in\mathcal{T}_{\mathsf{reg}} , there exists a unique solution \vec{k}\in[0,1]^{j} such that ( 6 ) holds. This means we can define a function \vec{k}\colon\mathcal{T}_{\mathsf{reg}}\to[0,1]^{j} which maps every regular \vec{t} to the unique \vec{k} that satisfies ( 6 ). We will show this function is continuous. To see this, let \vec{t}_{n}\to\vec{t} in \mathcal{T}_{\mathsf{reg}} , and define the sequence \vec{k}_{n}\vcentcolon=\vec{k}\left(\vec{t}_{n}\right) . This sequence lives in a compact set [0,1]^{j} , which implies it has a convergent subsequence \vec{k}_{n_{i}}\to\vec{k}_{\infty} . By continuity of F , we see 0=\vec{F}\left(\vec{k}_{n_{i}},\vec{t}_{n_{i}}\right)\to\vec{F}\left(\vec{k}_{\infty},\vec{t}\right). By definition of \vec{k} , this implies that \vec{k}_{\infty}=\vec{k}(t) . Using the same reasoning, any other convergent subsequence of the \vec{k}_{n} has the same limit. Hence the function \vec{k} is continuous.∎ On the other hand, we have some confirmation that these fears are well-founded. We occasionally need to include irregular states in our audit graphs (for example, vertex 3a in the audit graph for our case study). We have no guarantee from Theorem 2.4 that the keep factor solutions for these election states are well behaved; and indeed we find that in general it is possible to find states that are arbitrarily close to being regular where these solutions are not well-behaved. Theorem 2.11. For arbitrary m\geq 3 and arbitrarily large N , there exists a set of candidates C containing a subset W=\{w_{0},w_{1}\} and a profile P\colon[N]\to R_{C} such that the election state S=(W,C\backslash W) is regular, but switching two votes in P would make S degenerate. Proof. We construct a profile P on m candidates. Label the candidates as w_{0}=0,w_{1}=1,2,\ldots,m-1 . Define x=\left\lceil\frac{N}{m+1}+\varepsilon\right\rceil\;\text{ and }\;y=\left\lfloor\frac{N}{m+1}-\varepsilon\right\rfloor. Define the rankings r_{0}=\{(0,0),(1,1)\} and r_{1}=\{(0,1),(1,0)\} – these are rankings that list one winner as their first preference, the other as their second, and no other candidates subsequently. For 2\leq j\leq m-1 , define r_{j}=\{(0,j)\} . Construct the profile P by assigning r_{0} to the first x rankings, r_{1} to the next x rankings, then y rankings to each r_{j} for 2\leq jN+(m+1)\varepsilon , i.e. if and only if x^{\prime}>N/(m+1)+\varepsilon=q . But by construction, x^{\prime} is less than quota, so S is degenerate for P^{\prime} .∎ In view of this result, the best we can do is offer anecdotal evidence why we might not expect to see such turbulent election states in real-world profiles. Firstly, this phenomenon can only occur for election states of degree 2 or higher – this pathology can not arise when there are <2 winners. Secondly, the pathology relies on having many voters rank both ‘insecure winners’ one after the other; if a sufficient number of voters rank another hopeful candidate, or a secure winner, or no candidate at all after an insecure winner, the election state stops being degenerate. In Australia, for example, Above-the-Line voting means that when voters rank multiple winners in a row, the first (several) winners in that ranking are very secure, and only the last winner may be insecure. In particular, these two points imply that we are safe if we are auditing an election with m=3 seats, as long as one of the two winners in every degree 2 vertex of the audit graph is secure; this is certainly the case for all of the graphs we used in our Sections 4.2 and 4.3 . Finally, we outline some modifications of the Meek rule in Section 5 that might resolve these pathologies, while still being naturally auditable via our graph-based method. 3 Local Null Audits. Rather than discuss the statistical methods used to audit our local nulls in full generality, we will use our case study to show those details in practice. Once these details are laid out, we will finally be able to give estimates of the Average Sampling Numbers (ASN) of our methods in section 3.5 . 3.1 General Setup. As outlined in section 2.1 , our strategy is to reject one null hypothesis for each edge in a distinguished set \partial G\subseteq\vec{E}_{\Omega} . Here we define these local null hypotheses, and outline how we project our sample of ballot-CVR pairs onto the rejection rules for each of these local nulls. In each of the following subsections, we will re-formulate the local nulls and their rejection rules explicitly in the context where the degree of the election state S our local null concerns is small, but we can also formulate these rejection rules generally. To do this, we borrow the notion of an assorter from the RLA literature – cf. 13 , Section 2. Definition 3.1 . (Assorters.) When \text{BAL},\text{CVR}\in\mathscr{P} are fixed N -voter profiles on candidates H\subseteq C , and r\in R_{H} is a distinguished L -ranking, we define two discrepancy assorter maps \delta_{r},\lambda_{r}\colon[N]\to\{-1,0,+1\}, as follows: \displaystyle\delta_{r}(i) \displaystyle=\begin{cases}-1&\text{if}\;\mathsf{first}_{L}\circ\text{CVR}(i)=r\;\text{ and }\;\mathsf{first}_{L}\circ\text{BAL}(i)\neq r;\\ 1&\text{if}\;\mathsf{first}_{L}\circ\text{CVR}(i)\neq r\;\text{ and }\;\mathsf{first}_{L}\circ\text{BAL}(i)=r;\\ 0&\text{otherwise.}\end{cases} \displaystyle\lambda_{r}(i) \displaystyle=\begin{cases}-1&\text{if}\;\text{CVR}(i)=r\;\text{ and }\;\text{BAL}(i)\neq r;\\ 1&\text{if}\;\text{CVR}(i)\neq r\;\text{ and }\;\text{BAL}(i)=r;\\ 0&\text{otherwise.}\end{cases} These assorters measure how far off the profile projections T_{r}(\text{CVR}) and t_{r}(\text{CVR}) are from their true values T_{r}(\text{BAL}) and t_{r}(\text{BAL}) (cf. 2.7 for definitions), in the following sense: T_{r}(\text{BAL})=T_{r}(\text{CVR})+\sum_{i=0}^{N-1}\delta(i)\;\text{ and }\;t_{r}(\text{BAL})=t_{r}(\text{CVR})+\sum_{i=0}^{N-1}\lambda(i) Since the projections of the true profile BAL determine the path taken by the extended Meek rule through the universal graph \Omega , our strategy is to use the projections of the CVR as an ‘educated guess’ for their values, and use our random sample to correct those guesses by estimating the quantities \mu_{r}=\overline{\delta_{r}}=\displaystyle\frac{1}{N}\sum_{i=0}^{N-1}\delta(i)\;\text{ and }\;\nu_{r}=\displaystyle\overline{\lambda_{r}}=\frac{1}{N}\sum_{i=0}^{N-1}\lambda(i). To distinguish these ‘educated guesses’ from the projections of the true profile, we distinguish them with a ˇ accent: \displaystyle\check{T}_{r} \displaystyle\vcentcolon=T_{r}(\text{CVR})\;\text{ and }\;\check{t}_{r}\vcentcolon=t_{r}(\text{CVR}),\;\text{ whereas }\; \displaystyle T_{r} \displaystyle\vcentcolon=T_{r}(\text{BAL})\;\text{ and }\;t_{r}\vcentcolon=t_{r}(\text{BAL}). The quantities we end up auditing for our local nulls \mathcal{H}_{\vec{e}} of an election state (H,W) are margins \mathcal{M}_{i,j} between the tallies \mathcal{T}_{i} and \mathcal{T}_{j} of candidate pairs i,j\in H , as well as margins \mathcal{M}_{i,q} between a candidate i\in H and quota q . These quantities, originally defined in step 2 of the Algorithm 1.4 , can now be defined more concretely in terms of the profile projections and the instant keep factor solution k\colon W\to[0,1] from Equations ( 4 ) and ( 5 ): \displaystyle\mathcal{T}_{i} \displaystyle\vcentcolon=\sum_{r\in R_{H\cup W;i}}k(i)\left(\prod_{j=0}^{\mathsf{len}(r)-2}\Big(1-k\big(r(j)\big)\Big)\right)T_{r}; \displaystyle\mathcal{M}_{i,j} \displaystyle\vcentcolon=\mathcal{T}(i)-\mathcal{T}(j); \displaystyle q \displaystyle\vcentcolon=\frac{N-\sum_{r\in R_{W}}\left(\prod_{i=0}^{\mathsf{len}(r)-1}\Big(1-k(r(i))\Big)\right)t_{r}}{m+1}+\varepsilon; \displaystyle\mathcal{M}_{i,q} \displaystyle\vcentcolon=\mathcal{T}_{i}-q. With these quantities defined, we can define the local null hypotheses \mathcal{H}_{\vec{e}} corresponding to the edges {\vec{e}}\in\partial G : • If {\vec{e}}=\big(S,c\big) is a loser edge, the local null is “Candidate c loses to every other hopeful \ell\in H and no new candidate gets quota in this round.” The way we reject it is by either 1) checking \mathbb{P}(\mathcal{M}_{c\ell}<0)<\alpha , where \ell is the recorded loser in H , or 2) checking there is some other candidate h\in H that reaches quota in this round, in the sense that \mathbb{P}(\mathcal{M}_{hq}<0)<\alpha . Which of these options we check is something we decide based on the CVR, but we only ever check one of these hypotheses per loser edge. • Similarly, the null for a winner edge {\vec{e}}=\big(S,c\big) is “Candidate c makes quota in S , and has the highest tally among hopefuls in that round.” We reject it by either 1) checking that \mathbb{P}(\mathcal{M}_{cq}>0)\leq\alpha , or 2) checking there is some other hopeful h\in H such that \mathbb{P}(\mathcal{M}_{ch}>0)<\alpha . For the rest of this section, we outline the specifics of these rejection rules for degree-0, 1, and 2 election states, and demonstrate how we apply them to succesfully audit the Perth-Kinross profile from our case study in Section 1.1 re-imagined as a Meek election. As we do this, it will be helpful to refer back to its audit graph, which we re-draw in Figure 4 . The original profile for this election contained N=3689 votes, to which we add 150 ‘ghost’ votes to emulate votes that were invalidated before the election started, but might be added back in if they are sampled and found valid after all. 1 2 3a 3b 4 5 6 Elect Alan Livingstone Elect Henry Anderson Eliminate George Hayton Eliminate George Hayton Elect Henry Anderson Eliminate Andrew Dundas Elect Wilma Lumsden Figure 4 : The audit tree for an auditable margin of 40 votes. We pick a sample size of n=767 votes, or about 20% of the total number of ballot papers; this is on the larger side for an Average Sampling Number (ASN) , to account for the tight margin of 47 votes we must audit in the last round of the election. To conduct this synthetic audit, we artifically noise the CVR by perturbing a fraction \eta=0.05 of the rankings, including the artifical ghost ballots, in one of 4 ways, following a standard procedure established in the Appendix of 4 : either 1. Replace a random candidate in the ranking with another candidate not listed in the ranking; 2. Insert a random candidate that does not appear in the ranking into a random position in the ranking; 3. Randomly swap the positions of two candidates in the ranking; or 4. Remove a random candidate from the ranking. Finally we will use a risk level of \alpha=0.05 for this synthetic audit. 3.2 Degree-0 Audits. When the winner set of an election state S=(H,\varnothing) is empty, there are no keep factors to calibrate, and margins are straightforward to compute by hand. We need only worry about reducing quota after exhausting votes that listed only candidates in H^{\mathsf{c}} . This new quota simplifies as q=\frac{N-g}{m+1}+\varepsilon, Here there are only two discrepancy assorters of interest \delta_{c} and \lambda_{g}=\vcentcolon\lambda_{\varnothing} . We re-iterate their formal definitions in this context: \displaystyle\delta_{c}(i) \displaystyle=\begin{cases}-1&\text{if}\;\mathsf{fpv}_{S}(\text{CVR}(i))=c\;\text{ and }\;\mathsf{fpv}_{S}(\text{BAL}(i))\neq c;\\ 1&\text{if}\;\mathsf{fpv}_{S}(\text{CVR}(i))\neq c\;\text{ and }\;\mathsf{fpv}_{S}(\text{BAL}(i))=c;\\ 0&\text{otherwise.}\end{cases} \displaystyle\lambda_{g}(i) \displaystyle=\begin{cases}-1&\text{if}\;\pi_{S}\circ\text{CVR}(i)=\varnothing\;\text{ and }\;\pi_{S}\circ\text{BAL}(i)\neq\varnothing;\\ 1&\text{if}\;\pi_{S}\circ\text{CVR}(i)\neq\varnothing\;\text{ and }\;\pi_{S}\circ\text{BAL}(i)=\varnothing;\\ 0&\text{otherwise.}\end{cases} Using these assorters we can correct our guesses from the CVR and write a formula for the true exhaust total g and true tallies \mathcal{T}_{c} for c\in H : \displaystyle\mathcal{T}_{c}=T_{c} \displaystyle=\check{T}_{c}+\sum_{i=0}^{N-1}\delta_{c}(i)=\check{T}_{c}+N\mu_{c},\;\text{ where }\;\mu_{c}=\overline{\delta_{c}}=\frac{1}{N}\sum_{i=0}^{N-1}\delta_{c}(i); \displaystyle g \displaystyle=\check{g}+\sum_{i=0}^{N-1}\lambda_{g}(i)=\check{g}+N\mu_{g},\;\text{ where }\;\nu_{g}=\overline{\lambda_{g}}=\frac{1}{N}\sum_{i=0}^{N-1}\lambda_{g}(i). If we have estimators \hat{\mu}_{c} and \hat{\nu}_{g} for \mu_{c} and \nu_{g} , we can use them to construct estimators of our margins of interest: for fixed c,\ell\in H , we have \displaystyle\hat{\mathcal{M}}_{c\ell} \displaystyle=(\check{T}_{c}-\check{T}_{\ell})+N(\hat{\mu}_{c}-\hat{\mu}_{\ell}); \displaystyle\hat{\mathcal{M}}_{cq} \displaystyle=\left(\check{T}_{c}-\frac{N-\check{g}}{m+1}-\varepsilon\right)+N\left(\hat{\mu}_{c}+\frac{\hat{\nu}_{g}}{m+1}\right). In the degree-0 case, we could combine the two estimators \hat{\mu}_{c},\hat{\mu}_{\ell} into a single estimator \hat{\mu}_{0}=\hat{\mu}_{c}-\hat{\mu}_{\ell} . This would make the SHANGRLA compilers of 13 applicable to this margin. Likewise for \hat{M}_{cq} . We opt not to do this, to keep all of our auditing framework consistent about its usage of the delta method. Instead, for \mathcal{M}_{cq} , we pick \vec{\theta}=(\mu_{c},\nu_{g}) and take the gradient of \mathcal{M}_{cq} : \nabla_{\vec{\theta}}\mathcal{M}_{cq}=[\partial_{\mu_{c}}\mathcal{M}_{cq},\partial_{\nu_{g}}\mathcal{M}_{cq}]^{\mathsf{T}}=\left[N,\frac{N}{m+1}\right]^{\mathsf{T}} Then, if \Sigma_{\vec{\theta}} is the covariance matrix corresponding to \vec{\theta} (with the hypergeometric variance bounds on the diagonal as discussed in Section 2.2 ), the delta method says that asymptotically, \text{Var}(\hat{\mathcal{M}}_{cq})\approx\nabla_{\vec{\theta}}\mathcal{M}_{cq}^{\mathsf{T}}\Sigma_{\vec{\theta}}\nabla_{\vec{\theta}}\mathcal{M}_{cq}\Big|_{\vec{\theta}=(\hat{\mu}_{c},\hat{\nu}_{g})}. (7) Finally, we multiply by the Simple Random Sampling Without Replacement (SRSWOR) correction factor \frac{N-n}{N-1} and take a square root to get the standard error of the margin, which we use to build a one-sided confidence interval. The margin for \mathcal{M}_{c\ell} is similar, only with \vec{\theta}=(\mu_{c},\mu_{\ell}) . Example 3.2 . When we audit vertex 1 in our case study, one the main local nulls we have to reject is “Livingstone does not have quota at the start of the election.” If we call Livingstone candidate c , then our assorters record the following: • \delta_{c} contains 5 entries with a -1 , and 4 entries with a +1 ; the other 758 entries are all 0 . • \lambda_{g} contains 2 entries with a -1 , and 4 entries with a +1 ; the other 761 entries are all 0 . • One of the non-zero entries in \lambda_{g} overlaps with a non-zero entry of \delta_{c} , such that in total there are 15 ballot dicrepancies relevant to this margin; the induced variance bound is K/N=0.0328 , which we divide by n to bound the variance of the sample mean. • The resulting delta method matrix multiplication from 7 yields \displaystyle\begin{bmatrix}3839\\ 959.75\\ \end{bmatrix}^{\mathsf{T}}\begin{bmatrix}0.000043&-0.000002\\ -0.000002&0.000043\\ \end{bmatrix}\begin{bmatrix}3839\\ 959.75\\ \end{bmatrix}\approx 657.56 • Finally we multiply by the SRSWOR factor (N-n)/(N-1)\approx.8 and square root to get a \text{SE}\approx 22.94 . After multiplying by the appropriate z -score and adding the sampled margin, we get a lower bound of 149.51 on \mathcal{M}_{cq} . This bound being positive confirms that Livingstone does make quota with more than 95\% confidence. The only other nulls we would have to check in vertex 1 is that Livingstone beats every other candidate in that round (i.e. that no other candidate would get elected before him). 3.3 Degree-1 Audits. In the setting where there is a single elected candidate w in the election state, candidate-to-candidate margins have the form \displaystyle\hat{\mathcal{M}}_{c\ell}=(\check{T}_{c}-\check{T}_{\ell})+N(\hat{\mu}_{c}-\hat{\mu}_{\ell})+\bigg(1-\underbrace{\frac{\check{C}_{u}-N\hat{\mu}_{u}}{\check{C}_{v}+N\hat{\mu}_{v}}}_{\hat{k}}\bigg)(\check{T}_{wc}-\check{T}_{w\ell}+N(\hat{\mu}_{wc}-\hat{\mu}_{w\ell})) \displaystyle=(\check{T}_{c}-\check{T}_{\ell}+\check{T}_{wc}-\check{T}_{w\ell})+N(\hat{\mu}_{c}-\hat{\mu}_{\ell}+\hat{\mu}_{wc}-\hat{\mu}_{w\ell})-\frac{\check{C}_{u}-N\hat{\mu}_{u}}{\check{C}_{v}+N\hat{\mu}_{v}}(\check{T}_{wc}-\check{T}_{w\ell}+N(\hat{\mu}_{wc}-\hat{\mu}_{w\ell})). (8) where \displaystyle\check{C}_{u} \displaystyle=N-\check{g}-\check{t}_{w}+(m+1)\varepsilon, \displaystyle\hat{\mu}_{u} \displaystyle=\hat{\nu}_{g}+\hat{\nu}_{w}, \displaystyle\check{C}_{v} \displaystyle=(m+1)\check{T}_{w}-\check{t}_{w}, \displaystyle\hat{\mu}_{v} \displaystyle=(m+1)\hat{\mu}_{w}-\hat{\nu}_{w}. The candidate-to-quota margin can be similarly simplified: \hat{\mathcal{M}}_{cq}=(\check{T}_{c}+\check{T}_{wc})+N(\hat{\mu}_{c}-\hat{\mu}_{wc})-\frac{\check{C}_{u}-\hat{\mu}_{u}}{\check{C}_{v}+\hat{\mu}_{v}}(\check{T}_{wc}+\check{T}_{w}+N(\hat{\mu}_{wc}+\hat{\mu}_{w})) We use the same delta method to give one-sided confidence intervals for these margins. For \mathcal{M}_{c\ell} the parameters are \vec{\theta}=(\mu_{c},\mu_{\ell},\mu_{wc},\mu_{w\ell},\nu_{g},\nu_{w},\mu_{w}) . For \mathcal{M}_{cq} the parameters are \vec{\theta}=(\mu_{c},\mu_{wc},\nu_{g},\nu_{w},\mu_{w}) . The non-linear dependence of the margins on these parameters highlights the need for the delta method. Example 3.3 . In election state 2 , one of the loser edges {\vec{e}}\in\partial G is the edge corresponding to Dundas, who we refer to as c here. The recorded loser in this election state is Hayton, whom we refer to as \ell here. The null hypothesis corresponding to this loser edge is “ \mathcal{M}_{c\ell}<0 .” The original CVR margin between these candidates in this election state is \check{\mathcal{M}}_{c\ell}=94.1464 . After correcting this margin with our sampled parameters, it decreases to an estimate of \hat{\mathcal{M}}_{c\ell}=81.2074 . There are 24 discrepant ballots among those sampled, yielding an individual variance bound of K/N<0.000064 . The delta method calculation in equation ( 7 ) is too large to print, but it yields a variance bound of \text{Var}(\hat{\mathcal{M}}_{c\ell})<1959.4421 . After multiplying by our SRSWOR factor we get a standard error for our margin of \widehat{\text{SE}}\approx 39.6026 , yielding a lower bound of \hat{\mathcal{M}}_{c\ell}>16.0668>0 for our 95% confidence interval, allowing us to reject this local null. The other nulls we would have to check at this vertex are that no candidate other than Anderson makes quota in this election state, and that no hopeful candidate loses to Hayton head to head. 3.4 Degree-2 Audits. Without loss of generality, label the two winners in a degree- 2 election state as 1,2 . In this setting the instant keep factor equations in ( 5 ) can be solved to isolate k_{1}=k(1) and k_{2}=k(2) . We find that the keep factor k_{2} is the root of the polynomial P_{2}(\vec{\theta},k)=A_{2}(\vec{\theta})k^{2}+B_{2}(\vec{\theta})k+C_{2}(\vec{\theta}) , where \displaystyle A_{2} \displaystyle= \displaystyle T_{2}t_{12}-T_{12}t_{2}+T_{2}t_{21}+T_{21}t_{12}+T_{21}t_{2}+T_{21}t_{21}-(m+1)\Big(T_{12}T_{21}+T_{2}T_{21}\Big) (9) \displaystyle B_{2} \displaystyle= \displaystyle-T_{1}t_{12}-T_{1}t_{2}+T_{12}t_{2}-T_{2}t_{1}-T_{2}t_{12}-T_{1}t_{21}-T_{2}t_{21}+(N-g)(T_{21}-T_{12})-T_{21}t_{1} (10) \displaystyle\phantom{(m+1)}-2(T_{21}t_{12}+T_{21}t_{2}+T_{21}t_{21}) \displaystyle\phantom{(m+1)}+(m+1)\Big(T_{1}T_{12}+T_{1}T_{2}+T_{12}T_{21}+T_{2}T_{21}-T_{12}\varepsilon+T_{21}\varepsilon\Big) \displaystyle C_{2} \displaystyle= \displaystyle-(T_{1}+T_{21})\Big(N-g-t_{1}-t_{12}-t_{2}-t_{21}+(m+1)\varepsilon\Big) (11) The keep factor k_{1} is similarly a root of P_{1}(\vec{\theta},k)=A_{1}(\vec{\theta})k^{2}+B_{1}(\vec{\theta})k+C_{1}(\vec{\theta}) , whose coefficients just have the indices 1 and 2 switched. We solve these equations numerically with the sampled parameter \vec{\theta} to find \hat{k}_{1} and \hat{k}_{2} . For the candidate-to-candidate margin \mathcal{M}_{c\ell} , our parameters are \vec{\theta}=\big[\nu_{g},\mu_{1},\mu_{2},\mu_{12},\mu_{21},\nu_{1},\nu_{2},\nu_{12},\nu_{21},\mu_{c},\mu_{\ell},\mu_{1c},\mu_{1\ell},\mu_{2c},\mu_{2\ell},\mu_{12c}+\mu_{21c},\mu_{12\ell}+\mu_{21\ell}\big] (12) N.b. that the sum \delta_{12c}+\delta_{21c} is still bounded above by 1 , since it is not possible for these assorters to simultaneously be +1 or -1 . Likewise for \delta_{12\ell}+\delta_{21\ell} . In finding \nabla_{\vec{\theta}}\mathcal{M}_{c\ell} , we will need to take some partials \partial_{\theta_{i}}k . We use the Implicit Function Theorem to do this: \frac{\partial k}{\partial\theta_{i}}=-\frac{\partial_{\theta_{i}}P(k,\vec{\theta})}{\partial_{k}P(k,\vec{\theta})}=-\left.\frac{(\partial_{\theta_{i}}A)k^{2}+(\partial_{\theta_{i}}B)k+(\partial_{\theta_{i}}C)}{2Ak+B}\right|_{\vec{\theta},k=\hat{\theta},\hat{k}} Finally the candidate-to-candidate margin has the following form: \displaystyle\hat{\mathcal{M}}_{c\ell} \displaystyle=(\check{T}_{c}-\check{T}_{\ell})+N(\hat{\mu}_{c}-\hat{\mu}_{\ell}) \displaystyle+(1-\hat{k}_{1})\left(\check{T}_{1c}-\check{T}_{1\ell}+N(\hat{\mu}_{1c}-\hat{\mu}_{1\ell})\right) \displaystyle+(1-\hat{k}_{2})\left(\check{T}_{2c}-\check{T}_{2\ell}+N(\hat{\mu}_{2c}-\hat{\mu}_{2\ell})\right) \displaystyle+(1-\hat{k}_{1})(1-\hat{k}_{2})\left(\check{T}_{12c}+\check{T}_{21c}-\check{T}_{12\ell}-\check{T}_{21\ell}+N(\hat{\mu}_{12c}+\hat{\mu}_{21c}-\hat{\mu}_{12\ell}-\hat{\mu}_{21\ell})\right) We could similarly write down a symbolic form for \hat{\mathcal{M}}_{cq} , but degree-2 candidate-to-quota margins are not necessary when m=3 ; it is sufficient to check that the last recorded winner of the election beats every remaining hopeful candidate in every degree-2 vertex. Example 3.4 . Vertex 3A is the only irregular election state in our graph; according to the CVR, the keep factors would be k_{1}=0.8130 and k_{2}=1.0029 for the recorded winners Livingstone and Anderson. After substituting our sampled parameters into the coefficient equations ( 9 ) - ( 11 ), these become regular again; we get \hat{k}_{1}=0.814 and \hat{k}_{2}=0.9887 . The tightest margin we have to audit in this election state is again to check that Dundas does not lose to Hayton; the recorded margin between them (using the irregular keep factors) is 94.0624 ; this margin decreases to 81.6326 after applying our sampled parameters, and it is bounded below by 14.4745>0 according to our delta method, allowing us to reject this local null. Each of the Implicit Function Theorem derivatives \partial_{\theta_{i}}k are bounded above by 10^{-1} in our example, and the number of relevant ballot comparison discrepancies is 26 , leading to a variance bound of K/N<0.0520 . 3.5 Average Sampling Numbers. With the mechanics of local null audits established, we are equipped to discuss the expected minimal sample size n needed to successfully audit a given election, which we refer to as its Average Sampling Number (ASN) . This number depends mainly on the edge {\vec{e}}\in\partial G in the chosen audit graph whose rejection rule has the smallest margin. In this section we will treat the ASN as a function of this Least Auditable Margin (LAM) \mathfrak{m} , and we will only consider the case where the noise level \eta=0 . This reduction will help give us a sense of the scale of the ASN as a function of the smallest margin in the election. In the case where \eta=0 , we find that the variance bound K/N from Section 2.2 is asymptotically proportional to \frac{1}{n} in the regime where n\ll N . This in turn implies that the fractional ASN n/N needed for a succesful RLA will depend only on \mathfrak{m} , not on its scale relative to N . That is to say, the cost as a fraction of the profile size to audit a margin of \mathfrak{m}=100 votes is the same regardless of whether N=5000 or N=1,000,000 ; or in other words, a margin of 1\% costs comparatively less to audit in a larger profile. These results are underscored in Figure 5 . This seems like good news: it is reasonable to expect larger profiles will have numerically larger LAMs, in which case a successful RLA will have to sample a smaller fraction n/N of the profile. Figure 5 : ASN as a function of Least Auditable Margin A when \alpha=.05 . We spend the rest of this section mathematically justifying Figure 5 . Proposition 3.5. In the setting where \eta=0 and we budget the risk-limit as \alpha=\alpha_{0}+\alpha_{K} to audit a numerical Least Auditable Margin \mathfrak{m} of the N votes in a given profile, and there are d assorter parameters \vec{\theta} used to build the margin in question, the asymptotic relationship between the Average Sampling Number n and A is \frac{n}{N}\approx\frac{z_{1-\alpha_{0}}\sqrt{d\log(1/\za_K)}}{\mathfrak{m}} Proof. When we sample n out of the population of N ballots without replacements to find X=0 ballot discrepancies, and K is unknown a priori, the hypergeometric probability in Equation ( 1 ) simplifies to \displaystyle\mathbb{P}_{K}(X=0) \displaystyle=\frac{{{K}\choose{0}}{{N-K}\choose{n}}}{{{N}\choose{n}}}=\frac{\frac{(N-K)!}{n!(N-K-n)!}}{\frac{N!}{n!(N-n)!}} \displaystyle=\frac{(N-K)(N-K-1)\cdots(N-K-n+1)}{N(N-1)\cdots(N-n+1)} \displaystyle=\prod_{j=0}^{n-1}\left(1-\frac{K}{N-j}\right) Taking logarithms and using the approximation \ln(1+u)=u+O(u^{2})\approx u in the regime where u\ll 1 , i.e. K\ll N-n , we get \displaystyle\ln\mathbb{P}_{K}(X=0) \displaystyle=-\sum_{j=0}^{n-1}\frac{K}{N-j} \displaystyle=-K\sum_{j=0}^{n-1}\left(\frac{j}{N(N-j)}+\frac{1}{N}\right) \displaystyle\ln\mathbb{P}_{K}(X=0) \displaystyle=-K\left(\frac{n}{N}+\sum_{j=0}^{n-1}\frac{j}{N(N-j)}\right) (13) Now we note the sum is O(n^{2}/N^{2}) in the regime n\ll N , since N-j\geq N-n , hence 0\leq\sum_{j=0}^{n-1}\frac{j}{N(N-j)}\leq\frac{1}{N(N-n)}\sum_{j=0}^{n-1}j=\frac{n(n-1)}{N(N-n)}=O\left(\frac{n^{2}}{N^{2}}\right). Recalling from Equation ( 3 ) that K_{u} is the maximum value of K such that \mathbb{P}_{K}(X=0)\geq\alpha_{K} , we set the left hand side of Equation ( 13 ) equal to \ln(\za_k) and we substitute K=K_{u} into the right hand side, to find \ln(\za_K)=-K_{u}\left(\frac{n}{N}+O\left(\frac{n^{2}}{N^{2}}\right)\right)\approx-K_{u}\frac{n}{N}. In other words, our ballot-level stochastic variance bound is K_{u}/N\approx{\ln(1/\za_K)/n} . Dividing by n again to turn it into the variance of the sample, and ignoring the finite population correction factor in the regime n\ll N , we find the width of a one-sided (1-\alpha_{0}) -confidence interval resulting from the sum of d of these variance bounds is w=N\cdot z_{1-\alpha_{0}}\sqrt{\frac{d\ln(1/\za_K)}{n^{2}}}. The result follows from setting w=\mathfrak{m} and solving for n .∎ 4 Experimental Results. We can run this auditing framework on several databases of Cast Vote Records (CVRs) for past elections that used Ranked Choice Voting to measure success rate and viability 5 5 5 Replication code available here . . We use the same methodology as we did in our case study to produce these results: starting from the CVRs, we introduce a noise level \eta by perturbing a corresponding fraction of the ballots, synthetically emulating a paper ballot record, which the CVR is a noisy approximation of. We noise these ballots using the same procedure described at the end of Section 3.1 . None of these elections were originally run using the Meek rule – all of those included here used the WIGM rule, with either m=2,3,4, or rarely m=5 winners. We re-imagine all of them as 2 - or 3 -seat Meek elections, using the same CVRs. We also introduce some ‘ghost ballots’ to each profile – empty rankings which list none of the initial candidates – to simulate ballots that were spoilt before the election started. These ballots have no impact on the election itself (in Meek, they do not even change the quota), but there is a possibility our noise turns one of these ghosts into a valid ballot. We introduce one such ballot for every 100 ballots in the profile. In this setting where the noise level \eta between our two profiles is non-zero, we will consider the Average Sampling Number (ASN) to be the smallest sample size of the profile that will lead to a successful audit over 90\% of the time. In view of our discussion in Section 3.5 , we expect ASNs to decrease as profile sizes increase. To confirm this, we will run our ASNs on three ‘scales’ of elections: N\approx 5,000 , N\approx 50,000 , and N\approx 1,000,000 . 4.1 Small Elections: Scotland. Scotland has been using WIGM STV for its city councils since 2007. This has produced a rich database of 1068 ranked-choice voting profiles for small-to-medium sized elections (one of which was the profile for our Perth-Kinross case study). We ran our auditing methods on all profiles in this database that had |C|=6,7,8,9, or 10 candidates running. This includes 881 profiles, of which 1 was a race for m=2 seats, 439 profiles were races for m=3 seats, 439 more profiles were races for m=4 seats, and 1 profile was a race for 5 seats. The electorate for these elections is comparatively small: the average number of voters across all audited profiles is around 5,248 . For these audits, we used a noise level of \eta=2\% ; this is still a lot higher than recorded real-world noise levels, which are typically a fraction of a percent for political elections. We start by auditing these profiles with a risk level of \alpha=.05 , of which we allocate \alpha_{K}=.005 to the construction of the variance bounds discussed in Section 2.2 . We plot the resulting ASNs in Figure 6 , and the number of profiles auditable as a function of sample size in Figure 7 . Figure 6 : Average Sampling Number across 881 Scottish STV elections, \alpha=.05 To run batch audits on this large dataset and find ASNs, we used a 2-step greedy search process. First, we build audit graphs with iteratively larger minimal auditable margins M , continuing as long as the degree-3 vertices of the graph all have the same winner set as that recorded by the CVR. Second, we find the smallest sample size n that will lead to a successful RLA for the given audit graph over 90\% of the time. It’s worth noting that this greedy process is often not optimal; the search process only checked a handful of auditable margins and sample sizes, both of which could be pushed further by an individual tailoring them to each specific profile. Here is a verbal summary of these results: 76.6\% of the profiles, or 675/881 , were auditable with an ASN of \leq 30\% of the number of votes in the profile. Of the 107 profiles that were not auditable with any ASN of at most 50\% of the profile, 62.1\% of them recorded a margin of less than 0.5\% of the profile between the last winner of the election and their strongest opponent. In American city council elections, it is typical for such a margin to trigger an automatic full recount. We repeated these audits with an increased risk level of \alpha=.1 , of which we allocated \alpha_{K}=.02 to the variance bounds from Section 2.2 . The cumulative results are shown in Figure 8 : only 12 more profiles became auditable, but the ASNs needed to successfully audit each profile decreased slightly. Figure 7 : Number of Scottish elections auditable with an ASN at or below given threshold, \alpha=.05 . Figure 8 : Number of Scottish elections auditable with an ASN at or below given threshold, \alpha=.1 . 4.2 Medium Elections: Portland. The city of Portland switched its city council election to use WIGM STV for the first time in 2024. This election was split into 4 districts, each of which elected 3 councilors, for a total of 12 . These districts had a turnout of 42,678,\,77,024,\,84,356, and 76,566 voters respectively 6 6 6 N.b. that we artificially add ‘ghost votes’ to each of these profiles proportional to 1% of their weight, so the actual turnouts we use for the audits are inflated by a factor of 1.01x. , for an average district size of 70,156 . For our purposes, we re-imagine them as Meek elections, and artifically noise the CVRs with a noise level \eta=2\% , using a risk level of \alpha=5\% for our audits. Gracefully, the outcome of the election in each of these districts is the same whether we use WIGM or Meek (which was not always the case for the Scotland database, as evidenced by our case study). The most fragile of these elections was District 1, for which the largest LAM that led to a coherent audit graph was A=532 , or 1.2\% of the profile. We display this audit graph in Appendix A – it is instructive to look at, because its structure is typical of audit graphs: there is an initially turbulent cloud of low-stakes eliminations (the so-called ‘elimination cloud’), after which the graph converges back to a single vertex in election state , at which point the higher-stakes eliminations and elections of the more viable candidates begin. The size of the elimination cloud tends to blow up combinatorially with the number of candidates in the election, and as we will see later this is a recurring computational obstacle for our graph-based RLAs in larger elections. We find that this audit graph for Portland District 1 is consistently auditable with an ASN of n=1,077 ballot comparisons, or around 2.5\% of the profile. The only other Portland profile we contrive to audit close to optimally is District 4, which had a LAM of around A=2,000 votes, or 2.6\% of the profile. District 4 had 30 candidates (compared to 16 in District 1), and consequently the audit graph corresponding to this LAM is unrecommendably large – it contains 8,455,380 vertices, more than 95% of which occur in the first 16 of 31 layers of the graph. For this audit graph the smallest ASN was of n=386 votes, or 0.5\% of the profile. Districts 2 and 3 are a lot more stable than the others; the former has a LAM of around 3,500 votes, or 4.5\% of the profile, and the latter has a LAM of 9,000 votes, or 11.6\% . The audit graphs corresponding to these margins are too large to compute, leaving us with two options; either use a more modest LAM to get a (less efficient) successful RLA, or pre-emptively remove some of the less viable candidates from each profile, thereby skipping over the elimination cloud stage of the audit graph. The latter option seems like it should be justifiable – the candidates we remove from each profile all have less than 5\% of quota at the time of their elimination in the canonical Meek path through the graph – but it is not currently mathematically justified. Even so-called ‘non-viable candidates’ – candidates with fewer mentions than (initial) quota – might impact the election if their combined presence in a round denies enough votes to a winner to see them eliminated. Mathematically justifying this pre-emptive removal of non-viable candidates would considerably simplify and optimize the framework of graph-based RLAs. We show the ASNs corresponding to both approaches in Table 4 . Rigorous Approach Optimal Approach Profile LAM ASN LAM ASN District 1 532 (1.23%) 1077 (2.5%) 532 (1.23%) 1077 (2.5%) District 2 2,000 (2.4%) 311 (0.4%) 3,500 (4.1%) 253 (0.33%) District 3 400 (0.47%) 2839 (3.3%) 9,000 (11.6%) 102 (0.13%) District 4 2,000 (2.6%) 421 (0.55%) 2,000 (2.6%) 421 (0.55%) Table 4 : LAMs and ASNs for the audits of Portland Districts 1-4. It is worth dwelling for a moment longer on the computational challenge posed by these ‘elimination clouds.’ The graphs we used to audit districts 2 and 3 with a LAM of 2,000 and 400 respectively were made up of 8,244 and 14,955 vertices. Of these vertices, 8,113 (98.4%) and 14,822 (99.1%) respectively occurred in the first half of the graph, corresponding to the elimination cloud we describe. In District 4, layer 11 was the largest, containing 1,373,001 vertices, or 16% of the total, but by layer 23 the graph had collapsed back to a single-vertex layer, indicating the end of the elimination cloud. These clouds bear little impact on the outcome of the election, but currently represent the majority of the computational work of the audit. Worse, the size of the cloud is dependent mostly on the number of candidates in the election: District 3 had a much more robust election than District 2, but its computationally viable LAM was much lower because the former had 30 candidates while the latter had 22. This emphasizes the need for a mathematically rigorous justification to jump past this elimination cloud; else the best recommendation we will be able to make to keep STV elections secure will be to limit the number of candidates ahead of the election (which is arguably contrary to the spirit of STV elections). 4.3 Large Elections: Australia. Australia has been using STV for its Senate since 1949; they were using digitally tabulated WIGM STV by 1998, and they have published full CVRs for their 2016 7 7 7 The 2016 election is unusual because it was the result of a ‘double dissolution’ of Parliament, meaning each of Australia’s six federal states were electing 12 new senators, rather than the usual 6. This explains why the number of candidates running in each of these states was unusually high that year. , 2019, 2022, and 2025. Since 1985, the Australian Senate has been made up of 76 seats, 72 of which come from 6 federal states electing 12 senators each for staggered 6-year terms, and 4 of which come from 2 territories electing 2 senators each for 3-year term. Each state- and territory-level senatorial election uses (a version of) WIGM STV. This is the largest-scale use of STV for political elections in the world: the largest of these states, New South Wales, had a turnout of 5,219,341 voters in 2025. Australia is also singular for its use of “Above The Line (ATL)” voting, which allows voters to rank parties instead of candidates if they prefer. When a voter casts an ATL vote, the vote is counted as though it had ranked all candidates of each party listed by the vote, in an order pre-determined ahead of the election. It is common to see >90\% of the electorate cast ATL votes, and consequently Australian STV elections tend to see candidates reach quota much earlier and with larger surpluses than elsewhere. The two territories that elect 2 senators each every election cycle – the Northern Territory (NT) and Australian Capital Territory (ACT) – are small enough (and more importantly, see few enough candidates running for office) that our graph-based approach can usually do a full successful RLA for them. To make the audits computationally viable, we sometimes have to use a smaller LAM than would otherwise be possible; in such cases the resulting ASNs are slightly smaller, but in practice the difference is small as long as the LAM is on the order of thousands. We audit these elections as m=2 seat Meek elections, with our usual noise level of \eta=2\% and risk level of \alpha=0.05 . We show the results, as well as the number M=|C| of candidates, the number N of voters (including the 1% of ghost ballots added to the election) for each election in table 5 . Territory Year |C| N Optimal LAM Viable LAM ASN Australian Capital Territory 2016 22 256,906 38,000 (14.7%) 2,000 (0.8%) 1,027 (0.4%) 2019 17 272,933 35,000 (12.8%) 2,000 (0.7%) 1,364 (0.5%) 2022 23 288,069 17,000 (5.9%) 500 (0.2%) \infty 2025 14 296,408 40,000 (13.5%) 40,000 (13.5%) 296 (0.1%) Northern Territory 2016 19 102,516 18,000 (17.6%) 4,000 (4%) 146 (0.14%) 2019 18 106,077 19,000 (17.9%) 3,700 (3.5%) 151 (0.14%) 2022 17 104,653 14,000 (13.4%) 4,400 (4.2%) 139 (0.13%) 2025 17 107,875 19,000 (17.6%) 4,800 (4.45%) 134 (0.12%) Table 5 : RLA Results for Australia’s Smaller Territories. The only one of these territory elections we weren’t able to audit rigorously was the 2022 ACT election. If we use our informal shortcut to remove the 14 least viable candidates from the election before the audit starts (these are all candidates that had less than 4,000 votes as of the time of their elimination in the original election order), the election becomes auditable with an ASN of n=146 votes, or 0.05\% of the profile. Australia’s six federal states tend to have much larger turnouts and more candidates running for office (often more than 50 candidates). We also don’t currently have the technology to audit them as 6-seat elections (although that step forward seems accessible). Rather, we audit them as though they had been 3-seat elections, and we use the same method as we did in Portland to ‘skip ahead’ of the elimination cloud part of the graph – again, without strict mathematical justification, although the candidates we pre-emptively eliminate tend to have fewer mentions in the profile than the quota they would need to win a seat. We show the results of our auditing methods applied to Australia’s federal states in Table 6 . These results include the LAM we used for the audit, the ASN we got out of it, as well as the original number of candidates |C| and the number of remaining candidates |C^{\prime}| after we ‘jump over’ the elimination cloud. The results for these Australian audits seem particularly encouraging: for these elections that often have more than a million voters, sampling a few hundred ballots often suffices to perform a successful audit. State Year |C| |C’| N LAM ASN New South Wales 2016 151 16 4,274,747 172,000 (4%) 427 (0.01%) 2019 105 13 4,668,386 240,000 (5.14%) 194 (0.004%) 2022 75 11 4,822,863 113,000 (2.34%) 401 (0.008%) 2025 56 12 5,014,481 61,000 (1.22%) 1,337 (0.03%) Victoria 2016 116 14 3,477,543 13,000 (0.37%) 11,591 (0.33%) 2019 82 12 3,744,918 44,000 (1.17%) 936 (0.02%) 2022 79 12 3,834,047 211,000 (5.5%) 159 (0.004%) 2025 65 13 4,129,837 33,000 (0.7%) 2,359 (0.06%) Queensland 2016 122 17 2,731,865 95,000 (3.48%) 270 (0.01%) 2019 83 12 2,921,107 144,000 (4.93%) 208 (0.007%) 2022 79 11 3,036,380 26,000 (0.85%) 2,450 (0.08%) 2025 56 12 3,252,922 46,000 (1.41%) 896 (0.03%) Western Australia 2016 79 13 1,371,310 37,000 (2.7%) 390 (0.03%) 2019 67 13 1,459,142 85,000 (5.82%) 181 (0.01%) 2022 58 12 1,539,357 7,000 (0.45%) 5,118 (0.33%) 2025 49 12 1,636,041 11,000 (0.67%) 3,265 (0.2%) South Australia 2016 64 9 1,064,808 200,000 (18.78%) 177 (0.01%) 2019 42 12 1,104,303 3,000 (0.27%) 11,022 (1%) 2022 51 12 1,137,357 47,000 (4.13%) 206 (0.02%) 2025 40 12 1,174,613 36,000 (3.06%) 335 (0.03%) Tasmania 2016 58 14 341,487 7,000 (2.04%) 485 (0.14%) 2019 44 12 355,217 12,000 (3.38%) 315 (0.09%) 2022 39 14 364,547 227 (0.06%) 91,136 (25%) 2025 33 12 375,463 6,000 (1.6%) 625 (0.17%) Table 6 : RLA Results for Australia’s Federal States. 5 Future Work. The graph-based approach to algorithmic election RLAs is new, and there is a lot of fertile ground left to explore – mathematically, algorithmically, and computationally speaking. One immediate next step is to extend the local null constructions to higher degree election states. In the case of Meek elections, this will require a generalized framework to take partials \partial_{\theta_{i}}k of higher degree keep factors. The current Implicit Function Theorem framework could remain viable up to m=5 , but in general it might be a better idea to implicitly differentiate the equations in ( 5 ) and solve for the partials numerically. The turbulence of these higher degree solutions might make it more common for the audit graphs to include non-regular election states, which might be further perturbed into becoming degenerate by the auditing process, reducing viable LAMs for these elections. This is already a problem we observed in Portland District 3 – the high optimal LAM sometimes led to election states where the sampled parameters could not be solved for finite, positive keep factors. In such a case the only viable option is to reduce the LAM until all vertices become close enough to regular. Another direction to explore is using this graph-based approach on WIGM elections. This will require re-thinking the definition of audit graphs: because the chronology of elections matters in WIGM, the winner set of an election state will have to carry information about the hopeful set at the time of each winner’s election. This will make it less common for different branches of the graph to converge back to the same vertices, and as a result the audit graphs will be bushier. In every election state where a winner gets elected, a new branch of the audit graph will have to start, which will never re-join the other branches. This dependence on exact chronology might make WIGM elections more unstable in general – this is what we observed in the case study from Section 1.1 – but the relative computational simplicity of WIGM might counteract this, so that it is not clear which of these two election rules will be more auditable in the long run. Especially in cases when the timing of multiple winners is very certain, it might be the case that WIGM is more auditable than Meek. This would be the case, for instance, in Districts 1, 2, and 3 of Portland, where the first winner got elected relatively late and after receiving a large transfer, meaning their quota was quite secure. In District 4, however, Olivia Clark had an initial quota with a small surplus, making the exact timing of her election difficult to pin down in the audit graph – in the full audit graph we computed, there are 4,097,797 vertices corresponding to her election, each of which would have to create a separate branch if we were using WIGM STV. Another algorithmic challenge would be to find a statistically rigorous process allowing us to eliminate multiple candidates at the same time to ‘jump over’ the elimination clouds we ran into in our larger audit graphs from Sections 4.2 and 4.3 . Again, this is a place where Meek might be more structurally suited to the task: when it is possible for a winner to get elected in the middle of the elimination cloud (as was the case in Portland District 4), it seems like there can be no such shortcut in WIGM. One outline of this shortcut for Meek elections is the following: partition the set of candidates into ‘canonical winners,’ ‘strong,’ and ‘weak’ candidates. Then, statistically verify that each of the canonical winners beats each of the weak candidates, as long as the hopeful set contains all of the canonical winners. This can look a lot like the so-called “Never Loses (NL)” assertions in 3 ; or similarly we could compare the winner’s first place votes to the weak candidate’s mentions. If we can show this, then we are certain that all of the weak candidates must be eliminated before all of the canonical winners, and we know that the only possible vertices after the elimination cloud include all of the canonical winners and some subset of the strong candidates; by considering every such subset, we can initialize the graph in a ‘post-elimination cloud’ state. One mathematical simplification of our framework would be to find a way to deal with the parameter explosion we expect for higher degree local nulls by simultaneously bounding the effect of all high-degree transfers. As seen in Equation ( 12 ), there are already 17 parameters involved in the constuction of degree-2 local null audits. Even if Proposition 3.5 shows that the ASNs of our audits are only proportional to the square root of this number d of parameters, we expect the number of parameters to blow up combinatorially with degree. To keep ASNs reasonable, it will therefore be necessary either to 1) improve the hypergeometric variance bounding strategy outlined in Section 2.2 (which is very plausible), or 2) find some way of combining the effect of all higher-degree transfers into a single worst-case scenario parameter, to avoid tracking all the high-degree effects individually. A priori, there is reason to believe this to be something we can accomplish – intuitively, higher-degree transfers have the least impact on margin uncertainty, because votes that transfer through more winners lose more of their weight. But finding the right mathematical language to justify this may be tricky. Still on the subject of mathematical work, it would be good to have a better description of the properties needed of the profile projections for an election state to be ‘sufficiently far away’ from degeneracy. Our statistical framework for Meek auditing is only justified as long as the instant keep factor solutions to the system of equations \vec{F} in ( 6 ) live in a connected component of the solution space where the jacobian of \vec{F} is non-singular. Describing (and testing) necessary conditions for this criterion to be fulfilled would make this auditing framework more airtight. The best we can currently do is verify that at least one of the winners in all degree-2 election states we include in our audit graph is secure; in such a case it is impossible for the election state to become degenerate. But a better procedure would surely be needed to audit elections with more seats. Finally, one interesting line of thought might be to consider alternative election rulesets that combine the best of both worlds from Meek and WIGM STV. The advantage of Meek is its structural independence from chronology, whereas the WIGM rule’s advantage is computational simplicity. Both of these traits might reasonably be combined into a ‘hybrid’ election rule: for example, by re-computing transfer values/keep-factors each round as Meek does, but only running one iteration of the calibration process, such that there is no need to consider their convergence. Such a modification will surely have to consider chronology in some limited capacity – to account for scenarios where the second winner only makes quota because of transfers from the first, it will at least be necessary to calibrate the winners’ transfer values in the order they got elected, meaning election states will have to track this election order. This would still have an advantage over WIGM in that it would not be necessary to track the set of hopeful candidates at the time of each winner’s election. In the Portland District 4 example, this would make it so that all 4,097,797 edges that saw Olivia Clark elected could still collapse down to the same election state in time. The re-calculation of quota in every round, though elegant, might also best be avoided to keep a hybrid rule simple. Such a modified STV rule would still be flexible enough for the audit graphs not to diverge in cases such as our case study, while avoiding the computational challenges we noted in Section 2.4 – the dependence of the transfer values on the profile projections would be cleaner, and it would certainly remove the possibility of degenerate election states. Appendix A Audit Graph for Portland D1