Optimality and Impossibility in Multidimensional Strategyproof Facility Location
cs.GT
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility.
Abstract
We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects k facility locations based on the reports of n agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): sqrt 2(n 2+1) over n+1 for odd n at least3 and sqrt 2 for even n at least4. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in infinity d, whereas CM has a tight uniform approximation ratio of 2 already in the plane. We then consider two facilities in p spaces with 1<p< infinity and prove two impossibility results for every n>2. In the plane, no deterministic SP mechanism has a finite approximation ratio. In higher dimensions, the same impossibility holds for anonymous deterministic SP mechanisms. Finally, a reduction using distant agents and a limiting argument extends both impossibility results to every k>2 with n>k.
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments