Stable Roommates Problem - Algorithm

Algorithm

An efficient algorithm was given in (Irving 1985). The algorithm will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching.

Irving's algorithm has O(n2) complexity, provided suitable data structures are used to facilitate manipulation of the preference lists and identification of rotations (see below).

The algorithm consists of two phases. In the first phase, participants propose to each other, in a manner similar to that of the Gale Shapley algorithm for the stable marriage problem. Participants propose to each person on their preference list, in order, continuing to the next person if and when their current proposal is rejected. A participant rejects a proposal if he already holds, or subsequently receives, a proposal from someone he prefers. In this first phase, one participant might be rejected by all of the others, an indicator that no stable matching is possible. Otherwise, Phase 1 ends with each person holding a proposal from one of the others – this situation can be represented as a set S of ordered pairs of the form (p,q), where q holds a proposal from p – we say that q is p's current favorite. In the case that this set represents a matching, i.e., (q,p) is in S whenever (p,q) is, the algorithm terminates with this matching, which is bound to be stable.

Otherwise the algorithm enters Phase 2, in which the set S is repeatedly changed by the application of so-called rotations. Suppose that (p,q) is in the set S but (q,p) is not. For each such p we identify his current second favorite to be the first successor of q in p's preference list who would reject the proposal that he holds in favor of p. A rotation relative to S is a sequence (p₀,q₀), (p₁,q₁),. . ., (p_k-1,q_k-1) such that (p_i,q_i) is in S for each i, and q_i+1 is p_i's current second favorite (where i + 1 is taken modulo k). If, such a rotation (p₀,q₀), . . ., (p_2k,q_2k), of odd length, is found such that p_i = q_i+k+1 for all i (where i + k + 1 is taken modulo 2k + 1), this is what is referred to as an odd party, which is also an indicator that there is no stable matching. Otherwise, application of the rotation involves replacing the pairs (p_i,q_i), in S by the pairs (p_i,q_i+1), (where i + 1 is again taken modulo k).

Phase 2 of the algorithm can now be summarized as follows:

S = output of Phase 1; while (true) { identify a rotation r in S; if (r is an odd party) return null; (there is no stable matching) else apply r to S; if (S is a matching) return S; (guaranteed to be stable) }