# ballot_length_in_instant_runoff_voting__a605f0e3.pdf

Ballot Length in Instant Runoff Voting

Kiran Tomlinson1, Johan Ugander2, Jon Kleinberg1

1Cornell University 2Stanford University kt@cs.cornell.edu, jugander@stanford.edu, kleinberg@cornell.edu

Instant runoff voting (IRV) is an increasingly-popular alternative to traditional plurality voting in which voters submit rankings over the candidates rather than single votes. In practice, elections using IRV often restrict the ballot length, the number of candidates a voter is allowed to rank on their ballot. We theoretically and empirically analyze how ballot length can inﬂuence the outcome of an election, given ﬁxed voter preferences. We show that there exist preference proﬁles over k candidates such that up to k 1 different candidates win at different ballot lengths. We derive exact lower bounds on the number of voters required for such proﬁles and provide a construction matching the lower bound for unrestricted voter preferences. Additionally, we characterize which sequences of winners are possible over ballot lengths and provide explicit proﬁle constructions achieving any feasible winner sequence. We also examine how classic preference restrictions inﬂuence our results for instance, singlepeakedness makes k 1 different winners impossible but still allows at least Ω(

k). Finally, we analyze a collection of 168 real-world elections, where we truncate rankings to simulate shorter ballots. We ﬁnd that shorter ballots could have changed the outcome in one quarter of these elections. Our results highlight ballot length as a consequential degree of freedom in the design of IRV elections.

Introduction Instant runoff voting (IRV) has grown in popularity over the last two decades as an alternative to plurality voting for governmental and organizational elections. Also referred to as ranked choice voting (RCV), single transferrable vote (STV), alternative vote, preferential voting, or the Hare method, IRV allows voters to submit rankings over the candidates rather than voting for a single option. IRV determines a winner from these rankings by repeatedly eliminating the candidate who has the fewest ballots ranking them ﬁrst; the ballots that listed this eliminated candidate ﬁrst have their votes reallocated to the next candidate on their list. This process continues, repeatedly eliminating candidates, until only one is left the winner. Proponents of IRV argue that it allows voters to report their full preferences, mitigates vote-splitting when similar candidates run, encourages civility in campaigning, and

Copyright 2023, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

saves money compared to holding separate runoff elections (Fair Vote 2022; Lewyn 2012). Many local elections in the United States use IRV, including in Minneapolis, San Fransisco, Oakland, Santa Fe, and New York City, as well as statewide elections in Maine and Alaska. IRV is also used in other countries, including Australia and Ireland. However, IRV has vocal opponents who believe it to be too confusing for voters (Langan 2004; Saltsman and Paxton 2021), leading to outright bans on the use of IRV in Florida (Florida Legislature 2022) and Tennessee (Tennessee Legislature 2022). One particular issue critics point to is the complexity of a ballot that asks voters to rank every candidate, especially when the number of candidates is large. One ofﬁcial tasked with running Utah s ﬁrst IRV election raised this as her primary concern after the election: My concerns with the current RCV law are that we would recommend the number of rankings be limited to three or ﬁve instead of an unlimited number based on the number of candidates. So although you can list as many candidates as ﬁle on the ballot, I think it is a bit confusing to voters [...] For instance, in Minneapolis they rank three. In St. Paul, they rank ﬁve. They don t usually have them rank as many candidates as there are. (Swensen 2021, Salt Lake County Clerk) Indeed, many municipalities have different numbers of ranking slots on their IRV ballots, what we call ballot length: Oakland uses three, Alaska four, and New York City ﬁve. The count goes on: ballot length six would have been mandated by the failed 2019 Ranked Choice Voting Act proposing IRV for US Congressional elections (US Congress 2019). In Maine, voters can rank all of the candidates even if there are 15 of them. In fact, plurality voting can be viewed as IRV with ballot length one: losing candidates are repeatedly eliminated (without redistribution) until the candidate with a plurality is declared the winner. While making ballots shorter does make them simpler, it also strays from a goal of IRV: allowing voters to express their complete preferences over the candidates. Critics of IRV also raise concerns about ballot exhaustion during the IRV algorithm, where all candidates ranked by a voter have been eliminated and that vote no longer contributes to subsequent tallies (Burnett and Kogan 2015).1 Ballot length is

1In plurality, any vote not cast for the winner is exhausted.

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

therefore subject to competing desires: shorter ballots are easier to ﬁll out and simpler to print, but less informative about voter preferences. Despite the apparent trade-offs involved in ballot length, there has been very little investigation of how these tradeoffs might work. As noted above, plurality voting can be seen as IRV with ballot length one, and so the fact that plurality and IRV can produce different outcomes already indicates that ballot length can have important consequences. But aside from early work looking at simulations and a few real-world elections (Kilgour, Gr egoire, and Foley 2020; Ayadi et al. 2019) we do not have much insight into the consequences of ballot length more generally. Perhaps, for example, there are underlying structural properties to be discovered that constrain how many winners are possible as we vary the ballot length. Or perhaps anything goes, and if we specify which candidate we d like to see win at each possible ballot length, we can construct a ﬁxed set of rankings that produce each desired winner at the corresponding length.

