Metraipolis › archive › dc_8dd3236ae3db

Learning-Augmented Strategyproof Facility Location in $\mathbb{R}^d$ with $\ell_p$ Distances — arXiv:2609.12829

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12829
License (as archived)
CC0-1.0
Archived
2026-10-16T03:09:04.616Z
SHA-256 of the archived text
8e5ace406e0f96aac67244259f989f841954c719c825c868deb1a774d275629d
Stable URL of this page
https://metraipolis.com/documento/dc_8dd3236ae3db

How to cite

Learning-Augmented Strategyproof Facility Location in $\mathbb{R}^d$ with $\ell_p$ Distances — arXiv:2609.12829 — arXiv (en), https://arxiv.org/abs/2609.12829 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8dd3236ae3db (Metraipolis archive dc_8dd3236ae3db, sha256 8e5ace406e0f96aac67244259f989f841954c719c825c868deb1a774d275629d)
BibTeX
@misc{dc8dd3236ae3db,
  title = {Learning-Augmented Strategyproof Facility Location in $mathbbR^d$ with $ell_p$ Distances — arXiv:2609.12829},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12829},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8dd3236ae3db; sha256 8e5ace406e0f96aac67244259f989f841954c719c825c868deb1a774d275629d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12829. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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$.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-14 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.12829 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:04:07.414Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).