Research map / Learning theory and algorithms / Submodular and game algorithms
Approximation and Hardness of Shift-Bribery
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 |
|---|---|---|---|
| Apply LP-based approximation and preprocessing to arbitrary positional scoring rules | Shift-Bribery with positional scoring rules and arbitrary prices · Positional scoring rules | approximation ratio: $(1 + \varepsilon)$ | Helped |
| Use an EPTAS for unit-price Borda shift bribery | Borda Shift-Bribery · Borda, unit prices | approximation ratio: $(1 + \varepsilon)$ | Helped |
| Use a combinatorial PTAS that targets only the most over-scoring opponents | Borda Shift-Bribery · Borda, unit prices | approximation ratio: $(1 + \varepsilon)$ | Helped |
| Use the improved parameterized algorithm | Borda Shift-Bribery · Borda, arbitrary price functions | running time: $2^{O(K)}\text{poly}(|I|)$ versus $2^{O(K^2)}\text{poly}(|I|)$ | Helped |
| Round an LP basic solution and complete it with arbitrary shifts | Borda Shift-Bribery · Borda, unit prices | solution cost: $\opt(I) + \sqrt{\opt(I)}$ | Helped |
| Bribe voters who rank the preferred candidate lowest first | Borda Shift-Bribery · Borda, uniform-all-or-nothing prices | solution cost: $(1.5 \cdot \opt(I) + 1)$ | Helped |
| Reduce Densest-$k$-Subgraph to Copeland shift bribery | Copeland$^\alpha$-Shift-Bribery · Copeland, unit or all-or-nothing prices | approximability: $O(\tau(|V_G|^{O(1)})^2)$ | Hurt |
| Apply the Gap-ETH reduction for the unit-shift parameter | Copeland$^\alpha$-Shift-Bribery · Copeland, unit prices | approximability: $(2 - \varepsilon) \opt(I)$ | Hurt |
| Apply parameterized hardness for the affected-voter parameter | Copeland$^\alpha$-Shift-Bribery · Copeland, affected-voter parameter | approximability: any constant factor | Hurt |
| Reduce Cubic Vertex Cover to uniform-all-or-nothing Borda shift bribery | Borda Shift-Bribery · Borda, uniform-all-or-nothing prices | computational complexity: \NP-hard | Hurt |
Closest papers by meaning
- Complexity of Shift Bribery in Committee Elections (AAAI 2016 · similarity 0.91)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.85)
- Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.85)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.84)
- Multi-Winner Reconfiguration (NeurIPS 2024 · similarity 0.84)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.84)
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.