Research map / Learning theory and algorithms / Submodular and game algorithms
Randomized Strategic Facility Location with Predictions
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 randomized truthful learning-augmented mechanisms for strategic facility location under egalitarian cost on the line and in the Euclidean plane, giving tight robustness-consistency trade-offs for different prediction types.
Problem
Strategic facility location with egalitarian social cost: designing truthful mechanisms that use predictions while balancing consistency and robustness, and understanding the power of randomization and of different prediction types.
Approach
Shows randomization and stronger prediction types (full agent locations, or identities of extreme agents) enable better consistency-robustness trade-offs than deterministic optimal-location predictions; for the line a randomized mix of two known mechanisms is Pareto optimal, and in the plane a Centroid-on-extreme-agents mechanism with an Euler-line argument gives 1.67 consistency and 2 robustness.
Key results
- On the line, any randomized truthful-in-expectation mechanism that is (1+δ)-consistent can be no better than (2-δ)-robust, even with full location predictions; this trade-off is achieved by randomizing between LRM and MinMaxP.
- In the plane, a randomized truthful mechanism using predictions of extreme agent IDs achieves 1.67 consistency and 2 robustness.
- In the plane, any randomized truthful-in-expectation mechanism has approximation ratio at least 1.118 without predictions; no deterministic mechanism can be better than 2-consistent and better than 1+√2-robust with full predictions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use predicted extreme-agent identities and run the centroid mechanism only on those agents rather than all agents | Centroid mechanism in the Euclidean plane · Euclidean plane, accurate extreme-agent ID predictions | consistency: 2 - 1/n to 2 - 1/3 ≈ 1.67 | Helped |
| Mix LRM with MinMaxP, choosing LRM with probability 2δ | Truthful learning-augmented mechanisms on the line · Line, accurate predictions | consistency: 1 + δ consistency; 2 - δ robustness | Mixed |
| Use extreme-agent ID predictions instead of running the centroid mechanism over all agents | Centroid mechanism in the Euclidean plane · Euclidean plane, arbitrary predictions | robustness: 2 | No clear effect |
| Provide predictions for all agent locations except one extreme location | Truthful mechanisms on the line · Line, accurate predictions for n-1 agents | consistency: 2 deterministic; 1.5 randomized | No clear effect |
Surprising findings
- The 1.5 lower bound for randomized mechanisms on the line does not extend to two dimensions; the paper proves only 1.118 there.
- Full agent-location predictions do not improve deterministic consistency beyond 2 on the line, even without robustness constraints.
Limitations
- Euclidean plane results are not tight: gap between 1.118 and 2-1/n lower/upper bounds remains open.
- Results assume unanimous, anonymous, scale-independent mechanisms; the two-dimensional 1.67 result relies on a perturbation argument for at most three extreme agents.
- Two-dimensional lower bound for randomized mechanisms is only 1.118, and the 1.67 consistency result is for a specific prediction type.
Experimental setup
Metrics: consistency robustness approximation ratio of egalitarian social cost
Baselines: LRM mechanism MinMaxP mechanism Centroid mechanism Minimum Bounding Box mechanism
Builds on: Centroid mechanism MinMaxP mechanism LRM mechanism Minimum Bounding Box mechanism
Closest papers by meaning
- MAC Advice for facility location mechanism design (NeurIPS 2024 · similarity 0.90)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.88)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.88)
- Improved Bounds for Online Facility Location with Predictions (AAAI 2025 · similarity 0.86)
- Altruism in Facility Location Problems (AAAI 2024 · similarity 0.85)
- Procurement Auctions with Predictions: Improved Frugality for Facility Location (NeurIPS 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.