The Library
Bypassing combinatorial protections : polynomial-time algorithms for single-peaked electorates
Tools
Brandt, Felix, Brill, Markus, Hemaspaandra, Edith and Hemaspaandra, Lane A. (2015) Bypassing combinatorial protections : polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 53 . pp. 439-496. doi:10.1613/jair.4647 ISSN 1076-9757.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1613/jair.4647
Abstract
For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates---single-peaked preferences---those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems---including those for Kemeny and Llull elections---fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Journal of Artificial Intelligence Research | ||||
Publisher: | AAAI Press | ||||
ISSN: | 1076-9757 | ||||
Official Date: | 22 July 2015 | ||||
Dates: |
|
||||
Volume: | 53 | ||||
Page Range: | pp. 439-496 | ||||
DOI: | 10.1613/jair.4647 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |