This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Random paths to stability in the roommate problem

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Effrosyni Diamantoudi () (Concordia University - Department of Economics)
Eiichi Miyagawa () (Columbia University - Department of Economics)
Licun Xue () (McGill University - Department of Economics)

Additional information is available for the following registered author(s):

Abstract

This paper studies whether a sequence of myopic blockings leads to a stable matching in the roommate problem. We prove that if a stable matching exists and preferences are strict, then for any unstable matching, there exists a finite sequence of successive myopic blockings leading to a stable matching. This implies that, starting from any unstable matching, the process of allowing a randomly chosen blocking pair to form converges to a stable matching with probability one. This result generalizes those of Roth and Vande Vate (1990) and Chung (2000)under strict preferences.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://www.econ.columbia.edu/RePEc/pdf/DP0102-65.pdf
File Format: application/pdf
File Function:
Download Restriction: no

Publisher Info
Paper provided by Columbia University, Department of Economics in its series Discussion Papers with number 0102-65.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length: 15 pages
Date of creation: 2002
Date of revision:
Handle: RePEc:clu:wpaper:0102-65

Contact details of provider:
Postal: 1022 International Affairs Building, 420 West 118th Street, New York, NY 10027
Phone: (212) 854-3680
Fax: (212) 854-8059
Web page: http://www.econ.columbia.edu/
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Discussion Paper Coordinator).

Related research
Keywords:

Other versions of this item:

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
  1. Roth, Alvin E & Vande Vate, John H, 1990. "Random Paths to Stability in Two-Sided Matching," Econometrica, Econometric Society, vol. 58(6), pages 1475-80, November. [Downloadable!] (restricted)
  2. Sengupta, Abhijit & Sengupta, Kunal, 1996. "A Property of the Core," Games and Economic Behavior, Elsevier, vol. 12(2), pages 266-273, February. [Downloadable!] (restricted)
  3. Roth, Alvin E. & Sotomayor, Marilda, 1992. "Two-sided matching," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 16, pages 485-541 Elsevier. [Downloadable!] (restricted)
  4. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November. [Downloadable!] (restricted)
  5. Feldman, Allan M, 1974. "Recontracting Stability," Econometrica, Econometric Society, vol. 42(1), pages 35-44, January. [Downloadable!] (restricted)
  6. Green, Jerry R, 1974. "The Stability of Edgeworth's Recontracting Process," Econometrica, Econometric Society, vol. 42(1), pages 21-34, January. [Downloadable!] (restricted)
  7. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February. [Downloadable!] (restricted)
  8. Tayfun Sönmez & Suryapratim Banerjee & Hideo Konishi, 2001. "Core in a simple coalition formation game," Social Choice and Welfare, Springer, vol. 18(1), pages 135-153. [Downloadable!] (restricted)
    Other versions:
Full references

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

  1. E. Inarra & C. Larrea & E. Molis, 2008. "Random paths to P-stability in the roommate problem," International Journal of Game Theory, Springer, vol. 36(3), pages 461-471, March. [Downloadable!] (restricted)
  2. Somdeb Lahiri, 2003. "Stable Outcomes For Contract Choice Problems," Game Theory and Information 0311001, EconWPA. [Downloadable!]
    Other versions:
  3. Hideo Konishi & M. Utku Unver, 2003. "Credible Group-Stability in Many-to-Many Matching Problems," Boston College Working Papers in Economics 570, Boston College Department of Economics, revised 19 Jan 2005. [Downloadable!]
    Other versions:
  4. Bettina Klaus & Flip Klijn & Markus Walzl, 2007. "The Evolution of Roommate Networks: A Comment on Jackson and Watts JET (2002)," UFAE and IAE Working Papers 694.07, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC). [Downloadable!]
    Other versions:
  5. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei. [Downloadable!]
    Other versions:
  6. Gabrielle Demange, 2006. "The strategy structure of some coalition formation games," PSE Working Papers 2006-38, PSE (Ecole normale supérieure). [Downloadable!]
    Other versions:
  7. Angelov, Nikolay, 2006. "Modelling firm mergers as a roommate problem," Working Paper Series 2006:10, Uppsala University, Department of Economics. [Downloadable!]
    Other versions:
  8. Klaus, Bettina & Klijn, Flip & Walzl, Markus, 2008. "Stochastic Stability for Roommate Markets," Research Memoranda 010, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
  9. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Pairwise Kidney Exchange," Game Theory and Information 0408001, EconWPA, revised 16 Feb 2005. [Downloadable!]
    Other versions:
  10. Bettina Klaus & Flip Klijn, 2004. "Paths to Stability for Matching Markets with Couples," UFAE and IAE Working Papers 604.04, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC), revised 01 Dec 2005. [Downloadable!]
    Other versions:
  11. Peeters, Ronald & Strobel, Martin & Vermeulen, Dries & Walzl, Markus, 2007. "The impact of the irrelevant – Temporary buy-options and bidding behavior in online auctions," Research Memoranda 027, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
  12. Bettina Klaus & Flip Klijn, 2007. "Smith and Rawls Share a Room," UFAE and IAE Working Papers 706.07, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC). [Downloadable!]
    Other versions:
  13. Klaus, Bettina & Klijn, Flip, 2008. "Smith and Rawls Share a Room: Stability and Medians," Research Memoranda 009, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
    Other versions:
Statistics
Access and download statistics

Did you know? RePEc also has a blog.

This page was last updated on 2009-11-16.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.