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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Bribery in voting with CP-nets
- Frugal bribery in voting
- How hard is bribery in elections?
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
- 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
- Prices matter for the parameterized complexity of shift bribery
- Swap bribery
- The complexity of probabilistic lobbying
- The computational difficulty of manipulating an election
- When are elections with few candidates hard to manipulate?
Cited in
(19)- Approximating weighted and priced bribery in scoring rules
- Large-scale election campaigns: combinatorial shift bribery
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- Computational complexity characterization of protecting elections from bribery
- 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
- Bribery in voting with CP-nets
- Voting and bribing in single-exponential time
- Complexity of conformant election manipulation
- How hard is bribery with distance restrictions?
- 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)
