On the hardness of bribery variants in voting with CP-nets

B Dorn, D Krüger - Annals of Mathematics and Artificial Intelligence, 2016 - Springer
B Dorn, D Krüger
Annals of Mathematics and Artificial Intelligence, 2016Springer
We continue previous work by Mattei et al.(Ann. Math. Artif. Intell. 1042 68 (1–3), 135–160
2013) in which they study the computational complexity of bribery schemes when voters
have conditional preferences modeled as CP-nets. For most of the cases they considered,
they showed that the bribery problem is solvable in polynomial time. Some cases remained
open—we solve several of them and extend the previous results to the case that voters are
weighted. Additionally, we consider negative (weighted) bribery in CP-nets, when the briber …
Abstract
We continue previous work by Mattei et al. (Ann. Math. Artif. Intell. 1042 68(1–3), 135–160 2013) in which they study the computational complexity of bribery schemes when voters have conditional preferences modeled as CP-nets. For most of the cases they considered, they showed that the bribery problem is solvable in polynomial time. Some cases remained open—we solve several of them and extend the previous results to the case that voters are weighted. Additionally, we consider negative (weighted) bribery in CP-nets, when the briber is not allowed to pay voters to vote for his preferred candidate.
Springer