Online $b$-Matching with Stochastic Rewards

Sebastian Schubert; Susanne Albers

REVIEW 2 major objections 5 minor 20 references

Online $b$-Matching with Stochastic Rewards

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2411.16947 v1 pith:6A72WHRO submitted 2024-11-25 cs.DS

Susanne Albers , Sebastian Schubert This is my paper · ORCID

classification cs.DS MSC 68W2768R1090C27

keywords onlineb-matchingstochasticrewardscompetitiveratioBalanceprimal-dualanalysisvanishingprobabilitiesAdWordsbipartitematching

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

And 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.

The 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.

Who 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.

Recommendation: 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 2, Lemma 1] 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 2, Lemmas 2 and 7; Theorem 1] 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.

minor comments (5)

[Section 2, Lemma 2] 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 3, Lemma 14] 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 2, proof of Lemma 4] 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 2, before Lemma 1] 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.
[Abstract and Corollary 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the bounds are derived from explicit adversarial constructions and primal-dual certificates; the only flagged gap (unproved b>1 extension of an external lemma) is a correctness risk, not circular reasoning.

full rationale

I walked the derivation chain for both main claims. Theorem 1 (the 1-1/e upper bound against SOPT) is obtained as follows: Lemma 1 asserts that StochasticBalance is optimal on the constructed family G_b_n, citing Lemma 12 of Mehta and Panigrahi [15] and stating that 'their proof also works for all values of b.' This is an omitted proof for b>1 and it is load-bearing, but it is not circular: [15] is prior external work, not a self-citation, and the asserted extension is not equivalent to the theorem being proved. The remainder of Section 2 is a direct analytic computation: Lemma 2 uses the Poisson limit theorem to characterize the per-round number of successes, Lemma 3 upper-bounds the per-server expected reward, Lemma 4 evaluates the harmonic sum to (1-1/e), and Lemmas 5-7 compute the GREEDY lower bound on SOPT by solving an explicit recurrence and applying Stirling's approximation. No parameter is fitted to the target ratio; no quantity is defined in terms of itself. Theorem 2 (StochasticBalance is (1-1/e)-competitive as b tends to infinity) is established by a standard primal-dual certificate: the algorithm and dual variables are defined, the function f(x)=e^{x/b-1} and c=1-1/e are chosen, and Lemmas 8-14 verify dual feasibility directly via integral lower bounds, summation by parts, and Chebyshev's inequality. This is a guessed certificate that is then independently verified, not a fitted input renamed as a prediction. I also checked for self-citations: the paper cites [8,10,15] for prior techniques, but none of these citations is authored by Albers and Schubert, and none replaces a proof step in the present derivation. The only item worth flagging under the reviewing rule is the unproved claim that Mehta and Panigrahi's optimality proof 'also works for all values of b'; that is a correctness/robustness gap to weigh in a technical review, but it does not make the paper's derivation circular. The central claims retain independent mathematical content and are tested against external benchmarks (OPT and SOPT) that are not defined in terms of the algorithm's own performance. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

No new physical entities are introduced. The only design choice is the function f in the generalized StochasticBalance algorithm, which is an analysis parameter rather than a fitted constant. The proofs rest on standard LP duality, the cited optimality lemma, and classical concentration inequalities.

free parameters (1)

dual-fitting function f(x) = f(x)=e^(x/b-1) for x<=b, f(x)=1 for x>b
Chosen by hand in Section 3 to make the primal-dual integral evaluate to the target competitiveness 1-1/e; it is an algorithm design and analysis parameter, not an empirical fit.

assumptions (6)

domain assumption StochasticBalance is optimal for graph family G_b_n for all n and b (Lemma 1, citing Lemma 12 of [15]).
Load-bearing for the upper bound; proof not included and extension to b>1 asserted.
domain assumption The stochastic benchmark SOPT is upper bounded by the non-stochastic benchmark OPT (Golrezaei et al. [6]).
Used to transfer bounds between benchmarks.
standard math Vertex splitting turns b-matching into unit-capacity matching with no loss in SOPT.
Used in the proof of Theorem 1; standard reduction.
standard math LP weak duality and the primal-dual framework of Devanur et al.
Core of Section 3, relating primal and dual LP values.
standard math Poisson limit theorem: Binomial(b/p,p) converges to Poisson(b) as p goes to 0.
Used in Lemma 2 for vanishing probabilities.
standard math Chebyshev's inequality and the variance bound for Poisson binomial distributions.
Used in Lemma 13 for concentration of successes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Online $b$-Matching with Stochastic Rewards." pith.science (2026). https://pith.science/paper/6A72WHRO

@misc{pith2026241116947,
  author       = {Pith},
  title        = {Pith review of: Online $b$-Matching with Stochastic Rewards},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6A72WHRO}},
  note         = {Machine review of arXiv:2411.16947}
}

