A generalization of the stable matching problem

It is known that there may not exist any stable matching for a given instance of the stable roommates problem. A stable partition is a structure that generalizes the notion of a stable matching; Tan proved that every instance of the stable roommates problem contains at least one such structure. In this paper the authors propose a new algorithm for finding a stable partition, and hence a new algorithm for finding a stable matching if one exists. The present algorithm processes the problem dynamically as long as certain relative preference orders are maintained. Some theoretical results about stable partitions are also presented.