Computational Complexity of Verifying the Group No-show Paradox

Abstract

The (group) no-show paradox refers to the undesirable situation where a group of agents has the incentive to abstain from voting to get a more favorable winner. We examine the computational complexity of verifying whether the group no-show paradox exists given agents' preferences and the voting rule. We prove that the verification problem is NP-hard to compute for commonly studied voting rules such as Copeland, maximin, single transferable vote, and Black's rule. We propose integer linear programming-based algorithms and a breadth-first search algorithm for the verification problem. Experimental results illustrate that the former work better for a small number of alternatives, and the latter work better for a small number of agents. Using these algorithms, we observe that the group no-show paradoxes rarely occur in real-world data.