REVIEW 2 minor 29 references
The coordinate-wise median mechanism achieves a tight approximation ratio of exactly 2^{1-1/p} for p >= 2 and sqrt(2) for 1 <= p <= 2 under L_p-norm social cost in the Euclidean plane.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.3
2026-06-30 11:17 UTC pith:JQJP22Y5
load-bearing objection Confirms the Goel-Hann-Caruthers conjecture with a tight bound on CM and gives two randomized mechanisms that beat the deterministic ratio for some p.
Strategyproof Mechanisms for Euclidean Facility Location Problems under L_p-norm Social Cost
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The coordinate-wise median mechanism achieves a tight approximation ratio of exactly 2^{1-1/p} for p >= 2 and sqrt(2) for 1 <= p <= 2; it is optimal among all deterministic anonymous strategyproof mechanisms for all p >= 1. The uniformly rotated coordinate-wise median improves this bound strictly for 1 <= p < 2 while the centroid random dictatorship mixture improves over both for every finite p greater than or equal to roughly 1.6.
What carries the argument
The coordinate-wise median mechanism, which independently selects the median coordinate in each dimension of the agents' reported locations.
Load-bearing premise
The analysis assumes social cost is the L_p norm of Euclidean distances in the plane and that optimality claims apply only to deterministic anonymous strategyproof mechanisms.
What would settle it
A deterministic anonymous strategyproof mechanism whose worst-case L_p social cost ratio is strictly below 2^{1-1/p} for some p >= 2 on some set of agent locations in the plane would falsify the optimality result.
If this is right
- No deterministic anonymous strategyproof mechanism can beat the 2^{1-1/p} ratio for p >= 2.
- No deterministic anonymous strategyproof mechanism can beat the sqrt(2) ratio for 1 <= p <= 2.
- The uniformly rotated coordinate-wise median yields a strictly better ratio than sqrt(2) when 1 <= p < 2.
- The centroid random dictatorship mixture yields a strictly better ratio than both deterministic and uniformly rotated mechanisms for p greater than or equal to about 1.6.
Where Pith is reading between the lines
- Randomization appears most useful when the norm parameter p is small, suggesting a possible phase transition around p = 2.
- Extending the same median-based constructions to three or more dimensions may preserve similar ratios under the same anonymity and strategyproofness constraints.
- If the anonymity requirement is dropped, other deterministic mechanisms might close the gap to the randomized bounds for intermediate p values.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies strategyproof mechanisms for locating a single facility in the Euclidean plane R^2 to minimize the L_p-norm social cost (p ≥ 1). It resolves the Goel-Hann-Caruthers conjecture by proving that the coordinate-wise median (CM) mechanism achieves a tight approximation ratio of exactly 2^{1-1/p} for p ≥ 2 and √2 for 1 ≤ p ≤ 2. It further shows this is optimal among all deterministic anonymous strategyproof mechanisms. Two randomized mechanisms are analyzed: the uniformly rotated coordinate-wise median (URCM) improves the ratio strictly for 1 ≤ p < 2 (but not for p ≥ 2), and the centroid random dictatorship improves over both CM and URCM for every finite p ≳ 1.6.
Significance. If the proofs hold, the work provides a complete characterization of the best deterministic anonymous strategyproof mechanisms across all p ≥ 1 and identifies improved randomized alternatives for ranges of p. This resolves an open conjecture and advances the literature on approximation ratios for strategyproof facility location under general L_p costs, with the mathematical proofs constituting the core contribution.
minor comments (2)
- [Abstract] Abstract: the phrase 'for every finite p ≳ 1.6' is informal; if an exact threshold was derived in the analysis of the centroid random dictatorship, state it explicitly (e.g., 'for all p > 1.62').
- [Introduction] The abstract states that proofs exist for the tight bounds and randomized improvements, but the main text should include a clear roadmap (e.g., 'Theorem 3.1 proves the lower bound via ...') to aid readers in locating the key steps.
Simulated Author's Rebuttal
We thank the referee for the positive recommendation to accept the manuscript. The report accurately summarizes our contributions and confirms the resolution of the Goel-Hann-Caruthers conjecture along with the analysis of randomized mechanisms.
Circularity Check
No significant circularity
full rationale
The paper's central results consist of mathematical proofs establishing tight approximation ratios for the coordinate-wise median mechanism under L_p social cost, confirming a conjecture from Goel and Hann-Caruthers (distinct authors). The optimality among deterministic anonymous strategyproof mechanisms is explicitly attributed to prior independent work by those authors, not a self-citation chain or internal definition. No equations reduce by construction to fitted parameters, renamed empirical patterns, or ansatzes smuggled via self-reference; the derivation chain relies on standard mechanism design analysis against external optimal facility locations and is self-contained against those benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math L_p norms and Euclidean distances satisfy standard metric properties used in defining social cost and approximation ratios.
read the original 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 achievable by strategyproof mechanisms for general $p$. Our first result resolves an open question of Goel and Hann-Caruthers [Soc. Choice Welf. 2023]. They showed that the coordinate-wise median (CM) mechanism achieves an approximation ratio lying between \(2^{1-\frac{1}{p}}\) and \(2^{\frac{3}{2}-\frac{2}{p}}\) for $p\ge 2$, and they conjectured that it is exactly \(2^{1-\frac{1}{p}}\). We confirm this conjecture, and we further show that CM has a tight $\sqrt 2$-approximation for $1\le p\le 2$. Since it is previously known that the CM mechanism has the optimal approximation ratio among all deterministic anonymous strategyproof mechanisms for all $p\ge 1$, we complete the picture of deterministic mechanisms. Our second and third results demonstrate that two randomized mechanisms can yield better approximation ratios. In particular, we first consider the uniformly rotated coordinate-wise median (URCM) mechanism, and prove that, for \(1\le p<2\), its approximation ratio strictly improves over the deterministic bound \(\sqrt{2}\), while no such improvement is possible for $p\ge 2$. We then study the centroid random dictatorship mechanism that returns the average location (i.e., centroid) and the random dictatorship each with half probability, and show that its approximation ratio strictly improves over CM and URCM for every finite \(p\gtrsim 1.6\).
Figures
Reference graph
Works this paper leans on
-
[1]
Learning- augmented mechanism design: leveraging predictions for facility location
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: leveraging predictions for facility location. InProceedings of the 23rd ACM Conference on Economics and Computation, pages 497–528, 2022
work page 2022
-
[2]
Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof ap- proximation of the minimax on networks.Mathematics of Operations Research, 35(3):513– 526, 2010
work page 2010
-
[3]
Facility Location Mechanism Design: Breaking The Deterministic Barrier
Zohar Barak. Facility location mechanism design–breaking the deterministic barrier.arXiv preprint arXiv:2605.24750, 2026 (To appear in EC 26)
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[4]
Mechanism design for facility location problems: a survey
Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: a survey. InProceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), pages 4356–4365, 2021
work page 2021
-
[5]
Hau Chan, Jianan Lin, and Chenhao Wang. Obnoxious facility location problems: Strate- gyproof mechanisms optimizingl p-aggregated utilities and costs. InProceedings of the 2026 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 496–504, 2026
work page 2026
-
[6]
Hau Chan, Jianan Lin, and Chenhao Wang. Strategyproof facility location with prediction: minimizing the maximum cost.Autonomous Agents and Multi-Agent Systems, 40(1):22, 2026
work page 2026
-
[7]
Mechanism Design without Money via Stable Matching
Ning Chen, Nick Gravin, and Pinyan Lu. Mechanism design without money via stable matching.arXiv preprint arXiv:1104.2872, 2011
work page internal anchor Pith review Pith/arXiv arXiv 2011
-
[8]
Yukun Cheng, Wei Yu, and Guochuan Zhang. Strategy-proof approximation mechanisms for an obnoxious facility game on networks.Theoretical Computer Science, 497:154–163, 2013
work page 2013
-
[9]
Salman Fadaei and Martin Bichler. Generalized assignment problem: Truthful mechanism design without money.Operations Research Letters, 45(1):72–76, 2017. 35
work page 2017
-
[10]
Jiazhu Fang, Qizhi Fang, Wenjing Liu, and Minming Li. Heterogeneous facility location games with fractional preferences and limited resources.Autonomous Agents and Multi- Agent Systems, 39(2):41, 2025
work page 2025
-
[11]
Itai Feigenbaum, Jay Sethuraman, and Chun Ye. Approximately optimal mechanisms for strategyproof facility location: minimizing lp norm of costs.Mathematics of Operations Research, 42(2):434–447, 2017
work page 2017
-
[12]
Strategyproof facility location and the least squares ob- jective
Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares ob- jective. InProceedings of the 14th ACM Conference on Electronic Commerce (EC), pages 873–890, 2013
work page 2013
-
[13]
Truthful approximations to range voting
Aris Filos-Ratsikas and Peter Bro Miltersen. Truthful approximations to range voting. In International Conference on Web and Internet Economics, pages 175–188. Springer, 2014
work page 2014
-
[14]
Facility location games with fractional preferences
Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. Facility location games with fractional preferences. InProceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
work page 2018
-
[15]
Strategyproof facility location for concave cost functions
Dimitris Fotakis and Christos Tzamos. Strategyproof facility location for concave cost functions. InProceedings of the 14th ACM Conference on Electronic Commerce (EC), pages 435–452, 2013
work page 2013
-
[16]
Dimitris Fotakis and Christos Tzamos. Winner-imposing strategyproof mechanisms for multiple facility location games.Theoretical Computer Science, 472:90–103, 2013
work page 2013
-
[17]
Sumit Goel and Wade Hann-Caruthers. Optimality of the coordinate-wise median mech- anism for strategyproof facility location in two dimensions.Social Choice and Welfare, 61(1):11–34, 2023
work page 2023
-
[18]
Approximation guarantees of median mechanism inR d
Nikolai Gravin and Jianhao Jia. Approximation guarantees of median mechanism inR d. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 495–506, 2025
work page 2025
-
[19]
Strategy-proof allocation of multiple items between two agents without payments or priors
Mingyu Guo and Vincent Conitzer. Strategy-proof allocation of multiple items between two agents without payments or priors. InProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 881–888, 2010
work page 2010
- [20]
-
[21]
Strategic Facility Location with $p$-Norm Social Costs
Jabari Hastings. Strategic facility location withp-norm social costs.arXiv preprint arXiv:2606.12187, 2026
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[22]
Constrained truthful obnoxious two-facility location with optional preferences: P
Panagiotis Kanellopoulos and Alexandros A Voudouris. Constrained truthful obnoxious two-facility location with optional preferences: P. kanellopoulos, aa voudouris.Algorithmica, 88(3):42, 2026
work page 2026
-
[23]
Scheduling without payments.Theory of Computing Systems, 54(3):375– 387, 2014
Elias Koutsoupias. Scheduling without payments.Theory of Computing Systems, 54(3):375– 387, 2014. 36
work page 2014
-
[24]
Jianan Lin. Nearly complete characterization of 2-agent deterministic strategyproof mech- anisms for single facility location inl p space. InInternational Conference on Combinatorial Optimization and Applications, pages 411–425. Springer, 2020
work page 2020
-
[25]
Strategyproof facility location for three agents on a circle
Reshef Meir. Strategyproof facility location for three agents on a circle. InAlgorithmic Game Theory - 12th International Symposium (SAGT), volume 11801 ofLecture Notes in Computer Science, pages 18–33. Springer, 2019
work page 2019
-
[26]
Approximate mechanism design without money
Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC), 1(4):1–26, 2013
work page 2013
-
[27]
Characterization of group-strategyproof mechanisms for facility location in strictly convex space
Pingzhong Tang, Dingli Yu, and Shengyu Zhao. Characterization of group-strategyproof mechanisms for facility location in strictly convex space. InProceedings of the 21st ACM Conference on Economics and Computation (EC), pages 133–157, 2020
work page 2020
-
[28]
Equitable mechanism design for facility location
Toby Walsh. Equitable mechanism design for facility location. InProceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 275–283, 2025
work page 2025
-
[29]
Strategy-proof mechanism for obnoxious facility location on a line
Deshi Ye, Lili Mei, and Yong Zhang. Strategy-proof mechanism for obnoxious facility location on a line. InInternational Computing and Combinatorics Conference, pages 45–
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.