CNRS researchers resolve IRV communication complexity with tight bound

A team from CNRS (Élie de Panafieu, François Durand, Jérôme Lang) has settled a 20-year-old open question about the communication complexity of Instant-Runoff Voting (IRV). The problem asks: in the worst case, how many bits must n voters send to a central authority to determine the winner among m candidates under the most efficient elicitation protocol? Prior work by Conitzer and Sandholm (2005) established an upper bound of O(n (log m)²) and a lower bound of Ω(n log m), leaving a gap. The new paper bridges that gap with a tight lower bound of Ω(n (log m)²) using the fooling set technique, proving the communication complexity of IRV is exactly Θ(n (log m)²).

The researchers further show that this complexity drops to Θ(n log m) when voter preferences are single-peaked—a realistic restriction in many political settings. Additionally, both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension, share the same asymptotic communication complexity as IRV. These results provide fundamental limits for designing efficient, scalable voting protocols, with direct implications for large-scale elections and multi-agent systems where communication bandwidth is a constraint.