IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v107y2024i3d10.1007_s11134-024-09919-w.html
   My bibliography  Save this article

On the sub-additivity of stochastic matching

Author

Listed:
  • P. Moyal

    (Université de Lorraine/INRIA)

  • A. Bušić

    (INRIA/ENS)

  • J. Mairesse

    (CNRS/Université Pierre et Marie Curie)

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.

Suggested Citation

  • P. Moyal & A. Bušić & J. Mairesse, 2024. "On the sub-additivity of stochastic matching," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 295-339, September.
    • Handle: RePEc:spr:queues:v:107:y:2024:i:3:d:10.1007_s11134-024-09919-w
    DOI: 10.1007/s11134-024-09919-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-024-09919-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-024-09919-w?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ivo Adan & Gideon Weiss, 2012. "Exact FCFS Matching Rates for Two Infinite Multitype Sequences," Operations Research, INFORMS, vol. 60(2), pages 475-489, April.
    2. Mohammadreza Nazari & Alexander L. Stolyar, 2019. "Reward maximization in general dynamic matching systems," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 143-170, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jocelyn Begeot & Irène Marcovici & Pascal Moyal, 2023. "Stability regions of systems with compatibilities and ubiquitous measures on graphs," Queueing Systems: Theory and Applications, Springer, vol. 103(3), pages 275-312, April.
    2. Jean Mairesse & Pascal Moyal, 2022. "New frontiers for stochastic matching," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 473-475, April.
    3. Jose H. Blanchet & Martin I. Reiman & Viragh Shah & Lawrence M. Wein & Linjia Wu, 2020. "Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities," Papers 2002.03205, arXiv.org, revised Jun 2021.
    4. Francisco Castro & Hamid Nazerzadeh & Chiwei Yan, 2020. "Matching queues with reneging: a product form solution," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 359-385, December.
    5. Itai Ashlagi & Maximilien Burq & Patrick Jaillet & Vahideh Manshadi, 2019. "On Matching and Thickness in Heterogeneous Dynamic Markets," Operations Research, INFORMS, vol. 67(4), pages 927-949, July.
    6. Dongyuan Zhan & Gideon Weiss, 2018. "Many-server scaling of the N-system under FCFS–ALIS," Queueing Systems: Theory and Applications, Springer, vol. 88(1), pages 27-71, February.
    7. Burak Büke & Hanyi Chen, 2017. "Fluid and diffusion approximations of probabilistic matching systems," Queueing Systems: Theory and Applications, Springer, vol. 86(1), pages 1-33, June.
    8. Frank Kelly & Elena Yudovina, 2018. "A Markov Model of a Limit Order Book: Thresholds, Recurrence, and Trading Strategies," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 181-203, February.
    9. Mohammadreza Nazari & Alexander L. Stolyar, 2019. "Reward maximization in general dynamic matching systems," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 143-170, February.
    10. Jingui Xie & Yiming Fan & Mabel C. Chou, 2017. "Flexibility design in loss and queueing systems: efficiency of k-chain configuration," Flexible Services and Manufacturing Journal, Springer, vol. 29(2), pages 286-308, June.
    11. Süleyman Kerimov & Itai Ashlagi & Itai Gurvich, 2024. "Dynamic Matching: Characterizing and Achieving Constant Regret," Management Science, INFORMS, vol. 70(5), pages 2799-2822, May.
    12. Kristen Gardner & Pascal Moyal, 2024. "Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 199-203, September.
    13. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.
    14. Gideon Weiss, 2020. "Directed FCFS infinite bipartite matching," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 387-418, December.
    15. Ross Anderson & Itai Ashlagi & David Gamarnik & Yash Kanoria, 2017. "Efficient Dynamic Barter Exchange," Operations Research, INFORMS, vol. 65(6), pages 1446-1459, December.
    16. Bušić Ana & Cadas Arnaud & Doncel Josu & Fourneau Jean-Michel, 2024. "Performance paradox of dynamic matching models under greedy policies," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 257-293, September.
    17. Ivo Adan & Ana Bušić & Jean Mairesse & Gideon Weiss, 2018. "Reversibility and Further Properties of FCFS Infinite Bipartite Matching," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 598-621, May.
    18. Frank Kelly & Elena Yudovina, 2015. "A Markov model of a limit order book: thresholds, recurrence, and trading strategies," Papers 1504.00579, arXiv.org, revised Mar 2017.
    19. Adan, Ivo & Foss, Sergey & Shneer, Seva & Weiss, Gideon, 2020. "Local stability in a transient Markov chain," Statistics & Probability Letters, Elsevier, vol. 165(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:107:y:2024:i:3:d:10.1007_s11134-024-09919-w. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.