Complexity of Finding Equilibria of Plurality Voting Under Structured Preferences

摘要

We study the complexity of finding pure Nash equilibria in voting games over well-known restricted preference domains, such as the domains of single-peaked and single-crossing preferences. We focus on the Plurality rule, and, following the recent work of Elkind et al. [15], consider three popular tie-breaking rules (lexicographic, random-candidate, and random-voter) and two types of voters' attitude: lazy voters, who prefer to abstain when their vote cannot affect the election outcome, and truth-biased voters, who prefer to vote truthfully in such cases. Elkind et al. [15] have shown that for most of these combinations of tie-breaking rules and voters' attitudes finding a Nash equilibrium is NP-hard; in contrast, we demonstrate that in almost all cases this problem is tractable for preferences that are single-peaked or single-crossing, under mild technical assumptions.