Maximum-Cost Strategic Facility Location: The Limits of Randomization

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 \[ \alpha(\mathcal M) \ge 2 - e^{-\Theta(\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$.