# determining_winners_in_elections_with_absent_votes__12e5897f.pdf

Determining Winners in Elections with Absent Votes

Qishen Han1 , Am elie Marian2 , Lirong Xia1

1Rensselaer Polytechnic Institute 2Rutgers University hnickc2017@gmail.com, amelie.marian@rutgers.edu, xialirong@gmail.com

An important question in elections is determining whether a candidate can be a winner when some votes are absent. We study this determining winner with absent votes (WAV) problem with elections that take top-truncated ballots. We show that the WAV problem is NP-complete for single transferable vote, Maximin, and Copeland, and propose a special case of positional scoring rule such that the problem can be computed in polynomial time. Our results for top-truncated rankings differ from the results in full rankings as their hardness results still hold when the number of candidates or the number of missing votes are bounded, while we show that the problem can be solved in polynomial time in either case.

1 Introduction

In a multi-agent system, voting is one of the most common methods to aggregate preferences and make collective decisions. Voting has been rooted in the democratic procedure while emerging as new techniques to other scenarios including search engines [Dwork et al., 2001], crowdsourcing [Mao et al., 2013], and blockchain governance [Grossi, 2022]. An important question in these scenarios is the need to know possible winners without knowing the preferences of all the voters. There are several common reasons in practice why some votes may not be available right away for tallying: delay of absentee ballots, the forecasting of votes with polling results, or the contestation of the validity of some ballots.

Example 1. Suppose a city runs its mayoral election and adopts the single transferable vote (STV) (or so-called ranked-choice voting (RCV)) as the voting rule. Unfortunately, some of the absentee ballots have experienced substantial delays and are suspected to be lost. The official investigation will take about one month to locate these missing ballots, causing a significant disruption to the usual political proceedings. Is it possible for the city officials to offer a forecast of all potential winners by considering the current votes and estimating the number of undisclosed ballots?

A full version of this paper: https://arxiv.org/abs/2310.07150.

In fact, such examples have happened in practice in U.S. localities that have recently switched to ranked-choice voting. In 2018, the results of the RCV San Francisco mayoral election took a week to be confirmed and tabulated, largely due to the late counting of mail-in ballots. The results of the 2021 New York City primary election were not known until a full month after the election due to the large number of absentee ballots. These delays, the lack of transparency, and the incomplete information, or lack thereof, on the outcome of ballots led to distrust in the election process [Ennis, 2023]. Winner determination with absent votes also justifies a candidate s victory in ballots susceptible to manipulation [Baumeister and Hogrebe, 2023]. A proposed heuristic [Jelvani and Marian, 2022] empirically evaluated on NYC election night data shows promises in identifying election winners, or narrowing down the field of possible winners in a single transferrable vote scenario. From another perspective, determining winners with absent votes is also related to the classic problem of coalitional manipulation in computational social choice. In this context, a group of manipulators influence the outcome by strategically adding specific votes to the ballot. Originated from the famous Gibbard-Satterthwaite Theorem [Gibbard, 1973; Satterthwaite, 1975], there have been extensive theoretical studies on this problem in the computational social choice literature from the perspective of coalitional manipulation [Faliszewski and Procaccia, 2010; Faliszewski et al., 2010a]. Subsequent studies characterize the complexity of such problems for different voting rules including STV [Bartholdi and Orlin, 1991], positional scoring rules [Davies et al., 2011; Betzler et al., 2011], Copeland [Faliszewski et al., 2010b], and Maximin [Xia et al., 2009]. However, most previous studies assume that each voter casts a complete linear order, i.e. a full ranking toward all the candidates. In contrast, votes where voters cast a few top preferences become increasingly common in real-world scenarios. Top-ranked voting is more practical to implement because it simplifies the computation of the winner and prevents voters without full preferences from casting random votes and corrupting the ballot. Moreover, the results of coalitional manipulation under full rankings do not extend to the winner prediction for top-ranking votes. [2014] study vote where top-truncated votes are allowed. [2017] study a weighted version of coalitional manipulation for top-truncated votes. Yet

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

their hardness results also do not apply due to the incorporation of weights in the voting process. Therefore, the following question remains open: What is the complexity of determining possible winners in topranked voting election with absent votes?

1.1 Our Contribution

We investigate the computational complexity of determining winner with absent votes (WAV) under multiple voting rules. We focus on two specific settings of top-truncated rankings. In the top-ℓsetting, every voter is asked to provide their top-ℓ preference. And in the up-to-L setting, every voter can rank his/her at most L favorite candidates. We first show that, when the number of candidates or the quantity of absent votes is bounded, the WAV problem can be solved in polynomial time under both top-ℓand up-to-L settings. This distinguishes our work from the previous studies under full-ranking settings, in which the hardness results hold even for a bounded number of candidates or manipulators. Subsequently, we show that in STV, Maximin, and Copeland, determining the winner with absent votes is NPcomplete for every ℓ 2 in the top-ℓsetting and every L 2 in the up-to-L setting. Conversely, for the positional scoring rule, we show that the winner can be determined in polynomial time under both settings when the scoring vector does not distinguish the second to the ℓ-th (L-th, respectively) rank. This case covers many common voting rules including plurality, veto, and k-approval. A comparison between our results and the results in full rankings in previous works is in Table 1. We define the problem in the way of determining the winner with absent votes rather than following the convention of coalitional manipulation because the objectives of the two problems are opposite. For winner determination, we hope the problem is easy so that there are efficient ways to provide accurate predictions to the public. In the coalitional manipulation problem, on the other hand, hardness results are more welcomed because they prevent manipulators from corrupting the elections easily [Faliszewski et al., 2010a]. Our motivation aligns with the winner determination problem.