Overview of Results. In this paper, we show that the effect of ballot length essentially behaves like the latter extreme, where almost every sequence of outcomes is possible. In particular, we prove that modulo a simple feasibility constraint, it is possible to pick any sequence of candidates (with repetitions allowed), and to have this be the sequence of winners at ballot lengths 1, 2, 3, .... For example, there are voter preferences such that one candidate wins if the election is run with odd ballot length and another wins with even ballot length. We make a central assumption that voters have ﬁxed ideal rankings and report as long a preﬁx of their ideal ranking as the ballot allows. Given k candidates, we show that up to k 1 of them can win as the ballot length varies from 1, . . . , k 1 and voter preferences remain ﬁxed. Moreover, we establish exact matching lower bounds on the number of voters required to produce k 1 distinct winners. We also consider how these results are affected if we make standard modeling assumptions about voters. If we model voters abstractly as exhibiting single-peaked or singlecrossing preferences, we prove that k 1 distinct winners across ballot lengths cannot be achieved. We also consider voters who rank candidates according to a shared onedimensional ideological spectrum; since such voters are both single-peaked and single-crossing, there cannot be k 1 distinct winners in these cases. We ﬁnd through simulation that in this one-dimensional case, ballot lengths above k/2 almost always produce the same winner as full IRV ballots. Finally, we use data from 168 real-world elections from Pref Lib (Mattei and Walsh 2013) (most of them originally conducted using IRV), and we ﬁnd that different winners across ballot lengths is a phenomenon that occurs commonly: in 25% of the Pref Lib elections at least two different candidates win as the ballot length is varied by truncation. However, truly pathological cases with k 1 winners appear to be extremely rare: we observe at most three distinct winners across ballot lengths, and that occurs only once in the 168 Pref Lib elections. But even with these realworld voter preferences, more than three winners can occur; by resampling ballots in the Pref Lib elections, we ob-

serve cases with four, ﬁve, and even six different winners across ballot lengths. We note that one third of the elections initially used ballot length of at most four, where it is impossible to have more than three different winners across ballot lengths. An extended version of the paper including all proofs omitted for space is available online (Tomlinson, Ugander, and Kleinberg 2022). Our code and data are available at https://github.com/tomlinsonk/irv-ballot-length.

Related Work There has been considerable work on what happens when individual voters choose not to rank all the candidates a practice sometimes called voluntary truncation in contrast with forced truncation (i.e., ballot length restrictions) (Kilgour, Gr egoire, and Foley 2020). In many voting systems including IRV, election outcomes can change dramatically as voters independently choose to rank more or fewer candidates (Saari and Van Newenhizen 1988). This matter has been studied from a computational angle as the possible winners problem, which asks, given a collection of partial ballots, which candidates could become winners as those ballots are ﬁlled out (Konczak and Lang 2005; Chevaleyre et al. 2010; Baumeister et al. 2012; Xia and Conitzer 2011; Ayadi et al. 2019). There is also a wide array of research on how partial ballots can be used for strategic voting and campaigning (Baumeister et al. 2012; Narodytska and Walsh 2014; Menon and Larson 2017; Kamwa 2022; Fishburn and Brams 1984). On the empirical side, voluntary truncation is a concern since it can lead to ballot exhaustion (Burnett and Kogan 2015). In political science, voluntary truncation is also referred to as under-voting (Neely and Cook 2008). Several studies have asked whether different demographic groups are more likely to under-vote and how this could have a disenfranchising effect (Neely and Cook 2008; Coll 2021; Hoffman et al. 2021). There has also been research on overvoting in IRV, which refers to ranking a single candidate in more than one position (e.g., ﬁrst and second), especially its correlation with underrepresented voting populations (Neely and Cook 2008; Neely and Mc Daniel 2015). In contrast, we investigate what happens when all voter preferences are truncated as a result of ballot length. That is, we focus on a question of election design rather than on voter choice. In this direction, Ayadi et al. (2019) investigated how often IRV with short ballots produces the fullballot winner in the Mallows model and in ﬁve Pref Lib elections. However, all ﬁve Pref Lib elections they studied produced the full-ballot winner at all ballot lengths in analyzing a larger collection of 168 Pref Lib elections, we ﬁnd multiple winners across ballot lengths in 25% of them. Ayadi et al. also examined several other interesting facets of IRV ballot length, including a low-communication IRV protocol (a form of online, per-voter ballot length customization) and the complexity of the possible winners problem under truncated ballots. The issue of ballot length in IRV was also touched on by Kilgour, Gr egoire, and Foley (2020), who examined its effect in simulation for k = 4, 5, and 6 candidates, where they found up to k 2 distinct winners across ballot lengths. We prove that in fact k 1 winners are possible for all k 3. Ballot length has been considered in con-

voter count

ballot type B C D A 2 A 5

h = 2 D A 2

Figure 1: On the left, an example proﬁle with k = 4 candidates A, B, C, D and n = 24 voters of 6 types with partial ballots. Ballots are listed top-down, with the number of voters of each type above each ballot. On the right, the proﬁle is truncated to ballot length h = 2.

