Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L_p Norm of Costs

This paper is concerned with the problem of locating a facility on a line in the presence of strategic agents, also located on that line. Each agent incurs a cost equal to her distance to the facility whereas the planner wishes to minimize the L_p norm of the vector of agent costs. The location of each agent is only privately known, and the goal is to design a strategyproof mechanism that approximates the optimal cost well. It is shown that the median mechanism provides a 2^1−1/p approximation ratio, and that this is the optimal approximation ratio among all deterministic strategyproof mechanisms. For randomized mechanisms, two results are shown: First, for any integer p larger than 2, no mechanism—from a rather large class of randomized mechanisms—has an approximation ratio better than that of the median mechanism. This is in contrast to the case of p = 2 and p = ∞ where a randomized mechanism provably helps improve the worst case approximation ratio. Second, for the case of 2 agents, the Left-Right-Middle (LRM) mechanism, first designed by Procaccia and Tennenholtz for the special case of infinity norm, provides the optimal approximation ratio among all randomized mechanisms.