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