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. 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.
['Edith Elkind', 'Evangelos Markakis', 'Svetlana Obraztsova', 'Piotr Skowron']
Complexity of Finding Equilibria of Plurality Voting Under Structured Preferences