Determining Winners in Elections with Absent Votes

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 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 RelatedWorks

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 (MoV), 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) onM.

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 ∈ (⋃ℓ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- Table 1: Complexity of predicting winner with absent votes under full ranking, top ℓ ranking, and up to L ranking.

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 rL : (⋃Li=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 rL 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) = ∑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, ⃗sL = (a1, a2, · · · , aL) with a1 ≥ a2 ≥ · · · ≥ aL ≥ 0, and a rounding indicator, denoted by ↑ or ↓. In an up-rounding (↑-Rd for short) scoring rule ⃗sL↑, 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 ⃗sL↓, a candidate c ranked j-th in an ℓ-ranking vote Vi has a score s(Vi, c) = aL-ℓ+j. In both cases, an agent not ranked in a vote gets a score of 0. For any profile P, let s(P, a) = ∑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.

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 ⃗sL = (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 rL, we define the following problems.

Definition 2 (WAV-rL). Input: a set of candidatesM, 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 rL(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 rL, both WAV-rL with any fixed m ≥ 2 and WAV-rL with any fixed t can be solved in polynomial time if the winner of rL 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 ∗ | = q3 .

For an arbitrary RXC3 instance (X, S), where X = {x1, x2, . . . , xq} and S = {S1, S2, . . . , Sq}. We construct the followingWAV-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}.

• 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,

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 McGarvey [McGarvey, 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 followingWAV-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.

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) = q3 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-MaximinL is NP-complete.

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

7 Copeland

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

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 + q2 + 3 candidates: X ∪ S ∪ {c, b} ∪W, where W = {w1,w2, · · · ,wq2 +1}. W.l.o.g, we assume x1 ≻ x2 ≻ · · · ≻ xq ≻ c ≻ w1 ≻ · · · ≻ wq2 +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 ( q2 + 1); xi has (q + q2 + 1); Sj has at most (q + 4); wi has at most (q + q2 ); 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 q3 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 + q2 +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.

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.

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ℓ, WAV-⃗sℓ 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 WAV-⃗sℓ, 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.
• 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 ′ .

Edges: E1 ∪ E2 ∪ E3 ∪ E4.

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 WAV-⃗sℓ 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.

Theorem 7 directly indicates that WAV-⃗sℓ is in P for any ⃗sℓ when ℓ = 2.

Corollary 1. WAV-⃗s2 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 ⃗sL, WAV-⃗sL↑ 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 ⃗sL such that a2 = · · · = aL, WAV-⃗sL↓ 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 FutureWork

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.

1 We thank an anonymous reviewer for proposing this idea

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.