Metraipolis › archive › dc_772dc9725a93

Strategic Facility Location in Euclidean Spaces — arXiv:2609.05132

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.05132
License (as archived)
CC0-1.0
Archived
2026-10-16T22:45:40.387Z
SHA-256 of the archived text
3e88589fe23533eac014acea3ae7e19b74712e5c04054808ca1f041beb0553b4
Stable URL of this page
https://metraipolis.com/documento/dc_772dc9725a93

How to cite

Strategic Facility Location in Euclidean Spaces — arXiv:2609.05132 — arXiv (en), https://arxiv.org/abs/2609.05132 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_772dc9725a93 (Metraipolis archive dc_772dc9725a93, sha256 3e88589fe23533eac014acea3ae7e19b74712e5c04054808ca1f041beb0553b4)
BibTeX
@misc{dc772dc9725a93,
  title = {Strategic Facility Location in Euclidean Spaces — arXiv:2609.05132},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.05132},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_772dc9725a93; sha256 3e88589fe23533eac014acea3ae7e19b74712e5c04054808ca1f041beb0553b4},
  year = {2026}
}

Archived text

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

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-07 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.05132 — 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-16T22:29:53.696Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).