Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.10290 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917482700210176 |
|---|---|
| author | Birmpas, Georgios Chionas, Georgios Drousiotis, Efthyvoulos Habibi, Soodeh Mavronicolas, Marios Spirakis, Paul |
| author_facet | Birmpas, Georgios Chionas, Georgios Drousiotis, Efthyvoulos Habibi, Soodeh Mavronicolas, Marios Spirakis, Paul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_10290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tractable Exclusion Zones for Instant-Runoff Voting on Trees and Beyond Birmpas, Georgios Chionas, Georgios Drousiotis, Efthyvoulos Habibi, Soodeh Mavronicolas, Marios Spirakis, Paul Computer Science and Game Theory 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. |
| title | Tractable Exclusion Zones for Instant-Runoff Voting on Trees and Beyond |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2603.10290 |