{"id":"4748aa54-6d8d-4db6-85c8-3f280691c80f","arxiv_id":"2608.09061","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A randomized strategyproof two-facility mechanism on Ptolemaic metric spaces achieves approximation ratio 11/3, and the best possible ratio is at least (1+√2)/2.","lead":"The paper designs a randomized, manipulation-proof rule for placing two public facilities that achieves an approximation ratio of 11/3, improving on the 4-approximation bound that had stood since 2010. It also raises the lower bound on what any manipulation-proof rule can guarantee from about 1.045 to about 1.207.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 11/3 ratio rests on the unverified scalar inequality (23) in Section D.3; if that inequality fails, the mixture bound collapses.","rationale":"The paper's central claim is that M_{2/3} is strategyproof on Ptolemaic spaces with approximation ratio 11/3. I read the truthfulness proof carefully: the reduction to the Ptolemy inequality in Appendix A is intricate but internally consistent, and the K2,3 counterexample in Appendix B correctly shows the domain restriction is necessary. The lower bound construction in Section 4 is also clean and the algebra checks out. The dispersion framework is elegant, and the complementary worst-case behavior of the two mechanisms is plausible. However, the approximation ratio 11/3 is only as strong as Theorem 3.4, and that theorem's proof is the least secure part of the manuscript. The main text gives only a proof sketch; the full proof in Section D reduces the core estimate to inequality (23), a dense scalar certificate that is justified by casework and 'it suffices' steps rather than a complete, machine-checkable derivation. Because the paper reports no formal verification and the authors note that ChatGPT assisted with some proof steps, an independent computational check of (23) is the most direct way to settle whether the bound is real. The reader's weakest_assumption focused on the Ptolemy condition, but that condition is explicitly stated and its necessity is demonstrated; the scalar certificate is not demonstrated with equal rigor. Thus I partially agree with the reader: the CONDITIONAL verdict is appropriate, but the most load-bearing concern is the unverified D.3 inequality, not the Ptolemaic domain. My verdict remains UNCHANGED because the concern does not establish a known flaw; it identifies a verification gap that should be closed before the 11/3 claim is accepted at face value.","tokens_in":19237,"tokens_out":19256,"duration_ms":176930,"concrete_test":"Use an SMT solver (e.g., Z3) or a high-precision interval arithmetic package to verify inequality (23) over its full domain: n1 >= n2 >= 1, r >= 0, 0 <= z <= r, s = min(z,1), m = max(r, n1*z - r). If a counterexample is found, Theorem 3.4 is false and the 11/3 bound collapses. If the solver certifies the inequality, or an independent symbolic re-derivation of eq. (23) from eqs. (21) and (22) is produced without invoking the 'it suffices' shortcuts, the concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central upper bound of Theorem 3.5 depends on Theorem 3.4, which claims the Proportional mechanism satisfies SC(P,x) <= (4 - h(x)/2) OPT(x). The proof is only sketched in the main text and completed in Appendix D. The key step is the aggregate slack estimate eq. (4), which is derived by summing the scalar inequality (23) over all agents in cluster L1. Inequality (23) is stated in Section D.3 and then justified through a case split with several 'it suffices' reductions and assertions like 'visibly nonnegative' and 'the minimum occurs at pi = b - r'. No machine-checked certificate or direct algebraic derivation is provided. If (23) fails for some parameters (n1, n2, r, z), then eq. (4) fails, the slack that produces the 4 - h/2 bound disappears, and the mixture M_{2/3} is only known to inherit the factor-4 bounds of its two components. Since both Global Pair and Proportional separately have ratio exactly 4, the entire improvement below 4 rests on this unverified scalar certificate. This is more load-bearing than the Ptolemy-domain assumption, which is clearly stated and supported by the K2,3 counterexample in Appendix B. A secondary, less severe issue is that Theorem 3.5 claims the approximation ratio is 'exactly 11/3', but its own proof shows the ratio is approached only in the limit along the family x_m; under the paper's definition requiring equality at a finite profile, this is not shown. The D.3 inequality is the primary concern because an error there would invalidate the main result, not just weaken its wording.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies randomized strategyproof mechanisms for the two-facility location problem in metric spaces, with the goal of improving the long-standing 4-approximation upper bound and the 1.045 lower bound. It introduces a new Global Pair mechanism, which selects an unordered pair of agents with probability proportional to their mutual distance, and proves that this mechanism is strategyproof on Ptolemaic metric spaces. The paper then defines a dispersion parameter h(x) and proves that the Global Pair mechanism has approximation ratio at most 3+h(x) while the Proportional mechanism has ratio at most 4−h(x)/2. Mixing the two mechanisms with probabilities 2/3 and 1/3 is claimed to yield a strategyproof mechanism with approximation ratio exactly 11/3 on every Ptolemaic metric space. The paper also constructs a two-profile lower bound of (1+sqrt(2))/2 ≈ 1.207 for any randomized strategyproof mechanism. The main technical work is in the appendices: a detailed proof of truthfulness using the Ptolemy inequality, a metric triple lemma for the Global Pair analysis, a slack-based proof for the Proportional mechanism, and a lower-bound construction on the line.","tokens_in":19547,"tokens_out":19513,"duration_ms":184154,"significance":"If the main results are correct, this is the first strategyproof two-facility mechanism with worst-case ratio below 4, closing a gap that has been open since Lu, Sun, Wang, and Zhu (EC 2010). The dispersion-based complementarity argument is a genuinely new idea, and the block-amplification lower-bound construction is elegant and appears sound. The paper also provides a counterexample showing that the Ptolemaic assumption cannot be dropped, which strengthens the credibility of the truthfulness result. However, the central upper-bound proof rests on a dense scalar inequality in Section D.3 that is not fully verified in the text; until that certificate is supplied or machine-checked, the 11/3 result is conditional. The lower-bound part and the structure of the approximation analysis are otherwise convincing.","major_comments":[{"comment":"The entire improvement below ratio 4 depends on the scalar inequality (23), which is needed to establish the aggregate slack estimates in Eq. (4) and hence Theorem 3.4. The proof of (23) is a case split that contains several unexpanded assertions: for example, the line 'whose bracket is at least 2n2(1+z)' after clearing denominators, and the subsequent conclusion that the whole expression is nonnegative, are not derived. A referee cannot verify this step without substantial independent computation. Since a single failure of (23) would collapse the claimed slack and reduce the mixture bound back to 4, I ask that the authors provide a complete algebraic derivation of (23), or a machine-checkable certificate, before the result can be accepted.","section":"Section D.3, Eq. (23)"},{"comment":"In the proof of Theorem 3.1, after proving that it suffices to establish Eq. (14), the authors assert that under the constraints π≥b−r, θ≥c−r, π+θ≥b+c and the triangle upper bounds, 'the minimum occurs at π=b−r and θ=c+r'. This minimization claim is load-bearing for the truthfulness of the Global Pair mechanism and therefore for the strategyproofness of the mixture M_{2/3}. The claim is stated without proof, and the subsequent expression 'L−K(b+c)≥r(c−b)(a+b−r)+a²(b+c)≥0' is not derived from it. Please expand this argument into a complete verification.","section":"Appendix A, Case 3 of the truthfulness proof"},{"comment":"Theorem 3.5 claims that M_{2/3} has approximation ratio 'exactly 11/3', but the proof only shows that the ratio approaches 11/3 along the family x_m, and the text explicitly says 'the supremum is approached along the family and need not be attained at a finite profile'. This conflicts with the definition of approximation ratio given in Section 2, which requires 'there exists a profile x such that the ≤ holds with equality'. As written, the theorem overstates what is proved. The standard fix is to define the approximation ratio as a supremum, or to prove equality at a finite profile; otherwise Theorem 3.5 should be restated as a supremum bound.","section":"Theorem 3.5 vs. Section 2 definition"}],"minor_comments":[{"comment":"The sentence 'The two mechanisms are therefore complementary' appears twice in succession; one occurrence should be deleted.","section":"Section 3, first paragraph"},{"comment":"There is a typo: 'herd distance degree' should be 'her distance degree'.","section":"Section 3, 'herd distance degree'"},{"comment":"The dispersion h(x) is defined relative to a fixed optimal facility pair, but when the optimum is not unique, h is not uniquely determined by x. The statements of Theorems 3.3 and 3.4 should explicitly say 'for every choice of an optimal facility pair' to remove ambiguity.","section":"Definition 2.4 and Theorems 3.3–3.4"},{"comment":"The phrase 'exact in every Euclidean dimension because the profiles embed isometrically into every Euclidean space' is correct but could be clearer: the limiting ratio is independent of dimension because the bad-profile family lies on a line.","section":"Theorem 3.5 proof, final sentence"}],"recommendation":"major_revision","confidential_remarks":"To the editor: I did not find an outright false statement in the lower-bound construction or in the main approximation framework, and the lower bound of (1+sqrt(2))/2 appears sound. The decisive issue is the scalar certificate in D.3 and, to a lesser extent, the minimization assertion in Appendix A. These are exactly the points on which the paper's central claim rests, and they are not checkable from the text as written. I would be willing to accept the paper once those steps are expanded or machine-verified. The 'exactly 11/3' wording should also be aligned with the paper's own definition of approximation ratio."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper breaks the 4-approximation barrier for two-facility location with a genuinely new mechanism (Global Pair) mixed with Proportional, and it improves the lower bound from 1.045 to 1.207. The Global Pair idea is simple—select a pair with probability proportional to distance—and the Ptolemaic truthfulness argument is plausible, with a nice K2,3 counterexample in Appendix B showing the domain condition cannot be dropped.\n\nThe dispersion parameter is a genuinely useful contribution. Theorems 3.3 and 3.4 give opposite profile-dependent bounds, and the mixture at lambda = 2/3 yields 11/3. The lower bound proof is clean and correct: block amplification through co-located agents is a real trick.\n\nThe soft spots are real but not fatal. Theorem 3.4's proof depends on scalar inequality (23) in D.3. The argument is hand-verified, with several \"it suffices\" reductions and no machine-checked certificate or fully explicit algebraic derivation. If (23) fails anywhere, the improvement over 4 collapses. I could not find an error, but this is the load-bearing step and it deserves a formal or computational check. As written, the proof is plausible but not conclusive.\n\nThe tightness claim in Theorem 3.5 is also slightly overstated: the proof shows the ratio approaches 11/3 along x_m, but the paper's own definition of approximation ratio requires equality at a finite profile. The fix is local—state the supremum ratio or adjust the definition.\n\nMinor: the analysis assumes OPT(x) is attained; fine for Euclidean spaces but should be flagged for general Ptolemaic spaces.\n\nGiven the novelty and the quality of the lower bound, I would definitely send this to peer review. The referee should focus on D.3 and the tightness wording. If D.3 holds, this is a significant paper for the algorithmic mechanism design community.","headline":"Genuinely new mechanisms and a clean lower bound, but the main upper bound leans on a dense unverified scalar inequality—still worth refereeing.","tokens_in":20086,"tokens_out":5223,"would_cite":true,"duration_ms":48045,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B03","90B80","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized strategyproof two-facility mechanism achieves approximation ratio 11/3 on Ptolemaic metric spaces, breaking the factor-4 barrier.","keywords":["strategyproof mechanism design","two-facility location","randomized mechanism","approximation ratio","Ptolemaic metric space","Ptolemy inequality","dispersion parameter","lower bound"],"falsifier":"Find a single Ptolemaic metric space (for instance, a Euclidean space) and a profile where an agent's misreport strictly lowers her expected cost under the Global Pair mechanism or under the 2/3-mixture; that would contradict Theorems 3.1 and 3.5. Alternatively, find a Ptolemaic profile whose expected social cost under $M_{2/3}$ exceeds $11/3$ times the optimal cost, which would contradict the approximation claim. The paper's own $K_{2,3}$ counterexample shows the first failure occurs outside the Ptolemaic class, so the decisive check is whether it happens inside the class.","tokens_in":19027,"feed_emoji":"📍","tokens_out":13004,"duration_ms":114162,"temperature":0.7,"pith_summary":"The paper claims that the long-standing factor-4 barrier for strategyproof two-facility location can be broken by randomization: a carefully chosen mixture of two mechanisms, each individually with worst-case ratio 4, runs the Proportional mechanism with probability 2/3 and a new Global Pair mechanism with probability 1/3 and achieves approximation ratio exactly 11/3\\approx3.667 on every Ptolemaic metric space, a class that includes all Euclidean spaces. This matters because the best previous randomized strategyproof mechanism had ratio exactly 4 and the best lower bound was about 1.045; the paper also improves that lower bound to (1+\\sqrt{2})/2\\approx1.207 on the line. If true, the results narrow the gap for randomized strategyproof two-facility location from [1.045,4] to [1.207,3.667] and show that the Proportional mechanism's factor 4 is not the end of the line.","feed_headline":"Two-facility game breaks the 4-approximation barrier","feed_subtitle":"A 2/3-1/3 mix of known mechanisms beats the old factor-4 on every Euclidean space.","key_machinery":"The machinery has three pieces. The Global Pair mechanism selects an unordered pair $\\{i,j\\}$ with probability proportional to $d(x_i,x_j)$, equivalently a distance-degree-biased anchor followed by the same distance-proportional second draw as the Proportional mechanism. The dispersion $h(x)$ is a weighted average of capped ratios $\\min\\{c_i/\\delta,1\\}$, where $c_i$ is an agent's optimal cost and $\\delta$ the optimal facility separation; it measures how concentrated the optimal solution is and drives the two approximation bounds in opposite directions. The Ptolemy inequality $d(x,z)d(y,w)\\le d(x,y)d(z,w)+d(x,w)d(y,z)$ for all four-point configurations is the exact condition used to prove Global Pair's truthfulness, and the appendix shows the condition cannot be dropped.","core_discovery":"The central result is Theorem 3.5: the mechanism $M_{2/3}$ that runs the Proportional mechanism with probability 2/3 and the Global Pair mechanism with probability 1/3 is strategyproof on every Ptolemaic metric space and has approximation ratio exactly $11/3$. The Global Pair mechanism opens facilities at an unordered agent pair drawn with probability proportional to $d(x_i,x_j)$, making the anchor draw distance-degree biased rather than uniform. Although each component has worst-case ratio 4, their tight instances are complementary: measured by a dispersion parameter $h(x)$ in $[0,1]$, the Global Pair ratio is at most $3+h(x)$ and the Proportional ratio at most $4-h(x)/2$, so mixing cancels the dependence on $h$. The paper also proves a lower bound of $(1+\\sqrt{2})/2$ for any strategyproof mechanism using a two-profile block-amplification construction on the line.","pith_inferences":["The complementary-worst-case idea suggests a general recipe: whenever two strategyproof mechanisms are tight on disjoint families of profiles, a randomized mixture with profile-dependent guarantees can outperform both; this may apply to other facility-location variants.","The block-amplification lower bound uses only two profiles; concatenating more profiles or larger blocks may push the lower bound above $(1+\\sqrt{2})/2$, though the paper leaves this open.","Because the Global Pair mechanism is not strategyproof on the non-Ptolemaic $K_{2,3}$ metric, the Ptolemy condition marks a real boundary for this mechanism; extending below $11/3$ on general metric spaces will require a different mechanism rather than a different mixing weight.","A natural testable extension is to compute the exact optimal mixing weight and ratio within the mixture family by solving the one-parameter optimization over $\\lambda$ and over profile families; the paper brackets it between $(74+4\\sqrt{3})/23$ and $11/3$."],"forward_implications":["For the first time, a strategyproof randomized two-facility mechanism is known with approximation ratio below 4 on every Ptolemaic metric space, hence on every Euclidean space.","The mixture's ratio $11/3$ is tight in the sense that a family of profiles forces the ratio arbitrarily close to $11/3$, so no smaller guarantee follows from this construction.","Any strategyproof mechanism for the two-facility game on the line must have worst-case ratio at least $(1+\\sqrt{2})/2\\approx1.207$.","Within the family of fixed mixtures of the Proportional and Global Pair mechanisms, no mixing weight yields a ratio below $(74+4\\sqrt{3})/23\\approx3.5186$, so a better upper bound would require a genuinely new mechanism."],"supporting_citations":[{"why":"Defines the Proportional mechanism, proves its strategyproofness and factor-4 approximation, and states the open problem that the mixture resolves.","marker":"(Lu et al., 2010)"},{"why":"Supplies the previous 1.045 lower bound and the single-agent perturbation construction that the new block-amplification lower bound improves.","marker":"(Lu et al., 2009)"},{"why":"Establishes that Euclidean spaces, Hilbert spaces, CAT(0) spaces and metric trees are Ptolemaic, providing the class on which the Global Pair mechanism is truthful.","marker":"(Foertsch et al., 2007)"},{"why":"Introduces the approximate mechanism design without money setting and the deterministic two-extremes baseline that motivates random mechanisms.","marker":"(Procaccia and Tennenholtz, 2009)"}],"fun_headline_variants":["11/3 approximation: mixed mechanism beats factor 4","Two-facility games: break 4-barrier with 2/3-1/3 mix","Strategyproof facility location hits 3.667 ratio","New mechanism cracks two-facility approximation barrier","Improved bounds for two-facility location games"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the ambient metric is Ptolemaic: the Global Pair mechanism's strategyproofness proof needs the Ptolemy inequality for every four-point configuration, and the appendix's $K_{2,3}$ example shows the mechanism can be manipulated when that inequality fails.","fun_headline_variants_meta":{"raw":{"variants":["11/3 approximation: mixed mechanism beats factor 4","Two-facility games: break 4-barrier with 2/3-1/3 mix","Strategyproof facility location hits 3.667 ratio","New mechanism cracks two-facility approximation barrier","Improved bounds for two-facility location games"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1437,"prompt_tokens":1042,"completion_tokens":395,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":309}},"tokens_in":658,"tokens_out":395,"duration_ms":4431,"temperature":1.0,"reasoning_tokens":309,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:25:48.659058+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a single Ptolemaic metric space (for instance, a Euclidean space) and a profile where an agent's misreport strictly lowers her expected cost under the Global Pair mechanism or under the 2/3-mixture; that would contradict Theorems 3.1 and 3.5. Alternatively, find a Ptolemaic profile whose expected social cost under $M_{2/3}$ exceeds $11/3$ times the optimal cost, which would contradict the approximation claim. The paper's own $K_{2,3}$ counterexample shows the first failure occurs outside the Ptolemaic class, so the decisive check is whether it happens inside the class.","supporting_citations":[{"cited_title":"Non-positive curvature and the P tolemy inequality","cited_arxiv_id":null,"evidence_quote":"Establishes that Euclidean spaces, Hilbert spaces, CAT(0) spaces and metric trees are Ptolemaic, providing the class on which the Global Pair mechanism is truthful."}],"review_version":1}