IDEAS home Printed from https://ideas.repec.org/p/uts/ecowps/2019-07.html
   My bibliography  Save this paper

Stability against Robust Deviations in the Roommate Problem

Author

Listed:
  • Daisuke Hirata

    (Hitotsubashi University)

  • Yusuke Kasuya

    (Kobe University)

  • Kentaro Tomoeda

    (University of Technology Sydney)

Abstract

We propose a new solution concept in the roommate problem, based on the �robustness� of deviations (i.e., blocking coalitions). We call a deviation from a matching robust up to depth k, if none of the deviators gets worse off than at the original matching after any sequence of at most k subsequent deviations. We say that a matching is stable against robust deviations (for short, SaRD) up to depth k, if there is no robust deviation up to depth k. As a smaller k imposes a stronger requirement for amatching to be SaRD, we investigate the existence of a matching that is SaRD with a minimal depth k. We constructively demonstrate that a SaRDmatching always exists for k = 3, and establish sufficient conditions for k = 1 and 2.

Suggested Citation

  • Daisuke Hirata & Yusuke Kasuya & Kentaro Tomoeda, 2019. "Stability against Robust Deviations in the Roommate Problem," Working Paper Series 2019/07, Economics Discipline Group, UTS Business School, University of Technology, Sydney.
    • Handle: RePEc:uts:ecowps:2019/07
    as

    Download full text from publisher

    File URL: https://www.uts.edu.au/sites/default/files/2019-06/Kentaro%20working%20paper.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    2. 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.
    3. Klaus, Bettina & Klijn, Flip & Walzl, Markus, 2010. "Stochastic stability for roommate markets," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2218-2240, November.
    4. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    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. Hirata, Daisuke & Kasuya, Yusuke & Tomoeda, Kentaro, 2021. "Stability against robust deviations in the roommate problem," Games and Economic Behavior, Elsevier, vol. 130(C), pages 474-498.
    7. Klijn, Flip & Masso, Jordi, 2003. "Weak stability and a bargaining set for the marriage model," Games and Economic Behavior, Elsevier, vol. 42(1), pages 91-100, January.
    8. John C. Harsanyi, 1974. "An Equilibrium-Point Interpretation of Stable Sets and a Proposed Alternative Definition," Management Science, INFORMS, vol. 20(11), pages 1472-1495, July.
    9. , & , J. & ,, 2011. "Von Neumann-Morgenstern farsightedly stable sets in two-sided matching," Theoretical Economics, Econometric Society, vol. 6(3), September.
    10. Barbera, Salvador & Gerber, Anke, 2003. "On coalition formation: durable coalition structures," Mathematical Social Sciences, Elsevier, vol. 45(2), pages 185-203, April.
    11. Biró, Péter & Iñarra, Elena & Molis, Elena, 2016. "A new solution concept for the roommate problem: Q-stable matchings," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 74-82.
    12. Debraj Ray & Rajiv Vohra, 2015. "The Farsighted Stable Set," Econometrica, Econometric Society, vol. 83(3), pages 977-1011, May.
    13. Mas-Colell, Andreu, 1989. "An equivalence theorem for a bargaining set," Journal of Mathematical Economics, Elsevier, vol. 18(2), pages 129-139, April.
    14. Dutta, Bhaskar & Vohra, Rajiv, 2017. "Rational expectations and farsighted stability," Theoretical Economics, Econometric Society, vol. 12(3), September.
    15. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    16. Bettina Klaus & Flip Klijn & Markus Walzl, 2011. "Farsighted Stability for Roommate Markets," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 13(6), pages 921-933, December.
    17. Debraj Ray & Rajiv Vohra, 2019. "Maximality in the Farsighted Stable Set," Econometrica, Econometric Society, vol. 87(5), pages 1763-1779, September.
    18. 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.
    19. Iñarra, E. & Larrea, C. & Molis, E., 2013. "Absorbing sets in roommate problems," Games and Economic Behavior, Elsevier, vol. 81(C), pages 165-178.
    20. Peter Biro & Elena Iñarra & Elena Molis, 2014. "A new solution for the roommate problem. The Q-stable matchings," ThE Papers 14/04, Department of Economic Theory and Economic History of the University of Granada..
    21. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    22. Dutta, Bhaskar & Vartiainen, Hannu, 2020. "Coalition formation and history dependence," Theoretical Economics, Econometric Society, vol. 15(1), January.
    23. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
    24. Zhou Lin, 1994. "A New Bargaining Set of an N-Person Game and Endogenous Coalition Formation," Games and Economic Behavior, Elsevier, vol. 6(3), pages 512-526, May.
    25. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    26. 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.
    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. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    2. Hirata, Daisuke & Kasuya, Yusuke & Tomoeda, Kentaro, 2021. "Stability against robust deviations in the roommate problem," Games and Economic Behavior, Elsevier, vol. 130(C), pages 474-498.
    3. G.-Herman Demeze-Jouatsa & Dominik Karos, 2023. "Farsighted Rationality in Hedonic Games," Dynamic Games and Applications, Springer, vol. 13(2), pages 462-479, June.
    4. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    5. Hirata, Daisuke & Kasuya, Yusuke & Tomoeda, Kentaro, 2023. "Weak stability against robust deviations and the bargaining set in the roommate problem," Journal of Mathematical Economics, Elsevier, vol. 105(C).

    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. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    2. Hirata, Daisuke & Kasuya, Yusuke & Tomoeda, Kentaro, 2023. "Weak stability against robust deviations and the bargaining set in the roommate problem," Journal of Mathematical Economics, Elsevier, vol. 105(C).
    3. Kimya, Mert, 2020. "Farsighted Objections and Maximality in One-to-one Matching Problems," Working Papers 202014, University of Sydney, School of Economics, revised Jul 2021.
    4. Kimya, Mert, 2022. "Farsighted objections and maximality in one-to-one matching problems," Journal of Economic Theory, Elsevier, vol. 204(C).
    5. Kimya, Mert, 2020. "Farsighted Objections and Maximality in One-to-one Matching Problems," Working Papers 2020-14, University of Sydney, School of Economics.
    6. Bloch, Francis & van den Nouweland, Anne, 2020. "Farsighted stability with heterogeneous expectations," Games and Economic Behavior, Elsevier, vol. 121(C), pages 32-54.
    7. Herings, P. Jean-Jacques & Mauleon, Ana & Vannetelbosch, Vincent, 2020. "Matching with myopic and farsighted players," Journal of Economic Theory, Elsevier, vol. 190(C).
    8. Kenzo Imamura & Hideo Konishi, 2023. "Assortative Matching with Externalities and Farsighted Agents," Dynamic Games and Applications, Springer, vol. 13(2), pages 497-509, June.
    9. Ana Mauleon & Elena Molis & Vincent Vannetelbosch & Wouter Vergote, 2014. "Dominance invariant one-to-one matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 925-943, November.
    10. Mert Kimya, 2024. "Power, Status and the Stability of Hierarchies," Working Papers 2024-04, University of Sydney, School of Economics.
    11. Bettina Klaus & Flip Klijn & Markus Walzl, 2011. "Farsighted Stability for Roommate Markets," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 13(6), pages 921-933, December.
    12. Kimya, Mert, 2021. "Coalition Formation Under Dominance Invariance," Working Papers 202106, University of Sydney, School of Economics.
    13. Korpela, Ville & Lombardi, Michele & Vartiainen, Hannu, 2021. "Implementation in largest consistent set via rights structures," Games and Economic Behavior, Elsevier, vol. 128(C), pages 202-212.
    14. Korpela, Ville & Lombardi, Michele & Vartiainen, Hannu, 2019. "Implementation with foresighted agents," MPRA Paper 102496, University Library of Munich, Germany.
    15. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2023. "Matching markets with farsighted couples," UB School of Economics Working Papers 2023/445, University of Barcelona School of Economics.
    16. Mert Kimya, 2023. "Coalition Formation Under Dominance Invariance," Dynamic Games and Applications, Springer, vol. 13(2), pages 480-496, June.
    17. Jean-Jacques Herings, P. & Mauleon, Ana & Vannetelbosch, Vincent, 2017. "Stable sets in matching problems with coalitional sovereignty and path dominance," Journal of Mathematical Economics, Elsevier, vol. 71(C), pages 14-19.
    18. Kimya, Mert, 2021. "Coalition Formation Under Dominance Invariance," Working Papers 2021-06, University of Sydney, School of Economics.
    19. Wouter Vergote, 2019. "Revisiting stability in one-to-one matching problems," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 59-75, May.
    20. P. Jean-Jacques Herings & Ana Mauleon & Vincent Vannetelbosch, 2023. "Social Rationalizability with Mediation," Dynamic Games and Applications, Springer, vol. 13(2), pages 440-461, June.

    More about this item

    Keywords

    matching; stability; robustness; roommate problem;
    All these keywords.

    JEL classification:

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

    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:uts:ecowps:2019/07. 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: Duncan Ford (email available below). General contact details of provider: https://edirc.repec.org/data/edutsau.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.