Academic Commons


Random paths to stability in the roommate problem

Diamantoudi, Effrosyni; Miyagawa, Eiichi; Xue, Licun

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.



More About This Work

Academic Units
Department of Economics, Columbia University
Department of Economics Discussion Papers, 0102-65
Published Here
March 23, 2011


June 2002

Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.