{"id":"7086f3d8-1b88-4c80-b05f-6ac812a9377d","arxiv_id":"2507.04551","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A linear-program-guided greedy policy provably achieves the optimal competitive ratio 1/2 against an omniscient benchmark in dynamic matching with homogeneous abandonment rates.","lead":"This paper designs a greedy matching policy, selected by a new family of linear programs, and proves it earns at least half of the reward of an omniscient planner who knows all future arrivals and departures, whenever all agent types abandon at the same rate (or each side of a bipartite market does). The 1/2 ratio is shown to be the best possible for any online policy in that setting, improving the prior 1/8 guarantee.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tightness proof (Theorem 2) rests on an admitted-buggy external upper bound (Lemma 14); the 1/2 lower bound appears sound but the 'best possible' claim is unverified.","rationale":"I read the main proof chain for Theorem 1 carefully. Lemma 1's flow-cut argument, Lemma 6's convex-combination construction, and Lemma 7's duality argument all appear internally valid; the bipartite case also seems safe because nonpositive same-side matches cannot appear with positive value in an optimal basic feasible solution without admitting a feasible improvement that sets them to zero. Thus I do not see a defect in the 1/2 lower bound. The genuine weak point is the upper-bound/tightness result. The proof of Theorem 2 is a short reduction to Lemma 14, and the manuscript itself flags that the cited proof of that lemma is wrong. Since no corrected proof is supplied, the claim that 1/2 is the best possible constant is currently a belief with a broken citation, not a demonstrated theorem. This is load-bearing because the abstract and contributions explicitly advertise tightness and the impossibility of beating 1/2. A corrected proof or a numerical MDP verification on Example 1 would settle the matter. The reader's conditional verdict is appropriate: accept the main guarantee as plausible and well-supported, but require verification of the imported upper bound before the tightness claim is certified.","tokens_in":27654,"tokens_out":32729,"duration_ms":367490,"concrete_test":"Obtain or produce a complete proof of Lemma 14, or at least verify it on the specific instance in Example 1. Concretely, compute the optimal average reward for Example 1 with mu = 100 and lambda_2 large over all online policies by solving the average-reward Markov decision process on a truncated state space, increasing the truncation level until the value stabilizes, and compare this value to LPON(I) = 1 from Lemma 15. If the computed optimal online value exceeds 1, Lemma 14 is false and Theorem 2 collapses; if it is at most 1 for all truncations and a corrected proof is supplied, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weak point is the tightness half of the central claim. Theorem 2 asserts that no Markovian policy can beat 1/2 + epsilon, but its proof in Appendix B.5 is entirely mediated by Lemma 14, imported as Claim 3 of Aouad and Saritac (2022). The paper's own Footnote 1 (Section 1.1) states that the original proof of this imported result has a mistake, and no corrected proof or alternative argument is supplied anywhere in the manuscript. The chain V(pi) <= LPON(I) <= 1 < V(ADJ,I) after taking lambda_2 and mu large uses Lemma 14 as the only upper bound on online policies; if that lemma is false, the ratio could be larger than 1/2 and Theorem 2 would not follow. There is also an internal mismatch: Lemma 14 is stated only for deterministic stationary policies, while Theorem 2 quantifies over all Markovian policies; the paper does not explain why randomized or otherwise Markovian policies are covered by the same bound. Theorem 1's lower-bound proof (Propositions 1-3 and Lemma 1) does not rely on Lemma 14, so the 1/2 guarantee may survive, but the 'best possible' claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies dynamic matching with Poisson arrivals, exponential abandonment, type-dependent rewards, and an omniscient benchmark that knows the full future. It introduces a family of linear programs, LP^ALG, whose suitable optimal solutions define greedy policies. Under homogeneous-departure assumptions, the paper proves that the resulting greedy policy earns at least half of the omniscient reward rate (Theorem 1), improving the previous 1/8 bound. The proof combines a lower-bound LP for the greedy policy (Lemma 1 and Proposition 1), an upper-bound LP for the omniscient policy (Proposition 2), and a factor-2 comparison between the two LPs (Proposition 3). The paper also claims that the 1/2 ratio is best possible for Markovian policies (Theorem 2), proves a two-type extension (Theorem 3), and reports numerical experiments suggesting the 1/2 guarantee may hold more broadly.","tokens_in":27848,"tokens_out":24657,"duration_ms":279962,"significance":"If Theorem 1 is correct, the paper gives a substantial quantitative improvement over the prior 1/8 competitive ratio and introduces a genuinely novel proof device: using a linear program as a lower bound on the value of a concrete greedy policy, rather than only as an upper bound. The proof chain is explicit, parameter-free, and the paper is careful to separate proven results from conjectures, including a counterexample showing that the key inequality in Lemma 1 can fail for general Markovian policies. However, the tightness claim currently rests on an imported lemma whose proof the authors themselves flag as incorrect, and the bipartite case of the homogeneous-departure theorem has a gap in the application of Lemma 1. These issues affect load-bearing claims and need to be resolved before the paper can be accepted.","major_comments":[{"comment":"The tightness result Theorem 2 is entirely mediated by Lemma 14, which is imported as Claim 3 of Aouad and Sarıtaç (2022). Footnote 1 admits that the original proof of this claim contains a mistake, and the manuscript supplies no corrected proof, no independent derivation, and no formal verification of the lemma. Since V(pi,I) <= LP^ON(I) is the only upper bound on online policies used in the proof of Theorem 2, the claimed upper bound of 1/2 + epsilon for all Markovian policies is unsupported if Lemma 14 is false or unproven. In addition, Lemma 14 is stated only for deterministic stationary policies, whereas Theorem 2 quantifies over all Markovian policies; the reduction from general Markovian policies to deterministic stationary ones is not given. This is a load-bearing gap in the tightness half of the paper's central claim.","section":"Appendix B.5, Theorem 2, Lemma 14, Footnote 1"},{"comment":"The proof of Theorem 1 applies Lemma 1 to every set S with psi_Sj = 0, but Lemma 1 is stated only when all types in S have a common departure rate mu. In the bipartite case of Definition 2, departure rates are equal within each side but need not be equal across the two sides. The manuscript does not argue that the tight sets S arising in Proposition 1 are always contained in one side of the bipartition, nor does it prove an extension of Lemma 1 to sets that mix the two sides. As written, the claimed 1/2 guarantee for the bipartite setting with different side-specific departure rates does not follow from the lemmas stated in the paper.","section":"Section 4.1, Lemma 1, Definition 2"},{"comment":"The proof of Theorem 3 contains an unsupported assertion in the equality case. It claims that if r12 - v1 - v2 = 0, then z_Sj = 0 for all S and j, so v1 = v2 = 0 and all rewards are zero. This does not follow from the dual constraints (42)-(43) as displayed: positive z_Sj can coexist with a zero score, because the z variables enter the constraints for v1 and v2 through equation (43). The case analysis therefore does not establish that the greedy policy matches in both directions, which is exactly what is needed to prove inequality (28) for S = {1,2}. The proof of the two-type extension is incomplete.","section":"Appendix C.1, Theorem 3"}],"minor_comments":[{"comment":"The abstract refers to '(Proposition 4)' for the 1/2 lower-bound claim and to '(Proposition 3)' for the new upper bound, but the numbered results in Section 4 are Proposition 2 for the upper bound and Proposition 3 for the factor-2 comparison. The numbering should be corrected.","section":"Abstract and Section 4"},{"comment":"In the displayed computation of V(ADJ,I), the expression '2 - 2mu + 1/(1+mu)^2' appears to be a typo for '2 - (2mu+1)/(1+mu)^2'. The limiting argument as mu tends to infinity is correct, but the formula as printed is confusing.","section":"Appendix B.5, Lemma 16"},{"comment":"The compensated process X_Sj(t) - lambda_j * integral of 1(N_S(s) > 0) ds is called a submartingale in the proof of Lemma 2. For a non-prefix set S this process is a supermartingale, and the displayed inequality (72) has the correct direction. The terminology should be fixed.","section":"Appendix B.2, Lemma 2"},{"comment":"Constraint (14) is written for S subset of T(M,j), but gamma_S is undefined when S is empty. The paper should state explicitly that the constraints range over nonempty subsets S, or otherwise define gamma_empty consistently.","section":"Section 3.1, LP^ALG constraints (13)-(15)"},{"comment":"The quantity OMN(I) is defined as a limit as t tends to infinity, but the existence of this limit is not discussed. Since OMN(I) is the benchmark in Theorems 1 and 2, a brief justification of the limit's existence would make the statements fully rigorous.","section":"Section 2.1, Definition 4"}],"recommendation":"major_revision","confidential_remarks":"The central lower-bound idea is promising and within the journal's scope. I would ask the authors to prove or replace the imported Lemma 14 before the tightness claim can be accepted, and to close the bipartite gap in the application of Lemma 1. The numerical experiments are suggestive but cannot substitute for these fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is a 1/2 competitive ratio against the omniscient benchmark for greedy policies under homogeneous departures, improving the prior 1/8. The real novelty is the LP_ALG family, used as a lower bound on a greedy policy rather than an upper bound, and the Lemma 1 probability bound that makes it work. The central proof chain is coherent and largely self-contained: Lemma 6's piercing argument, the upper-bound LP, and the duality proof in Proposition 3 all hold together. I read through that part carefully and it checks out.\n\nThe soft spot is exactly where the stress-test puts it. Theorem 2's tightness claim — that no Markovian policy beats 1/2 + epsilon — rests entirely on Lemma 14, imported from Aouad and Saritac, whose proof the authors admit in footnote 1 is mistaken. No corrected proof is supplied. That is a genuine load-bearing gap: if the lemma is false, the ratio could be larger. There's also a scope mismatch: Lemma 14 is stated for deterministic stationary policies, but Theorem 2 quantifies over all Markovian policies. Randomized or history-dependent policies are not obviously covered. This does not damage Theorem 1, which never uses Lemma 14, but it does mean the 'best possible' half of the headline is unsupported as written.\n\nMinor issues: Lemma 3's counting argument is terse; the appendix calls the compensated process a submartingale in one place where it is actually a martingale (the inequality still goes the right way). The numerical experiments are illustrative and do not need error bars to support the theorem.\n\nThe citation pattern is honest, and the mistake admission is refreshing — but it creates an obligation the paper does not meet. The authors should either prove the needed upper bound directly or weaken Theorem 2 and mark it as conditional.\n\nWho this is for: people working in dynamic matching, prophet inequalities, and greedy policies. They will get real value from the LP lower-bound technique and the 1/2 guarantee under homogeneous departures. It deserves a serious referee; the tightness claim needs fixable but nontrivial work.","headline":"Solid 1/2 lower bound for greedy matching under homogeneous departures, but the tightness claim rests on an admitted-buggy cited lemma and needs repair.","tokens_in":28410,"tokens_out":1578,"would_cite":true,"duration_ms":16922,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","60K25","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For dynamic matching markets in which all agents share a common departure rate, a greedy policy selected by a linear program earns at least half of the omniscient reward, and no online policy can guarantee more than that half.","keywords":["dynamic matching markets","greedy policies","competitive ratio","omniscient benchmark","linear programming lower bounds","agent abandonment","Markovian policies","Poisson arrivals"],"falsifier":"On the two-type instance of Example 1 (arrival rate $\\lambda_1 = 1$, departure rates $\\mu_1 = \\mu_2 = \\mu$, rewards $r_{11} = 2+\\mu$, $r_{12} = r_{21} = 1$, $r_{22} = 0$), take $\\lambda_2$ very large and $\\mu$ large, and compute via dynamic programming on a truncated state space the best reward rate any Markovian policy can achieve; beating $(\\frac{1}{2}+\\epsilon)\\,\\mathrm{OMN}(I)$ would refute Theorem 2. Independently, a numerical search for any instance without homogeneous departures in which $V(\\mathrm{ALG}(I), I) < \\frac{1}{2}\\,\\mathrm{OMN}(I)$ would refute Conjecture 1 and show the departure-rate assumption is doing real work; Section 5's random instances found no such case.","tokens_in":27410,"feed_emoji":"🤝","tokens_out":18567,"duration_ms":145525,"temperature":0.7,"pith_summary":"Dynamic matching markets pair agents who arrive over time, earn a reward for each pair, and lose agents who wait too long and give up. This paper asks how much is lost by insisting on greedy policies, which fix a list of acceptable matches in advance and match as soon as both partners are present. The answer, for markets where all agents have the same patience, is that a greedy policy chosen by the authors' algorithm earns at least half of what an omniscient planner with full knowledge of the future earns, and no online policy can guarantee more than half. The proof works by building a linear program whose optimal value certifies the greedy policy's reward from below, a direction earlier LP-based analyses could not achieve. The same guarantee covers bipartite markets where patience is equal within each side, and it improves the previous general guarantee of $\\frac{1}{8}$.","feed_headline":"Greedy matching earns half the omniscient reward — and no more","feed_subtitle":"A greedy policy provably earns at least half of the omniscient reward — and no online policy can do better.","key_machinery":"The engine is the linear program $\\mathrm{LP}^{\\mathrm{ALG}}(I, M)$, whose variables are steady-state expected queue lengths $n_i$, match rates $x_{ij}$, and slacks $\\psi_{Sj}$. Constraint (13) balances each type's arrivals against matches and abandonment, while constraint (14) caps the rate at which arriving type-$j$ agents match into a type set $S$ at $\\lambda_j \\gamma_S \\sum_{i \\in S} n_i$, using $\\gamma_S = \\frac{1 - e^{-\\sum_{i\\in S}\\lambda_i/\\mu_i}}{\\sum_{i\\in S}\\lambda_i/\\mu_i}$ as a deliberately pessimistic estimate of the probability that an $S$-agent is present. A 'suitable' basic feasible solution is one in which $\\psi_{Sj} = 0$ forces $x_{ij} > 0$ for every $i \\in S$; Lemma 3 shows that such a solution encodes the preference lists of a greedy policy, and Algorithm 1 removes matches until the optimal solution is suitable. The technical core is Lemma 1, a complement to Markov's inequality asserting that, for any Markovian policy and any set $S$ of types sharing one departure rate, the probability that at least one $S$-agent is present is at least $\\gamma_S$ times the expected number present. Lemma 6 then shows the greedy policy's match-rate vector 'pierces' the LP's feasible region, so the LP value cannot exceed the policy's true reward, and Proposition 3 ties the bounds together so the chain closes at a factor of two.","core_discovery":"The paper's central claim is Theorem 1: for any instance $I$ with homogeneous departures, the greedy policy $\\mathrm{ALG}(I)$ produced by Algorithm 1 satisfies $V(\\mathrm{ALG}(I), I) \\geq \\frac{1}{2}\\,\\mathrm{OMN}(I)$, where $\\mathrm{OMN}(I)$ is the reward rate of the omniscient policy that knows the whole arrival and departure sequence. Theorem 2 says the factor is tight: for every $\\epsilon > 0$ there is a homogeneous-departure instance on which every Markovian online policy earns less than $(\\frac{1}{2}+\\epsilon)\\,\\mathrm{OMN}(I)$. The route is a new family of linear programs $\\mathrm{LP}^{\\mathrm{ALG}}(I, M)$ whose optimal value is a lower bound on the reward rate of the greedy policy it encodes (Proposition 1), paired with a new linear program $\\mathrm{LP}^{\\mathrm{OMN}}_{\\mathrm{REL}}(I)$ that upper bounds the omniscient benchmark (Proposition 2) and lies within a factor of two of $\\mathrm{LP}^{\\mathrm{ALG}}(I, M)$ (Proposition 3). These pieces close the chain $\\frac{1}{2}\\mathrm{LP}^{\\mathrm{OMN}}(I) \\leq \\mathrm{LP}^{\\mathrm{ALG}}(I,M) \\leq V(\\mathrm{ALG}(I),I) \\leq \\mathrm{OMN}(I) \\leq \\mathrm{LP}^{\\mathrm{OMN}}(I)$; every inequality holds for arbitrary instances except the lower-bound step, which is exactly where the homogeneous-departure condition enters through Lemma 1.","pith_inferences":["The lower-bound LP technique is portable in spirit: any matching or queueing setting in which the probability of 'some agent from set $S$ being present' admits a lower bound proportional to the expected number present could inherit the same proof template, including markets with non-exponential patience or correlated arrivals.","The authors show Lemma 1's inequality fails for a hand-built generic Markovian policy (Appendix C.3) but have found no greedy counterexample; if the inequality holds for every greedy policy, then Conjecture 1 follows and the homogeneous-departure condition in Theorem 1 is an artifact of the proof rather than of the problem.","The tightness construction uses an omniscient policy that pairs adjacent future arrivals of the same type, information a greedy policy cannot see; that suggests the entire gap of $\\frac{1}{2}$ is the value of knowing future departure times, consistent with earlier work where that information pushes guarantees above $\\frac{1}{2}$.","A cheap test of the conjecture outside the proven regime: run $\\mathrm{ALG}(I)$ on small instances with strongly asymmetric departure rates, comparing against $\\frac{1}{2}\\,\\mathrm{OMN}(I)$; the experiments in Section 5 hint the algorithm survives, but a counterexample, if one exists, would likely be small and asymmetric."],"forward_implications":["In homogeneous-departure markets, a platform can secure half of the omniscient reward with a greedy policy whose preference lists come from one solve of a linear program; no lookahead or forecasting is needed.","The factor $\\frac{1}{2}$ is a ceiling as well as a floor: Theorem 2 excludes any guarantee above $\\frac{1}{2}$ for every online policy, so the greedy algorithm is optimal up to the best possible constant.","The new upper-bound LP (Proposition 2) is tighter than the bounds of Collina et al. (2020) and Kessel et al. (2022) and handles non-bipartite compatibility graphs; combined with an existing result it yields a $(e-1)/(2e)$ guarantee for bipartite instances (Appendix C.2).","With only two types the $\\frac{1}{2}$ guarantee holds even without homogeneous departures (Theorem 3), and numerical evidence suggests the assumption may be unnecessary in general (Conjecture 1)."],"supporting_citations":[{"why":"Defines the same dynamic matching model with abandonment and the omniscient benchmark, and supplies the prior 1/8 competitive ratio and the LP upper bounds this paper improves.","marker":"Collina et al. (2020)"},{"why":"Claim 3 (restated as Lemma 14) upper-bounds all online policies and is the imported result on which Theorem 2's tightness proof rests; Lemma 17 is also used for the bipartite improvement.","marker":"Aouad and Sarıtaç (2022)"},{"why":"Establishes the 1/2 guarantee for the special case of a single patient type on one side of a bipartite market, the result Theorem 1 generalizes to many types on both sides.","marker":"Kessel et al. (2022)"},{"why":"Theorem 2.8 is cited to show every Markovian policy has a unique steady state (Lemma 9), a prerequisite for the steady-state analysis and Lemma 1.","marker":"Prieto-Rumeau and Hernández-Lerma (2016)"},{"why":"The PASTA property underlies the Poisson counts of agents present at arrival times used to derive the omniscient upper bound in Proposition 2.","marker":"Wolff (1982)"},{"why":"Martingale reasoning is cited in Lemma 2 to justify the steady-state balance equations linking arrivals, abandonment, and matches for greedy policies.","marker":"Pang et al. (2007)"}],"fun_headline_variants":["Greedy matching locks in half the omniscient reward","Greedy dynamic matching: 1/2 reward ratio is tight","Greedy policy earns half the omniscient reward — provably","Greedy matching improves bound from 1/8 to 1/2","Greedy dynamic matching achieves 1/2 omniscient reward"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that $\\frac{1}{2}$ is the best any online policy can do leans on an upper bound imported from another paper whose proof the authors themselves describe as mistaken, and no corrected proof is supplied here; if that imported bound is wrong, the tightness claim is unsupported even though the guarantee of at least $\\frac{1}{2}$ might still stand.","fun_headline_variants_meta":{"raw":{"variants":["Greedy matching locks in half the omniscient reward","Greedy dynamic matching: 1/2 reward ratio is tight","Greedy policy earns half the omniscient reward — provably","Greedy matching improves bound from 1/8 to 1/2","Greedy dynamic matching achieves 1/2 omniscient reward"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000323,"raw_usage":{"total_tokens":1969,"prompt_tokens":1252,"completion_tokens":717,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":868,"completion_tokens_details":{"reasoning_tokens":621}},"tokens_in":868,"tokens_out":717,"duration_ms":7086,"temperature":1.0,"reasoning_tokens":621,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:46:36.931138+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the two-type instance of Example 1 (arrival rate $\\lambda_1 = 1$, departure rates $\\mu_1 = \\mu_2 = \\mu$, rewards $r_{11} = 2+\\mu$, $r_{12} = r_{21} = 1$, $r_{22} = 0$), take $\\lambda_2$ very large and $\\mu$ large, and compute via dynamic programming on a truncated state space the best reward rate any Markovian policy can achieve; beating $(\\frac{1}{2}+\\epsilon)\\,\\mathrm{OMN}(I)$ would refute Theorem 2. Independently, a numerical search for any instance without homogeneous departures in which $V(\\mathrm{ALG}(I), I) < \\frac{1}{2}\\,\\mathrm{OMN}(I)$ would refute Conjecture 1 and show the departure-rate assumption is doing real work; Section 5's random instances found no such case.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the same dynamic matching model with abandonment and the omniscient benchmark, and supplies the prior 1/8 competitive ratio and the LP upper bounds this paper improves."},{"cited_title":"and Sar ta c , \\\"O","cited_arxiv_id":null,"evidence_quote":"Claim 3 (restated as Lemma 14) upper-bounds all online policies and is the imported result on which Theorem 2's tightness proof rests; Lemma 17 is also used for the bipartite improvement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the 1/2 guarantee for the special case of a single patient type on one side of a bipartite market, the result Theorem 1 generalizes to many types on both sides."},{"cited_title":"and Hern \\'a ndez-Lerma, O","cited_arxiv_id":null,"evidence_quote":"Theorem 2.8 is cited to show every Markovian policy has a unique steady state (Lemma 9), a prerequisite for the steady-state analysis and Lemma 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The PASTA property underlies the Poisson counts of agents present at arrival times used to derive the omniscient upper bound in Proposition 2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Martingale reasoning is cited in Lemma 2 to justify the steady-state balance equations linking arrivals, abandonment, and matches for greedy policies."}],"review_version":1}