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

arXiv: https://arxiv.org/abs/2007.00903 · HTML: https://mlsanity.com/paper/2007.00903/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2020.

## Built on by (most cited first, 4 of 4)

- [Facility Location Games with Scaling Effects](https://mlsanity.com/paper/2402.18908/) (2024)
- [MAC Advice for Facility Location Mechanism Design](https://mlsanity.com/paper/2403.12181/) (2024)
- [Equitable Mechanism Design for Facility Location](https://mlsanity.com/paper/2506.10460/) (2025)
- [Mechanism Design for Facility Location using Predictions](https://mlsanity.com/paper/2508.03818/) (2025)

## Abstract (arXiv)

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