New paper proves limits of strategyproof facility location mechanisms

A new arXiv paper by Rafael Gomes, Sophie Klumper, Guido Schäfer, and Jens Schlöter tackles the strategic facility location problem with an egalitarian objective: picking a spot to minimize the maximum distance to any agent. The catch? Agents can misreport their locations to tilt the decision in their favor. The authors prove that any mechanism that is strategyproof in expectation (agents gain nothing by lying) must have an approximation ratio of at least 1 + sqrt(d / (2(d+1))) in d-dimensional Euclidean space, an asymptotic improvement over prior bounds. They show this barrier is driven by large populations: for just two agents, a simple randomized mechanism achieves a sqrt(2) approximation, bypassing the lower bound.

Next, they explore an output-augmented framework where the facility can be placed outside the agents' domain. When agents are restricted to a line but the facility can be anywhere in the plane, they design a deterministic strategyproof sqrt(2)-approximate mechanism and prove a matching lower bound, showing that output augmentation can eliminate the need for randomness. For agents on a unit circle with the facility allowed anywhere in R^2, they introduce a randomized 3/2-approximate mechanism that is group-strategyproof in expectation. These results offer new design principles for practical location-based services (like server placement or emergency response) where users might game the system.