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 ti...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Jezik: | English |
| Izdano: |
ACM
2016
|
| _version_ | 1826296836171759616 |
|---|---|
| author | Elkind, E Markakis, E Obraztsova, S Skowron, P |
| author_facet | Elkind, E Markakis, E Obraztsova, S Skowron, P |
| author_sort | Elkind, E |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T04:22:28Z |
| format | Conference item |
| id | oxford-uuid:cb7cfd26-43eb-4a04-a20e-5e9668bef01c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:22:28Z |
| publishDate | 2016 |
| publisher | ACM |
| record_format | dspace |
| spelling | oxford-uuid:cb7cfd26-43eb-4a04-a20e-5e9668bef01c2022-03-27T07:15:13ZComplexity of finding equilibria of plurality voting under structured preferencesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:cb7cfd26-43eb-4a04-a20e-5e9668bef01cEnglishSymplectic ElementsACM2016Elkind, EMarkakis, EObraztsova, SSkowron, PWe 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. |
| spellingShingle | Elkind, E Markakis, E Obraztsova, S Skowron, P Complexity of finding equilibria of plurality voting under structured preferences |
| title | Complexity of finding equilibria of plurality voting under structured preferences |
| title_full | Complexity of finding equilibria of plurality voting under structured preferences |
| title_fullStr | Complexity of finding equilibria of plurality voting under structured preferences |
| title_full_unstemmed | Complexity of finding equilibria of plurality voting under structured preferences |
| title_short | Complexity of finding equilibria of plurality voting under structured preferences |
| title_sort | complexity of finding equilibria of plurality voting under structured preferences |
| work_keys_str_mv | AT elkinde complexityoffindingequilibriaofpluralityvotingunderstructuredpreferences AT markakise complexityoffindingequilibriaofpluralityvotingunderstructuredpreferences AT obraztsovas complexityoffindingequilibriaofpluralityvotingunderstructuredpreferences AT skowronp complexityoffindingequilibriaofpluralityvotingunderstructuredpreferences |