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

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107968
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10290

Browse the full library · About the Tower of Babel