Strategic Facility Location with $p$-Norm Social Costs

Jabari Hastings

Strategic Facility Location with $p$-Norm Social Costs

T0 review · 0 major / 4 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The coordinate-wise median mechanism never exceeds approximation ratio 3 for any p-norm social cost in any dimension, and is exactly 2^{1-1/max(p,q)} in the plane.

desk verdict Tight plane ratios for every p,q plus a clean dimension-independent 3 for all p-norms; the math holds and the conjecture is settled. read the letter →

arxiv 2606.12187 v2 pith:2BAJ7RAW submitted 2026-06-10 cs.GT

Jabari Hastings This is my paper · ORCID

classification cs.GT

keywords facilitylocationstrategyproofmechanismscoordinate-wisemedianp-normsocialcostapproximationratioℓ_qspacesmechanismdesign

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how well the classic coordinate-wise median (CM) mechanism locates a facility when agents can lie about their positions and the social cost is an arbitrary p-norm of the individual distances measured in an ℓ_q space. In the plane the paper proves that CM is a tight 2^{1-1/max(p,q)}-approximation for every p and q; this settles a conjecture for Euclidean distance and extends the guarantee to every ℓ_q plane. In every higher dimension the same mechanism never exceeds approximation ratio 3, no matter how large the dimension or how the two norms p and q are related. The results show that a single, simple, strategy-proof rule already gives constant-factor guarantees for an entire family of fairness-sensitive objectives simultaneously.

What carries the argument

A mathematical program that encodes the median constraints after translation and normalization; in two dimensions the program is solved by pairing agents from opposite orthants, while in higher dimensions a univariate relaxation of each agent's contribution is minimized.

What would settle it

Exhibit any finite set of points in ℓ_q(R^d) for which the ratio of CM social cost to optimal p-norm social cost strictly exceeds the claimed upper bound UB(p,q) (or 3).

Watch

Extended reading notes

Core claim

For every p,q ≥ 1 the coordinate-wise median mechanism has approximation ratio at most 2^{1-1/max(p,q)} in ℓ_q(R^{2}) (and the bound is tight), while in any dimension d the same mechanism has approximation ratio at most 3 for every p-norm social cost; more refined upper bounds that depend only on the ratio p/q are also obtained.

Load-bearing premise

The higher-dimensional bounds rely on a relaxation that replaces each agent's true cost contribution by a simpler univariate function of a single aggregated coordinate sum; if that relaxation is loose, the claimed constants may be larger than necessary.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper settles the Goel–Hann-Caruthers conjecture for the Euclidean plane and, more usefully, gives the exact approximation ratio of coordinate-wise median for every p-norm social cost and every ℓ_q distance in R^{2}: exactly 2^{1-1/max(p,q)}. It also shows that the same mechanism never exceeds 3 in any dimension for any p, generalizing the recent Gravin–Jia STOC result from utilitarian cost to all p-norms. Those are the two things worth knowing.

The d=2 argument is the cleanest part. Once the median constraints force equal mass in opposite orthants, pairing points and applying Jensen/Minkowski/power-mean (Lemma 1) immediately produces non-negativity of the objective for the claimed λ. Matching lower bounds close the gap in both regimes of p versus q. The concurrent Chan et al. work only covers the Euclidean special case, so the general-q plane result and the higher-d extension remain original.

For d≥3 the analysis switches to a univariate relaxation of the natural program. The justification (Lemma 6) is a long case analysis on the sign pattern and the ratio p/q; it is tedious but self-contained and recovers the known tight 1-D ratios when p=q or p=2q, which is a useful sanity check. The resulting UB(p,q) is never worse than 3 and is sometimes tighter. The abstract’s parenthetical claim for general monotone symmetric norms is stronger than the theorems actually prove, but that is cosmetic; the p-norm statements stand on their own.

No free parameters, no circularity, complete proofs, concurrent work properly disclosed. Soft spots are minor: the higher-d bounds are not claimed to be tight, and the relaxation step is only an upper-bound device. Anyone working on strategyproof facility location or multi-dimensional mechanism design will want the exact plane numbers and the uniform 3. I would send it to referees without hesitation.

Referee Report

0 major / 4 minor

Summary. The paper studies the approximation ratio of the coordinate-wise median (CM) mechanism for strategic facility location in ℓ_q(ℝ^d) under p-norm social costs. For d=2 it proves that CM is a tight 2^{1-1/max(p,q)}-approximation for every p,q≥1 (Theorems 1 and 3), resolving the Goel–Hann-Caruthers conjecture for the Euclidean plane and extending it to all ℓ_q norms. For d≥3 it derives upper bounds UB(p,q) that depend on the ratio p/q and never exceed 3 (Theorem 2), recovering the classical one-dimensional ratio when p=q or p=2q and generalizing the Gravin–Jia bound for the utilitarian case. The analysis proceeds by reducing the ratio to a mathematical program that encodes the median constraints, then either pairing opposite orthants (d=2) or relaxing to a univariate program whose non-negativity is established by exhaustive case analysis on p/q (d≥3).

Significance. The d=2 result is a clean, complete resolution of a published conjecture and supplies matching lower bounds for every regime of p and q; the higher-dimensional constant-3 guarantee removes the long-standing suspicion of an Ω(√d) blow-up and places the CM mechanism on a firm footing for arbitrary p-norm objectives. The proofs are self-contained, rely only on classical inequalities and the known strategyproofness of CM, and recover known tight ratios as special cases, giving an independent sanity check. The work therefore constitutes a substantial advance in the approximation theory of strategyproof facility location.

