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

Stability and Efficiency of Random Serial Dictatorship

Author

Listed:
  • Suhas Vijaykumar

Abstract

This paper establishes non-asymptotic convergence of the cutoffs in Random serial dictatorship in an environment with many students, many schools, and arbitrary student preferences. Convergence is shown to hold when the number of schools, $m$, and the number of students, $n$, satisfy the relation $m \ln m \ll n$, and we provide an example showing that this result is sharp. We differ significantly from prior work in the mechanism design literature in our use of analytic tools from randomized algorithms and discrete probability, which allow us to show concentration of the RSD lottery probabilities and cutoffs even against adversarial student preferences.

Suggested Citation

  • Suhas Vijaykumar, 2021. "Stability and Efficiency of Random Serial Dictatorship," Papers 2110.07024, arXiv.org.
    • Handle: RePEc:arx:papers:2110.07024
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Konrad Menzel, 2015. "Large Matching Markets as Two‐Sided Demand Systems," Econometrica, Econometric Society, vol. 83(3), pages 897-941, May.
    2. Atila Abdulkadroǧlu & Joshua D. Angrist & Yusuke Narita & Parag A. Pathak & Roman A. Zarate, 2017. "Regression Discontinuity in Serial Dictatorship: Achievement Effects at Chicago's Exam Schools," American Economic Review, American Economic Association, vol. 107(5), pages 240-245, May.
    3. 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.
    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. Atı̇la Abdulkadı̇roğlu & Joshua D. Angrist & Yusuke Narita & Parag Pathak, 2022. "Breaking Ties: Regression Discontinuity Design Meets Market Design," Econometrica, Econometric Society, vol. 90(1), pages 117-151, January.
    2. Yusuke Narita, 2020. "A Theory of Quasi-Experimental Evaluation of School Quality," Working Papers 2020-085, Human Capital and Economic Opportunity Working Group.
    3. Jiafeng Chen, 2021. "Nonparametric Treatment Effect Identification in School Choice," Papers 2112.03872, arXiv.org, revised Oct 2023.
    4. Shuyang Sheng & Xiaoting Sun, 2023. "Social Interactions with Endogenous Group Formation," Papers 2306.01544, arXiv.org.
    5. Atila Abdulkadiroğlu & Joshua D. Angrist & Yusuke Narita & Parag A. Pathak, 2017. "Research Design Meets Market Design: Using Centralized Assignment for Impact Evaluation," Econometrica, Econometric Society, vol. 85, pages 1373-1432, September.
    6. Thierry Magnac, 2018. "Quels étudiants pour quelles universités ? Analyses empiriques de mécanismes d’allocation centralisée," Revue économique, Presses de Sciences-Po, vol. 69(5), pages 683-708.
    7. Jaerim Choi, 2021. "Two-sided heterogeneity, endogenous sharing, and international matching markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(2), pages 473-509, September.
    8. Alfred Galichon & Simon Weber, 2024. "Matching under Imperfectly Transferable Utility," Papers 2403.05222, arXiv.org, revised Oct 2024.
    9. Carvalho, José-Raimundo & Magnac, Thierry & Xiong, Qizhou, 2016. "College Choice and the Selection of Mechanisms: A Structural Empirical Analysis," IWH Discussion Papers 3/2016, Halle Institute for Economic Research (IWH).
    10. YingHua He & Thierry Magnac, 2022. "Application Costs and Congestion in Matching Markets," The Economic Journal, Royal Economic Society, vol. 132(648), pages 2918-2950.
    11. Liang Chen & Eugene Choo & Alfred Galichon & Simon Weber, 2023. "Existence of a Competitive Equilibrium with Substitutes, with Applications to Matching and Discrete Choice Models," Papers 2309.11416, arXiv.org.
    12. Michael Greinecker & Christopher Kah, 2018. "Pairwise stable matching in large economies," Graz Economics Papers 2018-01, University of Graz, Department of Economics.
    13. SangMok Lee, 2022. "Preference Learning in School Choice Problems," Papers 2202.08366, arXiv.org, revised Mar 2023.
    14. repec:cty:dpaper:10.1016/j.geb.2020.08.009 is not listed on IDEAS
    15. Fuentes Matías & Tohmé Fernando, 2019. "Stable Matching with Double Infinity of Workers and Firms," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 19(2), pages 1-8, June.
    16. Parag A. Pathak & Tayfun Sönmez & M. Utku Ünver & M. Bumin Yenmez, 2024. "Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Healthcare Rationing," Management Science, INFORMS, vol. 70(6), pages 3999-4036, June.
    17. Ágoston, Kolos Csaba & Biró, Péter & Kováts, Endre & Jankó, Zsuzsanna, 2022. "College admissions with ties and common quotas: Integer programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 722-734.
    18. Jesús Fernández-Huertas Moraga & Hillel Rapoport, 2015. "Tradable Refugee-admission Quotas and EU Asylum Policy," CESifo Economic Studies, CESifo Group, vol. 61(3-4), pages 638-672.
    19. Yusuke Narita, 2021. "A Theory of Quasi-Experimental Evaluation of School Quality," Management Science, INFORMS, vol. 67(8), pages 4982-5010, August.
    20. Bjerre-Nielsen, Andreas & Christensen, Lykke Sterll & Gandil, Mikkel Høst & Sievertsen, Hans Henrik, 2023. "Playing the System: Address Manipulation and Access to Schools," IZA Discussion Papers 16197, Institute of Labor Economics (IZA).
    21. Hagen, Martin, 2022. "Tradable immigration quotas revisited," Journal of Public Economics, Elsevier, vol. 208(C).

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