IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v91y2019i1d10.1007_s11134-018-9593-y.html
   My bibliography  Save this article

Reward maximization in general dynamic matching systems

Author

Listed:
  • Mohammadreza Nazari

    (Lehigh University)

  • Alexander L. Stolyar

    (University of Illinois at Urbana-Champaign)

Abstract

We consider a matching system with random arrivals of items of different types. The items wait in queues—one per item type—until they are “matched.” Each matching requires certain quantities of items of different types; after a matching is activated, the associated items leave the system. There exists a finite set of possible matchings, each producing a certain amount of “reward.” This model has a broad range of important applications, including assemble-to-order systems, Internet advertising, and matching web portals. We propose an optimal matching scheme in the sense that it asymptotically maximizes the long-term average matching reward, while keeping the queues stable. The scheme makes matching decisions in a specially constructed virtual system, which in turn controls decisions in the physical system. The key feature of the virtual system is that, unlike the physical one, it allows the queues to become negative. The matchings in the virtual system are controlled by an extended version of the greedy primal–dual (GPD) algorithm, which we prove to be asymptotically optimal—this in turn implies the asymptotic optimality of the entire scheme. The scheme is real time; at any time, it uses simple rules based on the current state of the virtual and physical queues. It is very robust in that it does not require any knowledge of the item arrival rates and automatically adapts to changing rates. The extended GPD algorithm and its asymptotic optimality apply to a quite general queueing network framework, not limited to matching problems, and therefore are of independent interest.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:queues:v:91:y:2019:i:1:d:10.1007_s11134-018-9593-y
    DOI: 10.1007/s11134-018-9593-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-018-9593-y
    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-018-9593-y?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. B. R. K. Kashyap, 1966. "The Double-Ended Queue with Bulk Service and Limited Waiting Space," Operations Research, INFORMS, vol. 14(5), pages 822-834, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    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.

    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. 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.
    2. Xu, Zhengtian & Yin, Yafeng & Zha, Liteng, 2017. "Optimal parking provision for ride-sourcing services," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 559-578.
    3. Fabien Leurent, 2019. "Microeconomics of a taxi service in a ring-shaped city," Working Papers hal-02047269, HAL.
    4. 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.
    5. 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.
    6. Xin Liu, 2019. "Diffusion approximations for double-ended queues with reneging in heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 49-87, February.
    7. 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.
    8. 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.
    9. 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.
    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. 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.
    12. Ying Shi & Zhaotong Lian, 2016. "Equilibrium Strategies and Optimal Control for a Double-Ended Queue," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-18, June.
    13. Yang, Qiaoli & Yang, Bo & Qiao, Zheng & Tang, Min-an & Gao, Fengyang, 2021. "Impact of possible random factors on queue behaviors of passengers and taxis at taxi stand of transport hubs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 580(C).
    14. Jean Mairesse & Pascal Moyal, 2022. "New frontiers for stochastic matching," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 473-475, April.
    15. 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.
    16. Antonio Di Crescenzo & Virginia Giorno & Balasubramanian Krishna Kumar & Amelia G. Nobile, 2018. "A Time-Non-Homogeneous Double-Ended Queue with Failures and Repairs and Its Continuous Approximation," Mathematics, MDPI, vol. 6(5), pages 1-23, May.
    17. Lu Wang & Vidyadhar Kulkarni, 2020. "Fluid and diffusion models for a system of taxis and customers with delayed matching," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 101-131, October.
    18. Philipp Afèche & Adam Diamant & Joseph Milner, 2014. "Double-Sided Batch Queues with Abandonment: Modeling Crossing Networks," Operations Research, INFORMS, vol. 62(5), pages 1179-1201, October.
    19. Shi, Ying & Lian, Zhaotong, 2016. "Optimization and strategic behavior in a passenger–taxi service system," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1024-1032.
    20. Chai, Xudong & Liu, Liwei & Chang, Baoxian & Jiang, Tao & Wang, Zhen, 2019. "On a batch matching system with impatient servers and boundedly rational customers," Applied Mathematics and Computation, Elsevier, vol. 354(C), pages 308-328.

    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:91:y:2019:i:1:d:10.1007_s11134-018-9593-y. 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.