abstract

The $b$-matching problem is an allocation problem where the vertices on the left-hand side of a bipartite graph, referred to as servers, may be matched multiple times. In the setting with stochastic rewards, an assignment between an incoming request and a server turns into a match with a given success probability. Mehta and Panigrahi (FOCS 2012) introduced online bipartite matching with stochastic rewards, where each vertex may be matched once. The framework is equally interesting in graphs with vertex capacities. In Internet advertising, for instance, the advertisers seek successful matches with a large number of users. We develop (tight) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms, for $b$-matching with stochastic rewards. Our bounds hold for both offline benchmarks considered in the literature. As in prior work, we first consider vanishing probabilities. We show that no randomized online algorithm can achieve a competitive ratio greater than $1-1/e\approx 0.632$, even for identical vanishing probabilities and arbitrary uniform server capacities. Furthermore, we conduct a primal-dual analysis of the deterministic \textsc{StochasticBalance} algorithm. We prove that it achieves a competitive ratio of $1-1/e$, as server capacities increase, for arbitrary heterogeneous non-vanishing edge probabilities. This performance guarantee holds in a general setting where servers have individual capacities and for the vertex-weighted problem extension. To the best of our knowledge, this is the first result for \textsc{StochasticBalance} with arbitrary non-vanishing probabilities. We remark that our impossibility result implies in particular that, for the AdWords problem, no online algorithm can be better than $(1-1/e)$-competitive in the setting with stochastic rewards.

Figures

Figures reproduced from arXiv: 2411.16947 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[15]

Mehta and D

A. Mehta and D. Panigrahi. Online matching with stochas tic rewards. In Proc. 53rd Annual IEEE Sym- posium on F oundations of Computer Science (FOCS), pages 728–737, 2012

work page 2012
[1]

Aggarwal, G

G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online ver tex-weighted bipartite matching and single- bid budgeted allocations. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA), pages 1253–1264. SIAM, 2011

work page 2011
[2]

Birnbaum and C

B.E. Birnbaum and C. Mathieu. On-line bipartite matchin g made simple. SIGACT News, 39(1):80–87, 2008

work page 2008
[3]

Buchbinder, K

N. Buchbinder, K. Jain, and J. Naor. Online primal-dual a lgorithms for maximizing ad-auctions rev- enue. In Proc. 15th Annual European Symposium on Algorithms (ESA) , volume 4698 of Lecture Notes in Computer Science, pages 253–264. Springer, 2007

work page 2007
[4]

Buchbinder, J

N. Buchbinder, J. Naor, and D. Wajc. Lossless online roun ding for online bipartite matching (despite its impossibility). In Proc. 34th ACM-SIAM Symposium on Discrete Algorithms (SODA ), pages 2030–2068. SIAM, 2023

work page 2023
[5]

Devanur, K

N.R. Devanur, K. Jain, and R.D. Kleinberg. Randomized pr imal-dual analysis of RANKING for online bipartite matching. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA), pages 101–107, 2013. 15

work page 2013
[6]

Golrezaei, H

N. Golrezaei, H. Nazerzadeh, and P . Rusmevichientong. R eal-time optimization of personalized assort- ments. Manag. Sci., 60(6):1532–1551, 2014

work page 2014
[7]

Goyal and R

V . Goyal and R. Udwani. Online matching with stochastic r ewards: Optimal competitive ratio via path- based formulation. Oper . Res., 71(2):563–580, 2023

work page 2023

Show all 20 references

[8]

Huang, H

Z. Huang, H. Jiang, A. Shen, J. Song, Z. Wu, and Q. Zhang. On line matching with stochastic rewards: Advanced analyses using conﬁguration linear programs. In Proc. 19th International Conference on Web and Internet Economics (WINE) , volume 14413 of Lecture Notes in Computer Sc...

2023
[9]

Huang and T

