Research map / Learning theory and algorithms / Submodular and game algorithms
Obvious Strategyproofness Needs Monitoring for Good Approximations
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 |
|---|---|---|---|
| Add monitoring and first-price payments to an arbitrary algorithm | Direct-revelation mechanism · Scheduling and facility location | approximation guarantee: optimal (approximation, resp.) algorithm ... without losses to the approximation guarantee | Helped |
| Require OSP without monitoring and voluntary participation | Related-machine scheduling · Related-machine scheduling | approximation ratio: 2 | Hurt |
| Require OSP without monitoring | Facility location · Facility location | approximation ratio: n-1 | Hurt |
| Remove money while retaining monitoring and OSP | Facility location · Facility location | approximation ratio: n-1 | Hurt |
| Use a median-based first-price mechanism with monitoring | Facility location · Facility location | social cost: optimal | Helped |
| Use the interval mechanism's shifted payments | Facility location · Facility location | social cost: optimal | Helped |
| Use earlier declarations to optimize charges | Interval mechanism · Facility location | agent payments: from b-a to |x_i - f| | Helped |
| Remove monitoring | OSP scheduling mechanism · Related-machine scheduling | approximation ratio: 2 | Hurt |
| Remove monitoring and payments | OSP facility-location mechanism · Facility location | approximation ratio: n-1 | Hurt |
Closest papers by meaning
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.90)
- Automated Design of Affine Maximizer Mechanisms in Dynamic Settings (AAAI 2024 · similarity 0.86)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.86)
- Protocols for Verifying Smooth Strategies in Bandits and Games (NeurIPS 2025 · similarity 0.84)
- Mechanism design augmented with output advice (NeurIPS 2024 · similarity 0.83)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.83)
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.