Strategyproof Mechanisms for Euclidean Facility Location Problems

Strategyproof Mechanisms for Euclidean Facility Location Problems under $L_p$-norm Social Cost

arXiv:2606.08621v1 Announce Type: new Abstract: We study strategyproof mechanisms for eliciting agents' location preferences truthfully in the Euclidean plane $\mathbb R^2$ and locating a facility so as to minimize the $L_p$-norm social cost, defined as the $L_p$-norm of the vector of distances from the facility to the agents' preferred locations, for any $p \ge 1$. While the cases $p=1$ and $p=\infty$ have been well-studied, open questions remain about the optimal approximation ratios...