IDEAS home Printed from https://ideas.repec.org/p/hal/pseptp/halshs-02087847.html
   My bibliography  Save this paper

Efficiency and Stability in Large Matching Markets

Author

Listed:
  • Yeon-Koo Che

    (Columbia University [New York])

  • Olivier Tercieux

    (PJSE - Paris Jourdan Sciences Economiques - UP1 - Université Paris 1 Panthéon-Sorbonne - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris sciences et lettres - EHESS - École des hautes études en sciences sociales - ENPC - École des Ponts ParisTech - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement, PSE - Paris School of Economics - UP1 - Université Paris 1 Panthéon-Sorbonne - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris sciences et lettres - EHESS - École des hautes études en sciences sociales - ENPC - École des Ponts ParisTech - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement)

Abstract

We study Pareto efficient mechanisms in matching markets when the number of agents is large and individual preferences are randomly drawn from a class of distributions, allowing for both common and idiosyncratic shocks. We provide a broad set of circumstances under which, as the market grows large, all Pareto efficient mechanisms—including top trading cycles (with an arbitrary ownership structure), serial dictatorship (with an arbitrary serial order), and their randomized variants—produce a distribution of agent utilities that in the limit coincides with the utilitarian upper bound. This implies that Pareto efficient mechanisms are uniformly asymptotically payoff equivalent "up to the renaming of agents." Hence, when the conditions of our model are met, policy makers need not discriminate among Pareto efficient mechanisms based on the aggregate payoff distribution of participants.