texts other than IRV for instance, research on the Boston school choice mechanism found that limiting the number of schools parents could rank to ﬁve resulted in undesirable strategic behavior (Abdulkadiroglu et al. 2006). There has also been research on ballot length in approval voting from a learning theory angle, seeking to recover a population s preferences efﬁciently (Garg et al. 2019).

Preliminaries

An IRV election consists of k candidates labeled 1, . . . , k and n voters. Each voter j has a preference ordering over a subset of the candidates denoted by the ordered subset πj, which we refer to as a ballot. At any point down the ballot, πj can terminate, at which point the voter is indifferent over the remaining options. If πj includes all candidates, we call it full, otherwise we call it partial. We call a collection of ballots a proﬁle. Unless otherwise speciﬁed, a proﬁle may contain partial ballots.2 If multiple voters have identical ballots, we say they are of the same type. Given a proﬁle, IRV proceeds by eliminating the candidate with the fewest ballots ranking them ﬁrst and removing them from all ballots. Ballots that have all their candidates eliminated are exhausted. Eliminations continue until only one candidate remains, who is declared the winner (equivalently, one can terminate when one candidate has the majority of votes from non-exhausted ballots). Ties can be broken as desired (for instance, by coinﬂip), although they are unlikely in large elections. In many real-world elections, the number of candidates a voter can rank is limited to h < k, which we call the ballot length. We assume that if the ballot length is h, voters submit the length h preﬁx πj(1, . . . , h) of their ideal ballot πj. Voters who would have submitted a ranking listing h or fewer candidates are unaffected. Thus, we say that ballots are truncated to the ballot length h. See Figure 1 for an example of a proﬁle with partial ballots truncated to h = 2. Note that there is no difference between running IRV with ballot length k and k 1, since only one candidate remains after the (k 1)th elimination. The main question we focus on is how ballot length affects an election. For instance, how many different candidates can win as the ballot length varies for a ﬁxed proﬁle? In order to address this question, we make some assumptions

2All 168 elections in the Pref Lib data have partial ballots.

about the lack of consequential ties, since in trivial cases such as zero voters, any candidate can win depending on tie-breaks. We say that a proﬁle is consequential-tie-free if tie-breaks do not affect the winner under any ballot length h. We say it is elimination-tie-free if a tie for last place never occurs when running IRV for any ballot length h. Finally, we say it is tie-free if no two candidates ever have tied vote counts when running IRV at any ballot length h. We note that the problem of determining if a given candidate could win under some tie-breaking sequence is known to be NPcomplete (Conitzer, Rognlie, and Xia 2009).

Worst-Case Analysis of Ballot Truncation We say a proﬁle has c truncation winners if c different candidates can win depending on the ballot length. Previous simulation work found up to k 2 truncation winners for k = 4, 5, and 6 (Kilgour, Gr egoire, and Foley 2020). One of our main results is that up to k 1 truncation winners are possible for any k. We note that it is impossible to have all k candidates win under different ballot lengths, since lengths k and k 1 behave the same way. All proofs omitted for space can be found in the extended version of the paper (Tomlinson, Ugander, and Kleinberg 2022). First, we establish an exact lower bound on the number of voters required in order to achieve k 1 truncation winners in consequential-tie-free proﬁles. Our voter lower bound is based on the observation that the winner at h = 1 (the plurality winner) must be eliminated second under ballot lengths 2 for k 1 truncation winners to occur. In order for the plurality winner to be eliminated second, the ﬁrst elimination must redistribute enough votes for every other candidate to overtake the plurality winner.

Theorem 1. For any k > 3, a consequential-tie-free proﬁle requires at least 2k2 2k voters in order to produce k 1 truncation winners. For k = 3, the lower bound is k2 = 9.

Our main theoretical result is a construction matching this lower bound, showing that k 1 truncation winners can occur for any k 3. Our construction can not only produce k 1 truncation winners, but any sequence of winners over ballot lengths 1, . . . , k 1, provided that a candidate has not yet been eliminated.

Theorem 2. Let there be k > 3 candidates, labelled 1, . . . , k in their full-ballot IRV elimination order. Fix any sequence of candidates w1, . . . , wk 1 such that wh {h + 1, . . . , k} for all h [k 1]. There exists a consequentialtie-free proﬁle with 2k2 2k partial ballots whose sequence of truncated IRV winners from h = 1, . . . , k 1 is w1, . . . , wk 1. For k = 3, such a proﬁle exists with 9 ballots. Any sequence where wh h for some h [k 1] is impossible to realize as the sequence of truncated IRV winners for any consequential-tie-free proﬁle.

The idea behind the construction is to maintain a tie for second place among all candidates but two: the candidate about to be eliminated, in last, and the candidate next in the winner sequence, in ﬁrst. Each elimination redistributes ballots to move the next candidates into ﬁrst and last place. By carefully designing ballots, they become exhausted at just

the right moment to freeze the order once we reach step h of IRV, causing the candidate currently in ﬁrst to win. The example in Figure 1 uses this construction for k = 4 to achieve different winners at ballot lengths 1, 2, 3 (namely, A, B, C). Note that the full-ballot elimination order labeling of candidates A, B, C, D is 2, 3, 4, 1, which makes the truncation winner sequence 2, 3, 4 feasible. In contrast, the sequence 2, 2, 4 would not be feasible since the candidate eliminated second under full ballots cannot win at ballot length 2. Intuitively, a winner sequence with elimination order labeling is feasible if it is element-wise at least 2, 3, . . . , k.

