2019/07. Stability against Robust Deviations in the Roommate Problem
Daisuke Hirata, Hitotsubashi University; Yusuke Kasuya, Kobe University and Kentaro Tomoeda, University of Technology Sydney
Date of publication: May 2019
Working paper number: 07
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 there is no robust deviation 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.