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

Fragile Stable Matchings

Author

Listed:
  • Kirill Rudov

Abstract

We show how fragile stable matchings are in a decentralized one-to-one matching setting. The classical work of Roth and Vande Vate (1990) suggests simple decentralized dynamics in which randomly-chosen blocking pairs match successively. Such decentralized interactions guarantee convergence to a stable matching. Our first theorem shows that, under mild conditions, any unstable matching -- including a small perturbation of a stable matching -- can culminate in any stable matching through these dynamics. Our second theorem highlights another aspect of fragility: stabilization may take a long time. Even in markets with a unique stable matching, where the dynamics always converge to the same matching, decentralized interactions can require an exponentially long duration to converge. A small perturbation of a stable matching may lead the market away from stability and involve a sizable proportion of mismatched participants for extended periods. Our results hold for a broad class of dynamics.

Suggested Citation

  • Kirill Rudov, 2024. "Fragile Stable Matchings," Papers 2403.12183, arXiv.org.
    • Handle: RePEc:arx:papers:2403.12183
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Dogan, Battal & Ehlers, Lars, 2021. "Minimally unstable Pareto improvements over deferred acceptance," Theoretical Economics, Econometric Society, vol. 16(4), November.
    2. Herings, P. Jean-Jacques & Mauleon, Ana & Vannetelbosch, Vincent, 2020. "Matching with myopic and farsighted players," Journal of Economic Theory, Elsevier, vol. 190(C).
    3. Philip J. Reny, 2021. "A simple sufficient condition for a unique and student-efficient stable matching in the college admissions problem," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 9(1), pages 7-9, April.
    4. Newton, Jonathan & Sawa, Ryoji, 2015. "A one-shot deviation principle for stability in matching problems," Journal of Economic Theory, Elsevier, vol. 157(C), pages 1-27.
    5. E. Inarra & C. Larrea & E. Molis, 2008. "Random paths to P-stability in the roommate problem," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 461-471, March.
    6. Hector Chade & Jan Eeckhout & Lones Smith, 2017. "Sorting through Search and Matching Models in Economics," Journal of Economic Literature, American Economic Association, vol. 55(2), pages 493-544, June.
    7. Marcelo Ariel Fernandez & Kirill Rudov & Leeat Yariv, 2022. "Centralized Matching with Incomplete Information," American Economic Review: Insights, American Economic Association, vol. 4(1), pages 18-33, March.
    8. Fuhito Kojima & Mihai Manea, 2010. "Axioms for Deferred Acceptance," Econometrica, Econometric Society, vol. 78(2), pages 633-653, March.
    9. 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.
    10. Julien Combe & Umut Mert Dur & Olivier Tercieux & Camille Terrier & M. Utku Ünver, 2022. "Market Design for Distributional Objectives in (Re)assignment: An Application to Improve the Distribution of Teachers in Schools," Boston College Working Papers in Economics 1050, Boston College Department of Economics.
    11. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    12. Robert E. Hall & Alan B. Krueger, 2012. "Evidence on the Incidence of Wage Posting, Wage Bargaining, and On-the-Job Search," American Economic Journal: Macroeconomics, American Economic Association, vol. 4(4), pages 56-67, October.
    13. Donald Boyd & Hamilton Lankford & Susanna Loeb & James Wyckoff, 2013. "Analyzing the Determinants of the Matching of Public School Teachers to Jobs: Disentangling the Preferences of Teachers and Employers," Journal of Labor Economics, University of Chicago Press, vol. 31(1), pages 83-117.
    14. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    15. Emiliya Lazarova & Dinko Dimitrov, 2017. "Paths to stability in two-sided matching under uncertainty," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 29-49, March.
    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. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2022. "Limited Farsightedness in Priority-Based Matching," Papers 2212.07427, arXiv.org.
    2. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    3. Hirata, Daisuke & 平田, 大祐 & Kasuya, Yusuke & 糟谷, 祐介 & Okumura, Yasunori & 奥村, 保規, 2023. "Stability, Strategy-Proofness, and Respect for Improvements," Discussion Papers 2023-01, Graduate School of Economics, Hitotsubashi University.
    4. Yajing Chen & Zhenhua Jiao & Chenfeng Zhang & Luosai Zhang, 2021. "The Machiavellian frontier of top trading cycles," Papers 2106.14456, arXiv.org, revised Apr 2024.
    5. Afacan, Mustafa Og̃uz & Dur, Umut Mert, 2017. "When preference misreporting is Harm[less]ful?," Journal of Mathematical Economics, Elsevier, vol. 72(C), pages 16-24.
    6. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    7. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    8. Pietro Ortoleva & Evgenii Safonov & Leeat Yariv, 2021. "Who Cares More? Allocation with Diverse Preference Intensities," Papers 2108.12025, arXiv.org.
    9. Michael D. Bates & Michael Dinerstein & Andrew C. Johnston & Isaac Sorkin, 2022. "Teacher Labor Market Policy and the Theory of the Second Best," NBER Working Papers 29728, National Bureau of Economic Research, Inc.
    10. 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.
    11. Nikhil Agarwal & Eric Budish, 2021. "Market Design," NBER Working Papers 29367, National Bureau of Economic Research, Inc.
    12. Yajing Chen, 2017. "New axioms for deferred acceptance," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 393-408, February.
    13. Itai Ashlagi & Mark Braverman & Avinatan Hassidim, 2014. "Stability in Large Matching Markets with Complementarities," Operations Research, INFORMS, vol. 62(4), pages 713-732, August.
    14. Tomoya Tajika & Tomoya Kazumura, 2019. "Non-manipulability of uniform price auctions with a large number of objects," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 543-569, June.
    15. Itai Ashlagi & Mark Braverman & Yash Kanoria & Peng Shi, 2020. "Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations," Management Science, INFORMS, vol. 66(5), pages 2163-2193, May.
    16. Pierre Callataÿ & Ana Mauleon & Vincent Vannetelbosch, 2024. "Minimal farsighted instability," International Journal of Game Theory, Springer;Game Theory Society, vol. 53(2), pages 493-523, June.
    17. Gregory Z. Gutin & Philip R. Neary & Anders Yeo, 2021. "Unique Stable Matchings," Papers 2106.12977, arXiv.org, revised Jul 2023.
    18. Jacob Schwartz & Kyungchul Song, 2021. "The Law of Large Numbers for Large Stable Matchings," Papers 2101.00399, arXiv.org, revised Mar 2024.
    19. Liu, Ce, 2018. "Stability in Repeated Matching Markets," Working Papers 2018-13, Michigan State University, Department of Economics.
    20. Timm Opitz & Christoph Schwaiger, 2023. "Reciprocal Preferences in Matching Markets," Rationality and Competition Discussion Paper Series 388, CRC TRR 190 Rationality and Competition.

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