IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2206.10287.html
   My bibliography  Save this paper

Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets

Author

Listed:
  • Johannes Baumler
  • Martin Bullinger
  • Stefan Kober
  • Donghao Zhu

Abstract

We study a dynamic matching procedure where homogeneous agents arrive at random according to a Poisson process and form edges at random yielding a sparse market. Agents leave according to a certain departure distribution and may leave early by forming a pair with a compatible agent. The primary objective is to maximize the number of matched agents. Our main result is to show that a mild condition on the departure distribution suffices to get almost optimal performance of instantaneous matching, despite operating in a thin market. We are thus the first to provide a natural condition under which instantaneous decisions are superior in a market that is both sparse and thin. This result is surprising because similar results in the previous literature are based on market thickness. In addition, instantaneous matching performs well with respect to further objectives such as minimizing waiting times and avoiding the risk of market congestion. We develop new techniques for proving our results going beyond commonly adopted methods for Markov processes.

Suggested Citation

  • Johannes Baumler & Martin Bullinger & Stefan Kober & Donghao Zhu, 2022. "Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets," Papers 2206.10287, arXiv.org, revised Jun 2023.
    • Handle: RePEc:arx:papers:2206.10287
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2206.10287
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    2. Alvin E. Roth, 2018. "Marketplaces, Markets, and Market Design," American Economic Review, American Economic Association, vol. 108(7), pages 1609-1658, July.
    3. Jun Li & Serguei Netessine, 2020. "Higher Market Thickness Reduces Matching Rate in Online Platforms: Evidence from a Quasiexperiment," Management Science, INFORMS, vol. 66(1), pages 271-289, January.
    4. Mariagiovanna Baccara & Allan Collard-Wexler & Leonardo Felli & Leeat Yariv, 2014. "Child-Adoption Matching: Preferences for Gender and Race," American Economic Journal: Applied Economics, American Economic Association, vol. 6(3), pages 133-158, July.
    5. Loertscher, Simon & Muir, Ellen V. & Taylor, Peter G., 2022. "Optimal market thickness," Journal of Economic Theory, Elsevier, vol. 200(C).
    6. Vahideh H. Manshadi & Shayan Oveis Gharan & Amin Saberi, 2012. "Online Stochastic Matching: Online Actions Based on Offline Statistics," Mathematics of Operations Research, INFORMS, vol. 37(4), pages 559-573, November.
    7. 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.
    8. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    9. Shimer Robert & Smith Lones, 2001. "Matching, Search, and Heterogeneity," The B.E. Journal of Macroeconomics, De Gruyter, vol. 1(1), pages 1-18, April.
    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. 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.
    2. Suresh P. Sethi & Sushil Gupta & Vipin K. Agrawal & Vijay K. Agrawal, 2022. "Nobel laureates’ contributions to and impacts on operations management," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4283-4303, December.
    3. Jorgen Kratz, "undated". "Conflicting Objectives in Kidney Exchange," Discussion Papers 23/04, Department of Economics, University of York.
    4. Ali Aouad & Daniela Saban, 2023. "Online Assortment Optimization for Two-Sided Matching Platforms," Management Science, INFORMS, vol. 69(4), pages 2069-2087, April.
    5. Vincent W. Slaugh & Mustafa Akan & Onur Kesten & M. Utku Ünver, 2016. "The Pennsylvania Adoption Exchange Improves Its Matching Process," Interfaces, INFORMS, vol. 46(2), pages 133-153, April.
    6. Scott Duke Kominers & Parag A. Pathak & Tayfun Sönmez & M. Utku Ünver, 2020. "Paying It Backward and Forward: Expanding Access to Convalescent Plasma Therapy Through Market Design," NBER Working Papers 27143, National Bureau of Economic Research, Inc.
    7. Tayfun Sönmez & M Utku Ünver, 2017. "Market design for living-donor organ exchanges: an economic policy perspective," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 676-704.
    8. Manjunath, Vikram & Westkamp, Alexander, 2021. "Strategy-proof exchange under trichotomous preferences," Journal of Economic Theory, Elsevier, vol. 193(C).
    9. Baccara, Mariagiovanna & Lee, SangMok & Yariv, Leeat, 2020. "Optimal dynamic matching," Theoretical Economics, Econometric Society, vol. 15(3), July.
    10. Ross Anderson & Itai Ashlagi & David Gamarnik & Yash Kanoria, 2017. "Efficient Dynamic Barter Exchange," Operations Research, INFORMS, vol. 65(6), pages 1446-1459, December.
    11. Kim, Jaehong & Li, Mengling & Xu, Menghan, 2021. "Organ donation with vouchers," Journal of Economic Theory, Elsevier, vol. 191(C).
    12. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    13. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.
    14. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    15. Parag A. Pathak & Alex Rees-Jones & Tayfun Sönmez, 2020. "Immigration Lottery Design: Engineered and Coincidental Consequences of H-1B Reforms," NBER Working Papers 26767, National Bureau of Economic Research, Inc.
    16. Alcalde-Unzu, Jorge & Molis, Elena, 2011. "Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms," Games and Economic Behavior, Elsevier, vol. 73(1), pages 1-16, September.
    17. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    18. 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.
    19. Zhiwei Cui & Yan-An Hwang, 2017. "House exchange and residential segregation in networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 125-147, March.
    20. Morten Størling Hedegaard & Jean-Robert Tyran, 2018. "The Price of Prejudice," American Economic Journal: Applied Economics, American Economic Association, vol. 10(1), pages 40-63, January.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:arx:papers:2206.10287. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.