Instant Runoff Voting on Graphs: Exclusion Zones and Distortion

Georgios Birmpas, Georgios Chionas, Efthyvoulos Drousiotis, Soodeh Habibi, Marios Mavronicolas, Paul Spirakis

Abstract

We study instant-runoff voting (IRV) under metric preferences induced by an unweighted graph where each vertex hosts a voter, candidates occupy some vertices (with a single candidate allowed in such a vertex), and voters rank candidates by shortest-path distance with fixed deterministic tie-breaking. We focus on exclusion zones, vertex sets S such that whenever some candidate lies in S, the IRV winner must also lie in S. While testing whether a given set S is an exclusion zone is co-NP-Complete and finding the minimum exclusion zone is NP-hard in general graphs, we show here that both problems can be solved in polynomial time on trees. Our approach solves zone testing by designing a Kill membership test (can a designated candidate be forced to lose using opponents from a restricted set?) and shows that Kill can be decided in polynomial time on trees via a bottom-up dynamic program that certifies whether the designated candidate can be eliminated in round 1. A greedy shrinking process then recovers the minimum zone under a standard nesting assumption. To clarify the limits of tractability beyond trees, we also identify a rule level property (Strong Forced Elimination) that abstracts the key IRV behavior used in prior reductions, and show that both exclusion-zone verification and minimum- zone computation remain co-NP-complete and NP-hard, respectively, for any deterministic rank-based elimination rule satisfying this property. Finally, we relate IRV to utilitarian distortion in this discrete setting, and we present upper and lower bounds with regard to the distortion of IRV for several scenarios, including perfect binary trees and unweighted graphs.

Introduction

Instant Runoff Voting (IRV) is a multi-round elimination rule often praised for its ability to select moderate winners. To formalize this moderation, researchers use the concept of Exclusion Zones: a set of locations $S$ such that if any candidate is placed within $S$, the eventual winner must also come from $S$. While IRV is computationally difficult to analyze in general graphs due to its non-monotonic nature, this paper demonstrates that the problem becomes tractable when the underlying network is a tree.

Algorithmic Framework for Trees

The primary algorithmic contribution is a polynomial-time solution for trees based on a "Kill" membership test. The test, Kill(T, u, A), determines if a candidate $u$ can be forced to lose when all other candidates are chosen from a restricted set $A$.

Boundary Collapse and Dynamic Programming

On a tree, any subtree interacts with the rest of the graph only through a single "boundary" vertex. This "boundary collapse" allows for a bottom-up dynamic programming (DP) approach. The DP summarizes how voters in a subtree might support candidates inside versus outside that subtree.

Subtree structure and boundary vertices used in the tree dynamic program.

The authors prove a critical Round-1 Reduction: if $u$ can be eliminated at all, there exists a configuration where $u$ is eliminated in the very first round. This reduces the problem to a plurality-score feasibility check, which the DP evaluates by tracking a state tuple across subtrees.

The KILLDP Algorithm

The high-level algorithm for deciding the Kill test on trees is summarized below. It iterates through nodes in postorder, merging child summaries via knapsack-style aggregation to maintain feasible tuples.

High-level overview of the KILLDP algorithm for trees.

Hardness and Distortion Results

To explain the difficulty in general graphs, the paper introduces Strong Forced Elimination (SFE). This property abstracts the behavior where eliminating one candidate preserves the relative preferences for survivors. The authors show that any deterministic rank-based rule satisfying SFE (including IRV) remains NP-hard for exclusion-zone problems on general graphs.

Beyond complexity, the paper establishes the first distortion bounds for IRV in discrete graph-based metric spaces:

  • Paths ($P_n$): Distortion is at most 2 (and at least 1.8).
  • Perfect Binary Trees: Distortion is at most 3.
  • General Graphs: IRV distortion is $\Omega(\sqrt{\ln m})$ and $O(\ln m)$, matching bounds previously known only for more complex metric spaces.

Conclusion

This work provides the first polynomial-time results for IRV exclusion zones on trees, despite high exponents ($O(n^{13})$ for testing). It bridges social choice and graph theory by linking exclusion zones to utilitarian distortion. Future work remains in optimizing these algorithms and exploring randomized tie-breaking, which may bypass the hardness results associated with Strong Forced Elimination.

Summary updated

Abstract

We study instant-runoff voting (IRV) under metric preferences induced by an unweighted graph where each vertex hosts a voter, candidates occupy some vertices (with a single candidate allowed in such a vertex), and voters rank candidates by shortest-path distance with fixed deterministic tie-breaking. We focus on exclusion zones, vertex sets S such that whenever some candidate lies in S, the IRV winner must also lie in S. While testing whether a given set S is an exclusion zone is co-NP-Complete and finding the minimum exclusion zone is NP-hard in general graphs, we show here that both problems can be solved in polynomial time on trees. Our approach solves zone testing by designing a Kill membership test (can a designated candidate be forced to lose using opponents from a restricted set?) and shows that Kill can be decided in polynomial time on trees via a bottom-up dynamic program that certifies whether the designated candidate can be eliminated in round 1. A greedy shrinking process then recovers the minimum zone under a standard nesting assumption. To clarify the limits of tractability beyond trees, we also identify a rule level property (Strong Forced Elimination) that abstracts the key IRV behavior used in prior reductions, and show that both exclusion-zone verification and minimum- zone computation remain co-NP-complete and NP-hard, respectively, for any deterministic rank-based elimination rule satisfying this property. Finally, we relate IRV to utilitarian distortion in this discrete setting, and we present upper and lower bounds with regard to the distortion of IRV for several scenarios, including perfect binary trees and unweighted graphs.
BibTeX
@misc{birmpas2026instant,
  author = {Georgios Birmpas and Georgios Chionas and Efthyvoulos Drousiotis and Soodeh Habibi and Marios Mavronicolas and Paul Spirakis},
  title = {{Instant Runoff Voting on Graphs: Exclusion Zones and Distortion}},
  year = {2026},
  eprint = {2603.10290},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.10290},
}
Figure