Stability against robust deviations in the roommate problem

• 成果类型: Article
• 署名作者: Hirata, Daisuke; Kasuya, Yusuke; Tomoeda, Kentaro
• 署名单位: Hitotsubashi University; University of New South Wales Sydney; Kobe University; University of Technology Sydney
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2021.08.012
• 发表日期: 2021
• 页码: 474-498
• 关键词: Matching; Roommate problem; STABILITY

摘要

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 no deviation from it is robust up to depth k. As a smaller k imposes a stronger requirement for a matching to be SaRD, we investigate the existence of a matching that is SaRD with a minimal depth k. We constructively demonstrate that a SaRD matching always exists for k = 3 and establish sufficient conditions for k = 1 and 2. (C) 2021 Elsevier Inc. All rights reserved.