Stable roommates problem

From Wikipedia, the free encyclopedia

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 no element of any matched set prefers an element of a different matched set that also prefers any element. This is slightly different than the stable marriage problem in that stable roommates 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.

Contents 1 Solution 2 Algorithm 3 Applications 4 References

[edit] Solution

Please help improve this section by expanding it. Further information might be found on the talk page or at requests for expansion.

[edit] Algorithm

Please help improve this section by expanding it. Further information might be found on the talk page or at requests for expansion.

An efficient algorithm was given in (Irving 1985).

[edit] Applications

Please help improve this section by expanding it. Further information might be found on the talk page or at requests for expansion.

[edit] References

• Irving, Robert W. (1985), “An efficient algorithm for the "stable roommates" problem”, Journal of Algorithms 6 (4): 577-595, ISSN 01966774, 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, ISSN 01966774, doi:10.1006/jagm.2002.1219, <http://eprints.gla.ac.uk/11/01/SRT.pdf> 

v • d • e Topics in game theory Definitions Normal form game · Extensive form game · Cooperative game · Information set · Preference Equilibrium concepts Nash equilibrium · Subgame perfection · Bayesian-Nash · Perfect Bayesian · Trembling hand · Proper equilibrium · Epsilon-equilibrium · Correlated equilibrium · Sequential equilibrium · Quasi-perfect equilibrium · Evolutionarily stable strategy · Risk dominance · Pareto efficiency Strategies Dominant strategies · Pure strategy · Mixed strategy · Tit for tat · Grim trigger · Collusion Classes of games Symmetric game · Perfect information · Dynamic game · Repeated game · Signaling game · Cheap talk · Zero-sum game · Mechanism design · Stochastic game · Nontransitive game Games Prisoner's dilemma · Traveler's dilemma · Coordination game · Chicken · Volunteer's dilemma · Dollar auction · Battle of the sexes · Stag hunt · Matching pennies · Ultimatum game · Minority game · Rock-paper-scissors · Pirate game · Dictator game · Public goods game · Bargaining problem · Blotto games  · War of attrition Theorems Minimax theorem · Purification theorems · Folk theorem · Revelation principle · Arrow's theorem