Z. Huang and T. Tr¨ obst. Applications of online matching . In F. Echenique, N. Immorlica, and V .V . V azirani, editors, Online and Matching-Based Market Design , pages 109–129. Cambridge University Press, 2023

2023
[10]

Huang and Q

Z. Huang and Q. Zhang. Online primal dual meets online ma tching with stochastic rewards: conﬁguration LP to the rescue. In Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1153–1164, 2020

2020
[11]

Huang, Q

Z. Huang, Q. Zhang, and Y . Zhang. Adwords in a panorama. I n Proc. 61st IEEE Annual Symposium on F oundations of Computer Science (FOCS), pages 1416–1426, 2020

2020
[12]

Kalyanasundaram and K

B. Kalyanasundaram and K. Pruhs. An optimal determinis tic algorithm for online b-matching. Theor . Comput. Sci., 233(1-2):319–325, 2000

2000
[13]

Karp, U.V

R.M. Karp, U.V . V azirani, and V .V . V azirani. An optimal algorithm for on-line bipartite matching. In Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC ), pages 352–358, 1990

1990
[14]

A. Mehta. Online matching and ad allocation. F ound. Trends Theor . Comput. Sci., 8(4):265–368, 2013

2013
[16]

Mehta, A

A. Mehta, A. Saberi, U.V . V azirani, and V .V . V azirani. A dwords and generalized online matching. J. ACM, 54(5):22, 2007

2007
[17]

Mehta, B

A. Mehta, B. Waggoner, and M. Zadimoghaddam. Online sto chastic matching with unequal probabilities. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA), pages 1388–1404. SIAM, 2015

2015
[18]

R. Udwani. Adwords with unknown budgets and beyond. In Proc. 24th ACM Conference on Economics and Computation (RC) , page 1128. ACM, 2023

2023
[19]

R. Udwani. When stochastic rewards reduce to determini stic rewards in online bipartite matching. In Proc. 6th Symposium on Simplicity in Algorithms (SOSA) , pages 321–330. SIAM, 2024

2024
[20]

Online matching with stochastic rewards: Provable better bound via adversarial reinforcement learning

Qiankun Zhang, Aocheng Shen, Boyu Zhang, Hanrui Jiang, and Bingqian Du. Online matching with stochastic rewards: Provable better bound via adversarial reinforcement learning. In F orty-ﬁrst Interna- tional Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27,...

2024

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [15]

Mehta and D

A. Mehta and D. Panigrahi. Online matching with stochas tic rewards. In Proc. 53rd Annual IEEE Sym- posium on F oundations of Computer Science (FOCS), pages 728–737, 2012

work page 2012

[2] [1]

Aggarwal, G

G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online ver tex-weighted bipartite matching and single- bid budgeted allocations. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA), pages 1253–1264. SIAM, 2011

work page 2011

[3] [2]

Birnbaum and C

B.E. Birnbaum and C. Mathieu. On-line bipartite matchin g made simple. SIGACT News, 39(1):80–87, 2008

work page 2008

[4] [3]

Buchbinder, K

N. Buchbinder, K. Jain, and J. Naor. Online primal-dual a lgorithms for maximizing ad-auctions rev- enue. In Proc. 15th Annual European Symposium on Algorithms (ESA) , volume 4698 of Lecture Notes in Computer Science, pages 253–264. Springer, 2007

work page 2007

[5] [4]

Buchbinder, J

N. Buchbinder, J. Naor, and D. Wajc. Lossless online roun ding for online bipartite matching (despite its impossibility). In Proc. 34th ACM-SIAM Symposium on Discrete Algorithms (SODA ), pages 2030–2068. SIAM, 2023

work page 2023

[6] [5]

Devanur, K

N.R. Devanur, K. Jain, and R.D. Kleinberg. Randomized pr imal-dual analysis of RANKING for online bipartite matching. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithm s (SODA), pages 101–107, 2013. 15

work page 2013

[7] [6]

Golrezaei, H

N. Golrezaei, H. Nazerzadeh, and P . Rusmevichientong. R eal-time optimization of personalized assort- ments. Manag. Sci., 60(6):1532–1551, 2014

work page 2014

[8] [7]

Goyal and R

V . Goyal and R. Udwani. Online matching with stochastic r ewards: Optimal competitive ratio via path- based formulation. Oper . Res., 71(2):563–580, 2023

work page 2023