In mathematics, economics and computer science, particularly in the fields of combinatorics, game theory and algorithms, the stable-roommate problem (SRP) is the problem of finding a stable matching for an even-sized set.
In any solution, one of A, B, or C must be paired with D and the other two with each other (for example AD and BC), yet for anyone who is partnered with D, another member will have rated them highest, and D's partner will in turn prefer this other member over D. In this example, AC is a more favorable pairing than AD, but the necessary remaining pairing of BD then raises the same issue, illustrating the absence of a stable matching for these participants and their preferences.
Irving's algorithm has O(n2) complexity, provided suitable data structures are used to implement the necessary manipulation of the preference lists and identification of rotations.
In Phase 1, participants propose to each other, in a manner similar to that of the Gale-Shapley algorithm for the stable marriage problem.
The resulting reduced set of preference lists together is called the Phase 1 table.
The fact that it's a stable table in which this search occurs guarantees that each pi has at least two individuals on their list.
Phase 2 of the algorithm can now be summarized as follows: To achieve an O(n2) running time, a ranking matrix whose entry at row i and column j is the position of the jth individual in the ith's list; this takes O(n2) time.
This reduces repeated traversal of the tail, since it is largely unaffected by the elimination of the rotation.
The following are the preference lists for a Stable Roommates instance involving 6 participants: 1, 2, 3, 4, 5, 6.