Introduction
In modern democratic processes, especially those utilizing Ranked-Choice Voting (RCV), election results are frequently delayed by absentee or mail-in ballots. A prominent example is the 2021 New York City primary, where final results were not certified for an entire month. Such delays create a critical need for "winner prediction": given the current tally and an estimate of missing ballots, is it mathematically possible for a specific candidate to win? This research investigates the Winner with Absent Votes (WAV) problem, focusing on the realistic scenario of top-truncated rankings.
The WAV Problem and Top-Truncated Rankings
While theoretical models often assume voters provide a full ranking of all candidates, real-world voters typically only rank their top few choices (e.g., top 3 or top 5). This paper fills a significant gap in computational social choice by analyzing the WAV problem under these truncated conditions. The authors distinguish between different types of truncation, such as "Top-$k$" (exactly $k$ candidates ranked) and "Up-to-$k$" (at most $k$ candidates ranked).
Complexity: When Prediction is Hard
The study employs rigorous complexity analysis to map the computational landscape of winner determination. For several popular voting rules, the problem is proven to be NP-complete, meaning there is no known efficient algorithm to solve it as the number of candidates grows. Specifically, the authors find that:
- Single Transferable Vote (STV): Remains inherently complex due to its elimination rounds. A single missing vote can trigger a "butterfly effect," radically shifting which candidates are eliminated early and altering the final outcome.
- Copeland and Maximin: These rules are also hard to compute for any top-$k$ ranking where $k \ge 2$.
To prove these results, the authors use reductions from the Restricted Exact Three-Cover (RXC3) problem, constructing complex Weighted Majority Graphs (WMGs) to demonstrate how absent votes can be manipulated to change the winner.
Tractability: When Prediction is Easy
Despite the hardness results for some rules, the paper identifies several scenarios where winner prediction is computationally efficient (solvable in polynomial time):
- The "Indifference" Shortcut: Many common rules, such as plurality, veto, and $k$-approval, are efficient because they do not distinguish between the specific order of candidates once they fall outside the top tier of the ranking.
- Algorithm Design (Max-Flow): For Positional Scoring Rules (PSR), the problem can be reduced to a maximum flow problem in a network if the scoring vector is "flat" after the first choice (i.e., the 2nd through $k$-th choices receive the same points).
- Fixed-Parameter Analysis: The problem becomes "easy" if the number of candidates ($m$) or the number of missing votes ($t$) is held constant. This contrasts with full-ranking models, where even a small number of missing votes can sometimes make the problem NP-hard.
Conclusion and Future Directions
This research demonstrates that top-truncated rankings possess unique computational properties that distinguish them from full rankings. From a policy perspective, the authors argue that computational "easiness" is a desirable feature for voting rules. Efficient winner determination allows election officials to quickly and accurately inform the public about potential outcomes, maintaining trust during counting delays.
Future work may explore general Positional Scoring Rules where every rank has a unique weight (like the Borda count) in a truncated setting, which remains an open challenge. Additionally, the authors suggest investigating query models to determine the minimum amount of additional information needed to definitively call a winner, a concept highly applicable to post-election audits.
Summary updated