Determining Winners in Elections with Absent Votes

Qishen Han, Amélie Marian, Lirong Xia

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).

Comparison of Top-2 and Up-to-3 ranking structures used to model voter preferences.

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.

The construction of Weighted Majority Graphs (WMGs) for the current votes (P) and the potential total votes (P ∪ P') is central to proving NP-hardness for rules like Copeland.

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):

  1. 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.
  2. 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).
  3. 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

Abstract

An important question in elections is the determine whether a candidate can be a winner when some votes are absent. We study this determining winner with the absent votes (WAV) problem when the votes are top-truncated. We show that the WAV problem is NP-complete for the 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 in 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.
BibTeX
@inproceedings{han2024determining,
  author = {Qishen Han and Amélie Marian and Lirong Xia},
  title = {{Determining Winners in Elections with Absent Votes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure