New paper proves coordinate-wise median is 3-approximation for any facility location cost norm

Jabari Hastings' new paper on arXiv tackles a fundamental problem in computational social choice and mechanism design: placing a facility to minimize total social cost when agents' costs are measured by a general p-norm of their distances. The strategic facility location problem asks for a strategyproof mechanism (one where agents cannot benefit by lying) that approximates the optimal social cost. While the one-dimensional case is well understood, multi-dimensional settings under arbitrary p-norms have remained open.

The paper's main result is surprising: the simple coordinate-wise median (CM) mechanism — which takes the median of each coordinate independently — is robust to an entire class of social objectives. For every monotone symmetric norm (including all p-norms), CM achieves an approximation ratio of at most 3 in any ℓ_q(ℝ^d) space, regardless of dimension. This means a single, easy-to-implement mechanism works well for virtually any reasonable definition of social cost.

For the special case of d=2 (the plane), Hastings provides tight approximation ratios for all p,q ≥ 1. Specifically, the CM mechanism is a 2^{1-1/\max(p,q)}-approximation, resolving a conjecture by Goel and Hann-Caruthers (Social Choice and Welfare, 2023) for Euclidean spaces and extending to arbitrary ℓ_q distances. For higher dimensions (d ≥ 3), the paper refines the dimension-independent guarantee, offering upper bounds that depend on the relationship between the social-cost norm p and the underlying distance norm q. This generalizes the recent result of Gravin and Jia (STOC, 2025) for utilitarian social cost.

The work addresses feedback from reviewers and improves presentation of the p-norm result in higher dimensions. It also adds a bound for monotone symmetric norms, making the CM mechanism a versatile tool for facility location in AI planning, logistics, and public infrastructure placement where fairness and efficiency must be balanced.