Stable roommates problem

In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching — a matching in which there is no pair of elements, each from a different matched set, where each member of the pair prefers the other to their match. This is different from the stable marriage problem in that the stable roommates problem does not require that a set is broken up into male and female subsets. Any person can prefer anyone in the same set.

It is commonly stated as:

In a given instance of the Stable Roommates problem (SRP), each of 2n participants ranks the others in strict order of preference. A matching is a set of n disjoint (unordered) pairs of participants. A matching M in an instance of SRP is stable if there are no two participants x and y, each of whom prefers the other to his partner in M. Such a pair is said to block M, or to be a blocking pair with respect to M.

Solution

Unlike the stable marriage problem, the stable roommates may not, in general, have a solution. For a minimal counterexample, consider 4 people A, B, C and D such that the rankings are:

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

In this ranking, each of A,B,C is the most favorite of someone. In any solution, one of A,B,C must be paired with D and the other 2 with each other (for example AD and BC) yet D's partner and the one for whom D's partner is most favorite would each prefer to be with each other. In this example, AC is a more favorable pairing.

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(n²) 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)
	}

Example

The following are the preference lists for a Stable Roommates instance involving 6 participants p₁, p₂, p₃, p₄, p₅, p₆.

p₁ :   p₃   p₄   p₂   p₆   p₅
p₂ :   p₆   p₅   p₄   p₁   p₃
p₃ :   p₂   p₄   p₅   p₁   p₆
p₄ :   p₅   p₂   p₃   p₆   p₁
p₅ :   p₃   p₁   p₂   p₄   p₆
p₆ :   p₅   p₁   p₃   p₄   p₂

A possible execution of Phase 1 consists of the following sequence of proposals and rejections, where → represents proposes to and × represents rejects.

p₁ → p₃
p₂ → p₆
p₃ → p₂
p₄ → p₅
p₅ → p₃;   p₃ × p₁
p₁ → p₄
p₆ → p₅;   p₅ × p₆
p₆ → p₁

So Phase 1 ends with the set S = {(p₁,p₄), (p₂,p₆), (p₃,p₂), (p₄,p₅), (p₅,p₃), (p₆,p₁)}.

In Phase 2, the rotation r₁ = (p₁,p₄), (p₃,p₂) is first identified. This is because p₂ is p₁'s second favorite, and p₄ is the second favorite of p₃. Applying r₁ gives the new set S = {(p₁,p₂), (p₂,p₆), (p₃,p₄), (p₄,p₅), (p₅,p₃), (p₆,p₁)}. Next, the rotation r₂ = (p₁,p₂), (p₂,p₆), (p₄,p₅) is identified, and application of r₂ gives S = {(p₁,p₆), (p₂,p₅), (p₃,p₄), (p₄,p₂), (p₅,p₃), (p₆,p₁)}. Finally, the rotation r₃ = (p₂,p₅), (p₃,p₄) is identified, application of which gives S = {(p₁,p₆), (p₂,p₄), (p₃,p₅), (p₄,p₂), (p₅,p₃), (p₆,p₁)}. This is a matching, and is guaranteed to be stable.

References

• Irving, Robert W. (1985), "An efficient algorithm for the "stable roommates" problem", Journal of Algorithms, 6 (4): 577–595, doi:10.1016/0196-6774(85)90033-1
• Irving, Robert W.; Manlove, David F. (2002), "The Stable Roommates Problem with Ties" (PDF), Journal of Algorithms, 43 (1): 85–105, doi:10.1006/jagm.2002.1219