Restrictions on Proﬁles Since IRV can behave very erratically across ballot lengths for general proﬁles, we might hope that imposing restrictions on the space of proﬁles makes IRV more well-behaved. We consider three classic proﬁle restrictions from voting theory, single-peaked (Black 1948; Arrow 1951), singlecrossing (Gans and Smart 1996), and 1-Euclidean preferences (see (Elkind, Lackner, and Peters 2022) for a survey of preference restrictions). A proﬁle is single-peaked if there exists an order < over the candidates such that, for every ballot b ranking i ﬁrst, if j < k < i or i < k < j, then j is not ranked above k in b. A proﬁle is single-crossing if there exists an ordering L of the ballots such that for every ordered pair of candidates (i, j), the set of ballots ranking i above j forms an interval of L. Finally, a proﬁle is 1-Euclidean if there exist embeddings of the voters and candidates in [0, 1] such that if voter b is closer to candidate i than to candidate j, then voter b ranks i above j. Intuitively, single-peaked proﬁles arise when there is a political axis arranging candidates from left to right and voters prefer candidates closer to their ideal point on the axis (each voter can have their own ideal point). Single-crossing preferences arise when voters are arranged on an ideological axis and each candidate is most appealing to voters at a certain point on this axis. While the deﬁnitions appear similar, neither condition implies the other. 1-Euclidean proﬁles are both single-peaked and single-crossing but there are proﬁles that are both single-peaked and single-crossing, but not 1-Euclidean (Elkind, Faliszewski, and Skowron 2014). In contrast to general proﬁles, where k 1 truncation winners can occur, we show that such cases are impossible under either single-peaked or single-crossing preferences (and therefore 1-Euclidean proﬁles).

Theorem 3. With k 5 candidates, no consequential-tiefree single-peaked proﬁle has k 1 truncation winners.

Proof. Suppose for a contradiction that a single-peaked proﬁle has k 1 truncation winners (k 5). We know the candidate eliminated ﬁrst cannot win under any ballot length. In order for the candidate eliminated second (h 2) to win at some ballot length, it must be at h = 1 i.e., the plurality winner must be eliminated second under h 2. Thus, they must be overtaken by at least three candidates (for k 5) when the ﬁrst eliminated candidate X s ballots are redistributed. But the second place on ballots listing X ﬁrst can only be the candidate to the left or right of X in the single-peaked ordering, making this impossible.

Theorem 4. With k 5 candidates, no consequential-tiefree single-crossing proﬁle has k 1 truncation winners.

Proof. As in the proof of Theorem 3, we ll show that the ﬁrst candidate eliminated, X, can only redistribute ballots to two candidates. Suppose for a contradiction that they redistribute ballots to at least three candidates. Call these candidates A, B, and C in the order in which they ﬁrst appear as second choices in the ballots ranking X ﬁrst in the singlecrossing order L. By the single-crossing property, all ballots to the left of ballots starting X, A must rank A above B, since a ballot to its right ranks B above A, namely those starting X, B. Moreover, all ballots to the right of ballots starting X, C must rank C above B by symmetric reasoning. But this means B cannot have any ballots ranking them ﬁrst, contradicting that X (who does have ballots ranking them ﬁrst) is the ﬁrst eliminated. See below for a visual depiction of this argument:

X ranked over B

A ranked over B C ranked over B

Although the upper bound on truncation winners is strictly lower for single-peaked proﬁles than for general proﬁles, the number of achievable truncation winners still grows with k. In particular, we can show that Ω(

k) truncation winners are possible in a consequential-tie-free singlepeaked proﬁle with Θ(k) voters. Theorem 5. With k = κ(κ + 1)/2 candidates (κ 3), there is a single-peaked consequential-tie-free proﬁle with 3κ(κ + 1)/2 partial ballots that results in κ distinct truncation winners. The exact upper bound on the number of truncation winners for single-peaked (and single-crossing) preferences remains an open question it could be as large as k 2. Additionally, we do not know a non-trivial lower bound on the number of achievable truncation winners for single-crossing or 1-Euclidean proﬁles.

Restrictions on Ties Since our main theorem allows ties (albeit only ties that do not affect the winners), one might be concerned that the large number of truncation winners is a byproduct of these ties. In the following results, we show that even if no vote counts are ever tied, there can still be arbitrary truncation winner sequences. We can therefore get any feasible winner sequence regardless of the tiebreaking rule. As before, we start by establishing lower bounds on the number of voters required for k 1 truncation winners and then provide a matching construction for tie-free proﬁles achieving any truncation winner sequence.

Theorem 6. For any k 3, an elimination-tie-free proﬁle must contain at least (k3 3k)/2 voters in order to produce k 1 truncation winners.

Theorem 7. For any k 3, a tie-free proﬁle must contain at least (2k3 5k2 +3k)/2 voters in order to produce k 1 truncation winners.

Note that for consequential-tie-free proﬁles, the lower bound on voters for k 1 truncation winners is Ω(k2), but Ω(k3) for elimination-tie-free and tie-free proﬁles.

