{"id":"467bf465-e732-486b-984b-83a69546db9e","arxiv_id":"2606.12187","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Coordinate-wise median is a tight 2^{1-1/max(p,q)}-approximation for p-norm facility location in ℓ_q(R^2) and at most 3-approx in any dimension for all p,q≥1.","lead":"The coordinate-wise median mechanism achieves a tight 2^{1-1/max(p,q)} approximation for any p-norm social cost in two-dimensional ℓ_q spaces and never exceeds 3 in higher dimensions. This settles a 2023 conjecture and shows the mechanism remains robust across social objectives without dimension dependence.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the only non-elementary step (the pointwise lower bound g≥G) and correctly notes that its tightness is not independently certified. That step is nevertheless only required for an upper bound; the algebraic and calculus arguments that establish it appear free of gaps, and the resulting constant 3 is already known to be essentially tight for the utilitarian case. The two-dimensional analysis is fully rigorous and settles the published conjecture with matching lower bounds. No circularity, free parameters, or unstated assumptions affect the strongest claim. Consequently the ACCEPT verdict stands.","tokens_in":35213,"tokens_out":510,"duration_ms":33574,"concrete_test":"Fix any concrete triple (p,q,λ) with p/q∉{1,2} (e.g., p=3,q=2,λ=1/(1+2^{1/3})), sample 10^4 random points x whose signatures satisfy the median constraint, evaluate both g(x) and G(X) numerically, and verify that the inequality of Lemma 6 never fails by more than machine precision; if it holds, the relaxation step is confirmed for that regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims hold under the paper's own arguments. For d=2 the pairing of opposite orthants (constraints (2b)–(2c)) plus the elementary inequalities of Lemma 1 produce a non-negative objective for exactly the claimed λ, and the matching lower-bound constructions of Theorem 3 close the gap for every regime of p,q. For d≥3 the program relaxation of Section 5.1.2 is only an upper-bound device: once g(xi)≥G(Xi) is granted by the case analysis of Lemma 6, non-negativity of the univariate program immediately yields the stated UB(p,q)≤3. The lengthy calculus (second-derivative sign changes, boundary-exclusion arguments for the univariate minimizers, choice of auxiliary γ) is tedious but contains no hidden assumption that fails for any p/q≥1; the special cases p=q and p=2q recover the tight 1-D ratio, giving an independent sanity check. The abstract’s parenthetical claim for general monotone symmetric norms is not needed for the theorems that constitute the strongest claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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).","tokens_in":35460,"tokens_out":699,"duration_ms":7559,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and the central claims are fully proved. The only presentational mismatch is the abstract’s broader claim for monotone symmetric norms, which is easily fixed. I see no reason to delay acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","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.\n\nThe 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.\n\nFor 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.\n\nNo 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.","headline":"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.","tokens_in":36068,"tokens_out":495,"would_cite":true,"duration_ms":13090,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["facility location","strategyproof mechanisms","coordinate-wise median","p-norm social cost","approximation ratio","ℓ_q spaces","mechanism design"],"falsifier":"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).","tokens_in":36109,"feed_emoji":"📍","tokens_out":624,"duration_ms":6383,"temperature":0.7,"pith_summary":"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.","feed_headline":"Median mechanism stays within factor 3 for any p-norm cost","feed_subtitle":"Tight plane bound settles a conjecture and holds for every ℓ_q distance","key_machinery":"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.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["CM mechanism 3-approximates any p-norm cost in every ℓq space","Tight 2^{1-1/max(p,q)} plane ratio for coordinate-wise median","Coordinate-wise median is robust to all monotone symmetric norms","CM resolves plane conjecture for every ℓq distance and p-norm","Refined p/q bounds for multi-dimensional strategyproof facility location"],"cache_read_input_tokens":20864,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["CM mechanism 3-approximates any p-norm cost in every ℓq space","Tight 2^{1-1/max(p,q)} plane ratio for coordinate-wise median","Coordinate-wise median is robust to all monotone symmetric norms","CM resolves plane conjecture for every ℓq distance and p-norm","Refined p/q bounds for multi-dimensional strategyproof facility location"]},"model":"grok-4.5","effort":"low","cost_usd":0.00815,"raw_usage":{"total_tokens":2015,"prompt_tokens":889,"num_sources_used":0,"completion_tokens":105,"cost_in_usd_ticks":81500000,"prompt_tokens_details":{"text_tokens":889,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1021,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":889,"tokens_out":105,"duration_ms":8672,"temperature":1.0,"reasoning_tokens":1021,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T07:38:01.439434+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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).","supporting_citations":[],"review_version":2}