[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
IDEAS home Printed from https://ideas.repec.org/p/cwl/cwldpp/2013.html
   My bibliography  Save this paper

Efficiency and Stability in Large Matching Markets

Author

Listed:
  • Yeon-Koo Che

    (Dept. of Economics, Columbia University)

  • Olivier Tercieux

    (Dept. of Economics, Paris School of Economics)

Abstract
We study efficient and stable mechanisms in matching markets when the number of agents is large and individuals� preferences and priorities are drawn randomly. When agents� preferences are uncorrelated, then both efficiency and stability can be achieved in an asymptotic sense via standard mechanisms such as deferred acceptance and top trading cycles. When agents� preferences are correlated over objects, however, these mechanisms are either inefficient or unstable even in an asymptotic sense. We propose a variant of deferred acceptance that is asymptotically efficient, asymptotically stable and asymptotically incentive compatible. This new mechanism performs well in a counterfactual calibration based on New York City school choice data.

Suggested Citation

  • Yeon-Koo Che & Olivier Tercieux, 2015. "Efficiency and Stability in Large Matching Markets," Cowles Foundation Discussion Papers 2013, Cowles Foundation for Research in Economics, Yale University.
    • Handle: RePEc:cwl:cwldpp:2013
    Note: Includes supplementary material
    as

    Download full text from publisher

    File URL: https://cowles.yale.edu/sites/default/files/files/pub/d20/d2013.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. repec:oup:restud:v:84:y::i:1:p:444-463. is not listed on IDEAS
    8. 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.
    9. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    10. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    11. 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.
    12. Itai Ashlagi & Mark Braverman & Avinatan Hassidim, 2014. "Stability in Large Matching Markets with Complementarities," Operations Research, INFORMS, vol. 62(4), pages 713-732, August.
    13. Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
    14. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    15. 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.
    16. 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.
    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. Di Feng & Yun Liu & Gaowang Wang, 2023. "On the Asymptotic Performance of Affirmative Actions in School Choice," Annals of Economics and Finance, Society for AEF, vol. 24(2), pages 289-307, November.
    3. 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.
    4. Ortega, Josué, 2018. "Social integration in two-sided matching markets," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 119-126.
    5. Che, Yeon-Koo & Tercieux, Olivier, 2018. "Payoff equivalence of efficient mechanisms in large matching markets," Theoretical Economics, Econometric Society, vol. 13(1), January.
    6. 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.
    7. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2022. "Limited Farsightedness in Priority-Based Matching," Papers 2212.07427, arXiv.org.
    8. Aaron L. Bodoh-Creed, 2020. "Optimizing for Distributional Goals in School Choice Problems," Management Science, INFORMS, vol. 66(8), pages 3657-3676, August.
    9. Thilo Klein & Robert Aue & Josue Ortega, 2020. "School choice with independent versus consolidated districts," Papers 2006.13209, arXiv.org, revised Jul 2024.
    10. 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 Sep 2024.
    11. Rajnish Kunar & Kriti Manocha & Josue Ortega, 2020. "On the integration of Shapley-Scarf housing markets," Papers 2004.09075, arXiv.org, revised Jan 2022.
    12. Song, Yangwei, 2023. "Approximate Bayesian implementation and exact maxmin implementation: An equivalence," Games and Economic Behavior, Elsevier, vol. 139(C), pages 56-87.
    13. 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.
    14. 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.
    15. Di Feng & Yun Liu, 2022. "On the Asymptotic Performance of Affirmative Actions in School Choice," Papers 2202.03927, arXiv.org, revised Dec 2022.
    16. 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.
    17. 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.
    18. 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.
    19. Nick Arnosti, 2023. "Lottery Design for School Choice," Management Science, INFORMS, vol. 69(1), pages 244-259, January.
    20. 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.
    21. Kumar, Rajnish & Manocha, Kriti & Ortega, Josué, 2022. "On the integration of Shapley–Scarf markets," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    22. 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.
    23. Ashlagi, Itai & Nikzad, Afshin, 2020. "What matters in school choice tie-breaking? How competition guides design," Journal of Economic Theory, Elsevier, vol. 190(C).
    24. 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. 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.
    12. 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.
    13. Che, Yeon-Koo & Tercieux, Olivier, 2018. "Payoff equivalence of efficient mechanisms in large matching markets," Theoretical Economics, Econometric Society, vol. 13(1), January.
    14. 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.
    15. 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).
    16. 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.
    17. 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.
    18. 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.
    19. Yun Liu, 2017. "On the welfare effects of affirmative actions in school choice," Review of Economic Design, Springer;Society for Economic Design, vol. 21(2), pages 121-151, June.
    20. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers halshs-00860931, HAL.

    More about this item

    Keywords

    Large matching markets; Pareto efficiency; Stability; Fairness; Payoff equivalence; Asymptotic efficiency; and Asymptotic stability;
    All these keywords.

    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

    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:cwl:cwldpp:2013. 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: Brittany Ladd (email available below). General contact details of provider: https://edirc.repec.org/data/cowleus.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.