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:
“Who shall forbid a wise skepticism, seeing that there is no practical question on which any thing more than an approximate solution can be had? Is not marriage an open question, when it is alleged, from the beginning of the world, that such as are in the institution wish to get out, and such as are out wish to get in?”
—Ralph Waldo Emerson (1803–1882)
“There is a lot of talk now about metal detectors and gun control. Both are good things. But they are no more a solution than forks and spoons are a solution to world hunger.”
—Anna Quindlen (b. 1953)
“I can’t quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this world’s problems.”
—Robert Benchley (1889–1945)