{"id":"77c284ab-eb51-420b-8727-df8922349261","arxiv_id":"2607.21178","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Tighter (often exact) STV election margins are computed with improved bound heuristics and pruning, making mismatch-based risk-limiting audits practical for real elections.","lead":"This paper improves the algorithm for computing how many ballots would have to be rewritten to change who wins in a ranked-choice election under single transferable vote (STV) rules — the election's 'margin'. The new version computes much higher margins, and often exact margins, for real US, Scottish, Irish and Australian elections, making statistically rigorous post-election audits practical.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound heuristics assume one ballot alters a tally gap by at most 2 votes; STV's quota-driven transfer values can make a single ballot change swing many votes, so the computed 'lower bounds' may overestimate the true margin.","rationale":"The reader's weakest assumption focused on the min/max pile and ballot-value bookkeeping (Eqs. 2–7) possibly being incorrect. My stress-test identifies a more specific and more fundamental gap: even if those bounds on tallies are correct for the original ballot profile, the heuristics take a further step—dividing a tally difference by 2—that relies on a linearity property that STV does not have. This is the actual load-bearing step for the validity of the lower bound. The paper provides only worked examples, not a proof of the required Lipschitz property. Because the algorithm takes the maximum of several lower bounds, a single overestimating heuristic can break the central claim. I did not find a direct counterexample in the paper, but the absence of proof and the known non-linear behavior of STV make this a concrete, serious risk. The empirical results and the MINLP formulation are credible, so REJECT would be too strong; however, the claim 'exact or near-exact margins' and the RLA sample sizes should not be accepted without further validation. The reader's CONDITIONAL verdict remains appropriate, with the condition sharpened: the authors must prove or empirically test the /2 bound under non-linear transfer-value effects.","tokens_in":15398,"tokens_out":28564,"duration_ms":257265,"concrete_test":"Write a brute-force verifier for small STV elections (≤5 candidates, ≤3 seats, ≤25 ballots): enumerate all possible manipulated profiles up to a small budget m, compute the actual set of winners under WIGM, and record the true margin. For each prefix π generated by STV-26, evaluate the heuristics of §3.2 (Eqs. 6–18) and check whether any heuristic value exceeds the true margin. Run over all (or a large random sample of) profiles. If any prefix yields a heuristic > true margin, the lower bound is invalid. A simpler analytical test: construct a profile where one ballot change flips a candidate over quota so that a large surplus transfer changes another candidate's tally by >2, and check whether Eq. 14 overestimates the true displacement cost.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that STV-26 yields valid margin lower bounds depends on every lower-bounding heuristic in §3.2 never exceeding the true minimum manipulation. The elimination bound (Eq. 8), the displacement bound (Eq. 14), and the LeftAtEndCost construction (Eq. 18) all use the same core step: they divide a tally difference (V_min_c − V_max_c') by 2 and treat this as a ballot-change lower bound. This implicitly assumes that modifying one ballot can change the difference between two candidates' tallies by at most 2 votes. In STV/WIGM this is not true. A single altered ballot can push a candidate over (or under) the quota, changing the surplus transfer value τ = (V−Q)/V and thereby reweighting every ballot in that candidate's pile. One changed ballot can thus move many votes among subsequent candidates, breaking the 2-vote-per-ballot Lipschitz bound. Consequently, the true manipulation count to realize a given prefix can be far smaller than (V_min−V_max)/2, so the heuristic values in Eqs. 8–18 can overestimate the minimal manipulation. If even one such overestimation occurs, the algorithm's final returned 'lower bound' (the minimum over explored complete outcomes) can be above the true margin, and the §5 RLA sample sizes (e.g., ~55 ballots for NT'22) would not meet the stated risk limit. The paper states these bounds are demonstrated on Examples 4–7, but examples do not establish the required universal property, and no proof is offered. The MINLP lower bound (Appendix B) might be valid if solved globally, but the heuristics are used to prune and to define the search; an unsound heuristic can invalidate the result even when the MINLP is sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper improves the BST-19 branch-and-bound algorithm for computing lower bounds on the margin of STV (WIGM) elections. The contributions are a MINLP-based lower-bound solver, tighter margin upper bounds from ConcreteSTV, new lower-bounding heuristics (elimination, quota, displacement) built on min/max tally bookkeeping, and a dominance-based pruning rule. The authors report exact or near-exact margins for many real elections and argue that the resulting lower bounds make mismatch-based risk-limiting audits practical. The central claim is that the computed quantities are valid lower bounds on the number of ballot manipulations needed to change the winner set.","tokens_in":15627,"tokens_out":18976,"duration_ms":190918,"significance":"If the bounds are valid, the work is practically significant: it substantially reduces audit sample sizes for mid-sized STV elections and provides an open-source implementation. The controlled re-baselining on identical hardware (BST-19*) and the explicit statement that the lower-bound guarantee does not depend on upper-bound correctness are good methodological choices. However, the validity of the new lower-bounding heuristics is the linchpin of the paper, and no proof is supplied; on inspection, the 1/2-vote argument is inconsistent with WIGM's transfer and skip dynamics.","major_comments":[{"comment":"The factor 1/2 is load-bearing and unproved, and it is false under WIGM. These equations implicitly assume that changing one ballot changes the difference between two candidates' tallies at a round by at most 2 votes. In WIGM a single changed ballot can flip a candidate across the quota threshold, changing the eligibility/skip status of an entire transfer. Concretely, with Q=308, let E have 307 first preferences and C have 510, of which 110 are [C,E,D]. If E receives C's surplus, E's tally is 307+110·(202/510)=350.57. Changing one ballot so that E has 308 first preferences at the start of round 1 makes E ineligible for C's transfer, so E's tally is 308: a swing of about 42.6 votes from one ballot. Hence the heuristics can overestimate the true minimal manipulation. Examples 4–7 are arithmetic demonstrations, not proofs; no theorem establishes the required lower-bound property.","section":"§3.2, Eqs (8), (14), (18)"},{"comment":"The min/max pile bookkeeping contradicts the stated WIGM skip rule. Section 2.1 says ballots skip any remaining candidate that had a quota at the start of the round, even if not yet seated. In Example 1/4, E has 350 first preferences, so E has a quota at the start of round 1; the 110 [C,E,D] ballots must skip E. Thus Vmax_{E,2}=393.56 in Example 4 is inconsistent with the paper's own rules; the value should be 350. This error propagates into Examples 5–7 and into the definitions of Bmaybe/Bmust (Eqs 3–6). The ambiguity the model tries to capture ('depending on when E achieves their quota') does not exist for a candidate that starts the round with a quota.","section":"§2.1 vs §3.2, Example 4"},{"comment":"The empirical claims of exact or near-exact margins rest on the unsound lower bounds. The 'exact' entries are those where the STV-26 lower bound equals the ConcreteSTV upper bound; if the lower bound can overestimate, equality is not exactness. The paper should validate the bounds against independently computed exact margins for the small contests (e.g., the MN and Glasgow cases) and should report MINLP-only lower bounds separately from the heuristic bounds. Without such validation, the RLA sample-size statements (e.g., 'about 55 ballots' for NT 2022) are not supported.","section":"Table 3 and §5"}],"minor_comments":[{"comment":"Typo: 'In this this paper' should be 'In this paper'.","section":"§1"},{"comment":"The reported quota 9334 for |B|=2334 and N=3 is inconsistent; the Droop quota should be 584. Please check the data entry.","section":"Table 3, Langside row"},{"comment":"The notes state that bold marks the best value between STV-26 and BST-19*, and also that bold marks elections with an exact margin only with STV-26. These two conventions overlap and make the table hard to read; please distinguish them.","section":"Table 3"},{"comment":"The variable 'rul' is called a 'running upper limit' but it is an upper bound on the returned lower bound. Consider renaming it to 'incumbent' or 'best lower bound found' to avoid confusion.","section":"Algorithm 1"}],"recommendation":"reject","confidential_remarks":"I recommend reject rather than major revision because the core lower-bounding heuristics are not merely unproved: WIGM admits one-ballot swings larger than two votes, and the paper's own Example 4 contradicts its stated skip rule. Fixing this would require replacing or re-proving the central algorithmic claims and redoing the evaluation, which is beyond a normal revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the best current attempt at practical STV margin lower bounds, and the engineering improvements are real. But the central safety property — the heuristics in §3.2 are always true lower bounds on the manipulation count — is not proven and, on the evidence of the equations, may be false. If that's right, the §5 audit sample sizes (55 ballots for NT'22, etc.) are not guaranteed to meet the risk limit.\n\nWhat's genuinely good: the paper gives a controlled re-implementation baseline (BST-19*), full equations for the min/max tally bookkeeping, the displacement bound, and the MINLP formulation, plus worked examples. The performance gains are large and consistent: exact margins for many smaller contests, big improvements on Australian Senate contests. The authors are open about the ConcreteSTV upper bound caveat (Appendix A), which is a sign of care.\n\nThe major soft spot is the division-by-2 lower bound in Eqs. 8, 14, 18. It assumes one altered ballot changes the difference between two candidates' tallies by at most 2. In WIGM, that isn't true. A single ballot can push a candidate across the quota, changing the surplus transfer value and causing every subsequent ballot in that pile to be reweighted — or to skip the candidate entirely. Effects on a later candidate's tally can be far larger than 2 per changed ballot. The min/max tallies in Eqs. 5–7 are computed from the original ballot multiset; they do not bound tallies after manipulation. Worked Examples 4–7 show how the numbers come out; they do not establish the universal property. If any of these bounds overestimates, the final 'lower bound' can be above the true margin and the RLA sample sizes in §5 are too small.\n\nTwo smaller soft spots: the dominance rule in §3.3 rests on an unproven order-independence claim about the MINLP's relaxation; and the MINLP section never says which solver is used or whether the reported values are proven optima. That matters for the 'exact margin' claims. Also, no commit hash or solver version for the repo.\n\nBottom line: if I were running an RLA tomorrow, I wouldn't trust these numbers until the lower-bound heuristics carry proofs (or a small formal counterexample is found and fixed). But the MINLP alone is a sound method, and the empirical results might all be correct. The right path is a serious referee pass with a request for either a soundness proof or a re-scoped claim.","headline":"Real engineering improvements, but the new lower-bound heuristics are not proven to be lower bounds, and the quota-skip mechanism in WIGM gives a concrete reason to doubt them.","tokens_in":16324,"tokens_out":34483,"would_cite":false,"duration_ms":310461,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that an improved branch-and-bound algorithm, STV-26, computes exact or near-exact margins for many real STV elections and much tighter lower bounds for large ones, shrinking audit sample sizes from over a thousand ballots","keywords":["single transferable vote","margin of victory","risk-limiting audit","branch and bound","minimal manipulation","lower bounds","preferential voting","surplus transfer"],"falsifier":"Enumerate all possible manipulated profiles for a small STV election (e.g., 4–6 candidates, a few dozen ballots), compute the true margin by brute force, and compare with STV-26's reported lower bound; if any reported bound exceeds the true margin, the bookkeeping is unsound. Alternatively, instrument STV-26 to print the min/max tallies on a random profile and check against the actual tabulation of every nearby manipulated profile.","tokens_in":15136,"feed_emoji":"🗳️","tokens_out":6302,"duration_ms":55777,"temperature":0.7,"pith_summary":"Single transferable vote (STV) elections are hard to audit because the margin—the fewest ballots that must be changed to flip the winner set—is hard to compute. This paper tries to establish that a new algorithm, STV-26, can compute exact margins for many smaller real-world STV elections and substantially tighter lower bounds for large ones, by extending an existing branch-and-bound search with a nonlinear minimal-manipulation solver, sharper tally and transfer-value bounds, and dominance pruning. The payoff is concrete: for the NT 2022 election, a mismatch-based risk-limiting audit would need about 55 ballots on average with the new lower bound, versus more than 1000 with the previous method. If correct, this makes risk-limiting audits of many STV contests practical for the first time.","feed_headline":"New STV margin bounds shrink audits from 1000 to 55 ballots","feed_subtitle":"Improved branch-and-bound algorithm finds exact or near-exact margins for many real ranked-choice elections.","key_machinery":"The load-bearing machinery is the prefix-tree search with three lower-bounding heuristics—an elimination bound, a quota bound, and a new displacement bound—all built on min/max ballot-value bookkeeping (Equations 2–7) that tracks where each ballot could be and what value it could have at each round, including bounds on surplus transfer values. The MINLP that finds the minimal manipulation for a prefix is solved by keeping nonlinearities, with merged 'super candidate' elimination sequences to keep it tractable. A dominance rule prunes nodes sharing the same relaxed structure if a previously explored node has a lower bound no larger.","core_discovery":"The paper's central claim is that the STV-26 algorithm obtains valid and much tighter lower bounds on the margin of real STV elections than the previous BST-19 approach. The algorithm searches a tree of partial election orders (prefixes), computing for each prefix a lower bound on the number of ballot changes needed to realise an outcome extending that prefix. The improvements are: solving the minimal-manipulation MINLP with its nonlinearities intact under a super-candidate relaxation; new minimum/maximum ballot-value bookkeeping (tails, piles, transfer-value bounds) that yields sharper elimination, quota, and displacement lower bounds; and a dominance rule that discards nodes whose relaxed","pith_inferences":["The same prefix-based lower-bounding structure could likely be adapted to other sequential voting rules with transfers, such as variants that use the whole surplus, by replacing the transfer-value update equations.","A brute-force validation on small random profiles (comparing the returned lower bound to the true margin by exhaustive search) would empirically test the unproven bookkeeping bounds; this is cheap and could be done before deployment.","The combination of tighter upper bounds from constructive manipulation search and these tighter lower bounds could produce certified exact margins for contests that are currently too large for the MINLP to solve exactly.","One subtle risk: the implementation uses floating-point arithmetic, so formally verified or fixed-precision versions may be needed for legally binding audits."],"forward_implications":["Mismatch-based risk-limiting audits of STV elections become practical at scale: for example, the NT 2022 election would require roughly 55 sampled ballots at 0.1% mismatch instead of over 1000.","For many smaller contests the algorithm computes the exact margin, not just a bound, giving precise closeness information.","The improvements carry over to Australian Senate rules for 2-seat races, since WIGM and Senate transfer rules coincide when only one surplus distribution occurs.","Large Australian Senate contests with hundreds of candidates and 6–12 seats remain out of reach, so further scaling work is needed."],"fun_headline_variants":["STV margin bounds tightened: audits drop from 1000 to 55 ballots","New STV-26 algorithm yields tighter margins, slashes audit ballots","Tight STV margin bounds: risk-limiting audits need just 55 ballots","STV margin computation advances: audits now practical with 55 ballots","Improved STV margin bounds shrink audit workload to 55 ballots"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the min/max pile and ballot-value bookkeeping always bracket the true tabulation for every reachable prefix, so that the elimination, quota, and displacement heuristics never overestimate the true minimal manipulation; this is shown on worked examples but not proven, and the floating-point implementation could in principle violate it.","fun_headline_variants_meta":{"raw":{"variants":["STV margin bounds tightened: audits drop from 1000 to 55 ballots","New STV-26 algorithm yields tighter margins, slashes audit ballots","Tight STV margin bounds: risk-limiting audits need just 55 ballots","STV margin computation advances: audits now practical with 55 ballots","Improved STV margin bounds shrink audit workload to 55 ballots"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1183,"prompt_tokens":638,"completion_tokens":545,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":382,"completion_tokens_details":{"reasoning_tokens":449}},"tokens_in":382,"tokens_out":545,"duration_ms":5811,"temperature":1.0,"reasoning_tokens":449,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T08:14:55.606847+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all possible manipulated profiles for a small STV election (e.g., 4–6 candidates, a few dozen ballots), compute the true margin by brute force, and compare with STV-26's reported lower bound; if any reported bound exceeds the true margin, the bookkeeping is unsound. Alternatively, instrument STV-26 to print the min/max tallies on a random profile and check against the actual tabulation of every nearby manipulated profile.","supporting_citations":[],"review_version":1}