Roommates
The proof that any instance of the stable marriage problem has a solution leaves open the question of whether stable matchings are possible under less restricted situations. One such extension of the stable marriage problem is known as the stable roommates problem.

The stable roommates problem removes the specification of bipartite sets from the premise of the stable marriage problem. Instead of looking at people sorted by gender, the stable roommates problem asks college students to rank all other students, and assigns them to roommate pairs accordingly. There are many other applications of the stable roommates problem. For example, most real meeting or dating companies offer services to heterosexual, homosexual and bisexual clients. Designing an algorithm to match people given these conditions would require some combination of the stable marriage problem and the stable roommates problem. There are some stable roommates problems for which there is an obvious solution. Consider an instance of the stable marriage problem. Now let each man add every other man to his preference list in arbitrary order, so long as every man is below every woman. Let the women do the same for the other women. We have created an instance of the stable roommates problem, since every member has ranked every other member. But any solution to the original stable marriage problem will still be a solution to the derived stable roommates problem. Since every man prefers every woman to every other man, no pair of men would ever exchange their female roommates for each other, and no pair of women would exchange their male roommates for each other. This scenario seems simple enough, but before trying to develop an algorithm to pair roommates, it would be useful to know whether a stable arrangement will always exist. The negative result can be shown by counterexample. Consider the following preference sets.

We can now attempt to find a stable matching. Let’s pair Peter with Mopsy, his first choice. Then Flopsy is paired with Cottontail. But Mopsy would be happier with Flopsy than with Peter, and Flopsy would be happier with anyone than with Cottontail. So Flopsy and Mopsy would prefer each other to their assigned partners, and the matching is not stable. Now let’s try pairing Peter with Flopsy, his second choice. Then Mopsy is paired with Cottontail. But Mopsy and Peter would be happier with each other than with their assigned partners. So this matching is not stable. Finally, let’s assign Peter to Cottontail and Flopsy to Mopsy. Peter and Flopsy would be happier with each other than their assigned partners, so this matching is not stable. So pairing Peter with Flopsy, Mopsy or Cottontail leads to an unstable matching. So Peter cannot be paired with anyone. So there is no stable matching.

So there are some stable roommates problem instances for which there is no solution. It is possible, however, to find an algorithm that will either find that no matching exists or will produce a stable roommate matching if one does exist.
Let R be an instance of the stable roommates problem. Begin by assuming that everyone is free. As long as there is some person x who is free and has a nonempty preference list, x will propose to y, the first person on x’s list. Person x is assigned to be “semi-engaged” to y, but the state of person y is not changed. If person z was previously semi-engaged to y, z is assigned to be free. Finally, the preference lists are modified as follows: any person x’ such that y prefers x to x' is deleted from y’s list. The reciprocal deletions (ie y is deleted from x'’s list) are also made.

Lemma 1: Let R be a stable roommates problem and let x and y be participants in R. Then if the pair {x, y} is not present in the preference lists resulting from the execution of the above algorithm, then {x, y} could not be part of any stable roommate matching.

Proof: Without loss of generality, assume that {x, y} was the first pair deleted from the lists, and furthermore that {x, y} was deleted as a result of z proposing to x. So z cannot have a better partner than x, since no pairs were removed prior to {x, y}, and x prefers z to y, or y would not have been deleted from x’s list. Since x prefers z to y and x is z’s first choice, x cannot be paired with y in any stable matching.

Theorem 1: If there is some x in R with an empty preference list at the end of the algorithm, R has no stable solution.

Proof: By the lemma proved above, we know that no pair not in the preference lists can be part of a stable matching. But then x cannot be a member of any stable pair. So the matching is not stable.

This algorithm rules out a number of instances of the problem in which no matching exists, but only in an extremely rare case would it produce a set of preference lists in which each participant has exactly one remaining choice. In that case, the result of this algorithm would be a stable roommate matching, but in the case where each participant’s list has at least one name and where some participants’ lists contain more than one name, the algorithm presented above does not suffice do determine whether a stable roommate matching exists, let alone to produce one.

In order to find a stable roommate matching, we must define a second phase of the algorithm. We will perform this phase on the output of the first phase – that is, the preference lists from which some names have been deleted.

The second phase of the algorithm requires some slightly more complicated procedures. Instead of relying on proposals, rejections and deletions, this part of the algorithm relies on rotations.

Definition: Let _ be a set of ordered pairs (x0, y0), (x1, y1), . . . , (xr-1, yr-1). Then _ is a rotation if yi is the first person on xi’s list, yi+1 is the second person on xi’s list, and i is modulo r.

I will prove several interesting lemmas about the result of phase 1 of the algorithm.

Lemma 2: At the end of phase 1 of the algorithm, if x first on y’s list if and only if y is last on x’s list.

Proof: Let y be last on x’s list. At the end of phase 1, everyone is semi-engaged. Since no participant can have two people semi-engaged to him, everyone has exactly one participant semi-engaged to him. So the person who is last on any participant’s list is semi-engaged to him. So y is semi-engaged to x. But then x must be first on y’s list, since y has proposed to all participants ranked above x and has been rejected.

Now let x be first on y’s list. Then y has proposed to x, and there is no participant who x likes less than y on x’s list. So x is last on y’s list.

Lemma 3: If some participant in a stable roommate matching has at least two people on his or her preference list, a rotation exists.

Proof: The deletions in phase 1 are reciprocal. Let x have only y on his preference list. Then, by lemma 2, y is the first person on x’s preference list, so x is the last person on y’s preference list. Similarly, y is the last person on x’s preference list, so x is the first person on y’s preference list. So x is the only person on y’s preference list. Let S be the (nonempty) set of participants that have more than one entry on their preference list. Let f and g be a functions from S to itself such that f(x) is the first person on x’s list, and the first person on g(x)’s list is the second person on x’s list. The functions f and g are well-defined since everyone in S has a first and second person on his list.

Now, consider a graph G in which every element of S is a vertex, and there is an edge from x to g(x). Then every vertex of G has outdegree 1, so there must be a cycle in G. Call the vertices in the cycle x0, x1,. . ., xr-1. But xi+1 = g(xi), mod r. So f(xi+1) is the second person on xi’s list. So (x0, f(x0)) (x1, f(x1)) . . . (xr-1, f(xr-1)) is a rotation.

Phase 2 of the algorithm is performed by finding and eliminating rotations from the table produced by phase 1 of the algorithm. A rotation is eliminated as follows: if yi prefers xi-1 to an element in his or her list, those elements are deleted from yi’s list. To ensure that the table remains symmetrical, if xj is deleted from yi’s list, then yi is deleted from xj’s list as well.

Theorem: Given a set of phase 1 reduced preference lists and a rotation, any stable matching possible in the preference lists is also possible in the lists after the rotation has been eliminated.

Proof omitted, as it is quite technical and involves a number of lemmas. Much of the interesting work occurs in the above lemmas.

Given the above theorem and lemmas, it is possible to eliminate rotations as long as there is some preference list with more than two entries, producing a stable matching if each list is reduced to one entry, or showing that no stable matching exists if every list is empty. [GD2]

contents