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\ge 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-\epsilon )$-approximation uniformly over all $n$ and $d$, for any universal constant $\epsilon >0$.

15 pages