2 Related Works

As mentioned in the introduction, winner determination with absent votes has been extensively explored by the computational social choice community from the perspective of coalitional manipulation. [1973] and [1975] show that all reasonable voting rules suffer from manipulation under some situations. The earliest studies on the complexity of manipulation problems [Bartholdi et al., 1989; Bartholdi and Orlin, 1991] show that determining even if a single manipulator would succeed is NP-hard under some voting rules when the number of candidates is unbounded. A large literature follows the path and develops theoretical results of coalitional manipulation under a spectrum of weighted [Conitzer and Sandholm, 2002; Conitzer et al., 2007; Hemaspaandra and Hemaspaandra, 2007; Zuckerman et al., 2009; Xia et al., 2010] and unweighted [Xia et al., 2009; Betzler et al., 2011; Davies et al., 2011; Narodytska et al., 2011; Faliszewski et

al., 2010b] voting rules. However, most of the previous work focuses on featuring full rankings. [2014] study manipulations under up-to-m setting, i.e., voters can rank an arbitrary number of candidates, and most of their results are very different from ours. [2017] study the complexity of weighted coalitional manipulation when top-truncated votes are allowed. However, the incorporation of the weights prevents their intractability results from extending to the unweighted version. A closely related problem to the winner with absent votes and coalitional manipulation is the possible winner problem. The problem takes a set of candidates and a profile of partial orders on the candidates and asks if there is a full-order profile that extends the partial orders and makes a certain candidate a winner. A coalitional manipulation instance can be seen as a possible winner instance where a portion of the profile is full orders and the rest is empty votes. When the number of candidates is bounded, the possible winner problem can be solved in polynomial time in unweighted votes and NPcomplete in weighted votes under multiple rules [Conitzer et al., 2007; Pini et al., 2011; Walsh, 2007]. When the number of candidates is unbounded, the problem is P in the Condorcet rule [Konczak and Lang, 2005] yet NP-complete in a large variety of other rules [Bartholdi and Orlin, 1991; Xia and Conitzer, 2008; Betzler and Dorn, 2010; Baumeister et al., 2012; Baumeister et al., 2023]. [2019] shows that the possible winner problem under STV is NP-hard even when the partial profile is restricted to top-2 rankings. Recent work has also looked at the intersection of voting theory with regulatory frameworks in the context of ranked-choice voting elections. In particular, there has been an interest in defining and computing the margin of victory (Mo V), an important robustness measure of elections in Australia, where small margins would trigger elections audits [Blom et al., 2016; Magrino et al., 2011], or potentially result in shifts in the balance of power [Blom et al., 2020a; Blom et al., 2020b], and in election manipulation [Blom et al., 2019] in the ranked-choice voting.

3 Preliminaries

Let M be the set of candidates (or alternatives). Let m = |M| denote the number of candidates. Given a positive integer ℓ, a top-ℓranking R is a ranking on a ℓ-subset of M, where all the unranked candidates are regarded tied with each other and ranked lower than the ranked candidates. Let Lℓ(M) denote the set of all top ℓrankings (or linear orders) on M. There are in total n + t voters in the vote, where n is the number of voters whose votes are known, and t is the number of voters whose votes are absent. In the top-ℓsetting, each voter casts a top ℓranking R Lℓ(M) to represent their preference, where a R b means the voter prefers a to b. In the up-to-L setting, each agent cast a ranking R (Sℓ i=1 Li(M)). The vector of all voters votes is called a profile. Let P denote the profile of known votes and P denote the profile of absent votes. We use square brackets to denote votes. For example, given M = {a, b, c, d}, [b] to denote a vote that prefers candidate b to all other candidates while indifferent among other can-

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Rule Top-ℓ Up-to-L Full Ranking

STV NPC for ℓ 2 (Thm. 1) NPC (Thm. 2) NPC [Bartholdi and Orlin, 1991] Maximin NPC for ℓ 2 (Thm. 3) NPC for L 2 (Thm. 4) NPC [Xia et al., 2009] Copeland NPC for ℓ 2 (Thm. 5) NPC for L 2 (Thm. 6) NPC [Faliszewski et al., 2010b]

PSR P for ℓ= 2 (Corollary 1) P for -Rd [Menon and Larson, 2017] P for plurality and veto P for a2 = = aℓ(Thm. 7) P for -Rd and a2 = = a L (Thm. 8) NPC for Borda [Davies et al., 2011]

Table 1: Complexity of predicting winner with absent votes under full ranking, top ℓranking, and up to L ranking.

(a) Top-2 (b) Up-to-3

Figure 1: Weighted majority graph of instances in Example 2.

didates, and [b a] is a vote that prefers b the most, a the second, and all other candidates the least. Given a profile P and two alternatives a and b, P[a b] denotes the votes in P that prefer a to b. The weighted majority graph (WMG) of P is a graph whose vertices are the candidates and weights on a b is ωP (a b) = P[a b] P[b a].

Example 2. Let M = {a, b, c, d}, n = 4, and t = 2. Let P1 be a profile of 4 votes under the top-2 setting. P1 contains two votes for [c a], one vote for [a d], and one vote for [b a]. Let P2 be a profile of 4 votes under the up-to-3 setting. P1 contain two votes for [a c], one vote for [b a d], and one vote for [c]. The weighted majority graph of P1 and P2 is in Figure 1.