Theorem 8. Given the same setup as in Theorem 2, there exists a tie-free proﬁle with (2k3 5k2+3k)/2 ballots whose sequence of truncated IRV winners from h = 1, . . . , k 1 is w1, . . . , wk 1.

The constructions for consequential-tie-free and tie-free proﬁles both use Θ(k2) distinct ballots. However, only Θ(k) distinct ballots are required to produce k 1 truncation winners. This is asymptotically tight, since each candidate who wins at some ballot length needs at least one ballot type listing them ﬁrst.

Theorem 9. Given k > 3 candidates, there is a tie-free proﬁle producing k 1 truncation winners with Θ(k3) voters of Θ(k) types.

Full Ballots So far, all of our constructions have relied on partial ballots. For proﬁles with full ballots, a simple extension of our constructions using ﬁller candidates allows us to achieve up to k/2 truncation winners, and in fact any feasible sequence of winners in the ﬁrst half of ballot lengths.

Corollary 1. Let k = 2κ for some κ > 3. Label the candidates 1, . . . , 2κ in order of their elimination under full ballots. Fix any sequence w1, . . . wκ 1 such that wh {κ + h + 1, . . . , 2κ} for all h [κ 1]. There exists a full-ballot consequential-tie-free proﬁle with 2κ2 2κ voters and a fullballot tie-free proﬁle with (2κ3 5κ2 +3κ)/2+κ(κ 1)/2 voters whose sequences of truncation winners from h = 1, . . . , κ 1 are w1, . . . , wκ 1.

While we have not found a general construction with full ballots and k 1 truncation winners, we have found fullballot elimination-tie-free proﬁles with k 1 truncation winners up to k = 10 using a linear-programming-based search (described at the end of this section). Full ballots make intuitive constructions more challenging, but do not appear to prevent a large number of truncation winners. However, how a full ballot requirement does or doesn t change our main result remains an open question. If instead of requiring ballots to be full, we require them to all have length at least k/2 c, we can improve the above extension of our constructions and get an additional c ballot lengths at which we can specify the winner.

Corollary 2. Let k = 2κ for some κ > 3. Suppose we require ballots to have length at least κ c for c < κ. Label the candidates 1, . . . , 2κ in order of the elimination under full ballots. Fix any sequence w1, . . . wκ+c 1 such that wh {κ c+h+1, . . . , 2κ} for all h [κ 1]. There exists a consequential-tie-free proﬁle with 2κ2 2κ ballots and a

k # trunc. winners ballot types voters voters lower bound (Theorem 6)

4 3 7 29 26 5 4 12 55 55 6 5 23 99 99 7 6 36 161 161 8 7 57 974 244 9 8 85 1759 351 10 9 122 4855 485

Table 1: LP full-ballot constructions. We used different search strategies for k 7 and k 8, leading to proﬁles farther from the voter lower bound for k 8.

tie-free proﬁle with (2κ3 5κ2+3κ)/2+(κ c)(κ c 1)/2 ballots whose sequence of truncated IRV winners from h = 1, . . . , κ + c 1 is w1, . . . , wκ+c 1. Given that explicit full-ballot constructions appear quite challenging, we turn to a computational approach to investigate whether full-ballot proﬁles can produce k 1 truncation winners. Using a linear programming (LP) search, we identiﬁed elimination-tie-free proﬁles with full ballots and k 1 truncation winners for k = 4, 5, 6, 7, 8, 9, 10 (the sizes of these proﬁles are shown in Table 1). Moreover, this approach was able to ﬁnd instances with voter counts matching the exact lower bound in Theorem 6 for k = 5, 6, 7. Our approach was not able to match the voter lower bound for k = 4. For k 8, we faced runtime constraints since the number of variables is exponential in the number of candidates, leading us to restrict the search space (described in further detail below). We consider elimination-tie-free proﬁles since they are easiest to encode as an LP, where we use constraints to enforce unambiguous eliminations. The idea behind the search is to construct possible elimination orders across all h that could result in k 1 winners, express these as conditions on the sums of counts of every full ballot type in Sk (the set of permutations on k elements), and then use an LP to ﬁnd a feasible real-valued solution of ballot type counts that result in that elimination order. We round these fractional ballot counts to be integers and check if the resulting proﬁle has the desired elimination order. If not, we can try another possible elimination order or increase the gaps in the constraints so that rounding is less likely to make a solution infeasible. For k 7, we tested all possible elimination orders, but only tested a single elimination order for k 8 due to runtime constraints. The exact LP formulation can be found in the extended version (Tomlinson, Ugander, and Kleinberg 2022).

Ballot Length in Simulation Our theoretical results show that the winner of an IRV election can change dramatically as the ballot length varies. Here, we ask how likely these changes are through simulated proﬁles. Such simulation analysis was previously conducted for k = 4, 5, 6 (Kilgour, Gr egoire, and Foley 2020). We extend these simulations up to k = 40 (our real-world IRV data has examples of elections with up to 30 candidates).

10 20 30 40 ballot length (h)

# candidates (k)

10 20 30 40 ballot length (h)

1-Euclidean

Pr(IRV winner wins)