Suggested Citation

  • Yeon-Koo Che & Olivier Tercieux, 2019. "Efficiency and Stability in Large Matching Markets," PSE-Ecole d'économie de Paris (Postprint) halshs-02087847, HAL.
    • Handle: RePEc:hal:pseptp:halshs-02087847
    DOI: 10.1086/701791
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Atila Abdulkadiro?lu & Yeon-Koo Che & Yosuke Yasuda, 2015. "Expanding "Choice" in School Choice," American Economic Journal: Microeconomics, American Economic Association, vol. 7(1), pages 1-42, February.
    2. Caterina Calsamiglia & Guillaume Haeringer & Flip Klijn, 2010. "Constrained School Choice: An Experimental Study," American Economic Review, American Economic Association, vol. 100(4), pages 1860-1874, September.
    3. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 119(2), pages 457-488.
    4. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    5. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, September.
    6. Parag A. Pathak & Tayfun Sönmez, 2013. "School Admissions Reform in Chicago and England: Comparing Mechanisms by Their Vulnerability to Manipulation," American Economic Review, American Economic Association, vol. 103(1), pages 80-106, February.
    7. Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
    8. Tayfun Sönmez & M. Utku Ünver, 2009. "Matching, Allocation, and Exchange of Discrete Resources," Boston College Working Papers in Economics 717, Boston College Department of Economics.
    9. Itai Ashlagi & Mark Braverman & Avinatan Hassidim, 2014. "Stability in Large Matching Markets with Complementarities," Operations Research, INFORMS, vol. 62(4), pages 713-732, August.
    10. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    11. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    12. repec:oup:restud:v:84:y::i:1:p:444-463. is not listed on IDEAS
    13. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    14. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    15. Ashlagi, Itai & Nikzad, Afshin & Romm, Assaf, 2019. "Assigning more students to their top choices: A comparison of tie-breaking rules," Games and Economic Behavior, Elsevier, vol. 115(C), pages 167-187.
    16. 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.
    17. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
    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. Yeon Koo Che & Olivier Tercieux, 2015. "An Analysis of Top Trading Cycles in Two-Sided Matching Markets," Levine's Bibliography 786969000000001059, UCLA Department of Economics.
    2. Li, Mengling, 2020. "Ties matter: Improving efficiency in course allocation by allowing ties," Journal of Economic Behavior & Organization, Elsevier, vol. 178(C), pages 354-384.
    3. Ortega, Josué, 2018. "Social integration in two-sided matching markets," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 119-126.
    4. Che, Yeon-Koo & Tercieux, Olivier, 2018. "Payoff equivalence of efficient mechanisms in large matching markets," Theoretical Economics, Econometric Society, vol. 13(1), January.
    5. 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.
    6. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2022. "Limited Farsightedness in Priority-Based Matching," Papers 2212.07427, arXiv.org.
    7. Aaron L. Bodoh-Creed, 2020. "Optimizing for Distributional Goals in School Choice Problems," Management Science, INFORMS, vol. 66(8), pages 3657-3676, August.
    8. Aue, Robert & Klein, Thilo & Ortega, Josué, 2020. "What happens when separate and unequal school districts merge?," ZEW Discussion Papers 20-032, ZEW - Leibniz Centre for European Economic Research.
    9. Estelle Cantillon & Li Chen & Juan S. Pereyra, 2022. "Respecting priorities versus respecting preferences in school choice: When is there a trade-off?," Papers 2212.02881, arXiv.org, revised Jan 2024.
    10. Rajnish Kunar & Kriti Manocha & Josue Ortega, 2020. "On the integration of Shapley-Scarf housing markets," Papers 2004.09075, arXiv.org, revised Jan 2022.
    11. Song, Yangwei, 2023. "Approximate Bayesian implementation and exact maxmin implementation: An equivalence," Games and Economic Behavior, Elsevier, vol. 139(C), pages 56-87.
    12. Estelle Cantillon & Li Chen & Juan Sebastian Pereyra Barreiro, 2022. "Respecting priorities versus respecting preferences in school choice: When is there a trade-off ?," Working Papers ECARES 2022-39, ULB -- Universite Libre de Bruxelles.
    13. Ashlagi, Itai & Nikzad, Afshin & Romm, Assaf, 2019. "Assigning more students to their top choices: A comparison of tie-breaking rules," Games and Economic Behavior, Elsevier, vol. 115(C), pages 167-187.
    14. Di Feng & Yun Liu, 2022. "On the Asymptotic Performance of Affirmative Actions in School Choice," Papers 2202.03927, arXiv.org, revised Dec 2022.
    15. Avinatan Hassidim & Assaf Romm & Ran I. Shorrer, 2021. "The Limits of Incentives in Economic Matching Procedures," Management Science, INFORMS, vol. 67(2), pages 951-963, February.
    16. Aue, Robert & Bach, Maximilian & Heigle, Julia & Klein, Thilo & Pfeiffer, Friedhelm & Zapp, Kristina, 2020. "The implication of school admission rules for segregation and educational inequality: Research report," ZEW Expertises, ZEW - Leibniz Centre for European Economic Research, number 223254.
    17. Nick Arnosti, 2023. "Lottery Design for School Choice," Management Science, INFORMS, vol. 69(1), pages 244-259, January.
    18. Georgy Artemov & Yeon-Koo Che & YingHua He, 2023. "Stable Matching with Mistaken Agents," Journal of Political Economy Microeconomics, University of Chicago Press, vol. 1(2), pages 270-320.
    19. Kumar, Rajnish & Manocha, Kriti & Ortega, Josué, 2022. "On the integration of Shapley–Scarf markets," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    20. Song, Yangwei, 2022. "Approximate Bayesian Implementation and Exact Maxmin Implementation: An Equivalence," Rationality and Competition Discussion Paper Series 362, CRC TRR 190 Rationality and Competition.
    21. Ashlagi, Itai & Nikzad, Afshin, 2020. "What matters in school choice tie-breaking? How competition guides design," Journal of Economic Theory, Elsevier, vol. 190(C).
    22. Kesten, Onur & Kurino, Morimitsu, 2019. "Strategy-proof improvements upon deferred acceptance: A maximal domain for possibility," Games and Economic Behavior, Elsevier, vol. 117(C), pages 120-143.

    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. Hatfield, John William & Kojima, Fuhito & Narita, Yusuke, 2016. "Improving schools through school choice: A market design approach," Journal of Economic Theory, Elsevier, vol. 166(C), pages 186-211.
    2. John William Hatfield & Fuhito Kojima & Yusuke Narita, 2011. "Promoting School Competition Through School Choice: A Market Design Approach," Working Papers 2011-018, Human Capital and Economic Opportunity Working Group.
    3. Fuhito Kojima & M. Ünver, 2014. "The “Boston” school-choice mechanism: an axiomatic approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 55(3), pages 515-544, April.
    4. Kesten, Onur & Kurino, Morimitsu, 2019. "Strategy-proof improvements upon deferred acceptance: A maximal domain for possibility," Games and Economic Behavior, Elsevier, vol. 117(C), pages 120-143.
    5. Anno, Hidekazu & Kurino, Morimitsu, 2016. "On the operation of multiple matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 166-185.
    6. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    7. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    8. Zhu, Min, 2014. "College admissions in China: A mechanism design perspective," China Economic Review, Elsevier, vol. 30(C), pages 618-631.
    9. Rustamdjan Hakimov & Onur Kesten, 2018. "The Equitable Top Trading Cycles Mechanism For School Choice," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 59(4), pages 2219-2258, November.
    10. Gabrielle Fack & Julien Grenet & Yinghua He, 2019. "Beyond Truth-Telling: Preference Estimation with Centralized School Choice and College Admissions," American Economic Review, American Economic Association, vol. 109(4), pages 1486-1529, April.
    11. Tayfun Sönmez, 2013. "Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism," Journal of Political Economy, University of Chicago Press, vol. 121(1), pages 186-219.
    12. Che, Yeon-Koo & Tercieux, Olivier, 2018. "Payoff equivalence of efficient mechanisms in large matching markets," Theoretical Economics, Econometric Society, vol. 13(1), January.
    13. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-1978, December.
    14. Fuhito Kojima & M. Utku Ünver, 2010. "The 'Boston' School-Choice Mechanism," Boston College Working Papers in Economics 729, Boston College Department of Economics, revised 08 Oct 2010.
    15. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers halshs-00860931, HAL.
    16. Jaimie W. Lien & Jie Zheng & Xiaohan Zhong, 2016. "Preference submission timing in school choice matching: testing fairness and efficiency in the laboratory," Experimental Economics, Springer;Economic Science Association, vol. 19(1), pages 116-150, March.
    17. Umut M. Dur & Scott Duke Kominers & Parag A. Pathak & Tayfun Sönmez, 2013. "The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice," NBER Working Papers 18981, National Bureau of Economic Research, Inc.
    18. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers 1327, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    19. Rong, Kang & Tang, Qianfeng & Zhang, Yongchao, 2020. "On stable and efficient mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 187(C).
    20. Atila Abdulkadiroğlu & Nikhil Agarwal & Parag A. Pathak, 2015. "The Welfare Effects of Coordinated Assignment: Evidence from the NYC HS Match," NBER Working Papers 21046, National Bureau of Economic Research, Inc.

    More about this item

    JEL classification:

    • C70 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - General
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
    • D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

    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:hal:pseptp:halshs-02087847. 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: Caroline Bauer (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.