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 $$\mathbb {R}^2$$ R 2 . We show that for the p-norm ( $$p \ge 1$$ 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 $$\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$$ 2 n 2 + 1 n + 1 . For the p-norm social cost objective ( $$p\ge 2$$ p ≥ 2 ), we find that the AR for CM is bounded above by $$2^{\frac{3}{2}-\frac{2}{p}}$$ 2 3 2 - 2 p . We conjecture that the AR of CM actually equals the lower bound $$2^{1-\frac{1}{p}}$$ 2 1 - 1 p (as is the case for $$p=2$$ p = 2 and $$p=\infty$$ p = ∞ ) for any $$p\ge 2$$ p ≥ 2 .