Figure 2: Probability that truncated ballots produce the full IRV winner for candidate counts k = 2, . . . , 40 and ballot lengths h = 1, . . . , k 1. (Left) For general preferences, the probability of producing the IRV winner increases smoothly with the ballot length h. (Right) For 1-Euclidean preferences, there is a sharper transition around h = k/2.

We simulate two different types of proﬁles: general proﬁles with rankings sampled uniformly at random and 1Euclidean proﬁles with voters and candidates embedded in one dimension. For the general proﬁles, we ﬁx 1000 voters. For 1-Euclidean proﬁles, we simulate an inﬁnite voter population uniformly distributed over [0, 1], where the number of ﬁrst-place votes a candidate i has is the size of the interval of [0, 1] containing points closer to i than any other candidate. For both general and 1-Euclidean proﬁles, we simulate both full and partial ballots to gauge the effect of forced truncation with and without voluntary truncation. For general proﬁles with partial ballots, we independently and uniformly perform voluntary truncation on each voter s preferences before applying forced truncation in the form of ballot length. For 1-Euclidean partial ballots, we do the same with each ballot type. In Figure 2, we show the probability that the full-ballot IRV winner is selected with each ballot length 1, . . . , k 1 for k = 3, . . . , 40 with initially full ballots (the heatmaps were qualitatively identical for partial ballots (Tomlinson, Ugander, and Kleinberg 2022)). For general preferences, the probability of selecting the full-ballot IRV winner increases smoothly as ballot length increases. Additionally, for any ﬁxed ballot length, the probability of selecting the IRV winner decreases as the number of candidates increases. For instance, for h = 3, the probability of selecting the IRV winner ﬁrst dips below 50% at k = 12. For 1-Euclidean preferences, small ballot lengths are even less likely to produce the full IRV winner: for h = 3, the probability ﬁrst drops below 50% for k = 9. On the other hand, the probability rapidly increases around h = k/2. For ballots longer than k/2, uniform 1-Euclidean preferences almost always produce the full IRV winner. In Figure 3, we visualize the same data in a different way. We plot the mean and maximum observed numbers of truncation winners across ballot lengths (the ﬁgure also includes Pref Lib winner counts described in the next section). While the difference between general and 1-Euclidean proﬁles was pronounced in the previous heatmaps, they result in almost

mean # truncation winners

general full general partial 1-Euclidean full 1-Euclidean partial Pref Lib

1 10 20 30 40 # candidates (k)

max # truncation winners

theoretical max

Figure 3: Mean (top) and maximum (bottom) number of truncation winners in 10000 synthetic ballot simulations and 10000 Pref Lib resampling trials. We simulated uniform general and 1-Euclidean preferences for k = 3, . . . , 40. The shaded regions show standard deviation across trials. To simulate partial ballots, each ballot is voluntarily truncated at a random length between 1 and k. While up to k 1 truncation winners are possible, the mean number of truncation winners only reaches 4 around k = 40. 1-Euclidean proﬁles and proﬁles with partial ballots tend to produce slightly fewer truncation winners. For the Pref Lib data, each point represents a single election, with horizontal jitter added for legibility. Real elections tend to produce even fewer truncation winners, although it is not rare to have more than 1.

the same number of truncation winners on average. Additionally, these simulated proﬁles tend to have a small number of truncation winners relative to the theoretical maximum. On average for k 10, there are around two truncation winners, while the theoretical maximum is nine. Additionally, the maximum observed number of winners in 10000 simulated trials was well below the theoretical maximum, especially for larger k: we only began generating any proﬁles with 10 truncation winners around k = 40. Intuitively, these simulation results therefore indicate that proﬁles with large numbers of truncation winners are very rare in the space of proﬁles, at least under these (uniform) measures. However, they do not appear to be signiﬁcantly rarer among 1-Euclidean proﬁles than among general proﬁles, as one might have expected given the increased structure of 1-Euclidean proﬁles. On the other hand, proﬁles in which there are more than one winner across ballot lengths are very common. Thus, while truly extreme cases with k 1 truncation winners might be rare, cases where ballot length has an effect occur readily in simulation.

