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

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 ℝ². 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.