How hard is safe bribery?

DOI10.1016/J.TCS.2023.114156MaRDI QIDQ6057829zbMATH OpenOpenAlexFDO

Authors Neel Karia, Faraaz Mallick, Palash Dey

Publication date 26 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsbriberycomputational complexityparameterized hardnesssafe briberyshift briberysocial choicevoting

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Bribery in an election is one of the well-studied control problems in computational social choice. In this paper, we propose and study the safe bribery problem. Here the goal of the briber is to ask the bribed voters to vote in such a way that the briber never prefers the original winner (of the unbribed election) more than the new winner, even if the bribed voters do not fully follow the briber's advice. Indeed, in many applications of bribery, campaigning for example, the briber often has limited control on whether the bribed voters eventually follow her recommendation and thus it is conceivable that the bribed voters can either partially or fully ignore the briber's recommendation. We provide a comprehensive complexity theoretic landscape of the safe bribery problem for many common voting rules in this paper.

Cites work

• A parameterized perspective on protecting elections
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• Approximating weighted and priced bribery in scoring rules
• Barriers to manipulation in voting
• Bribery in voting with CP-nets
• Campaign management under approval-driven voting rules
• Complexity of safe strategic voting
• Complexity of shift bribery for iterative voting rules
• Complexity of shift bribery in committee elections
• Control and bribery in voting
• Editing graphs to satisfy degree constraints: a parameterized approach
• Frugal bribery in voting
• How hard is bribery in elections?
• How hard is bribery with distance restrictions?
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Introduction to algorithms.
• Is it ever safe to vote strategically?
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Local distance constrained bribery in voting
• More natural models of electoral control by partition
• Multivariate complexity analysis of Swap Bribery
• On the hardness of bribery variants in voting with CP-nets
• Opinion diffusion and campaigning on society graphs
• Parameterized algorithms
• Prices matter for the parameterized complexity of shift bribery
• Soft constraint problems with uncontrollable variables
• Swap bribery
• The complexity of manipulative attacks in nearly single-peaked electorates
• The complexity of probabilistic lobbying
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(1)

• Parameterized analysis of bribery in \textit{Challenge the champ} tournaments

This page was built for publication: How hard is safe bribery?

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