Pith. sign in

REVIEW 3 major objections 7 minor 48 references

Online matching on stochastic block model

T0 review · 3 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read In sparse stochastic block models, two online matching policies have explicit deterministic large-system limits, and a bandit variant with unknown affinities keeps regret sublinear.

desk verdict Differential-inclusion fluid limits for online matching are a real contribution, but the regret theorem is not proven. read the letter →

arxiv 2506.04921 v1 pith:HJG2DV6Y submitted 2025-06-05 cs.DS

Maria Cherifa (MAP5 , CREST) , Clément Calauzènes , Vianney Perchet (CREST) This is my paper
classification cs.DS
keywords onlinebipartitematchingstochasticblockmodelsparseregimedifferentialinclusionfluidlimitregretboundexploration-exploitationgreedy
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

This paper studies online bipartite matching when edges follow a sparse stochastic block model: every offline node has a latent class, every arriving node has a latent class, and the chance of an edge depends only on the two classes. It claims that two simple, practical policies have deterministic large-system limits. The Myopic policy, which always tries to match into the class with the best static compatibility, concentrates with high probability around the solution of an explicit ODE; the paper also gives a closed-form approximation to that solution with explicit error bounds. The Ex-ante Balance policy, which picks the class whose remaining capacity makes a match most likely, concentrates around the unique solution of a differential inclusion—the set-valued generalization of an ODE needed when the decision rule is discontinuous—and the paper derives an explicit multi-phase formula for that solution. When the class affinities are unknown, an explore-then-commit bandit variant learns them online and keeps its regret at $O(T^{(q+3)/4})$ for $0

What carries the argument

The load-bearing object is the drift map $f_{c,b_c}(x)=\sum_{d=1}^D (1-e^{-a_{c,d}(b_c-x)})\nu(d)$, the probability that the next arrival connects to at least one still-free node of class $c$ when a fraction $x$ of class $c$'s budget has been matched. For Myopic, the random class choice is replaced by a fixed optimal transport plan $Q^*$, which makes the drift Lipschitz and the fluid limit an ODE. For Balance, the selection rule is the argmax of these drifts, a discontinuous function of the state; the limit is therefore a differential inclusion whose right-hand side is the convex hull of the drifts of the currently best classes. The paper resolves the inclusion explicitly by a phase construction: in phase $k$, the $k$ best classes keep their drifts equalized, decreasing at a common rate, until a new class joins, with phase times $t_k$ and residual budgets $\beta^{(k)}$ defined recursively and the phase curve $\mu_{k,\beta}$ solving a separable ODE.

What would settle it

Simulate the Ex-ante Balance policy on a symmetric two-class sparse SBM and record, at each step, the gap between the two classes' per-step match probabilities; if the gap tends to zero and stays at zero inside the phase, the margin condition used in the regret proof cannot hold, and the $O(T^{(q+3)/4})$ regret result would require a different argument. A second check is to compute the empirical average of the perturbation term $(1/N)\sum_t \Delta_{c,b_c,N}(\hat M_c(t))$ in the ETC-balance process: if it does not vanish, the learned trajectory does not track the same differential inclusion as Ex-ante Balance.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the normalized class-wise matching counts of natural greedy policies in a sparse bipartite stochastic block model have deterministic limits. For the Myopic policy, $M_c(t)/N$ is within $3L_c e^{\alpha L_c}/N^{1/3}$ of the solution $y_c$ of the ODE $\dot y_c(s)=\sum_{d=1}^D (1-e^{-a_{c,d}(b_c-y_c(s))})Q^*(c,d)$, $y_c(0)=0$, with probability at least $1-2C e^{-N^{1/3}L_c^2/8\alpha}$; the ODE solution is approximated by $\tilde y_c(t)=b_c-b_c e^{-tL_c}$ with error at most $J_c(1-e^{-L_c t})/L_c$. For Ex-ante Balance, the normalized counts converge with high probability to the unique solution $m$ of the differential inclusion $\dot m \in \operatorname{conv}\{f_{c,b_c}(m_c)e_c : c\in \arg\max_k f_{k,b_k}(m_k)\}$, where $f_{c,b_c}(x)=\sum_{d=1}^D (1-e^{-a_{c,d}(b_c-x)})\nu(d)$; the paper constructs the limiting trajectory explicitly as a sequence of phases in which the currently best classes have equalized drifts, giving the closed-form formula $m^*_c(t)$. The availability-aware Ex-post Balance policy converges to a similar inclusion with an added capacity constraint $b_c>m_c$. Finally, when affinities are unknown, the ETC-balance policy has regret $O(T^{(q+3)/4})$ relative to Ex-ante Balance with known affinities.

