Approximate Strategyproof Mechanisms for Facility Location Games

We present an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with n \geq 5 agents, any such mechanism either admits a unique dictator, or allocates the facilities to the two extreme locations of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely n-2.

Building on the techniques used for the characterization, we also show that:

-- For every k \geq 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for k-Facility Location on the line, even for simple instances with k+1 agents.

-- There do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on general metric spaces, which is true even for simple instances with 3 agents located in a star.

On the positive side, we present a randomized mechanism for locating k facilities on the line that achieves an approximation ratio of 2 for the objective of maximum cost and an approximation ratio of n for the objective of total cost.

This is a joint work with Christos Tzamos (CSAIL, MIT)