TY - JOUR
T1 - Bypassing combinatorial protections
T2 - Polynomial-time algorithms for single-peaked electorates
AU - Brandt, Felix
AU - Brill, Markus
AU - Hemaspaandra, Edith
AU - Hemaspaandra, Lane A.
N1 - Publisher Copyright:
© 2015 AI Access Foundation. All rights reserved.
PY - 2015/7/15
Y1 - 2015/7/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84938353788&partnerID=8YFLogxK
U2 - 10.1613/jair.4647
DO - 10.1613/jair.4647
M3 - Article
AN - SCOPUS:84938353788
SN - 1076-9757
VL - 53
SP - 439
EP - 496
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -