{"id":"9a1e9767-a07f-4890-b138-d4656d838f7d","arxiv_id":"2411.16947","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Online b-matching with stochastic rewards has optimal competitive ratio 1-1/e: impossible to beat against the stochastic benchmark, and achieved by StochasticBalance as capacities grow.","lead":"This paper proves a tight 1-1/e performance limit for online b-matching with stochastic rewards, even against the easier clairvoyant benchmark. It also shows a simple load-balancing algorithm reaches that limit when server capacities grow large.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's all-b upper bound depends entirely on Lemma 1, which is not proved here: the paper asserts that Mehta–Panigrahi's optimality proof 'also works for all values of b' without giving the argument. If that extension fails for any b>1, the hardness result has no support.","rationale":"The reader's weakest_assumption identifies the same load-bearing gap: Lemma 1 is asserted, not proved, and Theorem 1's upper bound collapses if the claimed extension of Mehta–Panigrahi's optimality lemma fails for b>1. I agree that this is the central correctness risk. The rest of the upper-bound derivation (Lemmas 2-7) is internally coherent, and the primal-dual lower-bound analysis in Section 3 is plausible and does not depend on Lemma 1. The conditionality of the verdict is appropriate: a precise proof or a locatable argument in [15] covering all b would resolve the concern, while a counterexample for b=2 would invalidate the all-b hardness claim. I therefore do not move the verdict; CONDITIONAL remains the right status until the lemma is substantiated.","tokens_in":18784,"tokens_out":27726,"duration_ms":288996,"concrete_test":"Verify Lemma 1 for the smallest nontrivial capacitated case. Set b=2, n=2, and in the p→0 limit model each round as a Poisson process of attempted assignments of total mass b (round 1 to servers {s1,s2}, round 2 to {s2}). Solve the resulting finite-horizon MDP by backward induction over the two rounds and states (remaining capacities of s1,s2) to obtain the optimal expected online reward. Compute the expected reward of StochasticBalance on the same instance under the paper's min-load rule. If the MDP value exceeds the StochasticBalance value, Lemma 1 is false for b=2; if the values match, repeat the comparison for b=3,n=3. This directly tests the unproved all-b extension on which Theorem 1 rests.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 is the sole bridge from 'StochasticBalance is optimal on G_b_n' to 'no algorithm beats 1-1/e against SOPT'. The paper does not prove it; it cites Lemma 12 of [15] and asserts the proof extends to all b. This is not a cosmetic gap: for b>1, capacity is consumed only on successful matches, so an algorithm is free to concentrate early requests on low-index servers that have no future value while preserving high-index servers for later rounds. Whether the load-balancing assignment rule of StochasticBalance remains optimal under that trade-off is exactly what needs a proof; unit-capacity exchange arguments from [15] do not automatically carry over. If a single b>1 instance in {G_b_n} admits an online policy with expected reward strictly above StochasticBalance, then E[SBAL(G_b_n)] is not an upper bound for arbitrary algorithms, and the claimed hardness for all b collapses. The paper itself does not flag this as an open assumption; it is stated as Lemma 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the online b-matching problem with stochastic rewards, where each server has capacity b and each assigned edge succeeds with a given probability. The main results are (i) an upper bound of 1-1/e on the competitive ratio of any randomized algorithm against the stochastic benchmark SOPT, for equal vanishing edge probabilities and arbitrary b (Theorem 1), and (ii) a lower bound showing that the deterministic StochasticBalance algorithm achieves (1-1/e)-competitiveness as b tends to infinity, for arbitrary non-vanishing probabilities, with extensions to vertex weights and individual capacities (Theorems 2 and 3). The upper bound is established through a family of graphs G^b_n, an optimality lemma for StochasticBalance on these graphs, and an exact analysis of the GREEDY algorithm that lower bounds SOPT. The lower bound uses a primal-dual analysis with a carefully chosen dual-fitting function.","tokens_in":60,"tokens_out":33539,"duration_ms":1342713,"significance":"If the results are correct, they pin the competitive ratio of online b-matching with stochastic rewards at the classical 1-1/e barrier for both benchmarks in the respective asymptotic regimes. The paper contains several strong technical contributions: the exact solution of the GREEDY recurrence in Lemma 6, the clean dual-fitting analysis in Section 3 that avoids the configuration LP needed for b=1, and an explicit hardness construction that applies to all capacities and to the stochastic benchmark for the first time. The lower bound for StochasticBalance with arbitrary non-vanishing probabilities appears to be the first such result. However, the upper bound rests on an unproved external lemma, which limits current confidence in the all-b claim.","major_comments":[{"comment":"Lemma 1 asserts that StochasticBalance is optimal for the graph family G^b_n for all b, citing Lemma 12 of Mehta and Panigrahi [15] and stating that 'their proof also works for all values of b'. Neither the proof nor the extension argument is given. This lemma is load-bearing: Theorem 1 uses it to conclude that E[SBAL(G^b_n)] upper bounds the expected reward of any algorithm, so without it the hardness result for b>1 collapses. The extension is not purely cosmetic: for b>1, capacity is consumed only on successful matches, so an algorithm can concentrate early assignments on low-index servers without immediately losing their future capacity, and the unit-capacity exchange arguments from [15] do not automatically carry over. The authors should provide a complete proof of Lemma 1 or a detailed explanation of why the proof of Lemma 12 in [15] transfers verbatim to all b.","section":"Section 2, Lemma 1"},{"comment":"The proof repeatedly replaces the binomial distribution Bin(b/p, p) with the Poisson distribution Pois(b) as p -> 0, but the approximation error is never bounded. Consequently, the formulas in Lemmas 2, 4, 5, and 7 are exact only in the limit p -> 0, while the impossibility claim requires a statement such as: for every epsilon > 0 and every b, there exist finite n and sufficiently small p such that no algorithm has competitive ratio greater than 1-1/e + epsilon. Please add an explicit epsilon-delta argument controlling the Poisson approximation error uniformly over the rounds and servers.","section":"Section 2, Lemmas 2 and 7; Theorem 1"}],"minor_comments":[{"comment":"The notation Ri ~ min{Pois(b), m} is nonstandard; please define it explicitly as a truncated Poisson distribution. The displayed distribution is only asymptotic as p -> 0, so this should be stated clearly in the lemma.","section":"Section 2, Lemma 2"},{"comment":"The integral limits are written in reverse order in two places: the text writes int_{l_s-1}^{-1} f(x) dx and int_{b-b^{2/3}-1}^{0} e^{x/b-1} dx, while the accompanying computation treats the intervals as [-1, l_s-1] and [0, b-b^{2/3}-1] respectively. The intended argument is clear, but the notation should be corrected in a proof that is load-bearing for dual feasibility.","section":"Section 3, Lemma 14"},{"comment":"The displayed inequality contains the expression '(k-i+1)+(n-k)/(n-i+1)' which is formally ambiguous; it should read '((k-i+1)+(n-k))/(n-i+1)'. The intended algebra is correct, but the formula as printed is not.","section":"Section 2, proof of Lemma 4"},{"comment":"The sentence 'In fact, their proof also works for all values of b' conflates the cited lemma with the asserted extension; this is precisely the claim that needs a proof or a detailed citation, so the sentence should be expanded or removed.","section":"Section 2, before Lemma 1"},{"comment":"The implication that the upper bound against SOPT yields the same upper bound against OPT is stated without explanation. It follows from SOPT <= OPT, but a one-line justification would improve readability.","section":"Abstract and Corollary 1"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the unproved Lemma 1. The authors cite Mehta-Panigrahi and claim the proof extends to all b, but the extension is not immediate because the unit-capacity arguments do not automatically carry over. If the authors can supply a complete proof of Lemma 1, the paper is a strong contribution. There is no issue with self-citation or fitted parameters; the analysis is genuinely parameter-free and the adversarial construction is explicit. I recommend asking for a full proof of Lemma 1 in the revision, and additionally for an explicit handling of the p -> 0 approximation error."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper does two things. Section 3 gives a primal-dual analysis of a generalized StochasticBalance for b-matching with stochastic rewards, showing it is (1-1/e)-competitive against OPT (and hence SOPT) as b→∞, for arbitrary non-vanishing edge probabilities, with an extension to vertex weights and individual capacities. That part looks solid to me. The dual-fitting algebra is standard but carefully executed, and the coupling lemma (Lemma 9) is correct and useful. If I had to bet, Theorem 2 is true as stated.\n\nThe harder part is Section 2, the claimed hardness of 1-1/e against SOPT for all b. The proof leans entirely on Lemma 1, which asserts that StochasticBalance is optimal for the graph family G^b_n for every b and n. That lemma is not proved here; it is cited to Lemma 12 of [15], with the comment \"their proof also works for all values of b.\" No argument is given. That is a load-bearing external assertion.\n\nAnd I am not convinced the extension is automatic. In G^b_n the servers are not symmetric: a server with a higher index is available in more rounds, so it is more valuable to keep it free. The balance rule, spreading load evenly across all available servers, seems to ignore exactly that trade-off. On small instances (n=2) you can see that a \"save the high-index server for later\" strategy looks better than equal load balancing. The unit-capacity exchange arguments from [15] do not obviously carry over; the capacity-consumed-only-on-success effect is different once b>1. So the stress-test concern is on target: if Lemma 1 fails for any b>1, Theorem 1 has no support.\n\nThe rest of the upper-bound section is fine. The Poisson approximation of rounds (Lemma 2) is clean, the bound on E[SBAL] via water-filling is correct, and the GREEDY lower bound for SOPT (Section 2.2) is a nice contribution. The citation pattern is clean—no self-citations, no circularity. The problem is purely that the bridge from \"SB is optimal\" to \"no algorithm beats 1-1/e\" is asserted rather than proved.\n\nWho is this for? People working on online matching and AdWords with stochastic rewards. The b→∞ result is a genuine step forward and will be cited. The all-b hardness result, if correct, closes a question from Goyal and Udwani. But as written, I would not accept Theorem 1 at face value.\n\nRecommendation: send it to review, but make the referee focus on Lemma 1. The authors should either supply a full proof of the b>1 extension, restrict the upper bound to b=1 with a proper reference, or state the extension as a conjecture. This is a conditional accept, not a clear accept.","headline":"The b→∞ lower bound for StochasticBalance is clean and valuable; the all-b hardness result rests on an unproved lemma about StochasticBalance that is not obviously true for b>1.","tokens_in":19507,"tokens_out":21528,"would_cite":true,"duration_ms":194076,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68R10","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that no randomized online algorithm can beat the 1-1/e competitive ratio for b-matching with stochastic rewards, even against the easier stochastic benchmark and with equal vanishing probabilities; StochasticBalance…","keywords":["online b-matching","stochastic rewards","competitive ratio","StochasticBalance","primal-dual analysis","vanishing probabilities","AdWords","bipartite matching"],"falsifier":"For small $b$ and $n$, e.g. $b=2$ and $n=3$, enumerate all deterministic online algorithms on the graph family $G^b_n$ as $p \\to 0$ and compare their expected matches with StochasticBalance; if any algorithm outperforms StochasticBalance, the unproved extension of the optimality lemma fails and the all-$b$ upper bound collapses.","tokens_in":18588,"feed_emoji":"⚖️","tokens_out":18441,"duration_ms":146567,"temperature":0.7,"pith_summary":"Online $b$-matching with stochastic rewards asks how to assign arriving requests to servers of capacity $b$ when each assignment succeeds with a known probability, with the goal of maximizing expected successful matches. This paper establishes that the well-known $1-1/e \\approx 0.632$ competitive-ratio barrier is unavoidable: no randomized online algorithm can do better against either of the two standard offline benchmarks, even when all success probabilities are equal and vanish to zero, for every capacity $b$. On the positive side, it shows that the simple StochasticBalance algorithm reaches exactly this barrier, achieving a competitive ratio of $1-1/e$ against the non-stochastic benchmark as server capacities grow without bound, for arbitrary heterogeneous non-vanishing edge probabilities. The result also covers vertex-weighted servers with individual capacities, and implies that in the AdWords setting with stochastic rewards no online algorithm can beat $1-1/e$.","feed_headline":"No algorithm beats 1-1/e in stochastic b-matching","feed_subtitle":"StochasticBalance reaches this ratio as capacities grow; the ceiling holds for every capacity.","key_machinery":"Two constructions carry the argument. For the upper bound, the graph family $G^b_n$ ($n$ servers of capacity $b$, $n$ rounds of $b/p$ identical requests, all edges of probability $p$) reduces the problem to counting successes; the optimality of StochasticBalance on this family (Lemma 1, extending a unit-capacity result) plus a Poisson approximation for the number of successes in each round yields the $1-1/e$ ceiling. For the lower bound, the paper uses a primal-dual analysis of a generalized StochasticBalance that assigns a request to the server maximizing $p_{s,r}(1-f(\\ell))$, where $\\ell$ is the server's current load; with $f(x)=e^{x/b-1}$ for $x \\le b$, the dual solution is shown to be feasible up to a $(1-\\varepsilon)$ factor as $b \\to \\infty$, giving weak duality and the $1-1/e$ ratio.","core_discovery":"The central claim is twofold. First, for $b$-matching with stochastic rewards, the competitive ratio of any randomized online algorithm is at most $1-1/e$ against the stochastic benchmark SOPT — the best offline algorithm that knows the graph but not which edges succeed — for every capacity $b$, even when all edges have equal success probability $p \\to 0$. This is proved by a family of graphs $G^b_n$ with $n$ servers of capacity $b$ and $n$ rounds of $b/p$ requests; StochasticBalance is optimal on these graphs, and its expected number of matches is asymptotically at most $(1-1/e)\\,n b$, while a greedy offline strategy shows SOPT is asymptotically at least $n b$. Second, StochasticBalance is $1-1/e$-competitive against the non-stochastic benchmark OPT in the limit $b \\to \\infty$ for arbitrary non-vanishing edge probabilities, proved through a primal-dual analysis with a carefully chosen function $f$; the same guarantee extends to vertex-weighted servers with individual capacities as the minimum capacity grows without bound.","pith_inferences":["For finite capacities, the paper leaves an open quantitative gap: the upper bound is $1-1/e$ for every $b$, while the matching lower bound for StochasticBalance is asymptotic in $b$; it is natural to expect that for each fixed $b$ the algorithm's ratio is strictly below $1-1/e$ and approaches it from below.","The hardness construction uses equal, vanishing probabilities, so it does not rule out better algorithms against SOPT in non-vanishing or heterogeneous regimes; an explicit hardness proof for those regimes would show whether the $1-1/e$ barrier is fully universal.","Because the lower-bound proof picks $f(x)=e^{x/b-1}$ largely for convenience, a capacity-aware $f$ optimized per $b$ could yield finite-$b$ competitive ratios, paralleling the numerical integral-equation analyses used at $b=1$."],"forward_implications":["No randomized algorithm can beat $1-1/e$ against the stochastic benchmark SOPT for any capacity $b$, so the stochastic benchmark does not escape the classic barrier.","The same $1-1/e$ ceiling holds against the non-stochastic benchmark OPT, by the known inequality SOPT ≤ OPT.","StochasticBalance is $1-1/e$-competitive as $b \\to \\infty$ even with arbitrary, non-vanishing edge probabilities — the first such guarantee for this algorithm.","The result extends to vertex-weighted servers with individual capacities, provided the minimum capacity tends to infinity.","For the AdWords problem with stochastic rewards, no online algorithm can be better than $1-1/e$-competitive."],"supporting_citations":[{"why":"introduced the stochastic-rewards model and its StochasticBalance algorithm; its Lemma 12 is the unit-capacity optimality lemma this paper extends to capacities b.","marker":"[15]"},{"why":"established SOPT ≤ OPT and gave a 1-1/e-competitive algorithm for b→∞ with arbitrary probabilities, supplying the benchmark relation and capacitated baseline.","marker":"[6]"},{"why":"shows 1-1/e is achievable for unit capacities against SOPT, making the new upper bound tight for b=1 and motivating the question.","marker":"[7]"},{"why":"supplies the primal-dual framework that the paper adapts to StochasticBalance with capacities.","marker":"[5]"},{"why":"shows the 1-1/e ceiling for AdWords when all probabilities are 1, which the corollary extends to stochastic rewards.","marker":"[16]"}],"fun_headline_variants":["Stochastic b-matching: no algorithm beats 1-1/e","Randomized algorithms can't beat 1-1/e in b-matching","StochasticBalance hits 1-1/e as capacities scale","Tight bound for online b-matching with stochastic rewards","For stochastic rewards, b-matching has 1-1/e limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper bound for arbitrary capacities assumes that the optimality lemma for StochasticBalance on the constructed graph family, proved for unit capacity in the cited work, extends to all capacities $b>1$; the paper asserts this extension without reproducing the proof.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic b-matching: no algorithm beats 1-1/e","Randomized algorithms can't beat 1-1/e in b-matching","StochasticBalance hits 1-1/e as capacities scale","Tight bound for online b-matching with stochastic rewards","For stochastic rewards, b-matching has 1-1/e limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001051,"raw_usage":{"total_tokens":4487,"prompt_tokens":1092,"completion_tokens":3395,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":708,"completion_tokens_details":{"reasoning_tokens":3303}},"tokens_in":708,"tokens_out":3395,"duration_ms":25403,"temperature":1.0,"reasoning_tokens":3303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:47:10.200311+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For small $b$ and $n$, e.g. $b=2$ and $n=3$, enumerate all deterministic online algorithms on the graph family $G^b_n$ as $p \\to 0$ and compare their expected matches with StochasticBalance; if any algorithm outperforms StochasticBalance, the unproved extension of the optimality lemma fails and the all-$b$ upper bound collapses.","supporting_citations":[{"cited_title":"Mehta and D","cited_arxiv_id":null,"evidence_quote":"introduced the stochastic-rewards model and its StochasticBalance algorithm; its Lemma 12 is the unit-capacity optimality lemma this paper extends to capacities b."},{"cited_title":"Golrezaei, H","cited_arxiv_id":null,"evidence_quote":"established SOPT ≤ OPT and gave a 1-1/e-competitive algorithm for b→∞ with arbitrary probabilities, supplying the benchmark relation and capacitated baseline."},{"cited_title":"Goyal and R","cited_arxiv_id":null,"evidence_quote":"shows 1-1/e is achievable for unit capacities against SOPT, making the new upper bound tight for b=1 and motivating the question."},{"cited_title":"Devanur, K","cited_arxiv_id":null,"evidence_quote":"supplies the primal-dual framework that the paper adapts to StochasticBalance with capacities."},{"cited_title":"Mehta, A","cited_arxiv_id":null,"evidence_quote":"shows the 1-1/e ceiling for AdWords when all probabilities are 1, which the corollary extends to stochastic rewards."}],"review_version":1}