minor comments (4)

The abstract asserts a 3-approximation for every monotone symmetric norm, yet the body only proves the claim for p-norms (Theorem 2). Either supply the short argument that extends the relaxation to general monotone symmetric norms or restrict the abstract statement to p-norms.
In Section 3 the signature map σ allows sign(0) to be chosen freely; a one-sentence clarification that the subsequent pairing and aggregation arguments remain valid under any consistent choice would remove a minor ambiguity.
The concurrent independent resolution of the Euclidean conjecture by Chan et al. (2026) is mentioned only briefly; a short comparison of the two proof techniques (pairing versus other methods) would help the reader place the contribution.
Several lengthy calculus arguments (second-derivative sign changes of G, boundary-exclusion lemmas for the univariate minimizers) are deferred to the appendix; a one-line roadmap at the start of each case in Section 5 would improve readability without lengthening the main text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: pure self-contained analysis of a mathematical program via classical inequalities and calculus, with no fitted parameters or self-referential reductions.

full rationale

The derivation chain is entirely internal and non-circular. For d=2 the median orthant-balance constraints (2b)–(2c) permit pairing of opposite points; Lemma 1 then applies Jensen/Minkowski/Power-Mean inequalities to obtain a uniform lower bound on g(a)+g(b), yielding non-negativity of the objective precisely when λ equals the claimed 2^{1/max(p,q)-1} (Corollary 2). Matching lower-bound constructions (Theorem 3) close the gap independently. For d≥3 the same program is relaxed by replacing each g(x_i) with a univariate G(X_i) (Lemma 6, proved by exhaustive case analysis on signs and critical-point conditions for the local minimizer); non-negativity of the resulting univariate program is established by second-derivative sign changes (Lemma 8), restriction of optimal supports (Claim 3), and explicit solution of the resulting one-dimensional critical-point equations, producing the stated UB(p,q)≤3. All steps rely only on elementary analysis and the already-known strategyproofness of coordinate-wise median; no quantity is defined in terms of the target ratio, no parameter is fitted to data and then re-used as a prediction, and the few external citations (Gravin–Jia program template, classical inequalities) are used as black-box tools rather than load-bearing uniqueness claims. The special cases p=q and p=2q recover the known one-dimensional ratio as an independent sanity check. Consequently the strongest claims stand free of circular reduction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The paper is a pure mathematical analysis of an existing mechanism. It relies only on standard real-analysis inequalities, the classical definition of strategyproofness, and the already-established fact that coordinate-wise median is strategyproof and anonymous. No free parameters are fitted; the auxiliary functions G and C* are derived, not postulated. The sole modeling choices are the usual ones of the facility-location literature (ℓ_q distances, p-norm aggregation, deterministic anonymous mechanisms).

assumptions (3)

domain assumption Coordinate-wise median is strategyproof and anonymous for any ℓ_q(R^d).
Invoked throughout; classical result used without re-proof (Section 2).
standard math Jensen’s inequality, Minkowski’s inequality, and the power-mean inequality hold for the relevant exponents.
Used repeatedly in Lemma 1 and the higher-d case analysis.
domain assumption When n is even the origin is a coordinate-wise median if and only if each orthant signature balances (signature-sum zero).
Encodes the median constraint in the mathematical program (Section 3).

invented entities (1)

The univariate relaxation G(Z) of the per-agent cost g
purpose: Converts the multi-dimensional program into a tractable one-dimensional optimization over aggregated coordinates X_i.
Defined in equation (7); its lower-bounding property is proved in Lemma 6 by case analysis on p/q. No independent existence claim is made; it is an analytic tool.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Strategic Facility Location with $p$-Norm Social Costs." pith.science (2026). https://pith.science/paper/2BAJ7RAW

@misc{pith2026260612187,
  author       = {Pith},
  title        = {Pith review of: Strategic Facility Location with $p$-Norm Social Costs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2BAJ7RAW}},
  note         = {Machine review of arXiv:2606.12187}
}

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 \geq 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\geq 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.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Strategyproof Mechanisms for Euclidean Facility Location Problems under $L_p$-norm Social Cost
cs.GT 2026-06 unverdicted novelty 7.0 of 10

Establishes tight approximation ratios for coordinate-wise median and strict improvements via randomized mechanisms for L_p social cost in the Euclidean plane.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

median voters

1 38 Border, K. C. and Jordan, J. S. (1983). Straightforward elections, unanimity and phantom voters. The Review of Economic Studies, 50(1):153–170. 1.2, 6.1 Chakrabarty, D. and Swamy, C. (2019). Approximation algorithms for minimum norm and or- dered optimization problems. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, page...

arXiv 1983
[2]

International Foundation for Autonomous Agents and Multiagent Systems. 1.2 41

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.

[1] [1]

median voters

1 38 Border, K. C. and Jordan, J. S. (1983). Straightforward elections, unanimity and phantom voters. The Review of Economic Studies, 50(1):153–170. 1.2, 6.1 Chakrabarty, D. and Swamy, C. (2019). Approximation algorithms for minimum norm and or- dered optimization problems. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, page...

arXiv 1983

[2] [2]

International Foundation for Autonomous Agents and Multiagent Systems. 1.2 41