IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v70y2024i5p2799-2822.html
   My bibliography  Save this article

Dynamic Matching: Characterizing and Achieving Constant Regret

Author

Listed:
  • Süleyman Kerimov

    (Jones Graduate School of Business, Rice University, Houston, Texas 77005)

  • Itai Ashlagi

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • Itai Gurvich

    (Kellogg School of Management, Northwestern University, Evanston, Illinois 60208)

Abstract

We study how to optimally match agents in a dynamic matching market with heterogeneous match cardinalities and values. A network topology determines the feasible matches in the market. In general, a fundamental tradeoff exists between short-term value—which calls for performing matches frequently—and long-term value—which calls, sometimes, for delaying match decisions in order to perform better matches. We find that in networks that satisfy a general position condition, the tension between short- and long-term value is limited, and a simple periodic clearing policy (nearly) maximizes the total match value simultaneously at all times. Central to our results is the general position gap ϵ ; a proxy for capacity slack in the market. With the exception of trivial cases, no policy can achieve an all-time regret that is smaller, in terms of order, than ϵ − 1 . We achieve this lower bound with a policy, which periodically resolves a natural matching integer linear program, provided that the delay between resolving periods is of the order of ϵ − 1 . Examples illustrate the necessity of some delay to alleviate the tension between short- and long-term value.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:ormnsc:v:70:y:2024:i:5:p:2799-2822
    DOI: 10.1287/mnsc.2021.01215
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2021.01215
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.2021.01215?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
    ---><---

    References listed on IDEAS

    as
    1. Ross Anderson & Itai Ashlagi & David Gamarnik & Yash Kanoria, 2017. "Efficient Dynamic Barter Exchange," Operations Research, INFORMS, vol. 65(6), pages 1446-1459, December.
    2. 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.
    3. Alberto Vera & Siddhartha Banerjee, 2021. "The Bayesian Prophet: A Low-Regret Framework for Online Decision Making," Management Science, INFORMS, vol. 67(3), pages 1368-1391, March.
    4. Itai Ashlagi & Afshin Nikzad & Philipp Strack, 2023. "Matching in Dynamic Imbalanced Markets," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 90(3), pages 1084-1124.
    5. Pornpawee Bumpensanti & He Wang, 2020. "A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue Management," Management Science, INFORMS, vol. 66(7), pages 2993-3009, July.
    6. Mohammad Akbarpour & Shengwu Li & Shayan Oveis Gharan, 2020. "Thickness and Information in Dynamic Matching Markets," Journal of Political Economy, University of Chicago Press, vol. 128(3), pages 783-815.
    7. 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.
    8. Jacob D. Leshno, 2022. "Dynamic Matching in Overloaded Waiting Lists," American Economic Review, American Economic Association, vol. 112(12), pages 3876-3910, December.
    9. Stefanus Jasin & Sunil Kumar, 2012. "A Re-Solving Heuristic with Bounded Revenue Loss for Network Revenue Management with Customer Choice," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 313-345, May.
    10. Alberto Vera & Siddhartha Banerjee & Itai Gurvich, 2021. "Online Allocation and Pricing: Constant Regret via Bellman Inequalities," Operations Research, INFORMS, vol. 69(3), pages 821-840, May.
    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. Mertikopoulos, Panayotis & Nax, Heinrich H. & Pradelski, Bary S.R., 2024. "Quick or cheap? Breaking points in dynamic markets," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    2. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    3. Zhaohua Chen & Chang Wang & Qian Wang & Yuqi Pan & Zhuming Shi & Zheng Cai & Yukun Ren & Zhihua Zhu & Xiaotie Deng, 2022. "Dynamic Budget Throttling in Repeated Second-Price Auctions," Papers 2207.04690, arXiv.org, revised Dec 2023.
    4. Irene Lo & Vahideh Manshadi & Scott Rodilitz & Ali Shameli, 2020. "Commitment on Volunteer Crowdsourcing Platforms: Implications for Growth and Engagement," Papers 2005.10731, arXiv.org, revised Jul 2021.
    5. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    6. Jhan-Jia Lin & Yu-Tse Lee & Ja-Ling Wu, 2021. "The Effect of Thickness-Based Dynamic Matching Mechanism on a Hyperledger Fabric-Based TimeBank System," Future Internet, MDPI, vol. 13(3), pages 1-21, March.
    7. Mohammad Akbarpour & Julien Combe & Yinghua He & Victor Hiller & Robert Shimer & Olivier Tercieux, 2020. "Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants without Money," Post-Print halshs-02973042, HAL.
    8. Nicole Immorlica & Brendan Lucier & Vahideh Manshadi & Alexander Wei, 2023. "Designing Approximately Optimal Search on Matching Platforms," Management Science, INFORMS, vol. 69(8), pages 4609-4626, August.
    9. Baccara, Mariagiovanna & Lee, SangMok & Yariv, Leeat, 2023. "Task allocation and on-the-job training," Journal of Economic Theory, Elsevier, vol. 207(C).
    10. Ali Aouad & Daniela Saban, 2023. "Online Assortment Optimization for Two-Sided Matching Platforms," Management Science, INFORMS, vol. 69(4), pages 2069-2087, April.
    11. Lingbo Huang & Tracy Xiao Liu & Jun Zhang, 2023. "Born to wait? A study on allocation rules in booking systems," Discussion Papers 2023-04, The Centre for Decision Research and Experimental Economics, School of Economics, University of Nottingham.
    12. David A. Goldberg & Martin I. Reiman & Qiong Wang, 2021. "A Survey of Recent Progress in the Asymptotic Analysis of Inventory Systems," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1718-1750, June.
    13. Itai Feigenbaum & Yash Kanoria & Irene Lo & Jay Sethuraman, 2020. "Dynamic Matching in School Choice: Efficient Seat Reassignment After Late Cancellations," Management Science, INFORMS, vol. 66(11), pages 5341-5361, November.
    14. Hua, Guowei & Zhang, Yi & Cheng, T.C.E. & Wang, Shouyang & Zhang, Juliang, 2020. "The newsvendor problem with barter exchange," Omega, Elsevier, vol. 92(C).
    15. Loertscher, Simon & Muir, Ellen V. & Taylor, Peter G., 2022. "Optimal market thickness," Journal of Economic Theory, Elsevier, vol. 200(C).
    16. Vahideh Manshadi & Sidhant Misra & Scott Rodilitz, 2020. "Diffusion in Random Networks: Impact of Degree Distribution," Operations Research, INFORMS, vol. 68(6), pages 1722-1741, November.
    17. Combe, Julien & Nora, Vladyslav & Tercieux, Olivier, 0. "Dynamic assignment without money: optimality of spot mechanisms," Theoretical Economics, Econometric Society.
    18. Kim, Jaehong & Li, Mengling & Xu, Menghan, 2021. "Organ donation with vouchers," Journal of Economic Theory, Elsevier, vol. 191(C).
    19. Battal Doğan & M. Bumin Yenmez, 2023. "When does an additional stage improve welfare in centralized assignment?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(4), pages 1145-1173, November.
    20. Li, Mengling & Riyanto, Yohanes E. & Xu, Menghan, 2023. "Prioritized organ allocation rules under compatibility constraints," Games and Economic Behavior, Elsevier, vol. 141(C), pages 403-427.

    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:inm:ormnsc:v:70:y:2024:i:5:p:2799-2822. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.