3.1 Voting Rules A (resolute) voting rule takes a profile as input and outputs a unique candidate as the winner. In the top-ℓsetting, a voting rule rℓ: (Lℓ(M)) M, and in the up-to-L setting, a voting rule r L : (SL i=1 Li(M)) M. A voting rule is anonymous if the winner is insensitive to the identities of agents. We focus on the variation of the following common voting rules for the top ℓor up to L rankings. For a voting rule r, we use rℓto denote its variation in top-ℓsetting and r L to denote its variation in up-to-L setting. The single transferable voting (STV) elects the winner in at most m 1 rounds. In each round, each vote contributes 1 score to its most preferred candidate that has not been eliminated, and the candidate with the lowest score is eliminated in that round. A tie-breaking mechanism is applied to select a single loser when necessary. If all candidates ranked in a vote are eliminated, that vote does not contribute to any candidate. The last remaining candidate becomes the winner. The Copeland rule is parametrized by a real number 0 α 1, denoted by Cdα. Given a profile P, a candidate a gains 1 score for every other candidate b it beats in the headto-head competition (the weight on edge a b is positive in the WMG) and α score when there is a tie. The candidate

with the highest score becomes the winner, and a tie-breaking mechanism is applied to select a single winner if necessary. In the Maximin rule, the min-score of a candidate a is the lowest weight of its out-going edges in the weighted majority graph, i.e. minb M\{a} ωP (a b). The candidate with the highest min-score becomes the winner, and a tie-breaking mechanism is applied to select a single winner if necessary.

Remark 1. We follow the definition of the Maximn rule in [Young, 1977]. There is an alternative definition (adopted, for example, in [Menon and Larson, 2017]) in which the min-score of a candidate a is the minb =a P[a b], where P[a b] is the number of votes in P that prefers a to another candidate b. The Maximin rule of two definitions always elect the same winner when P contains only full rankings, but may diverge from each other when P contains top-truncated rankings. See Appendix A for a concrete example of divergence.

We define the (integer) positional scoring rule in two settings respectively. In the top-ℓsetting, a positional scoring rule is characterized by an ℓ-dimension vector sℓ= (a1, a2, , aℓ) with a1 a2 aℓ 0. Given a top-ℓvote Vi and a candidate c, let s(Vi, c) = aj where j is the rank of c in Vi or s(Vi, c) = 0 if c is not ranked in i. For any profile P, let s(P, c) = P Vi P s(Vi, c). The candidate c maximizing s(P, c) becomes the winner, and a tie-breaking mechanism is applied to select a single winner if necessary. In the up-to-L setting, we follow the scheme from [2014] to deal with top-truncated rankings. A positional scoring rule is characterized by an L-dimensional vector, s L = (a1, a2, , a L) with a1 a2 a L 0, and a rounding indicator, denoted by or . In an up-rounding ( -Rd for short) scoring rule s L , a candidate c ranked j-th in an ℓ-ranking vote Vi has a score s(Vi, c) = aj. And in a down-rounding ( -Rd for short) scoring rule s L , a candidate c ranked j-th in an ℓ-ranking vote Vi has a score s(Vi, c) = a L ℓ+j. In both cases, an agent not ranked in a vote gets a score of 0. For any profile P, let s(P, a) = P Vi P s(Vi, c). The candidate c maximizing s(P, c) becomes the winner, and a tie-breaking mechanism is applied to select a single winner if necessary.

Example 3. We calculate the STV winner for the top-ℓinstance (P1) in Example 2. In the first round, c gets two votes, a and b get one vote each, and d gets no votes. Therefore, d is eliminated. In the second round, c gets two votes, and a and b get one vote each. Suppose we use a lexicographic tie-breaking mechanism. Therefore, b is eliminated.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

In the third round, [b a] contributes to candidate a. Therefore, both a and c get two votes. Then c is eliminated, and a becomes the winner. Example 4. We calculate the winner for the up-to-L instance (P2) in Example 2 under up-rounding and down-rounding positional scoring rules with s L = (8, 2, 1). In the up-rounding rule, a is ranked the first twice and the second once, so its score is 18. The score of b is 8, the score of c is 10, and the score of d is 1. Therefore, a is the winner. In the down-rounding rule, a gets 2 points from each [a c] as L = 3, and the ranking has a length of 2. a also get two points from [b a d], and has a score of 6, the score of b is 8, the score of c is 3, and the score of d is 1. Therefore, b is the winner.

3.2 Computational Problems We consider the following computational question: when ℓ (or L, respectively) is a constant, given a set of candidates M, a set of known profiles P of top-ℓ(up-to-L, respectively) votes, the number of absent votes t, and a targeted candidate c, is there a profile P of t votes that makes c the winner? We first define the question for the top-ℓsetting. For each constant ℓ 1 and a voting rule for top-ℓrankings, we define the following problem. Definition 1 (WAV-rℓ). Input: a set of candidates M, a profile P of known top-ℓranking votes, the number of absent votes t, and a candidate c. Determine: does there exist a profile P of t top-ℓranking votes such that rℓ(P P ) = c? We also consider two variations of the WAV problem with fixed parameters. In WAV with fixed m, the number of the candidates is removed from the input and becomes a predetermined constant. In WAV with fixed t, the quantity of the absent votes becomes a pre-determined constant. For the up-to-L setting, we follow a similar definition. For each constant L 1 and a voting rule r L, we define the following problems. Definition 2 (WAV-r L). Input: a set of candidates M, a profile P of known up-to-L ranking votes, the number of absent votes t, and a candidate c. Determine: does there exist a profile P of t up-to-L ranking votes ranking votes such that r L(P P ) = c? Similarly, we also consider WAV with fixed m and WAV with fixed t in the up-to-L setting. We focus on ℓ 2 and L 2 cases, as when ℓ= 1 or L = 1, most common voting rules reduce into plurality, and the WAV problem can be computed in polynomial time.

