2026/05/22 by Élie de Panafieu, François Durand, Jérôme Lang · 1 voice
Computer Science · #cs.MA
paper · pdf · doi:10.48550/arxiv.2605.23743
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 Ω(n log m). We resolve this open problem by raising the lower bound to Ω(n (log m)2) using the fooling set technique, thereby showing that the communication complexity of IRV is Θ(n (log m)2). We further show that this complexity drops to Θ(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.