Load-bearing premise

The regret bound rests on the assumption that at every exploitation step the estimated best class beats the others by a positive margin at least $4ea\sqrt{\log(2/\delta)/(2T_{\text{total}})}$ and that enough samples have accumulated for the estimates to concentrate; the paper does not establish these conditions, and the limiting phase solution has the top classes exactly tied, so the margin premise fails exactly where the differential inclusion has non-unique direction.

Editorial extensions

If this is right

  • If Theorem 1 is right, the Myopic policy's class-wise matching size is predictable at scale: the high-probability $N^{-1/3}$ concentration turns a stochastic process into a deterministic curve, and the closed-form surrogate $\tilde y_c$ can be evaluated without solving the ODE.
  • If Theorems 2 and 3 are right, Ex-ante Balance's trajectory in the sparse SBM is computable in closed form from the affinity matrix $a_{c,d}$, the budgets $b_c$, and the arrival distribution $\nu$, including the phase boundaries where the best class switches.
  • If Theorem 5 is right, verifying availability before choosing a class changes the limit only through the capacity constraint $b_c>m_c$, so the same differential-inclusion machinery covers both the ex-ante and ex-post variants.
  • If Theorem 4 is right, learning affinities online with explore-then-commit loses at most $O(T^{(q+3)/4})$ matches compared with knowing them, so the exploration-exploitation trade-off in this matching problem is sublinear.

Reading between the lines

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

  • The explicit phase solution implies that in the limit the active classes are exactly tied on their drifts, so the margin assumption behind the regret proof is not merely unverified: the limiting system violates it inside every phase. A correct regret argument will need to control the near-tie discrete fluctuations rather than assume a positive gap.
  • The convex-hull-of-argmax-drifts construction is a general recipe for other online allocation problems with discontinuous argmax policies—budgeted ad allocation, load balancing, or matching with estimated rewards—where multi-phase equalization formulas could be derived by the same inverse-drift machinery.
  • Because the paper reports that a UCB variant performs better empirically but leaves its analysis open, a natural next step is to run the same differential-inclusion machinery on UCB's confidence-set dynamics and compare its regret rate with the $T^{(q+3)/4}$ rate proven for ETC-balance.
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.

Referee Report

3 major / 7 minor

Summary. The paper studies online bipartite matching on a sparse bipartite stochastic block model. Offline nodes carry latent classes, online arrivals carry latent types, and edges are present independently with probability a_{c,d}/N, with T = alpha N. When the affinity matrix is known, the authors prove that the Myopic policy's class-wise matching counts concentrate around the solution of an ODE (Theorem 1), provide a closed-form approximation of that ODE with explicit error bounds, and prove that the Ex-ante Balance algorithm's matching counts concentrate around the solution of a differential inclusion (Theorem 2). They give an explicit multi-phase solution of that inclusion (Theorem 3) and extend the convergence statement to an Ex-post Balance variant (Theorem 5). When the affinities are unknown, they introduce an Explore-Then-Commit variant, ETC-balance, and claim regret O(T^{(q+3)/4}) against Ex-ante Balance (Theorem 4).

Significance. If fully established, the paper would provide a useful fluid-limit framework for online matching in structured random graphs. The Myopic analysis is a legitimate Wormald-type argument with explicit non-asymptotic bounds and a tractable surrogate ODE; the differential-inclusion formulation of Balance and the closed-form phase solution are genuinely novel and likely to be influential. The paper also gives concrete, checkable statements about finite-N concentration rather than only abstract convergence. However, the advertised bandit regret result is currently not proved: the proof of Theorem 4 relies on unproved margin and sample-size hypotheses that fail at the tie points of the limiting solution, and the estimator concentration lemma is not valid as stated. The core known-parameter results are plausible and worth publishing once the technical gaps below are addressed.