4 Fixed Number of Candidates and Fixed Number of Absent Votes We first show the easiness result for the variation of a fixed number of candidates and a fixed number of absent votes under both settings. Proposition 1. For any ℓ 2 and any anonymous voting rule rℓ, both WAV-rℓwith any fixed m 2 and WAV-rℓwith any fixed t can be solved in polynomial time if the winner of rℓ can be computed in polynomial time.

Proof Sketch. Fixed m. We enumerate all possible anonymous profiles P of t votes. There are m! (m ℓ)! = O(mℓ) = O(1) different top-ℓrankings. The numbers of these rankings sum up to t. Therefore, there will be at most O(tmℓ) = poly(t) many anonymous profiles. Fixed t. We enumerate all possible profiles P of t votes. For each vote, there are O(mℓ) different top-ℓrankings. Therefore, the number of all possible P is at most O(mtℓ).

Proposition 2. For any L 2 and any anonymous voting rule r L, both WAV-r L with any fixed m 2 and WAV-r L with any fixed t can be solved in polynomial time if the winner of r L can be computed in polynomial time.

Proposition 1 and 2 imply that previous results for fullrankings votes (where ℓ= m is variable) do not apply to our top-ℓand up-to-L settings, as their hardness results hold even when t is fixed, including Copeland when t = 2 [Faliszewski et al., 2010b], Maximin for any t 2 [Xia et al., 2009], and STV when t = 1 [Bartholdi and Orlin, 1991]. In the rest of the paper, we focus on the problem with variables t and m under common voting rules.

5 Single Transferable Vote

Theorem 1. For every constant ℓ 2, WAV-STVℓis NPcomplete.

Proof sketch. The membership of NP is held by running the vote and checking the winner. The hardness is proved by a reduction from restricted exact three-cover (RXC3) that follows the spirit of the reduction in the hardness proof for the manipulation problem under STV [Bartholdi and Orlin, 1991]. Here we only present the case of ℓ 4. The full proof, including the case of ℓ= 2 and ℓ= 3 is in Appendix B.

Definition 3 (RXC3 [Gonzalez, 1985]). Input: (1) a set of q-elements, denoted by X = {x1, x2, . . . , xq}, where q is divisible by 3; (2) q sets S = {S1, S2, . . . , Sq} such that for every j q, Sj X and |Sj| = 3. For every i q, xi is in exactly three sets in S. Without loss of generality, we assume that q is an even number. If q is odd, then we use an instance with duplicate X and S. Determine: if there exists a subset S S such that for every xi X, there exists exactly one Sj S such that xi Sj. We call S an exact 3-cover of X. Note that if such S , there exists |S | = q

For an arbitrary RXC3 instance (X, S), where X = {x1, x2, . . . , xq} and S = {S1, S2, . . . , Sq}. We construct the following WAV-STVℓinstance. Candidates: there are 3q + 3 alternatives {w, c} {d0, d1, . . . , dq} {b1, b1, . . . , bq, bq}. We assume that d0 d1 d2 dq b1 b1 b2 b2 bq bq in tie-breaking. Absent Votes: t = q/3. Known votes: The profile P consists of the following votes, of which only the top preferences are specified. We ll show that either w or c is the winner, therefore, the votes can be filled to top-ℓranking arbitrarily without affecting the proof. Both i and j in the list are in {1, 2, . . . , q}.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

P1: There are 12q votes of [c w]. P2: There are 12q 1 votes of [w c]. P3: There are 10q + 2q/3 votes of [d0 w c]. P4: For every i, there are 12q 2 votes of [di w c]. P 1 5 : For every i, there are 6q + 4i 6 votes of [bi bi w c]; and P 2 5 : for every i and every j such that xj Si, there are two votes of [bi dj w c]. P 1 6 : For every i, there are 6q + 4i 2 votes of [bi bi w c]; and P 2 6 : for every i, there are two votes of [bi d0 w c]. First, no matter what rankings P contains, the winner will be either c or w. This is because once one of c or w is eliminated in any round, the remaining other will get all 24q 1 votes from P1 and P2. On the other hand, all other alternatives cannot have such a high score and be the winner. Suppose RXC3 is a YES instance. S is an exact 3-cover of X, and I = {i | Si S } be the index set of S . Then we construct P as follows: for each i I, there is one vote of [bi bi c w]. In the first q round of voting, for each i q, if i I, bi is eliminated; otherwise bi is eliminated. At the beginning of the q+1 round, the plurality scores of the remaining alternatives are as in the following table. Therefore,

Rd. w c bi or bi d0 di

q + 1 12q 1 12q 12q + 8i 1 or 12q + 8i 5 12q 12q

Table 2: Plurality score in the q + 1 round.

