Frugal bribery in voting
From MaRDI portal
Publication:527399
DOI10.1016/J.TCS.2017.02.031zbMATH Open1371.91050arXiv1504.08248OpenAlexW1500002581MaRDI QIDQ527399FDOQ527399
Authors: Palash Dey, Neeldhara Misra, Y. Narahari 
Publication date: 11 May 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: Bribery in elections is an important problem in computational social choice theory. However, bribery with money is often illegal in elections. Motivated by this, we introduce the notion of frugal bribery and formulate two new pertinent computational problems which we call Frugal-bribery and Frugal- $bribery to capture bribery without money in elections. In the proposed model, the briber is frugal in nature and this is captured by her inability to bribe votes of a certain kind, namely, non-vulnerable votes. In the Frugal-bribery problem, the goal is to make a certain candidate win the election by changing only vulnerable votes. In the Frugal-{dollar}bribery problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only vulnerable votes, subject to a budget constraint of the briber. We further formulate two natural variants of the Frugal-{dollar}bribery problem namely Uniform-frugal-{dollar}bribery and Nonuniform-frugal-{dollar}bribery where the prices of the vulnerable votes are, respectively, all the same or different. We study the computational complexity of the above problems for unweighted and weighted elections for several commonly used voting rules. We observe that, even if we have only a small number of candidates, the problems are intractable for all voting rules studied here for weighted elections, with the sole exception of the Frugal-bribery problem for the plurality voting rule. In contrast, we have polynomial time algorithms for the Frugal-bribery problem for plurality, veto, k-approval, k-veto, and plurality with runoff voting rules for unweighted elections. However, the Frugal-{dollar}bribery problem is intractable for all the voting rules studied here barring the plurality and the veto voting rules for unweighted elections.
Full work available at URL: https://arxiv.org/abs/1504.08248
Recommendations
Cites Work
- Title not available (Why is that?)
- Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
- Title not available (Why is that?)
- When are elections with few candidates hard to manipulate?
- Multivariate complexity analysis of Swap Bribery
- The computational difficulty of manipulating an election
- Bribery in voting with CP-nets
- On the hardness of bribery variants in voting with CP-nets
- Prices matter for the parameterized complexity of shift bribery
- Swap bribery
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How hard is bribery in elections?
- The complexity of probabilistic lobbying
- More natural models of electoral control by partition
- Frugal bribery in voting
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
Cited In (19)
- Large-scale election campaigns: combinatorial shift bribery
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Computational complexity characterization of protecting elections from bribery
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- Complexity of manipulation with partial information in voting
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- How hard is safe bribery?
- On the hardness of bribery variants in voting with CP-nets
- Local distance constrained bribery in voting
- A parameterized perspective on protecting elections
- How hard is bribery in elections?
- Swap bribery
- Cost-conscious voters in referendum elections
- Voting and bribing in single-exponential time
- Bribery in voting with CP-nets
- Complexity of conformant election manipulation
- How hard is bribery with distance restrictions?
- Approximating weighted and priced bribery in scoring rules
- Frugal bribery in voting
This page was built for publication: Frugal bribery in voting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527399)
