Hostname: page-component-6bb9c88b65-zjgpb Total loading time: 0 Render date: 2025-07-23T07:58:18.787Z Has data issue: false hasContentIssue false
  • English
  • Français

Online matching for the multiclass stochastic block model

Part of: Markov processes Stability Graph theory Theory of computing Mathematical economics

Published online by Cambridge University Press:  21 July 2025

Nahuel Soprano-Loto ,
Matthieu Jonckheere  and
Pascal Moyal Open the ORCID record for Pascal Moyal [Opens in a new window]
Nahuel Soprano-Loto*
Affiliation:
LAAS-CNRS
Matthieu Jonckheere*
Affiliation:
LAAS-CNRS
Pascal Moyal*
Affiliation:
Université de Lorraine
*
*Postal address: LAAS-CNRS, 7 Av. du Colonel Roche, 31400 Toulouse, France.
*Postal address: LAAS-CNRS, 7 Av. du Colonel Roche, 31400 Toulouse, France.
****Postal address: Université de Lorraine, CNRS, Inria, IECL, F-54000 Nancy, France. Email: pascal.moyal@univ-lorraine.fr
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of sequential matching in a stochastic block model with several classes of nodes and generic compatibility constraints. When the probabilities of connections do not scale with the size of the graph, we show that under the Ncond condition, a simple max-weight type policy allows us to attain an asymptotically perfect matching while no sequential algorithm attains perfect matching otherwise. The proof relies on a specific Markovian representation of the dynamics associated with Lyapunov techniques.

Keywords

Online matchingrandom graphstochastic block modelMarkov chain

MSC classification

Primary: 05C80: Random graphs 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 91B68: Matching models 93D05: Lyapunov and other classical stabilities (Lagrange, Poisson, $L^p, l^p$, etc.) 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Information

Type
Original Article
Information
Journal of Applied Probability , First View , pp. 1 - 22
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Aoudi, M. H. A. D., Moyal, P. and Robin, V. (2022). Markovian online matching algorithms on large bipartite random graphs. Methodology Comput. Appl. Prob. 24, 3195–3225.10.1007/s11009-022-09973-yCrossRefGoogle Scholar
Aronson, J., Frieze, A. M. and Pittel, B. G. (1998). Maximum matchings in sparse random graphs: Karp–Sipser revisited. Random Structures Algorithms 12, 111–177.10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#3.0.CO;2-#>CrossRefGoogle Scholar
Begeot, J., Marcovici, I., Moyal, P. and Rahme, Y. (2021). A general stochastic matching model on multigraphs. ALEA Lat. Am. J. Prob. Math. Stat. 18, 1325–1351.10.30757/ALEA.v18-49CrossRefGoogle Scholar
Bordenave, C., Lelarge, M. and Salez, J. (2013). Matchings on infinite graphs. Prob. Theory Relat. Fields 157, 183–208.10.1007/s00440-012-0453-0CrossRefGoogle Scholar
Brémaud, P. (2020). Markov Chains – Gibbs Fields, Monte Carlo Simulation and Queues (Texts Appl. Math. 31), 2nd edn. Springer, Cham.10.1007/978-3-030-45982-6CrossRefGoogle Scholar
Cadas, A., Bušić, A. and Doncel, J. (2019). Optimal control of dynamic bipartite matching models. In Proc. 12th EAI Int, Conf. Performance Evaluation Methodologies and Tools, pp. 39–46.10.1145/3306309.3306317CrossRefGoogle Scholar
Cohen, I. R. and Wajc, D. (2018). Randomized online matching in regular graphs. In Proc. 29th Ann. ACM-SIAM Symp. Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 960–979.Google Scholar
Jonckheere, M., Moyal, P., Ramrez, C. and Soprano-Loto, N. (2023). Generalized max-weight policies in stochastic matching. Stoch. Systems 13, 40–58.10.1287/stsy.2022.0098CrossRefGoogle Scholar
Karp, R. M. and Sipser, M. (1981). Maximum matching in sparse random graphs. In Proc. 22nd Ann. Symp. Foundations of Computer Science, pp. 364–375.10.1109/SFCS.1981.21CrossRefGoogle Scholar
Karp, R. M., Vazirani, U. V. and Vazirani, V. V. (1990). An optimal algorithm for on-line bipartite matching. In Proc. 22nd Ann. ACM Symp. Theory of Computing. Association for Computing Machinery, New York, pp. 352–358.Google Scholar
Kerimov, S., Ashlagi, I. and Gurvich, I. (2021). Dynamic matching: Characterizing and achieving constant regret. SSRN Electron. J. 3824407.10.2139/ssrn.3824407CrossRefGoogle Scholar
Mairesse, J. and Moyal, P. (2016). Stability of the stochastic matching model. J. Appl. Prob. 53, 1064–1077.10.1017/jpr.2016.65CrossRefGoogle Scholar
Meyn, S. and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press.10.1017/CBO9780511626630CrossRefGoogle Scholar
Moyal, P. and Perry, O. (2017). On the instability of matching queues. Ann. Appl. Prob. 27, 3385–3434.10.1214/17-AAP1283CrossRefGoogle Scholar
Nazari, M. and Stolyar, A. L. (2019). Reward maximization in general dynamic matching systems. Queueing Systems 91, 143–170.10.1007/s11134-018-9593-yCrossRefGoogle Scholar
Noiry, N., Perchet, V. and Sentenac, F. (2021). Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm. In Proc. 35th Int. Conf. Neural Information Processing Systems, ed. Beygelzimer, A., Dauphin, Y., Liang, P. and Wortman Vaughan, J.. Association for Computing Machinery, New York, pp. 21400–21412.Google Scholar
Schrijver, A. (2003). Combinatorial Optimization. Polyhedra and Efficiency, vol. A (Algorithms and Combinatorics 24). Springer, Berlin.Google Scholar
Sentenac, F., Noiry, N., Lerasle, M., Ménard, L. and Perchet, V. (2023). Online matching in geometric random graphs. Preprint, arXiv:2306.07891.Google Scholar
Tutte, W. T. (1947). The factorization of linear graphs. J. London Math. Soc. 22, 107–111.10.1112/jlms/s1-22.2.107CrossRefGoogle Scholar