Home

Random paths to stability in the roommate problem

Effrosyni Diamantoudi; Eiichi Miyagawa; Licun Xue

Title:
Random paths to stability in the roommate problem
Author(s):
Diamantoudi, Effrosyni
Miyagawa, Eiichi
Xue, Licun
Date:
Type:
Working papers
Department:
Economics
Permanent URL:
Series:
Department of Economics Discussion Papers
Part Number:
0102-65
Publisher:
Department of Economics, Columbia University
Publisher Location:
New York
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.
Subject(s):
Economic theory
Item views:
292
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use