Instant Runoff Voting on Graphs: Exclusion Zones and Distortion
2026
Read Instant Runoff Voting on Graphs: Exclusion Zones and Distortion (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10290.txt.
Description
Georgios Birmpas and co-authors study exclusion zones in instant-runoff voting held on graphs, where voters rank candidates by shortest-path distance. They ask whether a target candidate can lose, whether a set forms an exclusion zone, and how to find the smallest such zone. All three tasks prove solvable in polynomial time on planar graphs, including trees, though the bounds show tractability rather than practical speed. On one-apex graphs the same tasks turn hard, so planarity marks a sharp boundary for this voting setup.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107968 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10290