Research map / Learning theory and algorithms / Submodular and game algorithms
Frugal Bribery in Voting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict vote changes to voters who prefer the desired candidate to the current winner | Frugal-bribery · Unweighted k-approval, simplified Bucklin, and plurality with runoff | computational complexity: in P | Helped |
| Add prices and a budget to the vulnerable-voter-only restriction | Frugal-$bribery · Unweighted plurality and veto | computational complexity: in P | No clear effect |
| Add prices and a budget to the vulnerable-voter-only restriction | Frugal-$bribery · Unweighted Borda, maximin, Copeland, and STV | computational complexity: NP-complete | Hurt |
| Use a uniform price of 1 for vulnerable votes and budget 2 | Uniform-frugal-$bribery · Unweighted Borda | computational complexity: NP-complete | Hurt |
| Restrict the budget to a constant | Frugal-$bribery · Unweighted k-approval, simplified Bucklin, and plurality with runoff | computational complexity: in P | Helped |
| Restrict vote changes to vulnerable voters | Frugal-bribery · Weighted plurality | computational complexity: in P | Helped |
| Use weighted votes rather than unweighted votes | Frugal-bribery · Plurality, maximin, Copeland, and other studied rules | computational complexity: 3 candidates; 4 candidates | Mixed |
Closest papers by meaning
- Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm (AAAI 2019 · similarity 0.90)
- Approximation and Hardness of Shift-Bribery (AAAI 2019 · similarity 0.88)
- Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates (AAAI 2016 · similarity 0.87)
- Generalized Distance Bribery (AAAI 2019 · similarity 0.87)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.85)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.