Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem

In the Stable Roommates problem, we seek a stable matching of the agents into pairs, in which no two agents have an incentive to deviate from their assignment. It is well known that a stable matching is unlikely to exist, but a stable partition always does and provides a succinct certificate for the unsolvability of an instance. Furthermore, apart from being a useful structural tool to study the problem, every stable partition corresponds to a stable half-matching, which has applications, for example, in sports scheduling and time-sharing applications. We establish new structural results for stable partitions and show how to enumerate all stable partitions and the cycles included in such structures efficiently. We also adapt known fairness and optimality criteria from stable matchings to stable partitions and give complexity and approximability results for the problems of computing such “fair” and “optimal” stable partitions.