Computational aspects of nearly single-peaked electorates
<p>Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become eas...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for the Advancement of Artificial Intelligence
2017
|
| _version_ | 1797072569133694976 |
|---|---|
| author | Erdelyi, G Lackner, M Pfandler, A |
| author_facet | Erdelyi, G Lackner, M Pfandler, A |
| author_sort | Erdelyi, G |
| collection | OXFORD |
| description | <p>Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly singlepeaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.</p> <p>In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the singlepeaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.</p> |
| first_indexed | 2024-03-06T23:09:36Z |
| format | Journal article |
| id | oxford-uuid:65025da2-eb1a-4834-9bb7-0d1c0762a6d7 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:09:36Z |
| publishDate | 2017 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:65025da2-eb1a-4834-9bb7-0d1c0762a6d72022-03-26T18:22:44ZComputational aspects of nearly single-peaked electoratesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:65025da2-eb1a-4834-9bb7-0d1c0762a6d7Symplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence2017Erdelyi, GLackner, MPfandler, A<p>Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly singlepeaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.</p> <p>In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the singlepeaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.</p> |
| spellingShingle | Erdelyi, G Lackner, M Pfandler, A Computational aspects of nearly single-peaked electorates |
| title | Computational aspects of nearly single-peaked electorates |
| title_full | Computational aspects of nearly single-peaked electorates |
| title_fullStr | Computational aspects of nearly single-peaked electorates |
| title_full_unstemmed | Computational aspects of nearly single-peaked electorates |
| title_short | Computational aspects of nearly single-peaked electorates |
| title_sort | computational aspects of nearly single peaked electorates |
| work_keys_str_mv | AT erdelyig computationalaspectsofnearlysinglepeakedelectorates AT lacknerm computationalaspectsofnearlysinglepeakedelectorates AT pfandlera computationalaspectsofnearlysinglepeakedelectorates |