Paper deep dive

The Communication Complexity of Instant-Runoff Voting

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

Year: 2026Venue: arXiv preprintArea: cs.MAType: PreprintEmbeddings: 52

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 7/8/2026, 7:34:56 PM

Summary

This paper resolves an open problem regarding the communication complexity of Instant-Runoff Voting (IRV). It proves that the worst-case communication complexity for IRV is Θ(n (log m)^2), matching the previously known upper bound. The authors use the fooling set technique to establish this lower bound. Additionally, they show that under single-peaked preferences, the complexity drops to Θ(n log m), and that IRV-Average and Single Transferable Vote (STV) share the same asymptotic complexity as IRV.

Entities (8)

Communication Complexity · concept · 99%Instant-Runoff Voting · voting-rule · 98%Fooling Set Technique · method · 97%Single-Peakedness · preference-restriction · 96%Conitzer and Sandholm · researcher · 95%Single Transferable Vote · voting-rule · 95%IRV-Average · voting-rule-variant · 94%Progressive Preference Revelation Protocol · protocol · 93%

Relation Signals (6)

Instant-Runoff Voting → hascommunicationcomplexity → Θ(n (log m)^2)

confidence 98% · 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).

Fooling Set Technique → proveslowerbound → Θ(n (log m)^2)

confidence 97% · 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).

Single-Peakedness → reducescomplexityto → Θ(n log m)

confidence 96% · 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)...

Conitzer and Sandholm → establishedupperbound → O(n (log m)^2)

confidence 95% · 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).

Single Transferable Vote → isextensionof → Instant-Runoff Voting

confidence 95% · Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV.

IRV-Average → hassamecomplexityas → Instant-Runoff Voting

confidence 94% · both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

51,581 characters extracted from source content.

Expand or collapse full text

The Communication Complexity of Instant-Runoff Voting ́ Elie de Panafieu 1 ,Franc ̧ois Durand 1 ,J ́ er ˆ ome Lang 2 1 Nokia Bell Labs 2 CNRS, LAMSADE, Universit ́ e Paris-Dauphine, PSL, France francois.durand, elie.de panafieu@nokia-bell-labs.com, lang@lamsade.dauphine.fr Abstract The communication complexity of a voting rule is the worst-case number of bits thatnvoters must transmit to a central authority under the most ef- ficient elicitation protocol in an election withm candidates.We study the communication com- plexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound ofO(n(logm) 2 ), but did not provide a match- ing lower bound beyondΩ(nlogm). We resolve this open problem by raising the lower bound toΩ(n(logm) 2 )using the fooling set technique, thereby showing that the communication complex- ity of IRV isΘ(n(logm) 2 ).We further show that this complexity drops toΘ(nlogm)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. A video presentation is available online [ de Panafieuet al., 2026 ] . 1 Introduction Assessing the suitability of a voting rule requires analyzing its normative properties, its computational issues, and itscom- munication complexity, while also taking into account the rule’s understandability by laypeople. Among these criteria, communication complexity is especially relevant: if exces- sive interaction is required, voters may abandon the voting process altogether or, at best, submit their preferences hastily and without due care. In this respect, communication com- plexity is arguably more directly relevant to practical deploy- ment than computational complexity: the cost of computation falls on a machine, whereas the cost of communication falls on voters. A communication protocol for a voting rule is an interac- tive elicitation procedure in which, at each step, some voters are asked to transmit information about their vote, conditional on the responses obtained in previous steps, and that fully de- termines the outcome of the election. The complexity of a communication protocol is the total number of bits transmit- ted by voters in the worst-case execution of the protocol. The communication complexity of a voting rule is the minimum complexity over all its communication protocols. In this paper, our main focus is on the communication com- plexity ofInstant-Runoff Voting(IRV), a prominent single- winner voting rule used in many large-scale political elec- tions. IRV proceeds by successive elimination of the candi- date with the fewest top-ranked votes. The rule is sometimes also referred to asSingle Transferable Vote(STV); following standard terminology, we use IRV for the single-winner rule and STV for its multiwinner variant. The communication complexity of voting rules was first, and mostly, studied by Conitzer and Sandholm [ 2005 ] . In this framework, only the bits sent by voters are counted: messages sent by the central authority and received by voters are not taken into account, as the communication (or elicitation) bur- den falls on voters rather than on the central authority, which is typically a computer. Their upper bounds are established via explicit communication protocols, whereas their lower bounds rely on the classicalfooling settechnique [ Kushilevitz and Nisan, 1997 ] , which we recall later. Their results iden- tify the communication complexity of most common voting rules, with a notable exception: IRV, for which they leave a gap between a lower boundΩ(nlogm)and an upper bound O(n(logm) 2 ). To date, this gap has not been filled yet. Answering this open question is particularly relevant given the prevalence of IRV in real-world elections, both in large- scale political contexts and in lower-stakes settings. If the communication complexity of IRV isΘ(n(logm) 2 ), then the known upper bound is asymptotically optimal, and efforts should focus on refining and implementing the existing pro- tocol on interactive voting platforms. If, on the other hand, the communication complexity of IRV has a smaller order of magnitude thann(logm) 2 , this would imply the existence of a more efficient protocol yet to be discovered. We do not resist the temptation to spoil the reader: we close this gap by proving that the communication complexity of IRV is indeedΘ(n(logm) 2 ). Section 2 provides background and related work. Section 3 introduces the framework. Section 4 presents our main result: the communication complexity of IRV is bounded below by Ω(n(logm) 2 ). In Section 5 we show that the communication complexity of IRV drops toΘ(nlogm)under the restriction to single-peaked profiles, and that both the IRV-Average vari- ant and the multiwinner rule STV have the same asymptotic arXiv:2605.23743v1 [cs.MA] 22 May 2026 communication complexity as IRV. Section 6 concludes. 2 Background and Related Work 2.1 Instant-Runoff Voting (IRV) IRV is used in a wide range of elections across several coun- tries, including Australia, India, Ireland, the UK, and the US. It is one of the few commonly studied single-winner rules that are independent of clones [ Tideman, 1987 ] , and arguably the only one used in large-scale real-world elections. It is computationally hard to manipulate, even by a single voter [ Bartholdiet al., 1989 ] ; the probability that a preference pro- file is manipulable is low in most settings [ Durand, 2023; Durand, 2025 ] ; and manipulation is cognitively demanding, which tends to encourage sincere voting [ Van der Straeten et al., 2010 ] . From a computational perspective, while IRV with immediate tie-breaking is easy to compute, itsparallel universeversion is NP-hard, though still tractable in practice [ Csaret al., 2017; Wanget al., 2019 ] . IRV has also been the subject of numerous empirical studies: see [ Institute for Mathematics and Democracy, 2026 ] for a continuously up- dated survey. 2.2 Communication Complexity of Voting Rules The seminal paper by Conitzer and Sandholm [ 2005 ] identi- fies three broad classes of voting rules.High-communication rules, such as Borda, Copeland, and ranked pairs, require vot- ers to transmit their full rankings in the worst case, yield- ing a communication complexity ofΘ(nmlogm). At the other end of the spectrum,low-communicationrules, such as plurality and plurality with runoff, require each voter to transmit not much more than a single candidate, leading to a communication complexity ofΘ(nlogm).Medium- communicationrules lie between these extremes; notable examples include voting trees and Bucklin, both of which have communication complexityΘ(nm). For IRV, the gap betweenΩ(nlogm)andO(n(logm) 2 )prevents classifica- tion as a medium-communication rule, although it is widely believed to require substantially more communication than nlogm. Service and Adams [ 2012 ] study the communication com- plexity of approximating voting rules. Mandalet al. [ 2019 ] investigate the trade-off between communication complex- ity and distortion.Chevaleyreet al. [ 2009 ] , Xia and Conitzer [ 2010 ] , and Karia and Lang [ 2024 ] focus on the one- round communication complexity of voting rules, known as compilation complexity. 2.3 Communication Issues for IRV The raw definition of IRV assumes full rankings and therefore entails a high communication burden. Two natural escape routes aresimplified ballotsandinteractive protocols. The most common form of simplified ballots consists of truncated ballots: voters rank only their topkcandidates, wherekmay depend on the voter. Smaller values ofk make the input easier to elicit but provide weaker guarantees that the resulting winner coincides with the true IRV win- ner. Such truncated-ballot approximations of IRV and STV have been studied both theoretically and empirically [ Burnett and Kogan, 2015; Ayadiet al., 2019; Kilgouret al., 2020; Hoffmanet al., 2021; Tomlinsonet al., 2023 ] . Other works allow voters to express indifference [ Delemazure and Peters, 2024 ] , or consider missing and truncated ballots [ Hanet al., 2024 ] . All these works assume one-shot elicitation. By contrast, to guarantee determination of the true IRV winner, one can rely on interactive elicitation protocols. Such protocols ask voters to provide partial preference in- formation to the central authority as needed during execu- tion. As mentioned above, Conitzer and Sandholm [ 2005 ] propose an IRV protocol with communication complexity O(n(logm) 2 ). Ayadiet al. [ 2019 ] improve its practical per- formance while preserving the same worst-case complexity. 3 Framework 3.1 Rankings and Profiles We consider a set ofnvotersV=0,...,n−1and a set ofmcandidatesC=0,...,m−1. Arankingris a linear order overC, for instance(2≻0≻1). AprofileP is a collection ofnrankings, one for each voter. Given two profilesPandQ, and a voterv∈ V, we denote byP −v + Q v the profile obtained fromPby replacing the ranking of votervinPwith their ranking inQ. 3.2 Communication Complexity of Voting Rules Following [ Conitzer and Sandholm, 2005 ] , avoting rulef maps a profile to a winning candidate. Thecommunication complexityoffis the worst-case number of bits transmitted by the voters in the most efficient protocol implementingf. Afooling setFis a collection of profiles such that: 1.fhas the same outcomewfor all profilesP∈F; and 2. for any two distinct profilesP,Q∈ F, there exists a profileTobtained by selecting, for each voterv, either P v orQ v , such thatf(T)̸=w. Its existence implies a communication complexity of at least log 2 |F|forf [ Kushilevitz and Nisan, 1997 ] . As observed by Conitzer and Sandholm [ 2005 ] , it suffices to construct a fooling set for a representative set of pairs(n,m), namely for infinitely many values ofmand, for each suchm, infinitely many values ofn. All these notions extend naturally to mul- tiwinner voting rules, wherefoutputs a subset of candidates rather than a single winner. 3.3 Instant-Runoff Voting (IRV) UnderInstant-Runoff Voting(IRV), the outcome is deter- mined through successive rounds of elimination. Initially, all candidates inCareactive. In each round, each voter as- signs one point to their most-preferred active candidate, and the candidate with the lowest score is eliminated from the ac- tive set. The procedure iterates until a single active candidate remains and is declared the winner. In practical implementa- tions, it may terminate as soon as a candidate obtains a strict majority of the votes, that is, a score greater thann/2, since this candidate is then guaranteed to win. Throughout the paper, we assume that ties are broken in every round in favor of candidates with smaller indices: if several candidates are tied for the lowest score, the one with Protocol 1PPR Protocol for IRV A←C▷active candidates forv∈V: t(v)←elicitthe top candidate ofv while true: forc∈A: V(c)←v∈V |t(v) =c▷voters supportingc score(c)←|V(c)| if∃c∈Asuch that score(c)> n/2: returnc▷cis the winner else: letcbe a candidate inAminimizing score(c)(possi- bly using tie-breaking) removecfromA forv∈V(c): t(v)←elicitthe top candidate ofvinA thelargestindex is eliminated. Alternative tie-breaking rules are discussed in Section 4.5. 4 Communication Complexity of IRV Section 4.1 recalls the communication protocol for IRV de- scribed by Conitzer and Sandholm [ 2005 ] , yielding an upper bound ofO(n(logm) 2 ). To obtain a matching lower bound, Sections 4.2, 4.3, and 4.4 introduce a family of profilesF, show that it forms a fooling set, and derive its asymptotic log- cardinalityΘ(n(logm) 2 ). Section 4.5 shows that this bound holds independently of the tie-breaking rule. 4.1 Progressive Preference Revelation Protocol Conitzer and Sandholm [ 2005 ] establish theO(n(logm) 2 ) upper bound on the communication complexity of IRV using Protocol 1, which we call theProgressive Preference Revela- tion(PPR) protocol. To make it more suitable for real-world usage, we add early termination as soon as a candidate obtains a strict majority of the votes. Beyond its interest for IRV, this protocol also serves as a basis for analyzing the alternative settings considered in Section 5. 4.2 Definition of the Fooling Set To build intuition for our fooling set, we start from perfectly symmetric profiles, where each ranking is represented by the same number of voters. In such profiles, the elimination order is(m−1,m−2,...,0), since ties are broken in favor of can- didates with smaller indices, and the winner is candidate0. However, some rankings cannot be distinguished by the IRV counting process in such profiles. For instance, the rank- ings(2≻4≻3≻0≻1)and(2≻0≻1≻3≻4) both initially count for candidate2and are then transferred to candidate0, where they remain until the end. We say that these two rankings have the samesignature(2,0). If two profiles differ only by replacing rankings with others having the same signature, then mixing these profiles cannot alter the IRV outcome and thus cannot prevent candidate0from win- ning, contradicting the definition of a fooling set. Thus, all rankings with the same signature will be replaced by a single ranking, called itsrepresentative. Candidates not seen by the IRV counting process, i.e., not appearing in the signature, are ranked so as to favor candi- dates with higher indices as much as possible. When mixing two distinct profiles from the fooling set, this choice will help a candidate other than0to win. Signature.As mentioned above, for a rankingr, itssig- natureσ(r)is the list of candidates observed during the IRV counting process, assuming the elimination order(m−1,m− 2,...,0). For example,σ (2≻4≻3≻0≻1) = (2,0). By convention, we include a final trivial round in which only candidate0remains and all voters vote for that candidate. For example,σ (1≻2≻0) = (1,0), even if this ballot sup- ports candidate 1 throughout the entire process in practice. Formally, the signatureσ(r)is defined by the follow- ing algorithm. Start with the empty list. For each rank i∈ 0,...,m−1, append the candidater i if and only if it has the smallest index encountered so far, that is, if r i = min j≤i r j . In combinatorics, this construction is known as therecordof a permutation, except that records are con- ventionally defined with respect to a maximum rather than a minimum [ Dumont and Kreweras, 1988 ] . The signature of a ranking is therefore always a decreasing list, starting with its top-ranked candidate and ending with candidate0. The pos- sible signatures are exactly the decreasing lists of candidates ending with0. Representative.Intuitively, for a signatures, we define its representativeρ(s)as the ranking with signaturesthat favors candidates with higher indices as much as possible. For ex- ample,ρ (2,0) = (2≻4≻3≻0≻1). Formally,ρ(s)is obtained by scanning the signatures: for each elements i , we appends i , followed by all candidates with higher indices that have not yet been added, in decreasing order. By construc- tion, for every signatures, we haveσ(ρ(s)) =s. Fooling set.Assumen=ℓm!, whereℓis a positive integer. LetP (ℓ) denote the set of all profiles in which each ranking appears exactlyℓtimes. We define our fooling setFas F= ρ(σ(P ini ))|P ini ∈P (ℓ) , whereρ(σ(P ini ))denotes the profile obtained fromP ini by replacing each rankingrwithρ(σ(r)), the representative of its signature. An equivalent definition is as follows.LetR(s) = |σ −1 (s)|denote the number of rankings with signatures. The fooling setFthen consists of all profiles that contain, for each signatures, exactlyℓR(s)copies ofρ(s). For example, form= 3, consider this profileP ini ∈P (1) : 001122 120201 212010 Each column represents a voter’s ranking; for instance, the leftmost voter has ranking(0≻1≻2). Candidates belong- ing to the signatures are highlighted in bold. Note that the first two rankings have the same signature, as do the next two. By taking the representative of each signature, we obtain the profileP=ρ(σ(P ini )), which belongs toF: 001122 222201 110010 The other profiles inFare the reorderings ofP, such as the following profileQ, where the reordered columns are high- lighted. 001212 222021 110100 In both profilesPandQ, the IRV counting process is the same as inP ini , and therefore candidate0wins. However, consider the profileP −3 +Q 3 , obtained by borrowing the fourthvoter fromQ(of index3, as indices start at0): 001222 222001 110110 Candidate1is eliminated in the first round; the corresponding ballot then transfers to candidate2, who is eventually elected. In particular, the winner is not candidate0. To prove thatF is a fooling set, it remains to generalize this observation. 4.3 Proof of the Fooling Set Property We now prove thatFis a fooling set for IRV. In any profileP ini ∈ P (ℓ) , the elimination order is(m− 1,m−2,...,0). Hence, in the profileP=ρ(σ(P ini )), the IRV counting process is identical, and candidate0is elected. LetPandQbe two distinct profiles ofF. Then there exists a votervwhose ranking isrinPand a different rankingr ′ inQ. Different tops.Suppose thatrandr ′ differ in their top- ranked candidate, saycforranddforr ′ , and assume without loss of generality thatc < d. Consider the profileP −v +Q v . In this profile, candidatecreceives one fewer top vote than average, whiledreceives one more. In the initial round t= 0, candidatecis therefore eliminated. By the defini- tion of the representativeρ, all corresponding vote transfers go to candidatem−1. At each subsequent roundt >0, can- didatem−1holds (t+1)n m votes, while every other remaining candidate has n m votes, up to a discrepancy of one vote due to voterv. One of these candidates is then eliminated, and again all transfers go to candidatem−1. Eventually, candi- datem−1is elected. General case.The two rankingsrandr ′ necessarily have distinct signatures: by construction ofF, if they had the same signatures, they would both be equal to the rankingρ(s). The signaturesσ(r)andσ(r ′ )share a common prefix and then differ at some position: σ(r) = (s 0 ,...,s j ,c,...), σ(r ′ ) = (s 0 ,...,s j ,d,...), where, without loss of generality, we assumec < d. Note thats j ̸= 1, otherwise we would havec=d= 0by defi- nition of a signature. Consider the profileP −v +Q v . Until the elimination ofs j , the counting process proceeds as usual, eliminating candidatesm−1,m−2,...,s j in this order. At that point, we are back in the case whererandr ′ differ in their top-ranked candidate, and candidates j −1is eventually elected. Sinces j ̸= 1, candidate0is not the winner, which establishes thatFis a fooling set. 4.4 Cardinality of the Fooling Set Rankings with a given signature.As shown by Wilf [ 1995, item (IV) ] , the number of rankings with a given signaturesis R(s) = Y c∈C c,(1) whereC the set of candidates that do not appear in the signature. The simplicity of this formula follows directly from our choice to label the candidates as0,1,...,m−1, which actually motivated this convention. Exact cardinality ofF.As noted in Section 4.2, the pro- files inFare exactly the reorderings of any one of them. If all voters had distinct rankings, this would yieldn!distinct profiles. However, for each signatures, there areℓR(s)vot- ers with identical rankings, and we must therefore divide by (ℓR(s))!to avoid multiple counting. Using Equation (1) and the change of variablesS=C , we obtain the following expression for the cardinality of the fooling set: |F|= n! Q S⊆[1,m−1] ℓ Q c∈S c ! ,(2) where the empty product corresponding toS=∅evaluates to1by convention. Asymptotics.We give here the main steps of the proof; full details are provided in Appendix A.1. To approximate Equa- tion (2), we considern=ℓm!, withℓ,m, or both tending to infinity. We take the logarithm of the exact expression (2) and apply Stirling’s formulalog(a!) =a(loga−1) +O(loga) twice, which yields log|F|=n logn−1 +O(logn) − X S⊆[1,m−1] ℓ Y c∈S c logℓ−1 + X c∈S logc +O X S⊆[1,m−1] log ℓ Y c∈S c . Interchanging the sums overS⊆[1,m−1]andc∈S, and applying twice the identity P T⊆B Q c∈T c= Q c∈B (1 +c), we obtain log|F|=n logn−1 −ℓm! logℓ−1 −ℓm! m−1 X j=1 jlogj j+ 1 +O X S⊆[1,m−1] log(ℓm!) which reduces, after substitutingn=ℓm!, to log|F|=n m−1 X j=1 logj j+ 1 +O(2 m logn). The sum is estimated using a Riemann sum-integral compari- son, and the error term is found negligible forn=ℓm!, which finally yields log|F|∼ n(logm) 2 2 . This establishes the desired lower bound on the worst-case communication complexity of any protocol for IRV. Combin- ing this result with the upper boundO(n(logm) 2 )provided by Conitzer and Sandholm [ 2005 ] and based on the PPR pro- tocol (Protocol 1), we deduce the following theorem. Theorem 1.The communication complexity of IRV isΘ n(logm) 2 . 4.5 Discussion of the Tie-Breaking Rule The fooling set studied in Sections 4.2, 4.3, and 4.4 relies on the assumption that ties are broken in favor of candidates with lower indices. However, the construction can be adapted to eliminate all ties, showing that the resulting lower bound remains valid under any tie-breaking rule. Indeed, we can append at the end of each profile a small collection of additional voters that simulates tie-breaking in favor of lower indices: one voter whose top choice is candi- datem−1, two voters whose top choice is candidatem−2, . . . ; andmvoters whose top choice is candidate0. Their rankings are completed by placing the remaining candidates in ascending order of their indices; for instance, the voter whose top choice ism−1has ranking(m−1≻0≻1≻ ·≻m−2). Altogether, this yields a numberm(m+ 1)/2 oftie-breaking voters. A closely related idea already appears implicitly in the proofs of Conitzer and Sandholm [ 2005 ] , al- though it is not stated explicitly in these terms. Now assumeℓ > m(m+ 1)/2. The outcome of IRV then depends only on the remaining voters, which we call thesig- nificant voters, except when a tie arises among them, in which case the tie-breaking voters come into play. Since the number of voters added in this way is negligible, the previous asymptotic estimate of the size of the fooling set remains unchanged, and consequently so does the lower bound on the communication complexity of any protocol for IRV. What does change with the tie-breaking rule is the upper bound: if the tie-breaking rule requires information that is not revealed during the PPR protocol, then the worst-case com- munication complexity may be larger. 5 Related Settings In this section, we consider three variants of our main setting: IRV under single-peaked preferences (Section 5.1), the IRV- Average voting rule (Section 5.2), and STV, the multiwinner version of IRV (Section 5.3). 5.1 IRV in Single-Peaked Profiles In this section, we add the classical assumption that voters’ preferences aresingle-peakedwith respect to the reference axis(0,...,m−1). This means that for any voter and any triple of candidatesc 1 < c 2 < c 3 , candidatec 2 cannot be the least preferred among the three. Equivalently, for any voter and any strict non-empty prefix(c 1 ≻...≻c j−1 )of her ranking, the next-ranked candidatec j must have either the immediately smaller or the immediately larger index among those not yet encountered. We further assume that the refer- ence axis is known in advance and can be exploited by the protocol. Upper bound.In this setting, the PPR protocol becomes significantly cheaper. The first step is unchanged, since each voter is asked to elicit her top-ranked candidate. At each subsequent step, however, it suffices to ask the relevant vot- ers whether their next preferred candidate, among the non- eliminated ones, lies to the left or to the right of the candidate that has just been eliminated. This requires only a single bit of communication, instead oflog 2 mbits. We give an example of execution in Appendix B.1. Whenjcandidates remain, the candidate eliminated in that round has at mostn/jtop supporters, since the minimum score is never larger than the average. Therefore, the worst-case communication complex- ity of the protocol is nlog 2 (m) + n m + n m−1 +·+ n 3 =O(nlogm). Definition of the fooling set.We now construct a fooling set that yields a matching lower bound on the communication complexity of IRV in the single-peaked setting. We may assume without loss of generality thatmis a power of two: it suffices to establish the lower bound for an infinite subset of possible values ofm. We also assume that n=ℓmfor some integerℓ >2; the rationale for this choice will become clear shortly. Our fooling setFconsists of all profiles with exactlyℓ voters for each ranking of the form (c≻c−1≻·≻0≻c+ 1≻c+ 2≻·≻m−1). In other words, there areℓvoters for each possible peak posi- tionc, and all voters complete their rankings by successively filling the remaining positions with all candidates to the left of the peak, followed by all candidates to the right. Proof of the fooling set property.We writec→das shorthand for the fact that candidatecis eliminated and all votes cast forcare transferred tod. In any profile ofF, under our usual tie-breaking rule favoring smaller indices, the elimination process unfolds as follows. First, we have m−1→m−2,m−3→m−4, . . . ,1→0, that is, odd-indexed candidates transfer to the even candidate imme- diately to their left. Next,m−2→m−4, . . . ,2→0, mean- ing that candidates congruent to2 mod 4transfer to candi- dates that are multiples of4. And so on. Eventually, we ob- tainm/2→0, and candidate0is declared the winner. Now letPandQbe two distinct profiles inF. There exists a votervwhose ranking isrinPand a different rankingr ′ inQ. Letcandddenote the respective peak candidates ofr andr ′ . Since profiles inFcontain only one type of ranking for each peak position, we necessarily havec̸=d. Without loss of generality, assume thatc < d, that is,chas a smaller index thand. Ifcis odd, consider the profileQ −v +P v , illustrated in Table 1. Initially, candidatecreceivesℓ+ 1votes, candi- datedreceivesℓ−1votes, and every other candidate re- ceives exactlyℓvotes. First, candidated, and possibly some ·ℓ+ 1ℓ·ℓ−1· ·c−2c−1c+ 1·d· c−3c−2c−1cd−1 . . . . . . . . . . . . . . . Table 1: Excerpt of the profileQ −v +P v constructed for the proof of the fooling set property in the single-peaked setting, when the peak candidatecof votervis odd. In each column, the header gives the number of voters, and the entries below specify their common ranking. After some eliminations of candidates with indices greater thanc, we havec−1→c−2, thenc−3→c−4, and so on, until 2→1, then candidate0is eliminated. candidates to the right ofcwithℓvotes, are eliminated; the corresponding votes are transferred to candidates of index at leastc. Once all remaining candidates to the right ofchave more thanℓvotes, eliminations then start to occur on the left ofc:c−1→c−2,...,2→1, and finally candidate0is eliminated. The winner is therefore not0. Ifcis even, consider the profileP −v +Q v . In the initial round, candidatecreceivesℓ−1votes, candidatedreceives ℓ+1votes, and every other candidate receives exactlyℓvotes. The first candidate eliminated is thereforec. Ifc= 0, we are done. Otherwise, we havec→c−1. Candidatec−1now has2ℓ−1votes, which is strictly greater thanℓ+ 1since we assumedℓ >2. From this point on, the remainder of the argument is analogous to the case wherecis odd: after some eliminations of candidates to the right ofc−1, eliminations occur on the left, yieldingc−2→c−3,...,2→1, and finally candidate0is eliminated. This completes the proof thatFis a fooling set. Cardinality ofF.The fooling set consists of all possible permutations of thenvoters, where the voters are partitioned intomclasses ofℓvoters with identical rankings. Conse- quently, |F|= n! (ℓ!) m . Applying Stirling’s approximation, straightforward calcula- tions detailed in Appendix B.2 yield log|F|∼nlogm. This establishes the desired lower bound on the worst-case communication complexity of any protocol for IRV in the single-peaked setting. We can therefore state the following theorem. Theorem 2.The communication complexity of IRV in the single-peaked setting isΘ (nlogm). In Appendix B.3, we show that, as in Section 4.5, the lower bound remains valid for any tie-breaking rule, using the same tie-breaking voters technique. 5.2 IRV-Average We now examineIRV-Average, a rule similar to IRV in which, at each round, multiple candidates may be eliminated simul- taneously, depending on how their scores compare to the av- erage (see, e.g., Durand [ 2023 ] ). We consider two variants. In thestrictversion, all candidates whose number of votes is strictly below the average are eliminated. In theweakversion, candidates with a score lower than or equal to the average are eliminated. In both cases, an exception rule must be specified to handle perfect ties and to prevent the elimination of either none or all candidates. This rule is similar to the Nanson and Kim–Roush rules, which operate analogously using, respectively, the Borda and Veto scores [ Niou, 1987; Kim and Roush, 1996 ] . A straightforward adaptation of the PPR protocol applies to IRV-Average and achieves the same worst-case communi- cation complexity, provided that the tie-handling exception requires no additional information. For example, perfect ties may be resolved by immediately declaring the smallest-index candidate the winner, or by eliminating the largest-index can- didate. Moreover, the fooling-set lower bound established for IRV extends to IRV-Average. To cover both the strict and weak variants, as well as all possible exception rules, it suffices to use the fooling set with tie-breaking voters introduced in Sec- tion 4.5. We thus obtain the following theorem, analogous to Theorem 1 for IRV. Theorem 3.The communication complexity of IRV-Average isΘ n(logm) 2 . 5.3 STV Single Transferable Vote (STV) is the multiwinner analogue of IRV. It satisfies several desirable normative properties and is used in political elections in a number of jurisdictions [ Tideman, 1995; Gallagher and Mitchell, 2005 ] . Letkdenote the number of candidates to be elected. STV is defined sequentially, similarly to IRV, with the difference that at each step either a candidate is elected or a candidate is eliminated. Initially, each voter has a voting weight equal to 1. A candidate is elected at a given step if the total weight of votes supporting it reaches a threshold called thequotaQ, which remains constant throughout the process. There are several classical ways to define the quota as a function ofn andk; the most common is theDroop quota,Q=⌊ n k+1 ⌋+ 1. Once a candidate is elected, the voters supporting it see their voting weights reduced and their votes are transferred to their next preferred candidate. Again, there are various ways to update the weights, either deterministically or stochastically. The choice of the quota rule and of the weight-update mech- anism does not affect the communication complexity of the rule. When no candidate is elected at a given step, the candidate with the least support is eliminated, and all votes supporting it are transferred to their next preferred candidate. The process continues until eitherkcandidates have been elected orn−kcandidates have been eliminated; in the latter case, the remaining active candidates become elected. Upper bound.The STV-PPR protocol (Protocol 2) gen- eralizes the PPR Protocol 1 to an arbitrary numberk≥1 of winners. Its worst-case communication complexity is at- tained on profiles in which each possible ranking appears the Protocol 2STV-PPR Protocol A←C▷active candidates E←∅▷elected candidates forv∈V: t(v)←elicitthe top candidate ofv w(v)←1▷weight of voterv while true: forc∈A: V(c)←v∈V |t(v) =c▷voters supportingc score(c)← P v∈V(c) w(v) letcbe a candidate inAmaximizing score(c) ifscore(c)≥Q: addctoEand remove it fromA if|E|=k: returnE update the weightsw(v)of voters inV(c) ▷several variants exist removev∈V(c)|w(v) = 0fromVandV(c) else: letcbe a candidate inAminimizing score(c) removecfromA if|E|+|A|=k: returnE∪A forv∈V(c): t(v)←elicitthe top candidate ofvinA same number of times. In such profiles, at each step all re- maining candidates are tied, and ties are broken, as usual, in favor of smaller indices. Candidatesm−1,...,kare therefore eliminated one by one; subsequently, all candi- datesk−1,...,0are elected. Provided thatkis constant, the resulting communication complexity of the protocol is O n(logm) 2 . STV-signature.We replace the notion of IRV-signature σ(r)of a rankingr, previously simply called asignature, with theSTV-signature ̃σ(r), defined as follows. For each ranki∈0,...,m−1, append the candidater i if and only if it is the smallest candidate index encountered so far, that is, ifr i = min j≤i r j . Stop as soon as an index belonging to 0,...,k−1has been added. Fork= 4, an example of an STV-signature is ̃σ(7≻9≻3≻4≻5≻0≻1≻6≻2≻8) = (7,3). Note that, unlike in the IRV case, candidate0does not neces- sarily appear in the signature. The STV-signature ̃σ(r)thus corresponds to the list of candidates encountered in rankingr by the STV-PPR protocol when assuming the elimination or- der(m−1,...,k). STV-representative.The notion of a representative for a signature is adapted similarly. Among the rankings compati- ble with a given STV-signature, we select the one that favors candidates with higher indices as much as possible. We de- note the STV-representative of an STV-signaturesby ̃ρ(s). For example, withm= 10andk= 4, ̃ρ (7,3) =7≻9≻3≻8≻6≻5≻4≻2≻1≻0. Fooling set.LetP (ℓ) again denote the family of all profiles overmcandidates in which each ranking appears exactlyℓ times, so that the total number of voters isn=ℓm!. We define F= ̃ρ( ̃σ(P ini ))|P ini ∈P (ℓ) , where ̃ρ( ̃σ(P ini ))is the profile obtained fromP ini by replacing each rankingrwith ̃ρ( ̃σ(r)), the STV-representative of its STV-signature. By an argument analogous to the one used for IRV,Fis a fooling set for STV. Size of the fooling set.An STV-signature is a decreasing sequence of elements from0,...,m−1that contains ex- actly one element in0,...,k−1, namely its last element. For any STV-signature(s 0 ,...,s j−1 ), there is a one-to-one correspondence between rankings having this STV-signature and rankings having IRV-signature(s 0 ,...,s j−2 ,0): it suf- fices to interchange candidatess j−1 and0. Recall thatR(s) denotes the number of rankings with IRV-signatures, and let ̃ R(s)denote the number of rankings with STV-signatures. Using (1), we obtain ̃ R((s 0 ,...,s j−1 )) = Y c∈[1,m−1]\s 0 ,...,s j−2 c. The size of the fooling set for STV is therefore |F|= n! Q S⊆[k,m−1] ℓ Q c∈[1,m−1] c ! k (3) Asymptotic communication complexity of STV.A sim- ilar analysis to the one carried out for IRV, detailed in Ap- pendix A.2, shows that, for fixedk, log|F|= Θ n(logm) 2 . Since this lower bound matches the upper bound derived from the analysis of the STV-PPR protocol, we obtain the follow- ing theorem, which is not affected by the choice of the quota rule and of the weight-update mechanism. Theorem 4.The communication complexity of STV isΘ n(logm) 2 . 6 Discussion Our main conclusion is that the communication complexity of IRV isΘ(n(logm) 2 ), which implies that the PPR protocol is asymptotically optimal and confirms that STV is, as ex- pected, a medium-communication rule. Since we now know that no significantly better protocol can exist asymptotically, it is timely to implement this protocol in interactive voting platforms. Of course, using the PPR protocol in practice re- quires voters to remain online long enough, or to reconnect when prompted,e.g.via email. Although such assumptions remain unrealistic for large-scale political elections, they may be reasonable in low-stake or small-scale settings. This conclusion also applies to STV and IRV-Average, but not to IRV under single-peaked preferences, for which the protocol simplifies. Since the lower bound is only attained asymptotically, it makes sense to study theexactcommunication complexity of IRV and STV for small values ofmand/orn, in order to de- sign finely optimized protocols for practical voting platforms. Acknowledgments We thank Emma Caizergues for fruitful discussions about the fooling set used for IRV. This work has been supported in part by a grant from the French State managed by the National Research Agency (ANR) through the France 2030 program, with the reference ANR-23-IACL-0008 (PR[AI]RIE-PSAI), and through the CONDORCET project with reference ANR- 24-EXMA-0001. References [ Ayadiet al., 2019 ] Manel Ayadi, Nahla Ben Amor, J ́ er ˆ ome Lang, and Dominik Peters. Single transferable vote: In- complete knowledge and communication issues. InPro- ceedings of the 18th International Conference on Au- tonomous Agents and Multiagent Systems, AAMAS ’19, pages 1288–1296, 2019. [ Bartholdiet 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, 1989. [ 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, 2015. [ Chevaleyreet al., 2009 ] Yann Chevaleyre, J ́ er ˆ ome Lang, Nicolas Maudet, and Guillaume Ravilly-Abadie. Compil- ing the votes of a subelectorate. InProceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI ’09, pages 97–102, 2009. [ Conitzer and Sandholm, 2005 ] Vincent Conitzer and Tuo- mas Sandholm. Communication complexity of common voting rules. InProceedings of the 6th ACM Conference on Electronic Commerce, EC ’05, pages 78–87, 2005. [ Csaret al., 2017 ] Theresa Csar, Martin Lackner, Reinhard Pichler, and Emanuel Sallinger. Winner determination in huge elections with mapreduce. InProceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI ’17, pages 451–458, 2017. [ de Panafieuet al., 2026 ] ́ Elie de Panafieu, Franc ̧ois Durand, and J ́ er ˆ ome Lang. The Communication Complexity of Instant-Runoff Voting. Video presentation, https://youtu. be/gTXV3R2DS6o, 2026. [ Delemazure and Peters, 2024 ] Th ́ eo Delemazure and Do- minik Peters. Generalizing instant runoff voting to allow indifferences. InProceedings of the 25th ACM Conference on Economics and Computation, EC ’24, page 50, 2024. [ Dumont and Kreweras, 1988 ] Dominique Dumont and Ger- main Kreweras. Sur le d ́ eveloppement d’une fraction con- tinue li ́ e ` 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, 1988. [ Durand, 2023 ] Franc ̧ois Durand. Coalitional manipulation of voting rules: Simulations on empirical data.Constitu- tional Political Economy, 34(3):390–409, 2023. [ Durand, 2025 ] Franc ̧ois Durand. Why instant-runoff voting is so resilient to coalitional manipulation: Phase transi- tions in the perturbed culture. InProceedings of the 24th International Conference on Autonomous Agents and Mul- tiagent Systems, AAMAS ’25, pages 658–666, 2025. [ Gallagher and Mitchell, 2005 ] Michael Gallagher and Paul Mitchell.The politics of electoral systems. OUP Oxford, 2005. [ Hanet al., 2024 ] Qishen Han, Amelie Marian, and Lirong Xia. Determining winners in elections with absent votes. InProceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI ’24, pages 2816–2824, 2024. [ Hoffmanet 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, 2021.Accessed: 2026-05-06. [ Institute for Mathematics and Democracy, 2026 ] Institute for Mathematics and Democracy.Em- piricalanalysisofrankedchoicemethods. https://mathematics-democracy-institute.org/ empirical-analysis-of-ranked-choice-voting-methods/, 2026. Accessed May 15, 2026. [ Karia and Lang, 2024 ] Neel Karia and J ́ er ˆ ome Lang. Com- piling the votes of a subelectorate for multi-winner voting rules. InInternational Conference on Algorithmic Deci- sion Theory, ADT ’24, pages 18–32, 2024. [ Kilgouret al., 2020 ] D.MarcKilgour,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, 2020. [ 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, 1996. [ Kushilevitz and Nisan, 1997 ] Eyal Kushilevitz and Noam Nisan.Communication complexity. Cambridge University Press, 1997. [ Mandalet al., 2019 ] Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David P. Woodruff. Efficient and thrifty voting by any means necessary. InAnnual Conference on Neural Information Processing Systems, NeurIPS ’19, pages 7178–7189, 2019. [ Niou, 1987 ] Emerson Niou. A note on Nanson’s rule.Pub- lic Choice, 54(2):191–193, 1987. [ Service and Adams, 2012 ] Travis C. Service and Julie A. Adams.Communication complexity of approximating voting rules. InInternational Conference on Autonomous Agents and Multiagent Systems, AAMAS ’12, pages 593– 602, 2012. [ Tideman, 1987 ] T. Nicolaus Tideman.Independence of clones as a criterion for voting rules.Social Choice and Welfare, 4(3):185–206, 1987. [ Tideman, 1995 ] Nicolaus Tideman. The single transferable vote.Journal of Economic Perspectives, 9(1):27–38, 1995. [ Tomlinsonet al., 2023 ] Kiran Tomlinson, Johan Ugander, and Jon M. Kleinberg. Ballot length in instant runoff vot- ing. InProceedings of the 37th AAAI Conference on Arti- ficial Intelligence, AAAI ’23, pages 5841–5849, 2023. [ Van der Straetenet 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, 2010. [ Wanget 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. InProceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI ’19, pages 2189–2196, 2019. [ Wilf, 1995 ] Herbert S Wilf. On the outstanding elements of permutations.preprint, 1995. [ Xia and Conitzer, 2010 ] Lirong Xia and Vincent Conitzer. Compilation complexity of common voting rules. InPro- ceedings of the Twenty-Fourth AAAI Conference on Artifi- cial Intelligence, AAAI ’10, pages 915–920, 2010. In this technical appendix, we provide detailed derivations and explanations that were omitted from the main body of the paper for the sake of concision. Section A groups together the closely related asymptotic analyses of the log-cardinality of the fooling sets for IRV (Section A.1) and STV (Section A.2). Section B is devoted to IRV in the single-peaked setting. We first present an example execution of the communication pro- tocol (Section B.1), then derive the asymptotic log-cardinality of the fooling set (Section B.2), and finally discuss the impact of the tie-breaking rule (Section B.3). A Asymptotic Log-Cardinality of the Fooling Set for IRV and STV A.1 Asymptotic Analysis for IRV We analyze the asymptotic behavior of the log-cardinality of the fooling setFdefined in Section 4 for IRV, which yields the lower bound underlying Theorem 1. The number of voters isn=ℓm!, and we assume thatℓ,m, or both tend to infinity. Application of Stirling’s formula.Starting from the exact expression (2), we take logarithms and obtain log|F|= log(n!)− X S⊆[1,m−1] log ℓ Y c∈S c ! . Applying Stirling’s formula log(a!) =a(loga−1) +O(loga) to each factorial term yields log|F|=n(logn−1) +O(logn) − X S⊆[1,m−1] ℓ Y c∈S c logℓ−1 + X c∈S logc +O X S⊆[1,m−1] log ℓ Y c∈S c . For any subsetS⊆[1,m−1], we haveℓ Q c∈S c≤ℓm! =n, and the number of subsets of[1,m−1]is2 m−1 . It follows that O X S⊆[1,m−1] log ℓ Y c∈S c =O(2 m logn), so theO(logn)term in the previous equation is absorbed. We now distribute the product over the sum in the previous equation, which yields log|F|=n(logn−1) −ℓ(logℓ−1) X S⊆[1,m−1] Y c∈S c −ℓ X S⊆[1,m−1] X c∈S logc Y c∈S c +O(2 m logn). A key combinatorial identity.On the one hand, we have X S⊆[1,m−1] Y c∈S c= Y c∈[1,m−1] (1 +c) =m!. Viewed algebraically as the expanded and factorized forms of the same expression, this identity also admits a combinatorial interpretation: the left-hand side sumsR(s), the number of permutations with signatures, over all possible signatures, and therefore equals the total number of permutationsm!. On the other hand, interchanging the order of summation overS⊆[1,m−1]andc∈S, and finally using the same combinatorial identity, yields X S⊆[1,m−1] X c∈S logc Y c∈S c = m−1 X c=1 X S⊆[1,m−1] c∈S logc Y d∈S d = m−1 X c=1 (logc)c X T⊆[1,m−1]\c Y d∈T d = m−1 X c=1 (logc)c m! 1 +c . We therefore obtain log|F|=n(logn−1)−ℓm!(logℓ−1) −ℓm! m−1 X c=1 c 1 +c logc+O(2 m logn). Simplification of the main expression.Substitutingn= ℓm!, we obtain log|F|=n(logℓ+ log(m!)−1)−n(logℓ−1) −n m−1 X c=1 (logc) c 1 +c +O(2 m logn) Usinglog(m!) = logm+ P m−1 c=1 logcand1− c 1+c = 1 1+c , and grouping several terms into the error term, we obtain log|F|=n m−1 X c=1 logc 1 +c +O(2 m logℓ+ 2 m mlogm). We assumed thatℓ,m, or both tend to infinity. Under these asymptotic regimes, the error terms2 m logℓand2 m mlogm are negligible compared toℓm! =n. Since 1 1+c = 1 c +O( 1 c 2 ),and since the series P c logc c diverges whereas P c logc c 2 converges, it follows that log|F|=n m−1 X c=1 logc c +O(n). Sum–integral comparison.The functionx7→ logx x has derivative 1−logx x 2 and is therefore decreasing forx≥3. It follows that Z m 4 logx x dx≤ m−1 X c=4 logc c ≤ Z m−1 3 logx x dx. For any fixeda >0andb, we have, asm→∞, Z m−b a logx x dx= log(m−b) 2 −(loga) 2 2 ∼ (logm) 2 2 . We therefore conclude that log|F|∼ n(logm) 2 2 . A.2 Asymptotic Analysis for STV In this section,Fdenotes the fooling set defined in Sec- tion 5.3, which is used to establish the lower bound on the communication complexity of STV underlying Theorem 4. We consider STV with a fixed numberkof candidates to be elected amongm. As in the IRV case, the number of voters isn=ℓm!, whereℓ,m, or both tend to infinity. The asymptotic analysis for STV closely follows that of IRV presented in Section A.1, and reduces to it in the special casek= 1. We therefore focus on the differences specific to STV, and only sketch the steps that are identical. Application of Stirling’s formula.Taking the logarithm of the expression (3) for the size of the STV fooling set yields log|F|= log(n!)−k X S⊆[k,m−1] log ℓ Y c∈[1,m−1] c ! . We then apply Stirling’s formula to each factorial term, dis- tribute the product over the sum, and bound the error term exactly as in the IRV case. This yields log|F|=n(logn−1) −kℓ(logℓ−1) X S⊆[k,m−1] Y c∈[1,m−1] c −kℓ X S⊆[k,m−1] X c∈[1,m−1] logc Y c∈[1,m−1] c +O(2 m logn). A key combinatorial identity.On the one hand, by factor- ization, we have X S⊆[k,m−1] Y c∈[1,m−1] c= (k−1)! X S⊆[k,m−1] Y c∈[k,m−1] c = (k−1)! Y c∈[k,m−1] (1 +c) = m! k . From a combinatorial perspective, the left-hand side counts the number of STV signatures associated with a fixed final candidate. Since there are exactlykpossible final candidates, multiplying this quantity bykyields the total number of per- mutations, namelym!. On the other hand, by rearranging the terms and introduc- ingT:= [k,m−1] , we obtain X S⊆[k,m−1] X c∈[1,m−1] logc Y c∈[1,m−1] c = X S⊆[k,m−1] log (k−1)! + X c∈[k,m−1] logc × (k−1)! Y c∈[k,m−1] c = m! k log (k−1)! + (k−1)! X T⊆[k,m−1] X c∈T logc Y c∈T c = m! k log (k−1)! + (k−1)! m−1 X c=k (logc) X T⊆[k,m−1] c∈T Y d∈T d = m! k log (k−1)! + (k−1)! m−1 X c=k (logc) m! k! c 1 +c = m! k log (k−1)! + m! k m−1 X c=k c 1 +c logc. We therefore obtain log|F|=n(logn−1)−ℓ(logℓ−1)m! −ℓm! log (k−1)! −ℓm! m−1 X c=k c 1 +c logc +O(2 m logn). End of the proof.Sincen=ℓm!, and under the asymptotic regimes considered here whereℓ,m, or both tend to infinity, this expression simplifies to log|F|=n m−1 X c=k logc 1 +c +O(n). The remainder of the argument is identical to the asymptotic analysis of the IRV fooling set. We therefore obtain log|F|∼ n(logm) 2 2 . B IRV in the Single-Peaked Setting In this section, we provide complementary explanations on IRV in the single-peaked setting introduced in Section 5.1. We first present an example execution of the elicitation pro- tocol, then derive the asymptotic log-cardinality of the cor- responding fooling set, and finally discuss the impact of the tie-breaking rule. B.1 Example of Execution of the Protocol We assumen= 18andm= 5, with reference axis (0,1,2,3,4). In the tables below, the header of each column indicates the number of voters in that group, and the entries give their common ranking restricted to the currently active candidates. Information transmitted during the protocol is highlighted in boldface. Voters first transmit their top-ranked candidate: 422343 012234 101343 220422 333111 444000 Candidate1is eliminated. Its two supporters are queried and each of them transmits one bit, namelyL, indicating that their next preferred candidate lies to the left of candidate1, that is, candidate0. 422343 0L(0)2234 220343 333422 444000 Candidate4is eliminated. Its three supporters do not need to be queried, since their next preferred candidate is known to be candidate3. 422343 002233 220322 333000 Candidate2is eliminated. Its five supporters are queried and each of them transmits one bit:L(left) for two of them and R(right) for the remaining three. 422343 00L(0)R(3)33 333000 The protocol then terminates, and the winner is candidate3. The total number of bits transmitted is18⌈log 2 5⌉+ 2 + 5 = 61. B.2 Asymptotic Log-Cardinality of the Fooling Set LetFdenote the fooling set for IRV in the single-peaked set- ting, defined in Section 5.1 and used to establish Theorem 2. Starting from the exact expression log|F|= log(n!)−mlog(ℓ!), we apply Stirling’s formula to obtain log|F|=n(logn−1)−mℓ(logℓ−1) +O(logn+mlogℓ). Substitutingn=ℓmand using thatℓ,m, or both tend to infinity, we conclude that log|F|∼nlogm. B.3 Discussion of the Tie-Breaking Rule We now show that the lower bound obtained in the single- peaked setting holds independently of the tie-breaking rule. Our argument is inspired by the construction used in Sec- tion 4.5, but it cannot be applied verbatim, since the tie- breaking voters introduced there are not compatible with the single-peakedness constraint. Instead, we introduce additional voters whose preferences are single-peaked with respect to the reference axis and whose role is to eliminate all ties deterministically. More pre- cisely, we add • one voter with ranking(m−1≻m−2≻·≻0); • two voters with ranking(m−2≻m−3≻ · ≻0≻ m−1); •fourvoters with ranking(m−3≻m−4≻ · ≻0≻ m−2≻m−1); •... •2 m−1 voters with ranking(0≻1≻·≻m−1). The use of powers of two ensures that no ties can occur at any stage of the elimination process. For instance, once can- didatem−1is eliminated, the above construction yields three votes for candidatem−2. Havingfourvoters with peakm−3 then guarantees a strictly higher score for candidatem−3than for candidatem−2. Altogether, this construction adds2 m −1tie-breaking vot- ers. Therefore, as soon asℓ≥2 m , the asymptotic lower bound derived for single-peaked IRV remains valid indepen- dently of the tie-breaking rule.

Instant research discovery