IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2604.12181.html

How to Use Prices for Efficient Online Matching

Author

Listed:
  • Terence Highsmith

Abstract

Many matching markets feature unknown, dynamic arrivals of agents that must match immediately. A caseworker must match an abused child to a foster home, a hospital must assign a patient in critical condition to a room, or a city must place a homeless individual into a shelter. We design an online matching algorithm -- the Sequential Equilibrium Mechanism (SEM) -- that approximates large market equilibria to match arriving agents to objects. SEM is asymptotically efficient, fair, and strategy-proof with probability one. Our application plans to deploy a lab-in-the-field experiment where real caseworkers match vulnerable children to host homes, and we provide simulation evidence that SEM can substantially improve welfare.

Suggested Citation

  • Terence Highsmith, 2026. "How to Use Prices for Efficient Online Matching," Papers 2604.12181, arXiv.org.
    • Handle: RePEc:arx:papers:2604.12181
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Yinghua He & Antonio Miralles & Marek Pycia & Jianye Yan, 2018. "A Pseudo-Market Approach to Allocation with Priorities," American Economic Journal: Microeconomics, American Economic Association, vol. 10(3), pages 272-314, August.
    2. Eduardo M. Azevedo & Jacob D. Leshno, 2016. "A Supply and Demand Framework for Two-Sided Matching Markets," Journal of Political Economy, University of Chicago Press, vol. 124(5), pages 1235-1268.
    3. Bogomolnaia, Anna & Moulin, Herve, 2001. "A New Solution to the Random Assignment Problem," Journal of Economic Theory, Elsevier, vol. 100(2), pages 295-328, October.
    4. Katta, Akshay-Kumar & Sethuraman, Jay, 2006. "A solution to the random assignment problem on the full preference domain," Journal of Economic Theory, Elsevier, vol. 131(1), pages 231-250, November.
    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. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    2. Andrew McLennan & Shino Takayama & Yuki Tamura, 2024. "An Efficient, Computationally Tractable School Choice Mechanism," Discussion Papers Series 668, School of Economics, University of Queensland, Australia.
    3. Schlegel, Jan Christoph & Mamageishvili, Akaki, 2020. "Welfare theorems for random assignments with priorities," Games and Economic Behavior, Elsevier, vol. 124(C), pages 62-81.
    4. Haris Aziz & Florian Brandl, 2020. "The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints," Papers 2008.08991, arXiv.org, revised Jul 2021.
    5. Jugal Garg & Yixin Tao & L'aszl'o A. V'egh, 2025. "Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms," Papers 2507.03359, arXiv.org, revised Feb 2026.
    6. Aziz, Haris & Brandl, Florian, 2022. "The vigilant eating rule: A general approach for probabilistic economic design with constraints," Games and Economic Behavior, Elsevier, vol. 135(C), pages 168-187.
    7. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    8. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    9. repec:cty:dpaper:10.1016/j.geb.2020.08.009 is not listed on IDEAS
    10. Yusuke Narita, 2018. "Toward an Ethical Experiment," Cowles Foundation Discussion Papers 2127, Cowles Foundation for Research in Economics, Yale University.
    11. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    12. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
    13. Youngsub Chun & Boram Park, 2017. "A graph theoretic approach to the slot allocation problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 133-152, January.
    14. Yusuke Narita, 2018. "Experiment-as-Market: Incorporating Welfare into Randomized Controlled Trials," Cowles Foundation Discussion Papers 2127r, Cowles Foundation for Research in Economics, Yale University, revised May 2019.
    15. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    16. Chang, Hee-In & Chun, Youngsub, 2017. "Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 80-92.
    17. Ivan Balbuzanov, 2016. "Convex strategyproofness with an application to the probabilistic serial mechanism," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(3), pages 511-520, March.
    18. Young-San Lin & Hai Nguyen & Thành Nguyen & Kemal Altinkemer, 2022. "Allocation with Weak Priorities and General Constraints," Operations Research, INFORMS, vol. 70(5), pages 2804-2819, September.
    19. Mihai Manea, 2008. "Random serial dictatorship and ordinally efficient contracts," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 489-496, March.
    20. Aziz, Haris & Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2017. "Computational aspects of assigning agents to a line," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 93-99.
    21. Chen, Yiling & Lai, John K. & Parkes, David C. & Procaccia, Ariel D., 2013. "Truth, justice, and cake cutting," Games and Economic Behavior, Elsevier, vol. 77(1), pages 284-297.

    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:2604.12181. 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.