Strategyproof facility location with learned predictions improves accuracy
Learning-Augmented Strategyproof Facility Location in $\mathbb{R}^d$ with $\ell_p$ Distances
Computer Science and Game Theory
Summary
Finding the best location for something like a public facility to minimize travel distances can be tricky, especially when people might lie about their locations. This paper studies a method that uses machine learning predictions combined with a strategy that prevents people from benefiting by lying. The authors analyze how well this method works when predictions are good and when they are wrong, in spaces of different dimensions and for various distance measures. They provide exact and asymptotic guarantees on how close their approach gets to the best possible location.
What this means in practice
- •For logistics planners: Place distribution centers to minimize total delivery costs even when location data is uncertain or strategic.
- •For urban planners: Decide facility sites like hospitals or schools with better guarantees on travel distance costs using learned location predictions.
A theory result. No direct application yet.
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
We study learning-augmented mechanism design for locating a single facility in $\mathbb{R}^d$ to minimize the sum of the agents' $\ell_p$ distances to the facility. We analyze the coordinate-wise median with predictions (CMP) mechanism, which adds $cn$ virtual agents at a predicted optimal facility location to the $n$ reported locations and returns their coordinate-wise median. The parameter $c\in[0,1)$ represents confidence in the prediction; CMP is known to be strategyproof when both are fixed independently of the reports. We determine its approximation guarantees under correct predictions (consistency) and arbitrary predictions (robustness) in two settings. First, for $d=2$, we establish exact guarantees for every $p\in[1,+\infty]$. For $1<p<+\infty$, the consistency and robustness are respectively $\Bigl(1+\bigl(\frac{1-c}{1+c}\bigr)^{\frac{p}{p-1}}\Bigr)^{\frac{p-1}{p}}$ and $\Bigl(1+\bigl(\frac{1+c}{1-c}\bigr)^{\frac{p}{p-1}}\Bigr)^{\frac{p-1}{p}}$. We use the median condition in each coordinate to compare the mechanism's cost with the optimal cost, and establish tightness using instances with agents at only three distinct locations. Second, for $1<p<+\infty$, we obtain dimension-independent consistency and robustness upper bounds valid for every $d\ge1$. For each fixed $p$ and $c$, we construct families of instances whose ratios approach the respective upper bounds as $d\to\infty$, proving asymptotic tightness. We also establish exact guarantees for $p=1$ in every dimension and asymptotically tight bounds for $p=+\infty$. Our high-dimensional results recover the prediction-free bounds of Gravin and Jia (STOC 2025) when $c=0$ and their learning-augmented bounds in arbitrary-dimensional Euclidean spaces when $p=2$.