Determining Winners in Elections with Absent Votes
This addresses computational challenges in election systems for scenarios with incomplete voter participation, though it appears incremental as it extends prior work on full rankings to top-truncated cases.
The paper tackles the problem of determining election winners when some votes are absent and rankings are top-truncated, showing that the problem is NP-complete for several voting rules (single transferable vote, Maximin, Copeland) but polynomial-time solvable for a special case of positional scoring rules.
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.