{"id":"10a44cb4-c062-4721-9704-de4863400905","arxiv_id":"2607.20196","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Improved lower bounds for randomized strategyproof facility location in R^d, plus new mechanisms in an output-augmented framework: deterministic sqrt(2) for a line with planar output, and a group-strategyproof 3/2 mechanism when agents lie on a circle.","lead":"This paper proves that any manipulation-proof rule for choosing a shared facility in d-dimensional space must have an approximation ratio of at least 1 + sqrt(d/(2(d+1))) for large agent populations, improving the planar bound from 1.118 to 1.577. It also introduces 'output augmentation'—letting the facility lie outside the agents' domain—and designs deterministic and randomized mechanisms that beat classical bounds in this setting.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Circle mechanism's strategyproofness proof uses an infeasible intermediate profile; Lemma 4.24's cross-boundary deviation argument is invalid, leaving Theorem 4.12 without a complete proof.","rationale":"The reader's weakest assumption identifies the same gap: Lemma 4.24's use of an infeasible intermediate profile invalidates the strategyproofness proof for cross-boundary deviations, and Theorem 4.25 inherits this gap. The lower-bound result (Theorem 3.1) is well supported by the simplex construction, Lemma 3.3's chaining argument, and the asymptotic density argument; I see no significant issue there. The line-augmented deterministic mechanism and its matching lower bound also appear correct. The circle mechanism's approximation ratio is straightforward to verify, but its incentive property is not established by the written proof. This warrants conditional acceptance rather than rejection, because the gap is localized and may be repairable with a direct proof for Lemma 4.24; however, as submitted, the advertised 3/2 group-strategyproof circle mechanism lacks a complete proof. My assessment therefore agrees with the reader's CONDITIONAL verdict, and no verdict change is needed.","tokens_in":32724,"tokens_out":13449,"duration_ms":117004,"concrete_test":"Attempt to realize the intermediate profile [−γ, α] from the truthful profile by a sequence of unilateral deviations: the only agent at α is the deviator, so moving it to −γ leaves no report at α; hence the two-step decomposition in Lemma 4.24 is infeasible. To check whether the underlying inequality is nevertheless true, numerically evaluate the Chord-Midpoint Mechanism on the true profile (B at 0, A at α) versus the deviated profile (A reports −γ, all other reports unchanged) for a fine grid of α∈(0,π), γ∈(0,π−α), comparing E[d(M(x'),A)] with sin(α/2). Any instance with E[d(M(x'),A)] < sin(α/2) would refute Theorem 4.12 directly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's advertised circle result (Theorem 4.12) depends on the Chord-Midpoint Mechanism being group-strategyproof. That proof rests on Theorem 4.16, whose Case 3 (cross-boundary deviations) is Lemma 4.24. Lemma 4.24 decomposes a unilateral deviation by extreme agent A (truthful angle α) to a new arc [−γ, β] into two steps via an intermediate span [−γ, α]. This intermediate profile is not a valid input profile: after A moves to −γ, no agent reports α, so the minimal spanning arc cannot have right endpoint α. Lemmas 4.21 and 4.23, which justify the expansion and shrink steps, apply only to actual profiles; they cannot be chained through a nonexistent profile. The proof therefore does not establish that the deviating agent's expected cost increases. Since Theorem 4.25 (group-strategyproofness) invokes Theorem 4.16 and Lemma 4.24 in several places, the circle mechanism's incentive guarantee is unproven. This gap is specific and addressable, but it is load-bearing: without it, the main upper-bound contribution of the paper lacks a complete proof. The lower bound (Theorem 3.1) and the line-augmented deterministic results are independent and appear sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies strategic facility location under the egalitarian objective and strategyproofness, in both the standard setting I=O=R^d and an output-augmented setting I⊊O. The main claimed contributions are: (i) a lower bound of 1+sqrt(d/(2(d+1))) for any randomized strategyproof mechanism as n→∞, improving the planar bound from 1.118 to about 1.577; (ii) a randomized sqrt(2)-approximate two-agent mechanism in R^d; (iii) a deterministic sqrt(2)-approximate mechanism for line agents with the facility in the plane, with a matching lower bound; and (iv) a randomized 3/2-approximate, group-strategyproof-in-expectation Chord-Midpoint Mechanism for agents on the unit circle with the facility in the plane. The lower bound proof uses a regular-simplex configuration and a cluster-deviation lemma; the line-augmented results use an explicit midpoint-with-height mechanism; the circle mechanism randomizes among the two extreme reports and the chord midpoint with a report-dependent probability λ(α).","tokens_in":33055,"tokens_out":15738,"duration_ms":140771,"significance":"If the main results hold, the lower-bound component is a substantial and clean contribution: the planar bound 1.577 improves the previous 1.118, the d→∞ limit is 1.707, and the proof is parameter-free and internally coherent. The two-agent Orthogonal Sphere Mechanism and the deterministic line-augmented sqrt(2) mechanism with matching lower bound are also convincing and demonstrate that output augmentation is genuinely more powerful. The circle mechanism is inventive, but its proof is currently incomplete because the cross-boundary deviation lemma uses an infeasible intermediate profile. Until Lemma 4.24 is repaired, the advertised 3/2 circle result is not established. The paper contains no fitted constants or circular calibration; all parameter choices are explicit and the lower-bound derivations do not assume the target results.","major_comments":[{"comment":"The proof of Lemma 4.24 decomposes a cross-boundary unilateral deviation by the extreme agent A from the truthful arc [0,α] to the final arc [−γ,β] into two steps through the intermediate span [−γ,α]. This intermediate span is not a feasible reported profile after a unilateral deviation: once A reports −γ, no remaining report is at α, so no actual profile has minimum spanning arc [−γ,α]. Lemmas 4.21 and 4.23 are proved only for transitions between actual profiles and cannot be chained through a nonexistent profile. Therefore the claimed inequality E[d(M(x),x_i)]<E[d(M(x'),x_i)] is not established. Since Theorem 4.16 Case 3 and Theorem 4.25 depend on this lemma, the strategyproofness and group-strategyproofness of the Chord-Midpoint Mechanism—and hence Theorem 4.12—are currently unproven.","section":"§4.2.3, Lemma 4.24"},{"comment":"In the subcase W_y=W, the proof states that any unilateral deviation by a boundary agent that changes the minimum spanning arc increases that agent's expected cost, citing Lemmas 4.21 and 4.23. However, an extreme agent's deviation can also be cross-boundary, which is exactly the case addressed by Lemma 4.24. Thus the group-strategyproofness proof contains a second unproven step: it relies on a lemma whose current proof is invalid, and the citation at this point omits it. The argument can go through only if Lemma 4.24 is repaired and then explicitly invoked here.","section":"§4.2.4, Theorem 4.25, Case 2"}],"minor_comments":[{"comment":"Two occurrences of 'Lemma 12' should be cross-references to Lemma 4.9. The current numbering makes the argument difficult to follow.","section":"§4.2.2, proof of Lemma 4.10"},{"comment":"The statement says 'n≥6 agents', but the construction requires n to be a multiple of 3 (k=n/3 agents per cluster). Please state 'n=3k, k≥2' explicitly.","section":"§3.1, Theorem 3.5"},{"comment":"The displayed lower-bound expression for E[d(M(x'),A)] is missing parentheses or a denominator in the first term as typeset; rewriting it as a single fraction would remove ambiguity.","section":"§4.2.3, proof of Lemma 4.23"},{"comment":"The displayed derivation of MC(M,x) in Case 2 appears garbled: the intermediate line '1 + cos(α/2) / 1 + cos(α/2)' does not match the preceding substitution. Please correct the display to show sin(α/2)·(1+2cos(α/2))/(1+cos(α/2)).","section":"§4.2.2, proof of Lemma 4.15"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern is real and load-bearing: the circle mechanism's strategyproofness and group-strategyproofness depend on Lemma 4.24, whose intermediate profile is infeasible. The lower-bound and line-augmented results appear sound and are valuable. The gap is specific and likely repairable, so I recommend major revision rather than rejection; the paper should not be accepted while the circle mechanism's proof is incomplete."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the lower-bound part of this paper is real. Theorem 3.1's simplex/cluster-deviation argument gives an asymptotic bound of 1 + sqrt(d/2(d+1)), improving the planar bound from 1.118 to roughly 1.577, and the finite-n version in Theorem 3.5 plus the two-agent sqrt(2) mechanism look sound. The output-augmented line result is also clean: the deterministic sqrt(2) mechanism with a matching lower bound is a solid, interesting contribution, and the generalization to R^d x {0} is a natural bonus.\n\nThe circle Chord-Midpoint mechanism has a plausible 3/2 approximation, but the strategyproofness proof is not complete. Lemma 4.24 decomposes a cross-boundary deviation through an intermediate arc [-gamma, alpha]; in that intermediate profile no agent reports alpha, so the arc's right endpoint does not exist. Lemmas 4.21 and 4.23 apply to actual profiles, so they cannot be chained across a nonexistent one. Without Lemma 4.24, Theorem 4.16 is missing its third case, and Theorems 4.25 and 4.12 fall with it. This is specific and addressable, not evidence the claim is false, but it is load-bearing. There is also a smaller issue in Theorem 4.2: the strategyproofness proof for the two extreme agents cites the randomized Theorem 3.11, which does not apply to a deterministic mechanism; a direct calculation likely fixes it.\n\nThe lower-bound work is parameter-free and the citation pattern is fine. Who should read this: anyone working on approximate mechanism design without money, especially lower-bound techniques. It deserves a serious referee, but the referee should require the circle proof to be repaired before publication.","headline":"The simplex lower bound is a genuine advance; the circle mechanism's group-strategyproofness proof has a load-bearing gap, but the paper deserves a serious referee.","tokens_in":33526,"tokens_out":5565,"would_cite":true,"duration_ms":53879,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90B80","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized strategyproof facility-location mechanisms in R^d must have egalitarian approximation ratio at least 1 + sqrt(d/(2(d+1))), roughly 1.577 in the plane.","keywords":["facility location","strategyproofness","randomized mechanisms","egalitarian objective","approximation ratio","output augmentation","Euclidean space","lower bounds"],"falsifier":"Directly compute, for the Chord-Midpoint Mechanism, the expected cost of an extreme agent at angle α before and after a cross-boundary report that moves the opposite extreme to angle −γ (with γ+β < π); if any instance yields a decrease, Theorem 4.16 and hence the 3/2 circle mechanism fail. For the simplex lower bound, a strategyproof-in-expectation mechanism in R^2 with asymptotic ratio below 1 + 1/sqrt(3) — for instance an anonymous mechanism achieving 1.5 for all n — would falsify Theorem 3.1.","tokens_in":32630,"feed_emoji":"📍","tokens_out":5408,"duration_ms":47754,"temperature":0.7,"pith_summary":"The paper establishes a new lower bound on the best possible guarantee of any randomized, strategyproof-in-expectation mechanism for placing a single facility under the egalitarian objective: in d-dimensional Euclidean space the approximation ratio cannot go below 1 + sqrt(d/(2(d+1))), which in the plane is about 1.577 and tends to about 1.707 as dimension grows. It also shows this barrier is driven by large populations, giving a sqrt(2)-approximate randomized mechanism for two agents, and proves finite-n lower bounds that already exceed 3/2 for 15 agents in the plane. In a second direction, the paper introduces output augmentation — allowing the facility to be placed outside the agents' domain — and shows that on a line this extra room lets a simple deterministic mechanism achieve sqrt(2), with a matching lower bound, beating even the classical randomized 3/2 barrier on the line. For agents on a circle with the facility in the plane, it proposes a randomized mechanism with ratio 3/2 that is group-strategyproof in expectation, meaning no coalition can jointly misreport so that every member improves.","feed_headline":"Truthful randomized placement can't beat 1.577 in the plane","feed_subtitle":"New dimension-by-dimension lower bound, plus output room that lets mechanisms beat older ratio limits.","key_machinery":"The lower bound's engine is a regular simplex inscribed in the unit sphere together with a cluster-deviation lemma: since a group of agents sharing one true location cannot improve their expected distance by moving together, the mechanism's output on the deviated profile must stay at least distance 1 from the original vertex; classical circumradius-to-diameter bounds then convert a large-population discretization of the surrounding sphere into the ratio 1 + sqrt(d/(2(d+1))). The upper-bound machinery is the Orthogonal Sphere Mechanism for two agents and the Chord-Midpoint Mechanism for the circle, whose mixing weight lambda(alpha) = cos(alpha/2)/(2(1+cos(alpha/2))) interpolates between the d","core_discovery":"On the paper's own terms, the central discovery is that the egalitarian approximation barrier for strategyproof-in-expectation mechanisms is governed by the geometry of the regular simplex: place agents in equal clusters at the d+1 vertices of a regular simplex, let one cluster deviate to the surrounding sphere, and the deviation together with a cluster-deviation lower bound forces any mechanism to pay at least 1 + sqrt(d/(2(d+1))) times the optimum in the limit of infinitely many agents. Complementing this, the paper claims an output-augmented circle mechanism, the Chord-Midpoint Mechanism, that mixes between the two extreme reported points and the chord midpoint with a probability dependin","pith_inferences":["Going beyond the paper's own claims, if the simplex barrier is tight, an optimal mechanism in R^d would have to look structurally different from centroid-style mechanisms; the finite-n thresholds suggest concrete population sizes where mechanisms would need to change behavior.","The output-augmented line result suggests a general principle: extra output dimensions can substitute for randomness; a natural next test is whether randomized mechanisms can beat sqrt(2) in the same augmented setting.","If the circle mechanism's cross-boundary step is completed, chord-midpoint-style randomization may transfer to other compact input domains, such as spherical caps or ellipses, suggesting a broader design recipe for output-augmented facility location."],"forward_implications":["In the plane, no randomized strategyproof-in-expectation mechanism can achieve an asymptotic egalitarian ratio below 1 + 1/sqrt(3) ≈ 1.577, narrowing the gap to the known 2 − 1/n upper bound.","For n ≥ 15 agents in R^2, the lower bound already exceeds 3/2, the best possible randomized ratio on the line.","For two agents in R^d, a randomized mechanism based on an orthogonal sphere achieves sqrt(2), separating randomized from deterministic and beating the two-agent line limit of 1.5.","Output augmentation replaces randomness: on a line with the facility in the plane, a deterministic strategyproof mechanism achieves sqrt(2), matched by a lower bound for any deterministic mechanism.","On the circle with the facility in the plane, the Chord-Midpoint Mechanism is group-strategyproof in expectation with ratio 3/2, while any deterministic unanimous group-strategyproof mechanism has ratio at least 2."],"fun_headline_variants":["Simplex geometry forces 1.577 floor for truthful placement","Give the facility more room: deterministic sqrt(2) replaces randomness","Circle agents, plane facility: group-truthful 3/2 mechanism","Randomness can't beat 1.577; letting the facility wander can"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The circle mechanism's proof that cross-boundary misreports are unprofitable assumes an intermediate bracket [-gamma, alpha] that no single deviation can actually realize, so the advertised 3/2 group-strategyproof circle mechanism stands or falls on whether that expansion-then-shrink step can be replaced by a direct argument.","fun_headline_variants_meta":{"raw":{"variants":["Simplex geometry forces 1.577 floor for truthful placement","Give the facility more room: deterministic sqrt(2) replaces randomness","Circle agents, plane facility: group-truthful 3/2 mechanism","Randomness can't beat 1.577; letting the facility wander can"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000879,"raw_usage":{"total_tokens":3646,"prompt_tokens":759,"completion_tokens":2887,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":2809}},"tokens_in":503,"tokens_out":2887,"duration_ms":20562,"temperature":1.0,"reasoning_tokens":2809,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T10:31:18.956126+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Directly compute, for the Chord-Midpoint Mechanism, the expected cost of an extreme agent at angle α before and after a cross-boundary report that moves the opposite extreme to angle −γ (with γ+β < π); if any instance yields a decrease, Theorem 4.16 and hence the 3/2 circle mechanism fail. For the simplex lower bound, a strategyproof-in-expectation mechanism in R^2 with asymptotic ratio below 1 + 1/sqrt(3) — for instance an anonymous mechanism achieving 1.5 for all n — would falsify Theorem 3.1.","supporting_citations":[],"review_version":1}