Strategic Facility Location with $p$-Norm Social Costs

Abstract

We consider the strategic facility location problem in ${\ell }_q({\mathbb{R}}^d)$ spaces where the social cost is defined by an arbitrary $p$-norm of the individual costs. While the optimal approximation ratios for deterministic strategyproof mechanisms are well established in the $d=1$ setting, the guarantees for multi-dimensional spaces under an arbitrary $p$-norm are less understood. In this work, we analyze the well-studied, strategyproof coordinate-wise median (CM) mechanism and provide approximation guarantees for these generalized social costs. * We show that the CM mechanism is in fact robust to a broader class of social objectives: for every monotone symmetric norm objective, including all $p$-norm social costs, its approximation ratio never exceeds $3$ in arbitrary ${\ell }_q({\mathbb{R}}^d)$ spaces, regardless of the dimension. * For $d=2$, we establish tight approximation ratios for all $p,q\ge 1$ in ${\ell }_q({\mathbb{R}}^2)$. In particular, we show that the CM mechanism is a $2^{1-1/\max (p,q)}$-approximation, resolving the conjecture of Goel and Hann-Caruthers (Social Choice and Welfare, 2023) in the Euclidean case and extending the guarantee to arbitrary ${\ell }_q$ distances. * For $d\ge 3$, we refine the dimension-independent approximation guarantee for $p$-norm social costs in ${\ell }_q({\mathbb{R}}^d)$ spaces, giving 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 the utilitarian social cost.

Addresses recent reviewer feedback, improves the presentation of p-norm result in higher dimension, and adds a bound for monotone symmetric norms