A new solution concept for the roommate problem: QQ-stable matchings

• We propose a new solution for roommate problems, called QQ-stable matchings.
• It is core consistent and conciliates most of solutions proposed in the literature.
• We construct an efficient algorithm for computing a QQ-stable matching.
• We show that the outcome of the algorithm always belongs to an absorbing set.

The aim of this paper is to propose a new solution concept for the roommate problem with strict preferences. We introduce maximum irreversible matchings and consider almost stable matchings (Abraham et al., 2006) and maximum stable matchings (Tan 1990, 1991b). These solution concepts are all core consistent. We find that almost stable matchings are incompatible with the other two concepts. Hence, to solve the roommate problem we propose matchings that lie at the intersection of the maximum irreversible matchings and maximum stable matchings, which we call QQ-stable matchings. We construct an efficient algorithm for computing one element of this set for any roommate problem. We also show that the outcome of our algorithm always belongs to an absorbing set (Inarra et al., 2013).