Research map / Bandits and online learning / Online convex optimization and games
MAC Advice for facility location mechanism design
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies strategyproof k-facility location with MAC (mostly approximately correct) predictions, showing the geometric median is robust to corruptions and designing a randomized mechanism for 2-facility location on a line beating the no-prediction bound of 4.
Problem
Strategyproof k-facility location mechanism design where agents may misreport locations and the per-agent predictions may be arbitrarily wrong for a delta-fraction of agents; prior prediction models assume worst-case error, which breaks robustness.
Approach
Introduces MAC predictions (most predictions approximately correct, a delta-fraction arbitrarily corrupted), proves quantitative breakdown-point robustness of the 1-median and balanced k-medians, and combines them with a second-facility proportional mechanism to get beyond-interpolation randomized mechanisms.</ идея="">
Key results
- Single-facility mechanism in R^d achieves approximation min{1+4delta/(1-2delta), sqrt(d)} using geometric median of predictions.
- Randomized mechanism for 2-facility location on a line achieves expected approximation 3.6 + O(delta), beating the no-prediction bound of 4.
- Balanced k-facility deterministic mechanism achieves approximation c + O(delta/beta), versus n/2 - 1 without predictions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAC predictions to choose between the geometric median of predictions and the coordinate-wise median of reports | Single-facility location in R^d · Single-facility location in R^d | approximation ratio: min{1 + 4δ/(1-2δ), √d} vs. √d | Helped |
| Use MAC predictions and reports in a randomized strategyproof mechanism | 2-facility location on a line · 2-facility location on a line | expected approximation ratio: 3.6 + O(δ) vs. 4 | Helped |
| Use predictions to compute a slightly less balanced k-median | β-balanced k-facility location · β-balanced k-facility location | approximation ratio: 1 + 4k/(b-2 - 2k) vs. n/2 - 1 | Helped |
| Use the geometric median of predictions after changing a δ-fraction of points | Geometric median · Single-facility location in a metric space | approximation robustness: 1 + 4δ/(1-2δ) | Helped |
| Require balanced clusters when using k-medians under corruptions | k-median location estimator · k-median with δ-fraction corruptions | robustness: 1 + 4k/(b-2-2k) | Helped |
| Use unbalanced k-medians without a balancedness condition | k-median location estimator · 2-median with a single changed point | solution robustness | Hurt |
| Use the proportional mechanism to choose the second facility | Second facility location · Second facility location on a line | expected approximation ratio: 3 | Helped |
Surprising findings
- Robustness completely breaks down for unbalanced 2-facility location on a line with deterministic mechanisms, even though the 1-median is robust.
Limitations
- Results for 2-facility location on a line use constants (3.6) that are not optimized and only hold for small constant delta.
- Balanced k-facility results only for constant k and require a minimum cluster size assumption.
- Deterministic k-median robustness fails without balancedness.
Experimental setup
Metrics: approximation ratio expected approximation ratio distance robustness approximation robustness
Baselines: Lu et al. 2010 randomized mechanism (expected ratio 4) Two Extremes mechanism (n-2) coordinate-wise median (sqrt(d)) Chen et al. 2019 predicted-location mechanism
Builds on: proportional mechanism (Lu et al. 2010) geometric median breakdown point (Huber) PMAC learning model
Closest papers by meaning
- Learning-Augmented Mechanism Design for Facility Location under $L_p$-Norm Social Costs (NeurIPS 2026 · similarity 0.91)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.90)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.86)
- Improved Bounds for Online Facility Location with Predictions (AAAI 2025 · similarity 0.85)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.85)
- Altruism in Facility Location Problems (AAAI 2024 · similarity 0.82)
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.