{"id":"9ad3f373-bde0-4f2b-8125-b8b773c520fe","arxiv_id":"2411.08218","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For stationary online bipartite matching, the paper breaks the 1 - 1/e approximation barrier and improves the known competitive ratio to 1 - 1/sqrt(e) + η.","lead":"This paper presents an online matching algorithm for markets where workers and patients arrive continuously and leave after a random wait, proving a (1 - 1/e + δ) guarantee against the best online policy, which is the first improvement over the long-standing 1 - 1/e barrier. The same method also improves the competitive ratio against a clairvoyant offline policy to 1 - 1/sqrt(e) + η, while simplifying earlier proof techniques.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.20's Paley-Zygmund step appears to require θ=1/2 while the allowed parameters give θ>1, so concentration bound (23) is not justified; this gap threatens the universal constant in Lemma 3.11.","rationale":"The reader's verdict identifies Lemma 3.20, the core-set concentration lemma, as the load-bearing step for the universal constant ζ, and I agree: this is where the paper is least secure. My stress test sharpens the reader's concern by pointing to a specific technical gap inside Step 2: the Paley-Zygmund application uses θ=1/2 without verifying that the desired threshold is at most half the mean. Under the extremal constants permitted by inequalities (20)–(22), the threshold can exceed the mean by a factor of roughly two, so the stated bound (23) does not follow from the cited facts. This is not an internal contradiction in the overall approach—the constants δ, κ, ε, and the definitions of u and δ' could plausibly be adjusted to make the argument work, and the paper only needs existence of some positive universal ζ. But as written, the proof has a gap in a chain that supports Theorem 1.1. The CDF inequality reversal flagged by the reader is a secondary issue: it appears to be a sign typo rather than a substantive error, since the integral inequality that follows is consistent with the correct direction F_i ≥ F̃_i. The binary-queue truncation is also somewhat heuristic but is explicitly described as an analysis-only device with an O(ε^2/n) loss, so I do not treat it as the primary risk. My recommendation is therefore unchanged from the reader's CONDITIONAL verdict: the result is plausible and likely fixable, but the proof of Lemma 3.20's concentration bounds should be completed and verified before the paper is accepted as fully rigorous.","tokens_in":49093,"tokens_out":32287,"duration_ms":304041,"concrete_test":"Re-derive inequality (23) analytically: fix the extremal parameter set satisfying (20)–(22) (e.g., ǫ'=κ=0.1, u=0.1444) and compute the Paley-Zygmund bound with the actual θ = (1/(4δ'Γ̃)) / E[∑η^n_t], using T=⌈Λ̃/(δ'Γ̃)⌉, E[η^n] ≥ (1−ǫ')u/Λ̃, and Var[η^n] ≤ (4/Γ̃)·E[η^n]. Check whether the resulting lower bound on Pr[∑η^n_t ≥ 1/(4δ'Γ̃)] is at least c0 for all δ'≤4δ allowed by Lemma 3.20. If the bound can fall below c0, Lemma 3.20 is not established as stated; alternatively, run a Monte Carlo simulation of the alternating renewal process with empty cycles Exp(Λ̃) and nonempty cycles distributed as the hyperexponential in Claim 3.21, using the extremal parameters, to measure the probability in Lemma 3.20 and compare it with c0·1[t_i≥τ̃_i].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The universal constant ζ in Lemma 3.11 ultimately rests on Lemma 3.20, whose Step 2 derives concentration bounds (23) and (24) for the alternating renewal process of the core set I_core. Inequality (23) is obtained by applying the Paley-Zygmund inequality (Fact D.3) with θ=1/2. This application is valid only if the threshold 1/(4δ'Γ̃) is at most (1/2)·E[∑_{t=1}^T η^n_t]. Using T=⌈Λ̃/(δ'Γ̃)⌉ and E[η^n] ≥ (1−ǫ')u(ǫ',κ)/Λ̃, the mean is E[∑η^n_t] ≥ (1−ǫ')u/(δ'Γ̃). With the proof's choice 1/δ' = t_iΓ̃/4, this becomes E ≥ (1−ǫ')u·t_i/4, while the threshold is t_i/16. For the extremal parameters allowed by the core-set inequalities (20)–(22), e.g., ǫ'=κ=0.1 giving u=0.1444, the ratio E/threshold is 4(1−ǫ')u ≈ 0.52, so θ ≈ 1.93, not 1/2. The paper supplies no alternative bound valid for θ>1. If the true lower bound on the event in (23) drops below the constant c0 used in Lemma 3.20, the constant-probability gap in Lemma 3.14—and hence the universal ζ in Lemma 3.11—is unsupported. Separately, the CDF inequality reversal near equation (16) appears to be a sign typo (the integral inequality direction is consistent with F_i ≥ F̃_i), so it is not the primary concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies stationary online bipartite matching in which offline nodes arrive according to Poisson processes and have exponentially distributed patience, while online nodes must be matched immediately. The main claim is Theorem 1.1: a polynomial-time algorithm whose expected long-run average reward is at least (1−1/e+δ) times the optimal online policy's reward for a universal δ>0, thereby breaking the 1−1/e barrier established by Aouad and Saritaç. The proof introduces a tightened LP relaxation (TLPon) with subset constraints, proves a (1−1/e)-approximation via independent Markov chains and pivotal sampling, identifies three 'easy' cases in which the analysis is loose, and then analyzes a Balanced Greedy algorithm on the remaining vertex-weighted highly-connected instances using weakly correlated Markov chains and renewal-theoretic concentration. A byproduct is a (1−1/√e+η)-competitive algorithm against the offline optimum (Theorem 4.1).","tokens_in":49423,"tokens_out":15959,"duration_ms":149658,"significance":"If the main theorem is correct, it is a significant advance: it answers an open direction in stationary matching by showing that correlation in the offline queueing process can be exploited algorithmically, and it improves the best-known competitive ratio. The paper's strengths include a clean stochastic-dominance coupling for the baseline, a non-trivial use of pivotal sampling for dependent rounding, and a clear reduction of the hard case to a structured VWHC instance. No code or machine-checked proofs are included; the contribution is analytic and the constants are non-explicit but in principle computable. The main findings are falsifiable: the claimed universal constant either follows from the supplied lemmas or not. The load-bearing gap identified below prevents me from recommending acceptance in the current form.","major_comments":[{"comment":"The concentration step in Lemma 3.20 is not justified as written. Fact D.3 is invoked with θ=1/2, but the event whose probability is needed is {Σ_{t=1}^T η^n_t ≥ 1/(4δ′Γ̃)}. From T=⌈Λ̃/(δ′Γ̃)⌉ and E[η^n_t] ≥ (1−ǫ′)u(ǫ′,κ)/Λ̃ (inequality (48)), one has E[Ση^n_t] ≥ (1−ǫ′)u(ǫ′,κ)/(δ′Γ̃). Hence threshold/E[Ση^n_t] = 1/[4(1−ǫ′)u(ǫ′,κ)], which is ≈1.93 for ǫ′=κ=0.1 and can exceed 1 for admissible parameters; when the threshold is above the mean, Paley–Zygmund with any θ<1 gives no lower bound on the desired tail. Even when the ratio is below 1, the correct factor is (1−ratio)^2 rather than the 1/4 used in (50)–(52), so the constants c0, δ̄, and ultimately ζ in Lemma 3.11 are not established. The authors should supply a valid concentration bound for the renewal sum (for instance by enlarging T so that the target threshold is at most a constant fraction of the mean, or by an exponential tail bound for the hyperexponential variables) and re-derive the constants.","section":"§3.4, Appendix D.7.2, inequalities (23) and (49)–(52)"}],"minor_comments":[{"comment":"The inequality F_i(u,τ_i) ≤ F̃_i(u,τ_i) has the wrong direction; Lemma 3.14's stochastic dominance gives F_i ≥ F̃_i, and the subsequent integral upper bound is valid only with that corrected direction.","section":"Proof of Lemma 3.11, after equation (16)"},{"comment":"The symbol sMc appears without definition in the phrase 'the depletion of sMc'; this should be a named process or defined notation.","section":"Proof of Lemma 3.13"},{"comment":"The universal constants ζ, δ, and η are asserted to exist but never quantified; this is acceptable for an existence proof, but the paper would be more useful if the main theorem stated how the constants are obtained from c0, δ̄, and f(·).","section":"Main theorems"}],"recommendation":"major_revision","confidential_remarks":"The reader's report and the stress-test note converge on the same point. I agree that the paper's central structure is sound and the issue is a gap in a key lemma rather than a demonstrated counterexample; the fix may be achievable by enlarging T or choosing κ small. I would ask the authors in revision to supply a complete, correct concentration argument for Lemma 3.20 and to re-derive c0 and δ̄. No concerns about attribution or scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a serious paper that likely has a gap in its central technical lemma. The authors break 1-1/e in stationary bipartite matching using a new LP relaxation with subset constraints, pivotal sampling, and a weakly correlated Markov chain analysis. The (1-1/e) warm-up is clean, the reduction to VWHC instances is elegant, and the competitive-ratio improvement over PW24 is a useful byproduct. But the concentration argument in Lemma 3.20 does not hold as written.\n\nThe issue is in Step 2 of the proof sketch and Appendix D.7.2. Inequality (23) is obtained by Paley-Zygmund with theta=1/2. The threshold is 1/(4 delta' Gamma-tilde), while E[sum eta^n_t] is at least (1-eps')u(eps',kappa)/(delta' Gamma-tilde). So the ratio threshold/mean is 1/[4(1-eps')u]. For the allowed parameters (e.g., eps'=kappa=0.1, u=0.1444), this ratio is about 1.93, so theta>1. For any positive eps',kappa, u<0.5, so the ratio exceeds 1/2. Thus the event in the Paley-Zygmund bound does not imply the desired event, and inequality (23) is unjustified. This matters because Lemma 3.20 feeds into Lemma 3.14, which gives the constant probability gap that produces the universal zeta in Lemma 3.11. Without it, the VWHC analysis collapses and Theorem 1.1 is not established.\n\nThe rest of the paper seems careful; I didn't find other load-bearing issues. The reversed CDF inequality near (16) looks like a sign typo. The binary-queue reduction is analysis-only but plausible. The core-set counting in D.7.1 is okay, but the concentration step needs repair. A correct proof might use a different concentration inequality or a different choice of the core set to make the mean large enough.\n\nThis paper is for researchers in online matching and stochastic optimization. It deserves peer review, but the referee assignment should ask for a fix of Lemma 3.20. If that fails, the main theorem is unproven, though the competitive ratio result might survive. I would not cite the main theorem yet.\n\nRecommendation: send to peer review with a targeted request to fix the Paley-Zygmund step.","headline":"Serious attempt at breaking 1-1/e in stationary bipartite matching, but a likely invalid Paley-Zygmund step in Lemma 3.20 leaves the universal constant unsupported.","tokens_in":50014,"tokens_out":9240,"would_cite":false,"duration_ms":79212,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-12T21:52:55.586078+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}