Stable Roommates Problem
In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching — a matching in which there is no pair of elements, each from a different matched set, where each member of the pair prefers the other to their match. This is different from the stable marriage problem in that the stable roommates problem does not require that a set is broken up into male and female subsets. Any person can prefer anyone in the same set.
It is commonly stated as:
- 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. Such a pair is said to block M, or to be a blocking pair with respect to M.
Read more about Stable Roommates Problem: Solution, Algorithm
Famous quotes containing the words stable and/or problem:
“In short, no association or alliance can be happy or stable without me. People can’t long tolerate a ruler, nor can a master his servant, a maid her mistress, a teacher his pupil, a friend his friend nor a wife her husband, a landlord his tenant, a soldier his comrade nor a party-goer his companion, unless they sometimes have illusions about each other, make use of flattery, and have the sense to turn a blind eye and sweeten life for themselves with the honey of folly.”
—Desiderius Erasmus (c. 1466–1536)
“The problem of the twentieth century is the problem of the color-line—the relation of the darker to the lighter races of men in Asia and Africa, in America and the islands of the sea. It was a phase of this problem that caused the Civil War.”
—W.E.B. (William Edward Burghardt)