Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions

We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in ℝ2. We show that for the p-norm (p ≥ 1) objective, the coordinate-wise median mechanism (CM) has the lowest worst-case approximation ratio in the class of deterministic, anonymous, and strategyproof mechanisms. For the minisum objective and an odd number of agents n, we show that CM has a worst-case approximation ratio (AR) of √2frac√n2+1n+1. For the p-norm social cost objective (p≥ 2), we find that the AR for CM is bounded above by 2^frac32-frac2p. We conjecture that the AR of CM actually equals the lower bound 2^1-frac1p (as is the case for p=2 and p=∞) for any p≥ 2.