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.
Read more about this topic: Stable Roommates Problem
Famous quotes containing the word solution:
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“Let us begin to understand the argument.
There is a solution to everything: Science.”
—Allen Tate (1899–1979)
“There’s one solution that ends all life’s problems.”
—Chinese proverb.