Tractable Exclusion Zones for Instant-Runoff Voting on Trees and Beyond
Pith reviewed 2026-05-15 13:47 UTC · model grok-4.3
The pith
Exclusion zones for instant-runoff voting become polynomial-time computable on trees.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
On trees with deterministic tie-breaking, both exclusion-zone verification and minimum-zone computation are solvable in polynomial time. A membership test asks whether a candidate can be forced to lose against opponents from a restricted region; a round-1 reduction shows any such loss has a first-round elimination witness, enabling a bottom-up dynamic program. The pairwise-loss graph is a tournament, so every nonempty exclusion zone is generated by the closure of one vertex and the minimum zone is found by testing only linearly many candidates.
What carries the argument
The round-1 reduction to first-round elimination witnesses together with the closure property of the pairwise-loss tournament, which together support the bottom-up dynamic program on trees.
If this is right
- Verification of any proposed exclusion zone runs in polynomial time on trees.
- The minimum exclusion zone can be found by testing only linearly many candidate closures instead of all subsets.
- The same hardness results extend to the broader class of strong forced-elimination rules on general graphs.
- The dynamic program works for any deterministic multi-round elimination rule that respects the first-round reduction.
Where Pith is reading between the lines
- Similar dynamic programs may become tractable on graphs of bounded treewidth.
- Election districts whose road networks are tree-like could adopt these checks for robustness analysis.
- The tournament-closure observation may simplify minimum-zone search for other elimination-based voting rules.
Load-bearing premise
The input graph is a tree and tie-breaking is deterministic.
What would settle it
A small tree instance in which the dynamic program outputs a zone that still permits an IRV winner from outside the zone under the given distances and tie-breaking.
read the original abstract
Instant-runoff voting (IRV) is often used when voters rank candidates rather than choosing only one favourite. We study IRV under graph-induced metric preferences where each vertex of an unweighted undirected graph hosts one voter and is also a possible candidate location. Voters rank candidates by shortest-path distance with fixed deterministic tie-breaking. We focus on exclusion zones, i.e., sets S such that, whenever at least one candidate lies in S, the IRV winner must also lie in S. Such zones serve as robustness certificates, identifying regions whose participation prevents outside winners from emerging. For general graphs, exclusion-zone verification is co-NP-complete and minimum-zone computation is NP-hard. We show that both problems become polynomial-time solvable on trees. Our main tool is a membership test asking whether a candidate can be forced to lose using opponents from a restricted region. A round-1 reduction shows that any such loss has a witness in which the candidate is eliminated in the first IRV round, enabling a bottom-up dynamic program on trees. We also show that minimum-zone computation has a much smaller search space than its definition suggests. The pairwise-loss graph, obtained from all two-candidate elections, imposes closure constraints on every exclusion zone. With deterministic tie-breaking this graph is a tournament, implying that every nonempty exclusion zone on a tree is generated by the closure of one vertex. Thus, the minimum exclusion zone can be found by testing only linearly many candidate sets. On the opposite front, we refine the intractability range of computing minimum exclusion zones on general graphs, extending it to a much broader class of deterministic elimination rules, dubbed as Strong Forced Elimination.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies exclusion zones for Instant-Runoff Voting (IRV) under shortest-path metric preferences on graphs, where each vertex is both a voter and candidate location with deterministic tie-breaking. It claims that exclusion-zone verification and minimum-zone computation are polynomial-time solvable on trees via a round-1 reduction enabling bottom-up DP, plus a tournament closure argument on the pairwise-loss graph that reduces the search space to O(n) candidates. It also extends NP-hardness results for minimum exclusion zones on general graphs to the broader class of Strong Forced Elimination rules.
Significance. If the results hold, they supply efficient algorithms for identifying robust regions in IRV on tree-structured graphs, which arise in hierarchical or path-like networks. The explicit round-1 reduction and the linear search-space reduction via tournament closure are strengths that make the positive results on trees concrete and potentially implementable. The hardness extension to Strong Forced Elimination broadens the negative results without introducing new parameters.
major comments (1)
- [§4.2] §4.2 (Dynamic Program): the recurrence for subtree states tracks only local first-round margins but does not explicitly accumulate the global vote totals from ancestor subtrees; since IRV elimination depends on the full profile, this risks missing interactions that could alter the forced-loss witness outside the subtree.
minor comments (2)
- [§3] The definition of the pairwise-loss graph (used for the tournament closure) is introduced after the DP; moving the definition to §3 would improve readability when the linear-search claim is stated.
- [Figure 2] Figure 2 caption refers to 'closure of a single vertex' but the figure itself does not label the generating vertex; adding an explicit marker would clarify the illustration of the tournament property.
Simulated Author's Rebuttal
We thank the referee for the positive recommendation and the detailed comment on §4.2. We address the concern regarding accumulation of global vote totals in the dynamic program below.
read point-by-point responses
-
Referee: [§4.2] §4.2 (Dynamic Program): the recurrence for subtree states tracks only local first-round margins but does not explicitly accumulate the global vote totals from ancestor subtrees; since IRV elimination depends on the full profile, this risks missing interactions that could alter the forced-loss witness outside the subtree.
Authors: We appreciate the referee's observation on potential interactions with ancestor subtrees. The round-1 reduction (Lemma 4.1) is key here: any forced loss of a candidate admits a witness in which that candidate is eliminated in the very first IRV round. First-round elimination depends exclusively on first-place vote totals, which are strictly additive over the disjoint subtrees of any rooted tree. Consequently, the DP state maintained for each subtree is not merely a local margin but the full vector of first-place votes contributed by every voter inside the subtree to each relevant candidate. These vectors are combined bottom-up by summing the child vectors and adding the contribution of the local voter at the subtree root. The forced-loss test is then evaluated on the fully accumulated totals at the point where the candidate under consideration becomes the root of the current subtree. Because the first-round scores contain no higher-order dependencies and the tree decomposition ensures every voter belongs to exactly one subtree at each combination step, ancestor contributions are incorporated exactly when the DP reaches the relevant ancestor node. No additional state for ancestor margins is required. We are therefore confident that the recurrence already accounts for all global interactions needed for the round-1 witness. revision: no
Circularity Check
No significant circularity identified
full rationale
The derivation relies on direct structural reductions: a round-1 elimination witness for forced losses and the fact that deterministic tie-breaking turns the pairwise-loss graph into a tournament whose transitive closure on trees is generated by single vertices. These steps follow immediately from the definitions of IRV elimination, shortest-path distances, and tree topology; no parameter is fitted to data, no result is renamed as a prediction, and no load-bearing premise is justified solely by self-citation. The dynamic program and linear-time search are therefore independent of the target claims and remain valid under the stated assumptions of tree input and deterministic tie-breaking.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Input graphs are unweighted undirected trees with deterministic tie-breaking
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.