The Communication Complexity of Instant-Runoff Voting

de Panafieu, Élie; Durand, François; Lang, Jérôme

doi:10.24963/ijcai.2026/375

The Communication Complexity of Instant-Runoff Voting

Élie de Panafieu, François Durand, Jérôme Lang

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 3376-3384.

https://doi.org/10.24963/ijcai.2026/375

Keywords

Game Theory and Economic Paradigms: Computational social choice

Abstract

The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in an election with m candidates. We study the communication complexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound of O(n (log m)^2), but did not provide a matching lower bound beyond Omega(n log m). We resolve this open problem by raising the lower bound to Omega(n (log m)^2) using the fooling set technique, thereby showing that the communication complexity of IRV is Theta(n (log m)^2). We further show that this complexity drops to Theta(n log m) under the single-peakedness restriction, and that both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV. (Extended version with appendices: https://shs.hal.science/hal-05566718. Short video: https://youtu.be/gTXV3R2DS6o.)

Élie de Panafieu, François Durand, and Jérôme Lang. 2026. The Communication Complexity of Instant-Runoff Voting. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 3376–3384. https://doi.org/10.24963/ijcai.2026/375

@inproceedings{ijcai2026p375,
  title     = {The Communication Complexity of Instant-Runoff Voting},
  author    = {de Panafieu, Élie and Durand, François and Lang, Jérôme},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {3376--3384},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/375},
  url       = {https://doi.org/10.24963/ijcai.2026/375},
}

TY  - CPAPER
TI  - The Communication Complexity of Instant-Runoff Voting
AU  - de Panafieu, Élie
AU  - Durand, François
AU  - Lang, Jérôme
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 3376
EP  - 3384
DO  - 10.24963/ijcai.2026/375
UR  - https://doi.org/10.24963/ijcai.2026/375
ER  -