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

Stable Matchings and Their Histories: Historical Reachability under Population Shocks

Author

Listed:
  • Yi-You Yang

Abstract

Sequential-entry procedures need not reach every stable matching. We ask whether full reachability is restored when agents on both sides may enter and exit repeatedly, with proposal-chain restabilization after each population change. It is not: a three-by-three marriage market has a stable matching that is unreachable from the empty active market along any such history restricted to terminal agents. We then allow temporary historical agents who are absent at the terminal date. For every target stable matching, we construct a target-dependent, preference-preserving augmentation and an admissible history that reaches it, with all temporary agents exiting before termination. The construction extends to many-to-one markets with responsive hospital preferences. Thus reachability depends on the admissible history class. Terminal-agent histories may select a proper subset of the stable set, whereas preference-preserving augmented histories recover the full stable set. When such augmented histories are admissible but past participants are unobserved, the terminal primitives alone do not exclude any stable matching.

Suggested Citation

  • Yi-You Yang, 2026. "Stable Matchings and Their Histories: Historical Reachability under Population Shocks," Papers 2609.20176, arXiv.org.
  • Handle: RePEc:arx:papers:2609.20176
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Chambers, Christopher P. & Yenmez, M. Bumin, 2018. "A simple characterization of responsive choice," Games and Economic Behavior, Elsevier, vol. 111(C), pages 217-221.
    2. Ma, Jinpeng, 1996. "On Randomized Matching Mechanisms," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(2), pages 377-381, August.
    3. Cantala, David, 2004. "Restabilizing matching markets at senior level," Games and Economic Behavior, Elsevier, vol. 48(1), pages 1-17, July.
    4. Blum, Yosef & Roth, Alvin E. & Rothblum, Uriel G., 1997. "Vacancy Chains and Equilibration in Senior-Level Labor Markets," Journal of Economic Theory, Elsevier, vol. 76(2), pages 362-411, October.
    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. Elette Boyle & Federico Echenique, 2009. "Sequential entry in many-to-one matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(1), pages 87-99, June.
    2. Beatriz Millán & Eliana Pepa Risma, 2018. "Random path to stability in a decentralized market with contracts," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 79-103, June.
    3. Raïssa-Juvette Samba Zitou & Rhonya Adli, 2012. "Quasi stable outcomes in the assignment game," Theory and Decision, Springer, vol. 72(3), pages 323-340, March.
    4. Francis Bloch & David Cantala, 2013. "Markovian assignment rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(1), pages 1-25, January.
    5. 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.
    6. Ayse Yazici, 2022. "Decentralized Matching at Senior-Level: Stability and Incentives," Department of Economics Working Papers 2022_01, Durham University, Department of Economics.
    7. Agustin G. Bonifacio & Nadia Gui~nazu & Noelia Juarez & Pablo Neme & Jorge Oviedo, 2024. "Counting steps for re-stabilization in a labor matching market," Papers 2405.07084, arXiv.org.
    8. Péter Biró & Gethin Norman, 2013. "Analysis of stochastic matching markets," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(4), pages 1021-1040, November.
    9. Manocha, Kriti & Turhan, Bertan, 2025. "Gradual matching with affirmative action," Games and Economic Behavior, Elsevier, vol. 153(C), pages 164-178.
    10. Saglam, Ismail, 2019. "Measuring the External Stability of the One-to-One Matching Generated by the Deferred Acceptance Algorithm," MPRA Paper 91472, University Library of Munich, Germany.
    11. Mill'an Guerra Beatriz Alejandra, 2022. "The outcome of the restabilization process in matching markets," Papers 2202.12452, arXiv.org.
    12. Ismail Saglam, 2020. "Measuring external stability in one-to-one matching," Economics Bulletin, AccessEcon, vol. 40(1), pages 234-247.
    13. David Cantala, 2011. "Agreement toward stability in matching markets," Review of Economic Design, Springer;Society for Economic Design, vol. 15(4), pages 293-316, December.
    14. Nadia Guiñazú & Noelia Juarez & Pablo Neme & Jorge Oviedo, 2025. "Quasi-stability notions in two-sided matching models," International Journal of Game Theory, Springer;Game Theory Society, vol. 54(2), pages 1-23, December.
    15. Yazıcı, Ayşe, 2022. "Decentralized matching at senior-level: Stability and incentives," Journal of Mathematical Economics, Elsevier, vol. 101(C).
    16. Piotr Dworczak, 2021. "Deferred Acceptance with Compensation Chains," Operations Research, INFORMS, vol. 69(2), pages 456-468, March.
    17. Samson Alva & Battal Dou{g}an, 2021. "Choice and Market Design," Papers 2110.15446, arXiv.org, revised Nov 2021.
    18. 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.
    19. Rodríguez-Álvarez, Carmelo & Romero-Medina, Antonio, 2024. "School choice with transferable student characteristics," Games and Economic Behavior, Elsevier, vol. 143(C), pages 103-124.
    20. Damiano, Ettore & Lam, Ricky, 2005. "Stability in dynamic matching markets," Games and Economic Behavior, Elsevier, vol. 52(1), pages 34-53, July.

    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:2609.20176. 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: https://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.