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:
“To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
—Vladimir Nabokov (1899–1977)
“There’s one solution that ends all life’s problems.”
—Chinese proverb.
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)