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