pith. sign in

arxiv: 2605.23743 · v1 · pith:PTONMFUNnew · submitted 2026-05-22 · 💻 cs.MA

The Communication Complexity of Instant-Runoff Voting

\'Elie de Panafieu , Fran\c{c}ois Durand , J\'er\^ome Lang (LAMSADE , CNRS) This is my paper

Pith reviewed 2026-05-25 02:24 UTC · model grok-4.3

classification 💻 cs.MA
keywords communication complexityinstant-runoff votingfooling setsvoting rulessingle-peaked preferencessingle transferable votepreference elicitation
0
0 comments X

The pith

Instant-Runoff Voting requires Θ(n (log m)^2) bits of communication in the worst case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper closes the gap on the communication complexity of Instant-Runoff Voting by proving a new lower bound of Ω(n (log m)^2) that matches the existing O(n (log m)^2) upper bound. This is done by applying the fooling set technique to the function that maps voter preference profiles to the IRV winner. The result shows the complexity is tightly Θ(n (log m)^2). The same asymptotic cost holds for the IRV-Average variant and for Single Transferable Vote. Under the additional restriction that preferences are single-peaked, the complexity falls to Θ(n log m).

Core claim

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 have the same asymptotic communication complexity as IRV.

What carries the argument

Fooling set construction for the IRV winner function in the deterministic two-party communication model over voter profiles.

If this is right

  • The communication complexity of IRV is tightly Θ(n (log m)^2).
  • Single-peaked preferences reduce the communication complexity of IRV to Θ(n log m).
  • The IRV-Average variant has communication complexity Θ(n (log m)^2).
  • Single Transferable Vote has communication complexity Θ(n (log m)^2).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Optimal elicitation protocols for general IRV must transmit a quadratic number of bits in log m.
  • Fooling-set arguments may extend to other iterative voting rules that eliminate candidates one by one.
  • For elections with a large number of candidates the communication overhead scales with the square of the logarithm of the candidate set size.

Load-bearing premise

The IRV winner function admits a sufficiently large fooling set in the standard deterministic communication complexity model.

What would settle it

Either an explicit deterministic protocol that computes the IRV winner using o(n (log m)^2) bits in the worst case, or a proof that the largest fooling set for the IRV function is smaller than required for the Ω(n (log m)^2) bound.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper analyzes the communication complexity of Instant-Runoff Voting (IRV) in the standard two-party deterministic model where n voters communicate preference profiles over m candidates to compute the IRV winner. It improves the prior Ω(n log m) lower bound to Ω(n (log m)^2) via an explicit fooling-set construction on the IRV function, matching the known O(n (log m)^2) upper bound from Conitzer and Sandholm (2005) and establishing a tight Θ(n (log m)^2) bound. The paper further proves that the complexity reduces to Θ(n log m) under single-peaked preferences and that both the IRV-Average variant and multiwinner STV have the same asymptotic complexity as standard IRV.

Significance. If the lower-bound construction holds, the result closes a 20-year open question on the communication complexity of IRV, delivering a complete tight characterization that directly informs elicitation protocol design. The single-peaked restriction and the extensions to IRV-Average and STV are natural and strengthen the contribution by showing how domain restrictions and rule variants affect information requirements. The direct application of the fooling-set technique without auxiliary parameters or reductions is a methodological strength.

minor comments (3)
  1. [§3] §3 (lower-bound section): the fooling-set construction for the IRV elimination order should include an explicit small example with n=2, m=4 to illustrate how the pairwise disagreements force Ω((log m)^2) bits per voter pair.
  2. [§4] The single-peaked upper-bound protocol in §4 is only sketched; a short pseudocode or explicit message count would clarify why it achieves O(n log m) rather than inheriting the general-case quadratic log factor.
  3. [§5] The STV result claims identical complexity but does not specify whether the number of winners k is fixed or part of the input; this should be stated explicitly when defining the communication problem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The report correctly summarizes the main contributions, including the tight Theta(n (log m)^2) bound for IRV via the fooling-set lower bound, the reduction to Theta(n log m) on single-peaked domains, and the matching complexity for IRV-Average and multiwinner STV.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation applies the standard fooling-set technique directly to the IRV winner function in the deterministic two-party communication model to obtain the Ω(n (log m)^2) lower bound. The matching upper bound is cited from an independent 2005 reference by different authors. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, or imported uniqueness theorems appear; the central claim is obtained by external method application rather than reduction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of deterministic communication complexity and the fooling-set lemma; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Deterministic two-party communication complexity model for the IRV winner function
    Invoked implicitly when applying the fooling-set technique to obtain the Ω(n (log m)^2) lower bound.

