Other
A slightly modified version of stable matching is a Stable Roommates Problem. 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.
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 ot
c++
No comment