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

Original · EN

We consider the problem of locating a single facility on the real line. This facility serves a set of agents, each of whom is located on the line, and incurs a cost equal to his distance from the facility. An agent's location is private information that is known only to him. Agents report their location to a central planner who decides where to locate the facility. The planner's objective is to minimize a "social" cost function that depends on the agent-costs. However, agents might not report truthfully; to address this issue, the planner must restrict himself to strategyproof mechanisms, in which truthful reporting is a dominant strategy for each agent. A mechanism that simply chooses the optimal solution is generally not strategyproof, and so the planner aspires to use a mechanism that effectively approximates his objective function. In our paper, we study the problem described above with the social cost function being the Lₚ norm of the vector of agent-costs. We show that the median mechanism (which is known to be strategyproof) provides a 2¹⁻¹/ᵖ approximation ratio, and that is the optimal approximation ratio among all deterministic strategyproof mechanisms. For randomized mechanisms, we present two results. First, we present a negative result: we show that for integer ∞>p>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, we show that a mechanism called LRM, first designed by Procaccia and Tennenholtz for the special case of L∞, provides the optimal approximation ratio among all randomized mechanisms.