On the sub-additivity of stochastic matching

P. Moyal (), A. Bušić and J. Mairesse
Additional contact information
P. Moyal: Université de Lorraine/INRIA
A. Bušić: INRIA/ENS
J. Mairesse: CNRS/Université Pierre et Marie Curie

Queueing Systems: Theory and Applications, 2024, vol. 107, issue 3, No 4, 295-339

Abstract: Abstract We consider a stochastic matching model with a general compatibility graph, as introduced in Mairesse and Moyal (J Appl Probab 53(4):1064–1077, 2016). We prove that most common matching policies (including fcfm, priorities and random) satisfy a particular sub-additive property, which we exploit to show in many cases, the coupling-from-the-past to the steady state, using a backwards scheme à la Loynes. We then use these results to explicitly construct perfect bi-infinite matchings, and to build a perfect simulation algorithm in the case where the buffer of the system is finite.

Keywords: Stochastic matching; Graphs; Markov chains; Coupling from the past; Primary 60J10; Secondary 60K25; 05C70 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-024-09919-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:107:y:2024:i:3:d:10.1007_s11134-024-09919-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-024-09919-w

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().