major comments (3)
  1. [Appendix D, Lemma 20 and Eq. (129)] The proof of Theorem 4 requires that at every exploitation step the true argmax class be separated from all others by a margin psi at least 4ea sqrt(log(2/delta)/(2 T_total)). No argument establishes such a margin. In the limiting solution of Theorem 3, the active classes in a phase are exactly tied, so the continuous margin is zero; in the discrete process the gap at a tie is of order a/N, whereas the required radius with T_total = Theta(T) = Theta(N) is of order sqrt(log N / N), which is larger by a factor of order sqrt(N log N). Thus the margin hypothesis fails precisely where the differential inclusion has non-unique direction, and the bound on the indicator mismatch, and hence on the term w3 in Eq. (104), is unsupported. The claimed regret bound O(T^{(q+3)/4}) is therefore not established as stated.
  2. [Appendix C.1, Lemma 7 and Eq. (52)] The proof of Lemma 7 expands e^{alpha_c (N b_c - y)} as e^{alpha_c N b_c}(1 + alpha_c y). Since alpha_c = ln(1 - min_j a_{c,j}/N) is negative, the linear term has the wrong sign: the correct first-order expression is e^{alpha_c N b_c}(1 - alpha_c y + O(y^2)). The written inequality does not follow, so the proof of the bound |H_{c,b_c,N}(y)| <= c(1+|y|) is invalid as it stands. This bound is used in Lemma 11 and in the verification of the assumptions of Gast-Gaujal's Theorem 1, so the proof of Theorem 2 needs a corrected version of this lemma.
  3. [Appendix D, Lemma 18] Lemma 18 claims that Theta(m) is a sum of independent Bernoulli random variables and applies Hoeffding's inequality. This is not valid: the indicators {c(t)=c, d(t)=d, M_c(t)=m'} and the rewards Y_{c,d,m'}(t) depend on all past decisions, which in turn depend on past rewards, so the sampled variables are not independent. In addition, the sample size T_total is random and may be zero or too small for the estimator to concentrate; no lower bound on T_total is provided. Since Lemma 18 is the only concentration input used to control the perturbation Delta in Lemma 20, this is a second independent gap in the proof of Theorem 4.
minor comments (7)
  1. [Section 3.1] The sentence introducing the estimator contains an unresolved placeholder: 'whose form and concentration properties are given in ??'. It should cite Appendix D explicitly.
  2. [Figure 1 caption] The caption refers to 'the confidence set from ??' and to a UCB version of Balance that is not defined anywhere in the paper; these references should be resolved or removed.
  3. [Theorem 3] The statement contains a typo: 'is thel solution' should read 'is the solution'.
  4. [Theorem 1] The notation mixes s and t: the ODE in Eq. (1) is written for y_c(s), but the approximation formula is then stated in terms of t. Please unify the time variable.
  5. [Algorithm 3, line 8] The quantity s(m) = b_c/(b_c - m/N) is defined but never used; it should be removed or its role explained.
  6. [Lemma 19] The proof assumes alpha > 1, whereas the model only states alpha > 0. Either assume alpha > 1 explicitly throughout or adjust the statement of the lemma.
  7. [Abstract and Section 2] The abstract refers to the 'Balance algorithm' while Section 2 introduces 'Ex-ante Balance'; please standardize the terminology.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the fluid limits are derived from the stated stochastic model via external limit theorems, and the unproved margin condition in Appendix D is a correctness gap, not a circular step.

full rationale

The paper's central derivations are self-contained in the relevant sense. For Myopic, Lemma 1 computes the one-step conditional drift directly from the model, and Theorem 1 applies Wormald's external differential-equation method to that drift; the approximate solution tilde-y_c is obtained by linearizing the derived ODE and bounding the error with a comparison principle, so it is not a fitted input renamed as a prediction. For Ex-ante Balance, Lemma 5 computes the drift with the argmax indicator, and Theorem 2 applies the external Gast-Gaujal differential-inclusion limit theorem to that drift; Theorem 3 verifies the explicit phase formula m* against the same differential inclusion, and uniqueness comes from a one-sided Lipschitz argument rather than from an imported uniqueness theorem by the present authors. The regret analysis in Theorem 4 is not circular by construction: it decomposes regret against Ex-ante Balance, whose dynamics were derived independently, and the O(T^{(q+3)/4}) rate is partly a consequence of choosing Texplore = T^{(q+3)/4}, while the exploitation terms are intended to be controlled by the fluid-limit results. The genuine weakness is Appendix D: Lemma 20 requires the unproved margin hypothesis in Eq. (129), and at the phase ties of the limiting differential inclusion the gap is of order a/N while the required concentration radius is of order sqrt(log N / N), so the lemma's hypothesis is not established and the w3 term is unsupported. That is a correctness gap in Theorem 4, not a reduction of the theorem to its own assumptions. The only self-citations, such as [12] and [39], appear as background context in the related-work discussion and are not load-bearing for any theorem.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new physical or probabilistic entities; it works with the existing SBM latent classes and standard limit theorems. The main burden is carried by the sparse-scaling domain assumption and by two unproven ad hoc assumptions in the regret proof (positive margin, sufficient triplet counts). The only hand-chosen numeric parameters are the proof slack epsilon and the exploration exponent q, neither fitted to data.

free parameters (2)
  • epsilon (concentration slack) = epsilon^2 = N^{-(1-q)} in the proof of Theorem 4
    Introduced in Theorem 2 as an arbitrary slack controlling the concentration probability 1 - b alpha / (N epsilon^2); later set to N^{-(1-q)/2} to obtain the regret rate. Chosen by hand, not fitted to data.
  • q (exploration exponent) = 0 < q < 1, T_explore = T^{(q+3)/4}
    Design parameter for the length of the exploration phase; the regret bound O(T^{(q+3)/4}) holds for any q in (0,1), so it is not fitted to data.
assumptions (7)
  • standard math Wormald's differential equation method
    Used to prove Theorem 1 concentration of Myopic around the ODE; cited as [43,44].
  • standard math Gast-Gaujal theorem on Markov chains with discontinuous drifts
    The core tool for Theorem 2 and Theorem 5, providing convergence to differential inclusions; cited as [16].
  • standard math Existence and uniqueness of differential inclusions with one-sided Lipschitz set-valued maps
    Appendix A, used to guarantee a unique limiting solution for the Balance inclusion.
  • domain assumption Sparse regime p(c,d)=a_{c,d}/N with uniformly bounded a_{c,d}
    Section 1 defines the model; all fluid limits and error rates depend on this scaling.
  • domain assumption Conditional exchangeability of offline nodes within a class
    The drift calculations (Lemmas 1 and 5) use that given M_c(t), each free node in class c has the same edge probability (1-a/N)^{N b_c - M_c(t)} to the next arrival.
  • ad hoc to paper Positive margin psi between the top and second drift in the exploitation phase
    Lemma 20 requires a separation psi at least 4ea sqrt(log(2/delta)/(2 T_total)) for the argmax not to flip; this is not proven and fails for the exactly tied active classes in the limiting phase solution.
  • ad hoc to paper Enough observations T_total in every neighborhood V_m for the estimator
    Lemmas 17-18 define hat D_{c,d}(m) only when T_total > 0 and rely on Hoeffding over T_total i.i.d. samples; no lower bound on T_total across all states m is proven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online matching on stochastic block model." pith.science (2026). https://pith.science/paper/HJG2DV6Y

@misc{pith2026250604921,
  author       = {Pith},
  title        = {Pith review of: Online matching on stochastic block model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HJG2DV6Y}},
  note         = {Machine review of arXiv:2506.04921}
}
abstract

