Random paths to stability in the roommate problem

• 成果类型: Article
• 署名作者: Diamantoudi, E; Miyagawa, E; Xue, LC
• 署名单位: Columbia University; Concordia University - Canada; McGill University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2003.05.003
• 发表日期: 2004
• 页码: 18-28
• 关键词: roommates problem; Marriage problem; core convergence; indirect domination; cycle; odd ring

摘要

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 [Econometrica 58 (1990) 1475] and Chung [Games Econ. Behav. 33 (2000) 206] under strict preferences. (C) 2003 Elsevier Inc. All rights reserved.