Determining Winners in Elections with Absent Votes
Determining Winners in Elections with Absent Votes
Qishen Han, Amelie Marian, Lirong Xia
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2816-2824.
https://doi.org/10.24963/ijcai.2024/312
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.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice