---
title: "The Communication Complexity of Instant-Runoff Voting"
authors:
  - "Élie de Panafieu"
  - "François Durand"
  - "Jérôme Lang"
doi: "10.24963/ijcai.2026/375"
url: "https://ijcai.org/proceedings/2026/375"
pdf: "https://ijcai.org/proceedings/2026/0375.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "3376-3384"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: Computational social choice"
---

# The Communication Complexity of Instant-Runoff Voting

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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 3376-3384. DOI: [10.24963/ijcai.2026/375](https://doi.org/10.24963/ijcai.2026/375)

## 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.)