Research map / Learning theory and algorithms / Submodular and game algorithms
Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
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 |
|---|---|---|---|
| Use an additive-ε approximation algorithm based on a reduction to MKU | BVU with a constant number of candidates · BVU | objective value: OPT-ε | Helped |
| Introduce uncertainty that a bribed voter's vote may not be counted | classic plurality bribery · BVU, two candidates | polynomial-time multiplicative approximability: no O(1)-approximation | Hurt |
| Introduce bribed-voter uncertainty | classic plurality bribery parameterized by r · BVU, two candidates | FPT multiplicative approximability: no O(1)-approximation | Hurt |
Closest papers by meaning
- Frugal Bribery in Voting (AAAI 2016 · similarity 0.90)
- Approximation and Hardness of Shift-Bribery (AAAI 2019 · similarity 0.89)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.85)
- Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.85)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.84)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (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.