w is eliminated in round q + 1, and c will become the winner. Suppose WAV-STVℓis a YES instance. We prove that RXC3 is a YES instance in the following steps. Step 1. In the first q rounds, exactly one of bi and bi is eliminated for every i q. Firstly, the initial score of bi and bi is at most 6q + 4i + q/3 10q + q/3, while the score of other alternatives is at least 10q +2/3q. On the other hand, once one of bi and bi is eliminated, the other gets the transferred votes and has a score of more than 12q. Therefore, in the first q round, in each round, either bi or bi is eliminated for a distinct i. Step 2. Let I = {i : bi is eliminated in the first q rounds.}. Then I must be the index set of an RXC3 solution. Firstly, for each i I, bi needs at least one vote for P to win bi, and each vote in P can contribute to at most one bi. Therefore, there are at most q/3 of bi that beat bi. Then if I is not (the index set of) an RXC3 solution, there must exist some xj X that is not covered, and the corresponding dj does not get any transferred votes. Then in the q + 1 round, such dj will be eliminated with 12q 2 votes, and its vote will be transferred to w. Then w has a score of at least 24q 3 which exceeds c all the time. Therefore, c cannot be the winner. Therefore, once WAV-STVℓis a YES instance, the index set of eliminated bi in the first q rounds forms the index set of a solution to the RXC3, and RXC3 is a YES instance.

Theorem 2. For every constant L 2, WAV-STV L is NPcomplete. The proof for the up-to-L case follows the top-ℓcase by replacing all ℓto L. The construction of the WAV instance requires P to make use of all L positions in every vote to make c the winner.

6 Maximin For Maximin and Copeland, we leverage the following lemma to construct the instance in the reduction. Lemma 1. For any constant ℓ 2, an arbitrary set of candidates M with m ℓ, and two arbitrary candidates a, b M, there exists a voting profile P with poly(m) of top-ℓranking votes such that the weighted majority graph of P contains only one non-zero-weighted edge of a b with weight 2. Lemma 1 enables us to construct an arbitrary WMG with even edge weights in polynomial-many votes.

Proof. Our construction of P follows the spirit of Mc Garvey [Mc Garvey, 1953]. It takes two steps: Step 1: We first construct a slightly different profile P . For any ℓ-subset Mℓof M, and any permutation σMℓon Mℓ, P contains a vote for [σMℓ(1) σMℓ(2) σMℓ(ℓ)]. The number of votes in P is Am ℓ= O(mℓ). Due to symmetricity, all the candidates are tied in P , and the weights of all the edges are 0 in the WMG of P . Step 2: Pick one vote in P such that b is ranked the top and a is ranked the second. P is constructed by swapping a and b in this vote while keeping all other votes unchanged in P . Since the only change is the relative position between a and b in one vote, the WMG of P contains only one edge which is a b with weight 2. And P also contains O(mℓ) edges.

Theorem 3. For all constant ℓ 2, WAV-Maximinℓis NPcomplete. Remark 2. Theorem 3 does not contradict Theorem 11 in [Menon and Larson, 2017]. The two papers adopt different definitions of the Maximin rule which may lead to different winners under top-truncated votes, as discussed in Remark 1.

Proof sketch. The membership of NP is held by running the vote and checking the winner. For the hardness, we give a reduction from RXC3. For an RXC3 instance X = {x1, x2, . . . , xq} and S = {S1, S2, . . . , Sq}, we construct the following WAV-Maximinℓinstance. Candidates. There are 2q + ℓcandidates: X S {c} W, where W = {w1, w2, , wℓ 1}. We assume c x1 x2 xq in tie-breaking. Absent votes. t = q 3(ℓ 1). (Without loss of generality, we assume that q can be divided by 6(ℓ 1). With not, we duplicate both X and S for 6(ℓ 1) times.) Known votes. The WMG of P is shown in Figure 2. (There are no edges inside W, X, or S in WMG(P).) P can be constructed via Lemma 1 and adding one vote for [c w1 wℓ 1]. Then in profile P, the min score of c is (q + q 3(ℓ 1) + 1), of each wi is (2q + 1), of each xi is q (from Sj xi), and for each Sj is 2q. The details of the construction can be found in Appendix C.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

𝑥 𝑆 : 𝑆 𝒮: 𝑞 1 𝑆 𝒮: 𝑞

Figure 2: WMG for Maximin. Q = q 3(ℓ 1).

Intuition of construction. The min-score of each xi comes from three Sj xi, and is exactly q 3(ℓ 1) + 1 higher than c s min-score . To make c the winner, c appears in all votes in P to increase its min-score by q 3(ℓ 1). Moreover, the Sj that appears in P should consist of an exact 3-cover so that the min score of every xi decreases by 1. If not, c will be beaten by some xi not covered.

Suppose RXC3 is a YES instance. And let S be the exact 3-cover of X. Then we construct P as follows: c is ranked the top and followed by ℓ 1 of Sj in each vote. The set of all the Sj ranked the second to the ℓ-th in P (which is exactly q 3(l 1) (l 1) = q

3 of Sj) is exactly S . In P P , the min-score of c is ( q 1). For any xi, since S is an exact 3-cover, there exists a Sj S such that xi Sj. Since there is one vote that ranked Sj higher than xi in P , the min-score of xi in P P is q 1. The min-score of any Sj or any wi will not exceed 2q + 1. Therefore, c becomes the winner.

