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$. For the minisum objective and an odd number of agents, we show that the coordinate-wise median mechanism (CM) has a worst-case approximation ratio (AR) of $\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$. Further, we show that CM has the lowest AR for this objective in the class of deterministic, anonymous, and strategyproof mechanisms. For the $p-norm$ social welfare objective, we find that the AR for CM is bounded above by $2^{\frac{3}{2}-\frac{2}{p}}$ for $p\geq 2$. Since any deterministic strategyproof mechanism must have AR at least $2^{1-\frac{1}{p}}$ (\citet{feigenbaum_approximately_2017}), our upper bound suggests that the CM is (at worst) very nearly optimal. We conjecture that the approximation ratio of coordinate-wise median is actually equal to the lower bound $2^{1-\frac{1}{p}}$ (as is the case for $p=2$ and $p=\infty$) for any $p\geq 2$.