# MAC Advice for Facility Location Mechanism Design

arXiv: https://arxiv.org/abs/2403.12181 · HTML: https://mlsanity.com/paper/2403.12181/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 18 Mar 2024.

## Builds on (most cited first, 27 of 27)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [Improved Price of Anarchy via Predictions](https://mlsanity.com/paper/2205.04252/) (2022)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives](https://mlsanity.com/paper/1911.09813/) (2019)
- [Learning-Augmented Algorithms for Online Steiner Tree](https://mlsanity.com/paper/2112.05353/) (2021)
- [Hardness of Approximation of Euclidean k-Median](https://mlsanity.com/paper/2011.04221/) (2020)
- [Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions](https://mlsanity.com/paper/2007.00903/) (2020)
- [Mechanism Design With Predictions for Obnoxious Facility Location](https://mlsanity.com/paper/2212.09521/) (2022)
- [Bicriteria Multidimensional Mechanism Design with Side Information](https://mlsanity.com/paper/2302.14234/) (2023)
- [Strategyproof Facility Location for Three Agents on a Circle](https://mlsanity.com/paper/1902.08070/) (2019)
- [Clustering What Matters: Optimal Approximation for Clustering with Outliers](https://mlsanity.com/paper/2212.00696/) (2022)
- [Online Algorithms with Randomly Infused Advice](https://mlsanity.com/paper/2302.05366/) (2023)

## Abstract (arXiv)

Algorithms with predictions have attracted much attention in the last years across various domains, including variants of facility location, as a way to surpass traditional worst-case analyses. We study the k-facility location mechanism design problem, where the n agents are strategic and might misreport their location. Unlike previous models, where predictions are for the k optimal facility locations, we receive n predictions for the locations of each of the agents. However, these predictions are only "mostly" and "approximately" correct (or MAC for short) -- i.e., some δ-fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder of the predictions are allowed to be correct up to an varepsilon-error. We make no assumption on the independence of the errors. Can such predictions allow us to beat the current best bounds for strategyproof facility location? We show that the 1-median (geometric median) of a set of points is naturally robust under corruptions, which leads to an algorithm for single-facility location with MAC predictions. We extend the robustness result to a "balanced" variant of the k facilities case. Without balancedness, we show that robustness completely breaks down, even for the setting of k=2 facilities on a line. For this "unbalanced" setting, we devise a truthful random mechanism that outperforms the best known result of Lu et al. [2010], which does not use predictions. En route, we introduce the problem of "second" facility location (when the first facility's location is already fixed). Our findings on the robustness of the 1-median and more generally k-medians may be of independent interest, as quantitative versions of classic breakdown-point results in robust statistics.