Maximum-Cost Strategic Facility Location: The Limits of Randomization

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 $$\alpha (\mathcal{M})\ge 2-e^{-\mathrm{\Theta }(\sqrt{d})}-O\left(n^{-2\mathrm{/}(d-1)}\right)\mathrm{.}$$ Therefore, no strategyproof-in-expectation mechanism can guarantee a $(2-\epsilon )$-approximation uniformly over all $n$ and $d$, for any universal constant $\epsilon >0$.