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
(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 (
(pge 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
(pge 2)
.