While online bipartite matching has gained significant attention in recent years, existing analyses in stochastic settings fail to capture the performance of algorithms on heterogeneous graphs, such as those incorporating inter-group affinities or other social network structures. In this work, we address this gap by studying online bipartite matching within the stochastic block model (SBM). A fixed set of offline nodes is matched to a stream of online arrivals, with connections governed probabilistically by latent class memberships. We analyze two natural algorithms: a $\tt{Myopic}$ policy that greedily matches each arrival to the most compatible class, and the $\tt{Balance}$ algorithm, which accounts for both compatibility and remaining capacity. For the $\tt{Myopic}$ algorithm, we prove that the size of the matching converges, with high probability, to the solution of an ordinary differential equation (ODE), for which we provide a tractable approximation along with explicit error bounds. For the $\tt{Balance}$ algorithm, we demonstrate convergence of the matching size to a differential inclusion and derive an explicit limiting solution. Lastly, we explore the impact of estimating the connection probabilities between classes online, which introduces an exploration-exploitation trade-off.

Figures

Figures reproduced from arXiv: 2506.04921 by the authors.

Figure 1
Figure 1. Illustration of the matching size for the different methods. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

48 extracted references · 44 canonical work pages

  1. [1]

    Aamand, J

    A. Aamand, J. Y . Chen, and P. Indyk. (optimal) online bipartite matching with degree in- formation. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022

    work page 2022

  2. [2]

    E. Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2018

    work page 2018

  3. [3]

    E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing. Mixed membership stochastic blockmodels. In Advances in Neural Information Processing Systems (NeurIPS), 2008

    work page 2008

  4. [4]

    Aubin and A

    J.-P. Aubin and A. Cellina. Differential Inclusions: Set-Valued Maps and Viability Theory , volume 264 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1984

    work page 1984

  5. [5]

    Bollobás

    B. Bollobás. Random Graphs. Cambridge University Press, 2001

    work page 2001

  6. [6]

    S. P. Borgatti and M. G. Everett. Models of core/periphery structures. Social Networks, 21(4): 375–395, 2000

    work page 2000

  7. [7]

    Borodin, C

    A. Borodin, C. Karavasilis, and D. Pankratov. Greedy bipartite matching in random type poisson arrival model, 2018

    work page 2018

  8. [8]

    Borodin, C

    A. Borodin, C. Karavasilis, and D. Pankratov. An experimental study of algorithms for online bipartite matching. ACM J. Exp. Algorithmics, 25, mar 2020. ISSN 1084-6654. doi: 10.1145/ 3379552

    work page 2020

