Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates

Felix Brandt, Markus Brill, Edith Hemaspaandra, Lane A. Hemaspaandra

Research output: Contribution to journalArticlepeer-review

66 Scopus citations

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 NPhard 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 Θ2p-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.

Original languageEnglish
Pages (from-to)439-496
Number of pages58
JournalJournal of Artificial Intelligence Research
Volume53
DOIs
StatePublished - 15 Jul 2015

Fingerprint

Dive into the research topics of 'Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates'. Together they form a unique fingerprint.

Cite this