Truncating Real-World Election Data Given that many truncation winners are theoretically possible, we now ask how often multiple truncation winners occur in real-world election data. To this end, we analyze voter rankings from 168 elections in Pref Lib (Mattei and Walsh 2013). This collection includes 12 American Psychological Association (APA) presidential elections (Regenwetter et al. 2007) (h = 5), 14 San Francisco local elections (h = 3), and 21 Glasgow local elections (h = k), among others. The number of candidates in these elections ranges from 3 29 and the number of voters from tens to hundreds of thousands. See the extended version for additional summary statistics of these elections (Tomlinson, Ugander, and Kleinberg 2022). Some of these Pref Lib datasets included a small number of ballots with multiple candidates listed at the same rank (0.5% of all ballots), which we omit. In order to evaluate the impact of ballot length, we truncate the rankings at each possible shorter ballot length than the election actually used. We then run IRV on the truncated ballots. We assume that if ballots had been shorter, voters would have reported the same ranking, but truncated to the ballot length. It is possible that voters would express their preferences differently depending on the ballot length, so our approach should be seen as an approximation to this counterfactual scenario. In 41/168 elections, there were two different winners across ballot lengths, and in one election, there were three different winners. Overall, 25% of the elections were sensitive to ballot length. Among the elections with ballot length h 5, 12/85 = 14% of them had two different truncation winners; for elections with h > 5, 29/83 = 35% of elections had two or more different winners. In order to better understand the landscape of possible outcomes in each election, we also performed resampling of ballots. Given a collection of n ballots, we resample a collection of n ballots with replacement to simulate another possible election outcome with the same pool of voters. We then truncate those collections of votes to assess the impact of ballot length. In 10000 resampling trials, we observed up to six different truncation winners across the elections, but the expected number of truncation winners under resampling was between one and two for all elections (see Figure 3). In Figure 4, we also use ballot resampling to visualize the sequence of truncation winners in two Pref Lib elections. The 2009 Burlington Mayoral election famously had a different plurality winner (Kurt Wright) than the elected IRV winner (Bob Kiss), but our visualization reveals that at ballot length h = 2, the election was a complete toss-up and could have gone either way with only a small change in ballot counts. In the right subplot, we visualize the sequence of truncation winners in the one Pref Lib election that had three distinct truncation winners. Not only does this election have three truncation winners, but the sequence of winners ﬂips back and forth, as we proved theoretically possible. The smaller number of truncation winners in real data is likely due to the small number of front-runners in realworld elections, in contrast with the uniform preferences in our synthetic data. Our observations here are in line with the ﬁnding that ballot truncation is less likely to change the win-

1 2 3 4 5 Ballot length h

Resampling win prob.

2009 Burlington Mayor

Kurt Wright Bob Kiss

1 5 10 15 20 25 Ballot length h

ERS Election 5

Figure 4: Two elections in the Pref Lib data, the infamous 2009 Burlington mayoral election (left, k = 6, n = 8974) and an anonymous intra-organization election from the Electoral Reform Society (right, k = 26, n = 104). The stacked bars show the probability candidates have of winning at each ballot length under ballot resampling. Stars indicate the winners at each ballot length with actual ballot counts.

ner in the Mallows model when preferences are more tightly clustered around the central ranking (Ayadi et al. 2019).

Our theoretical results are fairly pessimistic: IRV election outcomes can change dramatically with ballot length. Our analysis of real and simulated data, on the other hand, presents a more mixed picture: ballot length regularly has an effect on the identity of the winner even in real elections, but the extreme changes between winners that are theoretically possible rarely occur, which may be cause for some degree of optimism. Nonetheless, changes in ballot length by truncation can often result in two or three different winners, even when the ballot length is short. There are a number of open theoretical questions around ballot length. First, is it possible to achieve every feasible truncation winner sequence with complete ballots? We suspect the answer is yes, but an explicit construction has proved elusive. Second, are more than O(

k) truncation winners possible for single-peaked ballots? How many truncation winners are possible with single-crossing ballots? Similar questions could be asked for other proﬁle restrictions, such as 1-Euclidean preferences. Our interest in IRV is due to its increasing popularity of IRV in United States local elections, but one could also investigate the effects of ballot length in other ranking-based voting systems such as Borda count or Copeland s method. Additionally, we do not address what ballot length should be used in practice, which requires making a tradeoff between competing desires. Finally, it would be interesting to understand when elections are close enough for ballot length to affect the winner. There has been research on calculating the margin of victory for IRV (Sarwate, Checkoway, and Shacham 2013; Blom et al. 2016; Magrino et al. 2011), deﬁned as the number of votes which would need to be altered to change the winner, which is NP-hard to compute (Xia 2012). A notion of margin of victory that relates to winners across different ballot lengths would be valuable.

Acknowledgments

This work was supported in part by ARO MURI, a Simons Investigator Award, a Simons Collaboration grant, a grant from the Mac Arthur Foundation, the Koret Foundation, and NSF CAREER Award #2143176. We thank the anonymous reviewers for their helpful feedback.

References Abdulkadiroglu, A.; Pathak, P. A.; Roth, A. E.; and Sonmez, T. 2006. Changing the Boston School Choice Mechanism. NBER Working Paper, (w11965). Arrow, K. J. 1951. Social Choice and Individual Values. John Wiley & Sons. Ayadi, M.; Amor, N.; Lang, J.; and Peters, D. 2019. Single transferable vote: Incomplete knowledge and communication issues. In AAMAS. Baumeister, D.; Faliszewski, P.; Lang, J.; and Rothe, J. 2012. Campaigns for lazy voters: truncated ballots. In AAMAS, 577 584. Black, D. 1948. On the rationale of group decision-making. Journal of Political Economy, 56(1): 23 34. Blom, M.; Teague, V.; Stuckey, P. J.; and Tidhar, R. 2016. Efﬁcient Computation of Exact IRV Margins. In ECAI, 480 488. Burnett, C. M.; and Kogan, V. 2015. Ballot (and voter) exhaustion under Instant Runoff Voting: An examination of four ranked-choice elections. Electoral Studies, 37: 41 49. Chevaleyre, Y.; Lang, J.; Maudet, N.; and Monnot, J. 2010. Possible winners when new candidates are added: The case of scoring rules. In AAAI. Coll, J. A. 2021. Demographic disparities using rankedchoice voting? Ranking difﬁculty, under-voting, and the 2020 Democratic primary. Politics and Governance, 9(2): 293 305. Conitzer, V.; Rognlie, M.; and Xia, L. 2009. Preference functions that score rankings and maximum likelihood estimation. In IJCAI. Elkind, E.; Faliszewski, P.; and Skowron, P. 2014. A characterization of the single-peaked single-crossing domain. In AAAI. Elkind, E.; Lackner, M.; and Peters, D. 2022. Preference Restrictions in Computational Social Choice: A Survey. ar Xiv:2205.09092. Fair Vote. 2022. Details About Ranked Choice Voting. https: //www.fairvote.org/rcv. Accessed: 2023-03-15. Fishburn, P. C.; and Brams, S. J. 1984. Manipulability of voting by sincere truncation of preferences. Public Choice, 44(3): 397 410. Florida Legislature. 2022. State of Florida Chapter No. 2022-73, Senate Bill No. 524. http://laws.ﬂrules.org/2022/ 73. Accessed: 2023-03-15. Gans, J. S.; and Smart, M. 1996. Majority voting with single-crossing preferences. Journal of Public Economics, 59(2): 219 237.

