{'fraction_non_alphanumeric': 0.038622129436325675, 'fraction_numerical': 0.0020876826722338203, 'mean_word_length': 5.26797385620915, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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. 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.