{"id":"2d401b08-aa2d-4ca3-bfca-e568e23f5297","arxiv_id":"2507.06509","paper_version":3,"verdict":"REJECT","confidence":"LOW","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper claims a strategyproof prediction-augmented mechanism for weighted facility location with consistency-robustness bounds depending on the ratio of maximum to minimum agent weight, but the supporting reduction proof is incomplete.","lead":"The paper extends a prediction-aided facility-location mechanism to agents with different importance, claiming explicit worst-case quality bounds that depend on the weight spread. The claimed bounds are computed for a special family of instances, but the proof that these instances are the worst case is not fully supplied.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reduction to COA instances is invalid in the weighted setting: Lemma 6 replaces weighted sums by counts, so Theorem 5 and hence Theorem 1 are unsupported.","rationale":"I read the paper as trying to extend Agrawal et al.'s CMP analysis to weighted facility location. The mechanism itself is well-defined and strategyproof because it ignores weights, and the COA calculations in Theorems 4 and 13 are internally consistent. The central claim therefore depends on Theorem 5's assertion that worst-case instances can be restricted to the COA family. That reduction is the weakest point. The paper states that many lemmas are the same as [1] without giving weighted proofs, and the lemmas it does provide contain concrete errors: Lemma 6's proof uses cardinalities where weighted sums are needed, and Lemma 8 redistributes weights among agents without proving the claimed cost comparison. These are not cosmetic gaps; they are exactly the steps that must convert arbitrary weighted instances into COA instances. Without them the upper bound is only a statement about COA instances, and the reader's REJECT verdict is justified. I agree with the reader's weakest assumption, though I would locate the first concrete failure at Lemma 6 rather than Lemma 8. No change to the verdict is needed; the paper could be reconsidered if a correct weighted reduction is supplied.","tokens_in":14929,"tokens_out":14366,"duration_ms":162249,"concrete_test":"Run an exhaustive numerical search over small weighted instances with locations on the two axes and at o (n <= 7, weights in {1,2,5,10}, c in {0.1,0.3,0.5,0.7}) such that the weighted optimum is o, f(P,o,c)=(0,0), and y_o >= x_o > 0; compute the CMP cost ratio and compare with the claimed COA maximum from Theorem 4 (and Theorem 13 for robustness). If any instance exceeds the claimed bound, or if the Lemma 6 construction on a configuration with one heavy right-side point and several light left-side points yields a decreased ratio, the reduction is falsified. Independently, re-derive the Lemma 6 inequality with weights to check whether Sum_{A_-} w_i >= Sum_{A_+} w_i + w_o is actually guaranteed; it is not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step for Theorem 1 is the reduction in Theorem 5 claiming that every weighted instance can be transformed into a weighted COA instance without lowering the approximation ratio. This reduction is not established. Lemma 6 shifts all non-y-axis points left by epsilon and asserts C_u(f(P))-C_u(f(Q)) = epsilon(Sum_{A_-} w_i - Sum_{A_+} w_i) <= 0 from the cardinality condition |A_-| >= |A_+| + 1. With non-uniform weights this implication is false: even when the count condition holds, one very heavy point on the right (or at o) makes the weighted sum positive, so the mechanism cost can increase and r(Q) can fall below r(P). Lemma 8 has the same problem in a different form: it re-assigns an average weight to x-axis points and invokes an unweighted corollary, but weights are part of the input and the proof does not justify that the weighted optimal cost decreases. Because Lemmas 6 and 8 are the steps that move arbitrary instances to CA/OA and then to COA, the bounds in Theorems 4 and 13 are proved only for the special COA family. The COA computations and the strategyproofness of CMP are fine; the missing piece is a valid weighted analogue of the Agrawal et al. reduction. As submitted, Theorem 1's consistency and robustness guarantees are not supported for all weighted instances.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic, strategyproof mechanisms for the weighted facility location problem in R^2 when the designer receives a prediction of the optimal location. It proposes to run the unweighted Coordinate Median with Prediction (CMP) mechanism, which adds cn phantom copies of the prediction and takes the coordinate-wise median, and claims a consistency-robustness trade-off (Theorem 1). The proof analyzes a family of worst-case instances (weighted COA) and claims via a reduction that every weighted instance can be transformed into a COA instance without lowering the approximation ratio. The paper also states an impossibility result (Theorem 2) for mechanisms that are 1-consistent and have bounded robustness. The COA-family computations are correct, but the reduction to COA is not validly proved for non-uniform weights, so the universal upper-bound claim is not established as written.","tokens_in":15214,"tokens_out":13303,"duration_ms":141608,"significance":"The target result is a natural and valuable extension of Agrawal et al.'s unweighted learning-augmented facility location to weighted agents; if established, it would provide an explicit tunable trade-off and would recover known unweighted bounds as a special case. The COA computations in Theorems 4 and 13 are elementary and check out, and CMP's strategyproofness is immediate because the mechanism ignores weights and uses only phantom points independent of reports. The missing piece is a valid weighted analogue of the reduction to COA; without it the main theorem is not proven for arbitrary weighted instances. The paper would be a useful contribution if that gap can be repaired, but the universal claims should not be cited as proven in the current form.","major_comments":[{"comment":"The reduction step in Lemma 6 is invalid for non-uniform weights. The proof shifts all non-y-axis points left by epsilon and asserts C_u(f(P)) - C_u(f(Q)) = epsilon( sum_{A_-} w_i - sum_{A_+} w_i ) <= 0 from the cardinality condition |A_-| >= |A_+| + 1. Cardinality does not imply the weighted inequality; one heavy point in A_+ can make the sum positive, so the mechanism cost can decrease and r(Q) can fall below r(P). Since Lemma 6 is the first step in Theorem 5's claim that all instances reduce to COA, Theorem 1's bounds are not established for arbitrary weighted instances.","section":"3.2, Lemma 6"},{"comment":"The OA-to-COA transformation reassigns weights by averaging them over the x-axis points and then invokes an unweighted corollary (Corollary 3 in [28]) to conclude that C_U(P, o(P)) decreases while C_U(P, (0,0)) remains unchanged. With non-uniform weights, this redistribution does not preserve the weighted cost to the optimal location, so the reduction is unsupported. A correct weighted analogue of the Agrawal et al. reduction is needed before Theorem 5 can be used to prove the claimed worst-case bounds.","section":"3.2, Lemma 8"},{"comment":"The impossibility proof applies Corollary 3 of [24], a characterization of deterministic, strategyproof, anonymous, and unanimous mechanisms as GCM with n-1 constant points, to prediction-augmented mechanisms. The prediction o(P) is a function of the reported profile, not a constant phantom point, and the paper does not verify that the mechanisms under consideration satisfy the hypotheses of that characterization. Therefore the claimed n * Wmax/Wmin lower bound is not proven. The proof also does not specify the wrong prediction used in the robustness scenario.","section":"3.5, Theorem 2"}],"minor_comments":[{"comment":"There are several typos in the text: 'heAs before' and 'TThe' appear in the paragraph after Algorithm 1, and the sentence 'The procedure of our mechanism does not rely on the weights, consider weights when computing the facility location' is garbled.","section":"3.1"},{"comment":"Lemma 11's proof cites 'Lemma 5' where the statement being used is Lemma 10; the citations to 'Corollary 3 in [28]' (Lemma 8) and 'Corollary 7 in [28]' (Lemma 12) should be checked and harmonized.","section":"3.2"},{"comment":"In the three-agent example, the consistency ratio for c < 2/3 is 3/sqrt(2), not 3*sqrt(2) as printed.","section":"3.4"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the paper's upper-bound proof has a real gap in the weighted reduction, and Theorem 2's proof also needs a justification of the characterization step. The COA-family bounds are correct, and a substantial revision that supplies a valid weighted reduction or appropriately weakens the claims could make the paper publishable. I have no concerns about novelty disclosure or citation practice beyond the internal inconsistency in the cited lemma numbers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is worth reading for the problem and the COA analysis, but not for the universal guarantees as stated. Theorem 1 claims consistency and robustness bounds for all weighted instances in R^2, and the proof rests on reducing arbitrary instances to weighted COA instances. That reduction is where it falls apart.\n\nWhat is genuinely new: the weighted extension of prediction-augmented facility location is natural, and the bounds depending on Wmax/Wmin are exactly what you would want. The COA computations in Theorems 4 and 13 are correct: maximizing over x gives the stated closed forms. The impossibility result in Theorem 2 is also a sensible target, though its proof is a sketch that leans on an unweighted characterization.\n\nThe load-bearing problem is Lemma 6. It says that if |A_-| >= |A_+ ∪ {o}| then you can shift non-y-axis points left by epsilon and the mechanism cost does not increase. In the unweighted case that is just a count. With weights, the cost difference is epsilon(Σ_{A_-} w_i − Σ_{A_+} w_i), and the cardinality condition says nothing about the weighted sum. One heavy point on the right flips the sign. Lemma 8 has the same disease in another form: it re-assigns average weights to x-axis points and invokes an unweighted corollary, but weights are part of the input and changing them changes the optimal cost. Lemma 10 is imported from Agrawal et al. without proof. So Theorem 5 has no support in the weighted case. The COA bounds are fine, but they are bounds for a special family, not for all instances.\n\nThere is also a smaller point: the text is rough in places, with duplicated and garbled sentences, and the impossibility section reads more like a construction than a proof. Both are fixable.\n\nIf a proper weighted reduction is supplied, the result is likely true and useful. As submitted, Theorem 1 is unsupported, but the paper is serious and the problem is worth refereeing. I would send it to review, and expect major revision.","headline":"The weighted CMP bounds for COA instances are correct, but the reduction that lifts them to all weighted instances fails at Lemma 6, leaving Theorem 1 unsupported as written.","tokens_in":15726,"tokens_out":2577,"would_cite":false,"duration_ms":30577,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B14","68W25","90B80"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a weight-ignoring median mechanism with phantom prediction copies achieves sharp tunable consistency and robustness bounds for weighted facility location, and proves an impossibility for perfect consistency.","keywords":["weighted facility location","prediction-augmented mechanism design","strategyproof mechanism","consistency and robustness","coordinate median with prediction","approximation mechanism design","impossibility result","learning-augmented algorithms"],"falsifier":"Construct a small weighted instance with one high-weight agent placed off the axes that the paper's transformation rules cannot move onto the axes without lowering the approximation ratio, then compute CMP's ratio; if it exceeds $\\frac{\\sqrt{(1+c)^2 W_{\\min}^2 + (1-c)^2 W_{\\max}^2}}{(1+c) W_{\\min}}$ for accurate predictions, the claimed worst-case reduction fails.","tokens_in":14742,"feed_emoji":"📍","tokens_out":6588,"duration_ms":66966,"temperature":0.7,"pith_summary":"This paper extends prediction-augmented facility location from unweighted to weighted agents, where agents matter unequally. It claims that a simple mechanism—the coordinate-wise median computed after inserting copies of the predicted optimal location—remains strategyproof and reaches a tunable balance between consistency (efficiency when predictions are right) and robustness (loss when predictions are wrong), with both bounds expressed through the smallest and largest agent weights. The worst-case analysis is carried out by reducing arbitrary weighted instances to a family of symmetric clusters-on-axes instances. The paper also proves that no deterministic strategyproof mechanism can be simultaneously 1-consistent and robust within a factor that grows gently with the number of agents and the weight ratio, so the trade-off is not an artifact of the proposed mechanism.","feed_headline":"Median mechanism tunes prediction trust in weighted facility location","feed_subtitle":"Adding copies of the predicted optimum keeps strategyproofness while controlling worst-case loss.","key_machinery":"The machinery is the family of weighted Clusters-and-OPT-on-Axes (COA) instances: agents placed at $(0,1)$ with maximum weight, agents split symmetrically at $(\\pm x,0)$ with minimum weight, the prediction at the origin, and the optimum at $(0,1)$. The paper argues that every configuration where CMP outputs the origin can be transformed, by moving points onto the axes and rearranging them symmetrically, into a COA instance whose approximation ratio is at least as large; the consistency and robustness formulas then come from a one-variable calculus maximization over $x$. The transformation lemmas are inherited from the unweighted proof and are restated in the weighted setting; they are what carries the argument from arbitrary instances to the clean COA worst case.","core_discovery":"On its own terms, the paper's central discovery is that the Coordinate Median with Prediction (CMP) mechanism—add $m = \\lfloor cn\\rfloor$ phantom copies of the predicted optimum $\\hat{o}$ to the reported locations and take the coordinate-wise median—extends cleanly to weighted agents even though it never looks at the weights. The mechanism is strategyproof by construction, and the paper claims it is $\\alpha(c)$-consistent and $\\beta(c)$-robust with $\\alpha(c) = \\frac{\\sqrt{(1+c)^2 W_{\\min}^2 + (1-c)^2 W_{\\max}^2}}{(1+c) W_{\\min}}$ and $\\beta(c) = \\frac{\\sqrt{(1-c)^2 W_{\\min}^2 + (1+c)^2 W_{\\max}^2}}{(1-c) W_{\\min}}$ in $\\mathbb{R}^2$. At $c=0$ the bound reduces to the known weighted coordinate-median approximation $W_{\\max}/W_{\\min}$, and when all weights coincide it reduces to the known unweighted bounds. A second result shows this trade-off is inherent: no deterministic strategyproof mechanism can reach 1-consistency while keeping robustness bounded by $O(n \\cdot W_{\\max}/W_{\\min})$.","pith_inferences":["A complete proof of the weighted transformation lemmas, particularly the step that redistributes points on the $x$-axis by their weights, would turn the COA worst-case calculation into a full worst-case bound; readers should treat the COA-only guarantee as the currently established part.","Since CMP never uses weights, a natural extension the paper leaves open is to add weighted phantom points or use a weighted median, which might improve the constants while keeping strategyproofness.","The impossibility proof assumes anonymity and unanimity through the characterization it cites; dropping anonymity could in principle open different trade-offs, though the paper does not explore that.","The coordinate-wise structure limits the result to $\\mathbb{R}^2$; in general metric spaces, where median mechanisms are not strategyproof, the same consistency-robustness balance would need a different mechanism."],"forward_implications":["Tuning $c\\in[0,1)$ moves a facility planner along a consistency-robustness frontier: larger $c$ improves performance under accurate predictions, while smaller $c$ reins in loss under misleading predictions.","Because the mechanism ignores weights, it can be deployed in weighted settings without soliciting or verifying agent weights, preserving its strategyproofness; the cost is a trade-off bound that degrades as $W_{\\max}/W_{\\min}$ grows.","Setting $c=0$ reproduces the best-known deterministic weighted facility-location guarantee, so prediction-augmented operation is free in the worst case.","The impossibility result implies weighted prediction-augmented design must accept an inherent factor $\\Omega(n W_{\\max}/W_{\\min})$ if it insists on perfect consistency."],"supporting_citations":[{"why":"Supplies the CMP mechanism, the COA construction, and the unweighted bounds and transformation lemmas that this paper extends to weighted agents.","marker":"[1]"},{"why":"Establishes the weighted coordinate-median approximation $W_{\\max}/W_{\\min}$, recovered here at $c=0$.","marker":"[32]"},{"why":"Provides the foundational strategic-facility-location framework and the strategyproofness perspective used throughout.","marker":"[25]"},{"why":"Provides the coordinate-wise median cost properties (Corollaries 3 and 7) used in the transformation lemmas.","marker":"[28]"},{"why":"Provides the characterization of deterministic strategyproof anonymous unanimous mechanisms as generalized coordinate-wise medians, which powers the impossibility construction.","marker":"[24]"},{"why":"Defines the consistency and robustness metrics that structure the prediction-augmented analysis.","marker":"[21]"}],"fun_headline_variants":["Prediction-augmented median for weighted facility location","Weighted facility location: tunable prediction robustness","Median trick with predictions for weighted agents","Balancing consistency and robustness via predicted medians","Predicted optimum in median: weighted facility design"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every weighted instance can be transformed into a symmetric clusters-on-axes instance without lowering CMP's approximation ratio; if that reduction fails for weights, the claimed bounds only hold for the special family.","fun_headline_variants_meta":{"raw":{"variants":["Prediction-augmented median for weighted facility location","Weighted facility location: tunable prediction robustness","Median trick with predictions for weighted agents","Balancing consistency and robustness via predicted medians","Predicted optimum in median: weighted facility design"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000641,"raw_usage":{"total_tokens":3050,"prompt_tokens":1144,"completion_tokens":1906,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":1836}},"tokens_in":760,"tokens_out":1906,"duration_ms":16119,"temperature":1.0,"reasoning_tokens":1836,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:03:50.250858+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small weighted instance with one high-weight agent placed off the axes that the paper's transformation rules cannot move onto the axes without lowering the approximation ratio, then compute CMP's ratio; if it exceeds $\\frac{\\sqrt{(1+c)^2 W_{\\min}^2 + (1-c)^2 W_{\\max}^2}}{(1+c) W_{\\min}}$ for accurate predictions, the claimed worst-case reduction fails.","supporting_citations":[{"cited_title":"Learning- augmented mechanism design: Leveraging predictions for facility location","cited_arxiv_id":null,"evidence_quote":"Supplies the CMP mechanism, the COA construction, and the unweighted bounds and transformation lemmas that this paper extends to weighted agents."},{"cited_title":"Strategyproof mechanism design for facility location games with weighted agents on a line.Journal of Combinatorial Optimization, 28:756–773, 2014","cited_arxiv_id":null,"evidence_quote":"Establishes the weighted coordinate-median approximation $W_{\\max}/W_{\\min}$, recovered here at $c=0$."},{"cited_title":"Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions","cited_arxiv_id":"2007.00903","evidence_quote":"Provides the coordinate-wise median cost properties (Corollaries 3 and 7) used in the transformation lemmas."},{"cited_title":"Range convexity, continuity, and strategy-proofness of voting schemes.Zeitschrift für Operations Research, 38:213–229, 1993","cited_arxiv_id":null,"evidence_quote":"Provides the characterization of deterministic strategyproof anonymous unanimous mechanisms as generalized coordinate-wise medians, which powers the impossibility construction."},{"cited_title":"Competitive caching with machine learned advice.Journal of the ACM (JACM), 68(4):1–25, 2021","cited_arxiv_id":null,"evidence_quote":"Defines the consistency and robustness metrics that structure the prediction-augmented analysis."}],"review_version":1}