The Communication Complexity of Instant-Runoff Voting
For computational social choice theorists, this provides the first tight lower bound for IRV's communication complexity, settling a question left open since 2005.
The paper resolves the open problem of the communication complexity of Instant-Runoff Voting (IRV), proving a tight bound of Θ(n (log m)²) bits, and shows that under single-peaked preferences the complexity drops to Θ(n log m).
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.