Often Harder than in the Constructive Case: Destructive Bribery in CP-nets

DOI10.1007/978-3-662-48995-6_23MaRDI QIDQ3460798zbMATH OpenOpenAlexFDO

Authors B. Dorn, Dominikus Krüger, Patrick Scharpfenecker

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1509.08628

zbMATH Keywords

briberycomputational social choiceCP-netsdestructivevoting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Abstract: We study the complexity of the destructive bribery problem---an external agent tries to prevent a disliked candidate from winning by bribery actions---in voting over combinatorial domains, where the set of candidates is the Cartesian product of several issues. This problem is related to the concept of the margin of victory of an election which constitutes a measure of robustness of the election outcome and plays an important role in the context of electronic voting. In our setting, voters have conditional preferences over assignments to these issues, modelled by CP-nets. We settle the complexity of all combinations of this problem based on distinctions of four voting rules, five cost schemes, three bribery actions, weighted and unweighted voters, as well as the negative and the non-negative scenario. We show that almost all of these cases are NP-complete or NP-hard for weighted votes while approximately half of the cases can be solved in polynomial time for unweighted votes.

Recommendations

• On the hardness of bribery variants in voting with CP-nets
• Bribery in voting with CP-nets
• On the complexity of bribery with distance restrictions
• Node and network resistance to bribery in multi-agent systems
• Approximation and hardness of shift-bribery
• Prices matter for the parameterized complexity of shift bribery
• A note on competitive bribery games
• On the complexity of bribery and manipulation in tournaments with uncertain information
• Bribery in path-disruption games
• On the constancy of bribe-proof solutions

Cites work

• A Richer Understanding of the Complexity of Election Systems
• Anyone but him: the complexity of precluding an alternative
• Bribery in voting with CP-nets
• How hard is bribery in elections?
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6928629 (Why is no real title available?)
• scientific article; zbMATH DE number 2243357 (Why is no real title available?)
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Often Harder than in the Constructive Case: Destructive Bribery in CP-nets
• On the hardness of bribery variants in voting with CP-nets
• Swap bribery

Cited in

(4)

• On the complexity of bribery with distance restrictions
• Bribery in voting with CP-nets
• On the hardness of bribery variants in voting with CP-nets
• Often Harder than in the Constructive Case: Destructive Bribery in CP-nets

Describes a project that uses

Uses Software

• CP-nets

This page was built for publication: Often Harder than in the Constructive Case: Destructive Bribery in CP-nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460798)