IDEAS home Printed from https://ideas.repec.org/p/ecl/harjfk/rwp19-016.html
   My bibliography  Save this paper

A Perfectly Robust Approach to Multiperiod Matching Problems

Author

Listed:
  • Kotowski, Maciej

    (Harvard Kennedy School)

Abstract

Many two-sided matching situations involve multiperiod interaction. Traditional cooperative solutions, such as stability and the core, often identify unintuitive outcomes (or are empty) when applied to such markets. As an alternative, this study proposes the criterion of perfect alpha-stability. An outcome is perfect alpha-stable if no coalition prefers an alternative assignment in any period that is superior for all plausible market continuations. Behaviorally, the solution combines foresight about the future and a robust evaluation of contemporaneous outcomes. A perfect alpha-stable matching exists, even when preferences exhibit inter-temporal complementarities. A stronger solution, the perfect alpha-core, is also investigated. Extensions to markets with arrivals and departures, transferable utility, and many-to-one assignments are proposed.

Suggested Citation

  • Kotowski, Maciej, 2019. "A Perfectly Robust Approach to Multiperiod Matching Problems," Working Paper Series rwp19-016, Harvard University, John F. Kennedy School of Government.
    • Handle: RePEc:ecl:harjfk:rwp19-016
    as

    Download full text from publisher

    File URL: https://research.hks.harvard.edu/publications/getFile.aspx?Id=2790
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Damiano, Ettore & Lam, Ricky, 2005. "Stability in dynamic matching markets," Games and Economic Behavior, Elsevier, vol. 52(1), pages 34-53, July.
    2. Chander, Parkash & Wooders, Myrna, 2020. "Subgame-perfect cooperation in an extensive game," Journal of Economic Theory, Elsevier, vol. 187(C).
    3. Scarf, Herbert E., 1971. "On the existence of a coopertive solution for a general class of N-person games," Journal of Economic Theory, Elsevier, vol. 3(2), pages 169-181, June.
    4. Haeringer, Guillaume & Iehlé, Vincent, 2021. "Gradual college admission," Journal of Economic Theory, Elsevier, vol. 198(C).
    5. Sasaki, Hiroo & Toda, Manabu, 1996. "Two-Sided Matching Problems with Externalities," Journal of Economic Theory, Elsevier, vol. 70(1), pages 93-108, July.
    6. Laura Doval, 2019. "Dynamically Stable Matching," Papers 1906.11391, arXiv.org, revised Feb 2021.
    7. Bernheim, B Douglas, 1984. "Rationalizable Strategic Behavior," Econometrica, Econometric Society, vol. 52(4), pages 1007-1028, July.
    8. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    9. Pereyra, Juan Sebastián, 2013. "A dynamic school choice model," Games and Economic Behavior, Elsevier, vol. 80(C), pages 100-114.
    10. Habis, Helga & Herings, P. Jean-Jacques, 2011. "Core concepts for incomplete market economies," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 595-609.
    11. Doval, Laura, 2022. "Dynamically stable matching," Theoretical Economics, Econometric Society, vol. 17(2), May.
    12. Attila Ambrus, 2006. "Coalitional Rationalizability," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 121(3), pages 903-929.
    13. Kadam, Sangram V. & Kotowski, Maciej H., 2018. "Time horizons, lattice structures, and welfare in multi-period matching markets," Games and Economic Behavior, Elsevier, vol. 112(C), pages 1-20.
    14. Tom Ginsburg & Jeffrey Wolf, "undated". "The Market for Elite Law Firm Associates," University of Illinois Legal Working Paper Series uiuclwps-1000, University of Illinois College of Law.
    15. Sangram V. Kadam & Maciej H. Kotowski, 2018. "Multiperiod Matching," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 59(4), pages 1927-1947, November.
    16. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    17. Samuelson, William & Zeckhauser, Richard, 1988. "Status Quo Bias in Decision Making," Journal of Risk and Uncertainty, Springer, vol. 1(1), pages 7-59, March.
    18. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    19. Morimitsu Kurino, 2020. "Credibility, efficiency, and stability: a theory of dynamic matching markets," The Japanese Economic Review, Springer, vol. 71(1), pages 135-165, January.
    20. Liu, Ce, 2023. "Stability in repeated matching markets," Theoretical Economics, Econometric Society, vol. 18(4), November.
    21. Posner, Richard A. & Avery, Christopher & Jolls, Christine & Roth, Alvin, 2001. "The Market for Federal Judicial Law Clerks," Scholarly Articles 2623748, Harvard University Department of Economics.
    22. Roth, Alvin E., 1985. "The college admissions problem is not equivalent to the marriage problem," Journal of Economic Theory, Elsevier, vol. 36(2), pages 277-288, August.
    23. Bernheim, B. Douglas & Peleg, Bezalel & Whinston, Michael D., 1987. "Coalition-Proof Nash Equilibria I. Concepts," Journal of Economic Theory, Elsevier, vol. 42(1), pages 1-12, June.
    24. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    25. Alvin E. Roth, 2002. "The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics," Econometrica, Econometric Society, vol. 70(4), pages 1341-1378, July.
    26. John Kennes & Daniel Monte & Norovsambuu Tumennasan, 2019. "Strategic Performance of Deferred Acceptance in Dynamic Matching Problems," American Economic Journal: Microeconomics, American Economic Association, vol. 11(2), pages 55-97, May.
    27. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    28. Gale, Douglas, 1978. "The core of a monetary economy without trust," Journal of Economic Theory, Elsevier, vol. 19(2), pages 456-491, December.
    29. Neil Thakral, 2019. "Matching with Stochastic Arrival," AEA Papers and Proceedings, American Economic Association, vol. 109, pages 209-212, May.
    30. Diamantoudi, Effrosyni & Miyagawa, Eiichi & Xue, Licun, 2015. "Decentralized matching: The role of commitment," Games and Economic Behavior, Elsevier, vol. 92(C), pages 1-17.
    31. Ce Liu & Ziwei Wang & Hanzhe Zhang, 2023. "Self-Enforced Job Matching," Papers 2308.13899, arXiv.org.
    32. John Kennes Jr. & Daniel Monte Jr. & Norovsambuu Tumennasan Jr., 2014. "The Day Care Assignment: A Dynamic Matching Problem," American Economic Journal: Microeconomics, American Economic Association, vol. 6(4), pages 362-406, November.
    33. Pearce, David G, 1984. "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica, Econometric Society, vol. 52(4), pages 1029-1050, July.
    34. Bernheim, B. Douglas & Whinston, Michael D., 1987. "Coalition-Proof Nash Equilibria II. Applications," Journal of Economic Theory, Elsevier, vol. 42(1), pages 13-29, June.
    35. Becker, Robert A & Chakrabarti, Subir K, 1995. "The Recursive Core," Econometrica, Econometric Society, vol. 63(2), pages 401-423, March.
    36. Qingmin Liu & George J. Mailath & Andrew Postlewaite & Larry Samuelson, 2014. "Stable Matching With Incomplete Information," Econometrica, Econometric Society, vol. 82(2), pages 541-587, March.
    37. Ambrus, Attila, 2006. "Coalitional Rationalizability," Scholarly Articles 3200266, Harvard University Department of Economics.
    38. Dean Corbae & Ted Temzelides & Randall Wright, 2003. "Directed Matching and Monetary Exchange," Econometrica, Econometric Society, vol. 71(3), pages 731-756, May.
    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. Doval, Laura & Schenone, Pablo, 2024. "Consistent conjectures in dynamic matching markets," Mathematical Social Sciences, Elsevier, vol. 132(C), pages 114-127.
    2. Morimitsu Kurino, 2020. "Credibility, efficiency, and stability: a theory of dynamic matching markets," The Japanese Economic Review, Springer, vol. 71(1), pages 135-165, January.
    3. Umut Dur & Thayer Morrill & William Phan, 2024. "Partitionable choice functions and stability," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(2), pages 359-375, September.
    4. Ce Liu, 2020. "Stability in Repeated Matching Markets," Papers 2007.03794, arXiv.org, revised Mar 2021.
    5. Haeringer, Guillaume & Iehlé, Vincent, 2021. "Gradual college admission," Journal of Economic Theory, Elsevier, vol. 198(C).
    6. Laura Doval, 2019. "Dynamically Stable Matching," Papers 1906.11391, arXiv.org, revised Feb 2021.
    7. Doval, Laura, 2022. "Dynamically stable matching," Theoretical Economics, Econometric Society, vol. 17(2), May.
    8. Vincent Iehlé, 2016. "Gradual College Admisssion," Post-Print halshs-02367006, HAL.
    9. Liu, Ce, 2023. "Stability in repeated matching markets," Theoretical Economics, Econometric Society, vol. 18(4), November.
    10. Bando, Keisuke & Kawasaki, Ryo, 2024. "Stability and substitutability in multi-period matching markets," Games and Economic Behavior, Elsevier, vol. 147(C), pages 533-553.

    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. Bando, Keisuke & Kawasaki, Ryo, 2024. "Stability and substitutability in multi-period matching markets," Games and Economic Behavior, Elsevier, vol. 147(C), pages 533-553.
    2. Kadam, Sangram V. & Kotowski, Maciej H., 2018. "Time horizons, lattice structures, and welfare in multi-period matching markets," Games and Economic Behavior, Elsevier, vol. 112(C), pages 1-20.
    3. Morimitsu Kurino, 2020. "Credibility, efficiency, and stability: a theory of dynamic matching markets," The Japanese Economic Review, Springer, vol. 71(1), pages 135-165, January.
    4. Kotowski, Maciej H., 2015. "A Note on Stability in One-to-One, Multi-period Matching Markets," Working Paper Series rwp15-042, Harvard University, John F. Kennedy School of Government.
    5. Shi, Fanqi, 2021. "Stability in sequential matching with incomplete information," Games and Economic Behavior, Elsevier, vol. 129(C), pages 492-502.
    6. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    7. Haeringer, Guillaume & Iehlé, Vincent, 2021. "Gradual college admission," Journal of Economic Theory, Elsevier, vol. 198(C).
    8. Dimakopoulos, Philipp D. & Heller, C.-Philipp, 2019. "Matching with waiting times: The German entry-level labor market for lawyers," Games and Economic Behavior, Elsevier, vol. 115(C), pages 289-313.
    9. Battal Doğan & M. Bumin Yenmez, 2023. "When does an additional stage improve welfare in centralized assignment?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(4), pages 1145-1173, November.
    10. Davi B. Costa, 2021. "Benefits of marriage as a search strategy," Papers 2108.04885, arXiv.org, revised Aug 2021.
    11. Gilles Grandjean & Ana Mauleon & Vincent Vannetelbosch, 2017. "Strongly rational sets for normal-form games," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 5(1), pages 35-46, April.
    12. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    13. Konishi, Hideo & Unver, M. Utku, 2006. "Credible group stability in many-to-many matching problems," Journal of Economic Theory, Elsevier, vol. 129(1), pages 57-80, July.
    14. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    15. Alcalde, José, 2018. "Beyond the Spanish MIR with consent: (Hidden) cooperation and coordination in matching," Games and Economic Behavior, Elsevier, vol. 110(C), pages 32-49.
    16. Ambrus, Attila, 2009. "Theories of Coalitional Rationality," Scholarly Articles 3204917, Harvard University Department of Economics.
    17. Laura Doval, 2019. "Dynamically Stable Matching," Papers 1906.11391, arXiv.org, revised Feb 2021.
    18. Doval, Laura, 2022. "Dynamically stable matching," Theoretical Economics, Econometric Society, vol. 17(2), May.
    19. Doval, Laura & Schenone, Pablo, 2024. "Consistent conjectures in dynamic matching markets," Mathematical Social Sciences, Elsevier, vol. 132(C), pages 114-127.
    20. Nobel Prize Committee, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.

    More about this item

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:ecl:harjfk:rwp19-016. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/ksharus.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.