Abstract
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 R². 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 √2√n²+1/n+1. For the p-norm social cost objective (p≥ 2), we find that the AR for CM is bounded above by 2^3/2-2/p. We conjecture that the AR of CM actually equals the lower bound 2^1-1/p (as is the case for p=2 and p=∞) for any p≥ 2.