Maximum-Cost Strategic Facility Location: The Limits of Randomization
2026-08-17 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a problem where a single facility has to be placed in space based on agents' reported locations, aiming to keep the farthest agent as close as possible. They focus on mechanisms that are strategyproof, meaning agents can't benefit from lying about their locations. Previous work showed deterministic mechanisms can't do better than twice the best possible result. The authors prove that even if randomization is allowed, no method can consistently beat this factor by any fixed amount for all dimensions and numbers of agents.
Facility locationEuclidean spaceStrategyproof mechanismApproximation ratioRandomizationDeterministic mechanismsMax distance minimizationAgent reportsMechanism designStrategyproof-in-expectation
Authors
Jabari Hastings, Misha Ivkov
Abstract
We consider strategic facility location in Euclidean space $\mathbb R^d$, where a mechanism selects a single facility based on the reported locations of $n$ agents and seeks to minimize the maximum distance from any agent to the facility. The optimal approximation ratio of deterministic strategyproof mechanisms is $2$. Whether randomization can yield a universal constant improvement over this factor has remained a major open question. We show that for $d \geq 2$, every strategyproof-in-expectation mechanism has approximation ratio at least \[ α(\mathcal M) \ge 2 - e^{-Θ(\sqrt d)} - O\left(n^{-2/(d-1)}\right). \] Therefore, no strategyproof-in-expectation mechanism can guarantee a $(2-\varepsilon)$-approximation uniformly over all $n$ and $d$, for any universal constant $\varepsilon>0$.