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.

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 where all prefer each other to D, and A prefers B over C, B prefers C over A, and C prefers A over B (so 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, yet D's partner and the one for whom D's partner is most favorite would each prefer to be with each other.^[1]

Algorithm

This section requires expansion.

An efficient algorithm was given in (Irving 1985). The algorithm will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching.

Applications

This section requires expansion.

References

• Irving, Robert W. (1985), "An efficient algorithm for the "stable roommates" problem", Journal of Algorithms 6 (4): 577–595, doi:10.1016/0196-6774(85)90033-1 
• Irving, Robert W.; Manlove, David F. (2002), "The Stable Roommates Problem with Ties", Journal of Algorithms 43 (1): 85–105, doi:10.1006/jagm.2002.1219, http://eprints.gla.ac.uk/11/01/SRT.pdf 
• ""Roommates" is a euphemism?". http://godplaysdice.blogspot.com/2009/07/roommates-is-euphemism.html. Retrieved 2009-08-14. 

This mathematics-related article is a stub. You can help Wikipedia by expanding it. v • d • e