pith-pipeline@v0.9.0 · 5720 in / 1181 out tokens · 14946 ms · 2026-05-25T02:24:46.565019+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Single transferable vote: In- complete knowledge and communication issues

    [Ayadi et al., 2019] Manel Ayadi, Nahla Ben Amor, J ´erˆome Lang, and Dominik Peters. Single transferable vote: In- complete knowledge and communication issues. In Pro- ceedings of the 18th International Conference on Au- tonomous Agents and Multiagent Systems, AAMAS ’19 , pages 1288–1296,

    work page 2019

  2. [2]

    Bartholdi, Craig A

    [Bartholdi et al., 1989] John J. Bartholdi, Craig A. Tovey, and Michael A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare , 6(3):227–241,

    work page 1989

  3. [3]

    Burnett and Vladimir Kogan

    [Burnett and Kogan, 2015] Craig M. Burnett and Vladimir Kogan. Ballot (and voter) ’exhaustion’ under instant runoff voting: An examination of four ranked-choice elec- tions. Electoral Studies, 37:41–49,

    work page 2015

  4. [4]

    Compil- ing the votes of a subelectorate

    [Chevaleyre et al., 2009] Yann Chevaleyre, J ´erˆome Lang, Nicolas Maudet, and Guillaume Ravilly-Abadie. Compil- ing the votes of a subelectorate. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI ’09, pages 97–102,

    work page 2009

  5. [5]

    Communication complexity of common voting rules

    [Conitzer and Sandholm, 2005] Vincent Conitzer and Tuo- mas Sandholm. Communication complexity of common voting rules. In Proceedings of the 6th ACM Conference on Electronic Commerce, EC ’05, pages 78–87,

    work page 2005

  6. [6]

    Winner determination in huge elections with mapreduce

    [Csar et al., 2017] Theresa Csar, Martin Lackner, Reinhard Pichler, and Emanuel Sallinger. Winner determination in huge elections with mapreduce. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI ’17, pages 451–458,

    work page 2017

  7. [7]

    The Communication Complexity of Instant-Runoff V oting

    [de Panafieu et al., 2026] ´Elie de Panafieu, Franc ¸ois Durand, and J ´erˆome Lang. The Communication Complexity of Instant-Runoff V oting. Video presentation, https://youtu. be/gTXV3R2DS6o,

    work page 2026

  8. [8]

    Generalizing instant runoff voting to allow indifferences

    [Delemazure and Peters, 2024] Th´eo Delemazure and Do- minik Peters. Generalizing instant runoff voting to allow indifferences. In Proceedings of the 25th ACM Conference on Economics and Computation, EC ’24, page 50,

    work page 2024

  9. [9]

    Sur le d´eveloppement d’une fraction con- tinue li´ee `a la s´erie hyperg´eom´etrique et son interpr´etation en termes de records et anti-records dans les permutations

    [Dumont and Kreweras, 1988] Dominique Dumont and Ger- main Kreweras. Sur le d´eveloppement d’une fraction con- tinue li´ee `a la s´erie hyperg´eom´etrique et son interpr´etation en termes de records et anti-records dans les permutations. European Journal of Combinatorics, 9(1):27–32,

    work page 1988

  10. [10]

    Coalitional manipulation of voting rules: Simulations on empirical data

    [Durand, 2023] Franc ¸ois Durand. Coalitional manipulation of voting rules: Simulations on empirical data. Constitu- tional Political Economy, 34(3):390–409,

    work page 2023

  11. [11]

    Why instant-runoff voting is so resilient to coalitional manipulation: Phase transi- tions in the perturbed culture

    [Durand, 2025] Franc ¸ois Durand. Why instant-runoff voting is so resilient to coalitional manipulation: Phase transi- tions in the perturbed culture. In Proceedings of the 24th International Conference on Autonomous Agents and Mul- tiagent Systems, AAMAS ’25, pages 658–666,

    work page 2025

  12. [12]

    The politics of electoral systems

    [Gallagher and Mitchell, 2005] Michael Gallagher and Paul Mitchell. The politics of electoral systems . OUP Oxford,

    work page 2005

  13. [13]

    Determining winners in elections with absent votes

    [Han et al., 2024] Qishen Han, Amelie Marian, and Lirong Xia. Determining winners in elections with absent votes. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI ’24 , pages 2816–2824,

    work page 2024

  14. [14]

    Proportionality in multi-winner RCV elections: A simulation study with ballot truncation

    [Hoffman et al., 2021] Christina Hoffman, Jakini Kauba, Julie Reidy, and Thomas Weighill. Proportionality in multi-winner RCV elections: A simulation study with ballot truncation. Technical report, SSRN: https://ssrn.com/abstract=3942892,

    work page 2021

  15. [15]

    [Institute for Mathematics and Democracy, 2026] Institute for Mathematics and Democracy

    Accessed: 2026-05-06. [Institute for Mathematics and Democracy, 2026] Institute for Mathematics and Democracy. Em- pirical analysis of ranked choice methods. https://mathematics-democracy-institute.org/ empirical-analysis-of-ranked-choice-voting-methods/,

    work page 2026

  16. [16]

    Com- piling the votes of a subelectorate for multi-winner voting rules

    [Karia and Lang, 2024] Neel Karia and J´erˆome Lang. Com- piling the votes of a subelectorate for multi-winner voting rules. In International Conference on Algorithmic Deci- sion Theory, ADT ’24, pages 18–32,

    work page 2024

  17. [17]

    Marc Kilgour, Jean-Charles Gr´egoire, and Ang `ele M

    [Kilgour et al., 2020] D. Marc Kilgour, Jean-Charles Gr´egoire, and Ang `ele M. Foley. The prevalence and con- sequences of ballot truncation in ranked-choice elections. Public Choice, 184(1):197–218,

    work page 2020

  18. [18]

    [Kim and Roush, 1996] Ki Hang Kim and Fred W. Roush. Statistical manipulability of social choice functions. Group Decision and Negotiation, 5(3):263–282,

    work page 1996

  19. [19]

    Communication complexity

    [Kushilevitz and Nisan, 1997] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press,

    work page 1997

  20. [20]

    Procaccia, Nisarg Shah, and David P

    [Mandal et al., 2019] Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David P. Woodruff. Efficient and thrifty voting by any means necessary. In Annual Conference on Neural Information Processing Systems, NeurIPS ’19, pages 7178–7189,

    work page 2019

  21. [21]

    A note on Nanson’s rule

    [Niou, 1987] Emerson Niou. A note on Nanson’s rule. Pub- lic Choice, 54(2):191–193,

    work page 1987

  22. [22]

    Service and Julie A

    [Service and Adams, 2012] Travis C. Service and Julie A. Adams. Communication complexity of approximating voting rules. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’12, pages 593– 602,

    work page 2012

  23. [23]

    Nicolaus Tideman

    [Tideman, 1987] T. Nicolaus Tideman. Independence of clones as a criterion for voting rules. Social Choice and Welfare, 4(3):185–206,

    work page 1987

  24. [24]

    The single transferable vote

    [Tideman, 1995] Nicolaus Tideman. The single transferable vote. Journal of Economic Perspectives, 9(1):27–38,

    work page 1995

  25. [25]

    Kleinberg

    [Tomlinson et al., 2023] Kiran Tomlinson, Johan Ugander, and Jon M. Kleinberg. Ballot length in instant runoff vot- ing. In Proceedings of the 37th AAAI Conference on Arti- ficial Intelligence, AAAI ’23, pages 5841–5849,

    work page 2023

  26. [26]

    Strategic, sincere, and heuristic voting under four election rules: an experimental study

    [Van der Straeten et al., 2010] Karine Van der Straeten, Jean-Franc ¸ois Laslier, Nicolas Sauger, and Andr ´e Blais. Strategic, sincere, and heuristic voting under four election rules: an experimental study. Social Choice and Welfare, 35(3):435–472,

    work page 2010

  27. [27]

    Practical algorithms for multi-stage voting rules with par- allel universes tiebreaking

    [Wang et al., 2019] Jun Wang, Sujoy Sikdar, Tyler Shep- herd, Zhibing Zhao, Chunheng Jiang, and Lirong Xia. Practical algorithms for multi-stage voting rules with par- allel universes tiebreaking. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI ’19 , pages 2189–2196,

    work page 2019

  28. [28]

    On the outstanding elements of permutations

    [Wilf, 1995] Herbert S Wilf. On the outstanding elements of permutations. preprint,

    work page 1995

  29. [29]

    Compilation complexity of common voting rules

    [Xia and Conitzer, 2010] Lirong Xia and Vincent Conitzer. Compilation complexity of common voting rules. In Pro- ceedings of the Twenty-Fourth AAAI Conference on Artifi- cial Intelligence, AAAI ’10, pages 915–920,

    work page 2010