Show all 48 references
  1. [9]

    Borodin, C

    A. Borodin, C. MacRury, and A. Rakheja. Bipartite stochastic matching: Online, random order, and i.i.d. models. 04 2020. doi: 10.48550/arXiv.2004.14304

    2020 doi arXiv

  2. [10]

    Brandenberger, B

    A. Brandenberger, B. Chin, N. S. Sheffield, and D. Shyamal. Matching Algorithms in the Sparse Stochastic Block Model. In C. Mailler and S. Wild, editors, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2...

    2024 doi

  3. [11]

    Brubach, K

    B. Brubach, K. A. Sankararaman, A. Srinivasan, and P. Xu. Online stochastic matching: New algorithms and bounds. Algorithmica, 82:2737 – 2783, 2016

    2016

  4. [12]

    Cherifa, C

    M. Cherifa, C. Calauzenes, and V . Perchet. Dynamic online matching with budget refills. 05

  5. [13]

    N. R. Devanur, K. Jain, and R. D. Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, page 101–107, USA, 2013. Society for Industrial and Applied Ma...

    2013

  6. [14]

    M. Dyer, A. Frieze, and B. Pittel. The average performance of the greedy matching algorithm. The Annals of Applied Probability, 3(2):526–552, 1993

    1993

  7. [15]

    A. F. Filippov. Differential Equations with Discontinuous Right-Hand Sides , volume 18 of Mathematics and Its Applications (Soviet Series) . Kluwer Academic Publishers, Dordrecht,

  8. [16]

    Gast and B

    N. Gast and B. Gaujal. Markov chains with discontinuous drifts have differential inclusions limits. Application to stochastic stability and mean field approximation. Research Report RR-7315, Apr. 2011. 10

    2011

  9. [17]

    C. D. Godsil. Matchings and walks in graphs. J. Graph Theory, 5:285–297, 1981

    1981

  10. [18]

    Goel and A

    G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA ’08, page 982–991, USA, 2008. Society for Industrial and Applied Mathematics

    2008

  11. [19]

    E. F. Grove, M.-Y . Kao, P. Krishnan, and J. S. Vitter. Online perfect matching and mobile computing. In Algorithms and Data Structures: 4th International Workshop, WADS’95 Kingston, Canada, August 16–18, 1995 Proceedings 4, pages 194–205. Springer, 1995

    1995

  12. [20]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983

    1983

  13. [21]

    Huang, X

    Z. Huang, X. Shu, and S. Yan. The power of multiple choices in online stochastic matching. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 91–103, New York, NY , USA, 2022. Association for Computing Machinery. ISBN 9781450392648. ...

    2022

  14. [22]

    Huang, Z

    Z. Huang, Z. G. Tang, and D. Wajc. Online matching: A brief survey. SIGecom Exch., 22(1): 135–158, Oct. 2024. doi: 10.1145/3699824.3699837

    2024

  15. [23]

    Jaillet and X

    P. Jaillet and X. Lu. Online stochastic matching: New algorithms with better bounds. Mathe- matics of Operations Research, 39(3):624–646, 2014. ISSN 0364765X, 15265471

    2014

  16. [24]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruci´nski. Random Graphs. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2011

    2011

  17. [25]

    R. M. Karp, U. V . Vazirani, and V . V . Vazirani. An optimal algorithm for on-line bipartite match- ing. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC ’90, page 352–358, New York, NY , USA, 1990. Association for Computing Machinery. ISB...

    1990

  18. [26]

    Karrer and M

    B. Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83(1):016107, 2011

    2011

  19. [27]

    H. K. Khalil. Nonlinear systems; 3rd ed. Prentice-Hall, Upper Saddle River, NJ, 2002. The book can be consulted by contacting: PH-AID: Wallet, Lionel

    2002

  20. [28]

    Kim and S

    M. Kim and S. Oh. Stochastic blockmodel with cluster-dependent connection probabilities for modeling bipartite networks. Journal of Machine Learning Research, 21(234):1–43, 2020

    2020

  21. [29]

    M. Kunze. Non-Smooth Dynamical Systems, volume 1744 of Lecture Notes in Mathematics. Springer, Berlin, 2000. ISBN 978-3-540-67993-6. doi: 10.1007/BFb0103843

    2000 doi

  22. [30]

    Lattimore and C

    T. Lattimore and C. Szepesvari. Bandit Algorithms. 2019

    2019

  23. [31]

    Lovász and M

    L. Lovász and M. D. Plummer. Matching Theory, volume 367. American Mathematical Society, 2009

    2009

  24. [32]

    Mahdian and Q

    M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 597–606, New York, NY , USA, 2011. Association for Computing...

    2011

  25. [33]

    V . H. Manshadi, S. O. Gharan, and A. Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4):559–573, 2012. ISSN 0364765X, 15265471

    2012

  26. [34]

    Mastin and P

    A. Mastin and P. Jaillet. Greedy online bipartite matching on random graphs. 07 2013

    2013

  27. [35]

    Mastin and P

    A. Mastin and P. Jaillet. Greedy online bipartite matching on random graphs. ArXiv, abs/1307.2536, 2013

    2013 arXiv

  28. [36]

    McPherson, L

    M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415–444, 2001. 11

    2001

  29. [37]

    A. Mehta. 2013. doi: 10.1561/0400000057

    2013 doi

  30. [38]

    A. Mehta. Online matching and ad allocation. 8 (4):265–368, 2013

    2013

  31. [39]

    Noiry, V

    N. Noiry, V . Perchet, and F. Sentenac. Online matching in sparse random graphs: Non- asymptotic performances of greedy algorithm. In A. Beygelzimer, Y . Dauphin, P. Liang, and J. W. Vaughan, editors,Advances in Neural Information Processing Systems, 2021

    2021

  32. [40]

    Schrijver

    A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency , volume 24. Springer Science & Business Media, 2003

    2003

  33. [41]

    Slivkins

    A. Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12(1–2):1–286, Nov. 2019. ISSN 1935-8237. doi: 10.1561/2200000068

    2019 doi

  34. [42]

    Soprano-Loto, M

    N. Soprano-Loto, M. Jonckheere, and P. Moyal. Online matching for the multiclass stochastic block model. arXiv preprint arXiv:2303.15374, 2023

    2023

  35. [43]

    L. Warnke. On wormald’s differential equation method. ArXiv, abs/1905.08928, 2019

    1905 arXiv

  36. [44]

    N. C. Wormald. Differential equations for random processes and random graphs. Annals of Applied Probability, 5:1217–1235, 1995

    1995

  37. [45]

    Zdeborová and M

    L. Zdeborová and M. Mézard. The number of matchings in random graphs.Journal of Statistical Mechanics: Theory and Experiment, 2006(05):P05003, may 2006. doi: 10.1088/1742-5468/ 2006/05/P05003. 12 A Differential inclusions This section aims to introduce the fundamental concepts...

    2006 doi

  38. [48]

    Then (Qc(t))t∈[T ] is a martingale difference sequence with respect to the filtration generated by M(t)

    − Mc(t)|M(t), B]. Then (Qc(t))t∈[T ] is a martingale difference sequence with respect to the filtration generated by M(t). Moreover, there exists a constantb >0 such that: E[Qc(t + 1)|M(t), B] = 0 and E[|Qc(t + 1)|2|M(t), B] ≤ b Proof. By direct computation, we obtain E[Qc(t +...

  39. [1988]

    Translated from the Russian

  40. [2024]

    doi: 10.48550/arXiv.2405.09920

    doi arXiv

Pith tools

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