Garg, N.; Gelauff, L. L.; Sakshuwong, S.; and Goel, A. 2019. Who is in your top three? Optimizing learning in elections with many candidates. In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, volume 7, 22 31. Hoffman, C.; Kauba, J.; Reidy, J.; and Weighill, T. 2021. Proportionality in multi-winner RCV elections: A simulation study with ballot truncation. Available at SSRN 3942892. Kamwa, E. 2022. Scoring rules, ballot truncation, and the truncation paradox. Public Choice. Kilgour, D. M.; Gr egoire, J.-C.; and Foley, A. M. 2020. The prevalence and consequences of ballot truncation in rankedchoice elections. Public Choice, 184(1): 197 218. Konczak, K.; and Lang, J. 2005. Voting procedures with incomplete preferences. In IJCAI Multidisciplinary Workshop on Advances in Preference Handling, volume 20. Langan, J. P. 2004. Instant runoff voting: A cure that is likely worse than the disease. Wm. & Mary L. Rev., 46: 1569. Lewyn, M. E. 2012. Two cheers for instant runoff voting. Phoenix L. Rev., 6: 117. Magrino, T. R.; Rivest, R. L.; Shen, E.; and Wagner, D. 2011. Computing the Margin of Victory in IRV Elections. In Electronic Voting Technology Workshop/Workshop on Trustworthy Elections (EVT/WOTE). Mattei, N.; and Walsh, T. 2013. Pref Lib: A library for preferences. In ADT, 259 270. Springer. Menon, V.; and Larson, K. 2017. Computational aspects of strategic behaviour in elections with top-truncated ballots. Autonomous Agents and Multi-Agent Systems, 31(6): 1506 1547. Narodytska, N.; and Walsh, T. 2014. The Computational Impact of Partial Votes on Strategic Voting. In ECAI, 657 662. Neely, F.; and Cook, C. 2008. Whose votes count? Undervotes, overvotes, and ranking in San Francisco s instantrunoff elections. American Politics Research, 36(4): 530 554. Neely, F.; and Mc Daniel, J. 2015. Overvoting and the equality of voice under instant-runoff voting in San Francisco. California Journal of Politics and Policy, 7(4). Regenwetter, M.; Kim, A.; Kantor, A.; and Ho, M.-H. R. 2007. The unexpected empirical consensus among consensus methods. Psychological Science, 18(7): 629 635. Saari, D. G.; and Van Newenhizen, J. 1988. The problem of indeterminacy in approval, multiple, and truncated voting systems. Public Choice, 59(2): 101 120. Saltsman, M.; and Paxton, R. 2021. Start Spreading the News Ranked-Choice Voting Is a Mess. The Wall Street Journal. Sarwate, A. D.; Checkoway, S.; and Shacham, H. 2013. Risk-limiting audits and the margin of victory in nonplurality elections. Statistics, Politics, and Policy, 4(1): 29 64. Swensen, S. 2021. Minutes of the Political Subdivisions Interim Committee. https://le.utah.gov/Mtg Minutes/

public Meeting Minutes.jsp?Com=INTPOL&meeting Id= 17750, 2:06:27. Accessed: 2023-03-15. Tennessee Legislature. 2022. State of Tennessee Public Chapter No. 621, Senate Bill No. 1820. https: //publications.tnsosﬁles.com/acts/112/pub/pc0621.pdf, note=Accessed: 2023-03-15. Tomlinson, K.; Ugander, J.; and Kleinberg, J. 2022. Ballot Length in Instant Runoff Voting. ar Xiv:2207.08958. US Congress. 2019. H.R.4464 - Ranked Choice Voting Act. https://www.congress.gov/bill/116th-congress/housebill/4464. Accessed: 2023-03-15. Xia, L. 2012. Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM Conference on Electronic Commerce, 982 999. Xia, L.; and Conitzer, V. 2011. Determining possible and necessary winners given partial orders. Journal of Artiﬁcial Intelligence Research, 41: 25 67.