Suppose WAV-Maximinℓis a YES instance. And let P be a profile of t votes such that Maximinℓ(P P ) = c. We proceed with the proof in two steps. Step 1. Without loss of generality, we can assume that c is ranked the first in all votes in P . If this is not the case, we can lift c to the first and keep the order of other candidates in every vote. Then the min-score of c will not decrease, and the min-score of any other candidate will not increase. Therefore, the new profile is also a solution. Step 2. For every vote in P , the second to ℓ-th rank is some Sj S, and the set of all these Sj (denoted by S ) is an exact 3-cover of X. First, the min-score of c in P P is q 1 since c is ranked top in all votes in P . Suppose S is not an exact 3-cover of X, then there exists an xi no covered by S , and the min-score of xi will be q from Sj xi, which is higher than c s min-score. Therefore, c cannot be the winner. Consequently, RXC3 is a YES instance with solution S . The full proof is in Appendix C.

Theorem 4. For any constant L 2, WAV-Maximin L is NP-complete.

The proof follows the top-ℓcase by replacing ℓwith L.

Theorem 5. For any constant ℓ 2 and any α [0, 1], WAV-Cdα ℓis NP-complete.

𝑥 𝑆 𝑥 𝑆 : 1

Figure 3: The WMG for Copeland. Q = q 3(ℓ 1).

Proof sketch. The membership of NP is held by running the vote and checking the winner. For the hardness, we give a reduction from RXC3. We apply a similar but slightly more complicated construction as in Maximin s proof. We present the construction for α < 1 (more precisely, α < q 3

q , which converges to 1 as q increases). The full proof including how to modify the construction for α = 1 is in Appendix D. We assume that q can be divided by 6(ℓ 1). Candidates. There are 2q + q

2 + 3 candidates: X S {c, b} W, where W = {w1, w2, , w q

2 +1}. W.l.o.g, we assume x1 x2 xq c w1 w q

2 +1 in tie-breaking. Absent votes. t = q 3(ℓ 1). Known votes. The weighted majority graph (with weights of some key edges) of P is in Figure 3. For edges inside S and X respectively (not shown in the figure), each candidate beats about half of the other candidates inside the group in the head-to-head competition and is beaten by the other half. The edges inside W will not affect the winner. The Copeland score for each candidate in P is as follows: c has ( q

2 + 1); xi has (q + q

2 + 1); Sj has at most (q + 4); wi has at most (q + q

2); and b has (q + 2). Intuition of construction. The only edges that can be flipped by P are Sj c and xi Sj for xi Sj. We set the weights so that c needs to win every Sj to become the winner, which requires every vote in P to include c. On the other hand, every xi needs to be tied with or be beaten by some Sj xi to make c the winner. Therefore, the rest q

3 positions in P will be taken by Sj that forms an exact 3-cover. Suppose RXC3 is a YES instance with solution S . We construct P : c is ranked the top and followed by ℓ 1 of Sj in each vote, and the set of all the Sj ranked second to the ℓ-th in P is exactly S . Then c becomes the candidate with the unique highest score (q + q

2 +1) and becomes the winner. Suppose WAV-Cdα ℓis a YES instance with solution P . We could first show that all votes in P must contain c. Then all Sj ranked in P must form an exact 3-cover of X. Otherwise, there will be some xi not covered, and the Copeland score of such xi will also be equal to c. Then according to the tie-breaking rule, c cannot be the winner. The full proof is in Appendix D.

Similar to STV and Maximin, this proof also applies to the up-to-L setting by replacing ℓwith L. Theorem 6. For any constant L 2 and any α [0, 1], WAV-Cd α L is NP-complete.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Figure 4: An illustration of the network when M = {a, b, c}, t = 2, and ℓ= 3.

8 Positional Scoring Rules (PSR)

For scoring rules sℓ= (a1, a2, , aℓ), We show that the WAV problem is in P for the special case a2 = = aℓ.

Theorem 7. For any ℓ 2 and sℓsuch that a2 = = aℓ, WAVsℓcan be determined in polynomial time.

Proof sketch. We convert the problem into a maximum flow problem with a similar idea in [Baumeister et al., 2012]. Given an instance of WAVsℓ, we construct the following network flow. An illustration is in Figure 4. Nodes: { s, t} T TM M. s is the source node, and t is the sink node. T contains (ℓ 1)t nodes. For each absent vote v, and d = 2, , ℓ, there is a node vd for thed-th position of v. TM contains t(m 1) nodes. For each absent vote v and each candidate a = c, there is a node (v, a) in TM. M contains m 1 nodes, each representing a candidate other than c. Edges: E1 E2 E3 E4. For each node vd T, there is an edge s vd with capacity 1. For each vote v, each position d, and each candidate a, there is an edge vd (v, a) with capacity 1. For each vote v and each candidate a = c, there is an edge (v, a) a with capacity 1. Let a2 = = aℓ= A. Let s(P, a) be the score of a from profile P. For each node a M, there is an edge a t with capacity s(P,c) s(P,a)+t a1

