Stable roommates problem
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. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of “men” and “women”.
It is commonly stated as:
Unlike the stable marriage problem, a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal example of a stable pairing not existing, consider 4 people A, B, C, and D, whose rankings are:
In this ranking, each of A, B, and C is the most preferable person for someone. 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.
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 implement the necessary manipulation of the preference lists and identification of rotations.
The algorithm consists of two phases. In Phase 1, participants propose to each other, in a manner similar to that of the Gale-Shapley algorithm for the stable marriage problem. Each participant orders the other members by preference, resulting in a preference list — an ordered set of the other participants. Participants then propose to each person on their list, in order, continuing to the next person if and when their current proposal is rejected. A participant will reject a proposal if they already hold a proposal from someone they prefer. A participant will also reject a previously-accepted proposal if they later receive a proposal that they prefer. In this case, the rejected participant will then propose to the next person on their list, continuing until a proposal is again accepted. If any participant is eventually rejected by all other participants, this indicates that no stable matching is possible. Otherwise, Phase 1 will end with each person holding a proposal from one of the others.
...
Wikipedia