A . (We assume the capacities are non-negative. Otherwise, it is a NO instance.) Interpretation of network. For a flow f: f(vd (v, a)) = 1 stands for that a denotes that candidate a is ranked at d-th in vote v. f((v, a) a) = 1 stands for that a appears in the top-ℓ ranking in v. The capacity ensures that every candidate appears at most once in v. A f(a t) stands for the total score a gets from P . The capacities in E1, E2, and E3 guarantee that the profile P is valid. The capacities in E4 ensure that the total score of a does not exceed the total score of c from P P . When the max-flow f is (ℓ 1)t (we assume f is an integer flow without loss of generality [Ford and Fulkerson, 1956]), it means that there is a way to fill all (ℓ 1)t positions (2 to ℓin t votes) by some candidates and form a valid profile P such that no other candidates scores exceed c. Therefore, c becomes the winner in P P . When WAVsℓis a YES instance with solution P , we could assume that c is ranked the top at all votes v P . Then we can construct a flow f of (ℓ 1)t by setting the corresponding edge flows to 1.

The full proof is in Appendix E.

Theorem 7 directly indicates that WAVsℓis in P for any sℓwhen ℓ= 2. Corollary 1. WAVs2 can be determined in polynomial time for any s2. In the up-to-L setting, whether c can be a winner under an up-rounding scoring rule can be verified by checking the case when all votes in P are [c], i.e. rank c alone. Proposition 3 ([Menon and Larson, 2017], Theorem 1). For any constant L 1 and any scoring vector s L, WAVs L can be computed in polynomial time. For the down-rounding scoring rule, we show a similar result as the top-ℓsetting. Theorem 8. For any constant L 2 and s L such that a2 = = a L, WAVs L can be determined in polynomial time.

Proof Sketch. Firstly, if a solution P exists, we could assume without loss of generality that P contains only top-1 ranking and top-L ranking, and c is ranked the top in all the votes. If this is not the case, we could substitute all non-top-L votes into [c], and rank c the top of all the top-L votes while keeping the order of other candidates unchanged. In this way, the scoring of c is strictly increasing, while the score of all other candidates is non-increasing. Then we give the algorithm outline. First, we enumerate the number of top-1 votes and top-L votes in P . The sum of two kinds of votes is t. Therefore, there are in total t+1 cases. For each case, we set all top-1 votes to be [c], and construct a maximum flow instance as in the proof of Theorem 7. If there is some case where the maximum flow is above the threshold, then we output YES. Otherwise, when all cases the maximum flow is below its threshold, we output NO.

9 Conclusion and Future Work We investigate the computational complexity of determining winners with absent votes when the votes are top-truncated. We have shown that the problem is in P when the number of candidates or the quantity of absent votes is bounded. In the unbounded cases, we show that the problem is NP-complete for STV, Maximin, and Copeland. We also give a special case of scoring rules where the problem can be computed in polynomial time. Winner determination with absent votes is closely related to the classic coalitional manipulation problem in social choice, yet previous results on full rankings do not directly extend to top-truncated settings. A question that remains open in our paper is the complexity of WAV for general positional scoring rules. In the fullranking setting, the complexity of coalitional manipulation is regarded as a challenging task. There are hardness results under an artificially constructed scoring vector [Xia et al., 2010] and Borda [Betzler et al., 2011]. Another related topic is to reduce the possible winners by eliciting extra information from voters via, for example, a query model.1 We would care about protocols that may predict the final winner most accurately conditioned on query constraints.

1We thank an anonymous reviewer for proposing this idea

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Acknowledgements This work was partially supported by NSF Grant SES2218975. LX acknowledges NSF #2007994, #2106983, # 2303000, # 2313136, and a Google Research Award for support. We thank the anonymous reviewers for their helpful comments.

References [Ayadi et al., 2019] Manel Ayadi, Nahla Ben Amor, J erˆome Lang, and Dominik Peters. Single transferable vote: Incomplete knowledge and communication issues. In Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, page 1288 1296, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. [Bartholdi and Orlin, 1991] John Bartholdi, III and James Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341 354, 1991. [Bartholdi et al., 1989] John Bartholdi, III, Craig Tovey, and Michael Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227 241, 1989. [Baumeister and Hogrebe, 2023] Dorothea Baumeister and Tobias Hogrebe. On the complexity of predicting election outcomes and estimating their robustness. SN Computer Science, 4(4):362, 2023. [Baumeister et al., 2012] Dorothea Baumeister, Piotr Faliszewski, J erˆome Lang, and J org Rothe. Campaigns for lazy voters: Truncated ballots. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, page 577 584, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems. [Baumeister et al., 2023] Dorothea Baumeister, Marc Neveling, Magnus Roos, J org Rothe, Lena Schend, Robin Weishaupt, and Lirong Xia. The possible winner with uncertain weights problem. Journal of Computer and System Sciences, 138:103464, 2023. [Betzler and Dorn, 2010] Nadja Betzler and Britta Dorn. Towards a dichotomy for the possible winner problem in elections based on scoring rules. Journal of Computer and System Sciences, 76(8):812 836, 2010. [Betzler et al., 2011] Nadja Betzler, Rolf Niedermeier, and Gerhard Woeginger. Unweighted coalitional manipulation under the Borda rule is NP-hard. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), pages 55 60, Barcelona, Catalonia, Spain, 2011. [Blom et al., 2016] Michelle Blom, Vanessa Teague, Peter J Stuckey, and Ron Tidhar. Efficient computation of exact irv margins. In ECAI 2016, pages 480 488. IOS Press, 2016. [Blom et al., 2019] Michelle Blom, Peter J Stuckey, and Vanessa J Teague. Election manipulation with partial information. In International Joint Conference on Electronic Voting, pages 32 49. Springer, 2019.

[Blom et al., 2020a] Michelle Blom, Andrew Conway, Peter Stuckey, and Vanessa Teague. Shifting the balance-ofpower in stv elections. In Electronic Voting, pages 1 18. Springer International Publishing, Cham, 09 2020. [Blom et al., 2020b] Michelle Blom, Andrew Conway, Peter J. Stuckey, and Vanessa J. Teague. Did that lost ballot box cost me a seat? computing manipulations of stv elections. Proceedings of the AAAI Conference on Artificial Intelligence, 34(08):13235 13240, Apr. 2020. [Conitzer and Sandholm, 2002] Vincent Conitzer and Tuomas Sandholm. Complexity of manipulating elections with few candidates. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 314 319, Edmonton, AB, Canada, 2002. [Conitzer et al., 2007] Vincent Conitzer, Tuomas Sandholm, and J erˆome Lang. When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3):1 33, 2007. [Davies et al., 2011] Jessica Davies, George Katsirelos, Nina Narodytska, and Toby Walsh. Complexity of and algorithms for Borda manipulation. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 657 662, San Francisco, CA, USA, 2011. [Dwork et al., 2001] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pages 613 622, 2001. [Ennis, 2023] Chad Ennis. Ranked-choice voting is an elections-administration nightmare. In The Hill. 2023. [Faliszewski and Procaccia, 2010] Piotr Faliszewski and Ariel D. Procaccia. AI s war on manipulation: Are we winning? AI Magazine, 31(4):53 64, 2010. [Faliszewski et al., 2010a] Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. Using complexity to protect elections. Communications of the ACM, 53:74 82, 2010. [Faliszewski et al., 2010b] Piotr Faliszewski, Edith Hemaspaandra, and Henning Schnoor. Manipulation of copeland elections. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pages 367 374, 2010. [Ford and Fulkerson, 1956] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399 404, 1956. [Gibbard, 1973] Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41:587 601, 1973. [Gonzalez, 1985] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293 306, 1985. [Grossi, 2022] Davide Grossi. Social choice around the block: On the computational social choice of blockchain. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 1788 1793, 2022.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

[Hemaspaandra and Hemaspaandra, 2007] Edith Hemaspaandra and Lane A. Hemaspaandra. Dichotomy for voting systems. Journal of Computer and System Sciences, 73(1):73 83, 2007. [Jelvani and Marian, 2022] Alborz Jelvani and Am elie Marian. Identifying possible winners in ranked choice voting elections with outstanding ballots. Proceeding of the 10th AAAI Conference on Human Computation and Crowdsourcing, 2022. [Konczak and Lang, 2005] Kathrin Konczak and J erˆome Lang. Voting procedures with incomplete preferences. In Multidisciplinary Workshop on Advances in Preference Handling, 2005. [Magrino et al., 2011] Thomas R Magrino, Ronald L Rivest, Emily Shen, and David Wagner. Computing the margin of victory in irv elections. In EVT/WOTE, 2011. [Mao et al., 2013] Andrew Mao, Ariel Procaccia, and Yiling Chen. Better human computation through principled voting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1142 1148, 2013. [Mc Garvey, 1953] David C. Mc Garvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608 610, 1953. [Menon and Larson, 2017] Vijay Menon and Kate Larson. Computational aspects of strategic behaviour in elections with top-truncated ballots. Autonomous Agents and Multi Agent Systems, 31(6):1506 1547, 2017. [Narodytska and Walsh, 2014] Nina Narodytska and Toby Walsh. The Computational Impact of Partial Votes on Strategic Voting. In Proceedings of the 21st European Conference on Artificial Intelligence, 2014. [Narodytska et al., 2011] Nina Narodytska, Toby Walsh, and Lirong Xia. Manipulation of Nanson s and Baldwin s rule. In Proceedings of the National Conference on Artificial Intelligence (AAAI), San Francisco, CA, USA, 2011. [Pini et al., 2011] Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Incompleteness and incomparability in preference aggregation: Complexity results. Artificial Intelligence, 175(7 8):1272 1289, 2011. [Satterthwaite, 1975] Mark Satterthwaite. Strategyproofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187 217, 1975. [Walsh, 2007] Toby Walsh. Uncertainty in preference elicitation and aggregation. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 3 8, Vancouver, BC, Canada, 2007. [Xia and Conitzer, 2008] Lirong Xia and Vincent Conitzer. Determining possible and necessary winners under common voting rules given partial orders. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 196 201, Chicago, IL, USA, 2008. [Xia et al., 2009] Lirong Xia, Michael Zuckerman, Ariel D. Procaccia, Vincent Conitzer, and Jeffrey Rosenschein.

Complexity of unweighted coalitional manipulation under some common voting rules. In Proceedings of the Twenty First International Joint Conference on Artificial Intelligence (IJCAI), pages 348 353, Pasadena, CA, USA, 2009. [Xia et al., 2010] Lirong Xia, Vincent Conitzer, and Ariel D. Procaccia. A scheduling approach to coalitional manipulation. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 275 284, Cambridge, MA, USA, 2010. [Young, 1977] H.P. Young. Extending Condorcet s rule. Journal of Economic Theory, 16(2):335 353, 1977. [Zuckerman et al., 2009] Michael Zuckerman, Ariel D. Procaccia, and Jeffrey S. Rosenschein. Algorithms for the coalitional manipulation problem. Artificial Intelligence, 173(2):392 412, 2009.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)