Stable roommates problem - Misplaced Pages

(Redirected from Stable roommate problem) Type of stable matching problem

In mathematics, economics and computer science, particularly in the fields of combinatorics, game theory and algorithms, the stable-roommate problem (SRP) is the problem of finding a stable matching for an even-sized set. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women".

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 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 their 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, a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal example of a stable pairing not existing, consider 4 people A, B, C, and D, whose 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, and C is the most preferable person for someone. In any solution, one of A, B, or C must be paired with D and the other two with each other (for example AD and BC), yet for anyone who is partnered with D, another member will have rated them highest, and D's partner will in turn prefer this other member over D. In this example, AC is a more favorable pairing than AD, but the necessary remaining pairing of BD then raises the same issue, illustrating the absence of a stable matching for these participants and their preferences.

Algorithm

An efficient algorithm (Irving 1985) is the following. The algorithm will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching. Irving's algorithm has O(n) complexity, provided suitable data structures are used to implement the necessary manipulation of the preference lists and identification of rotations.

The algorithm consists of two phases. In Phase 1, participants propose to each other, in a manner similar to that of the Gale-Shapley algorithm for the stable marriage problem. Each participant orders the other members by preference, resulting in a preference list—an ordered set of the other participants. Participants then propose to each person on their list, in order, continuing to the next person if and when their current proposal is rejected. A participant will reject a proposal if they already hold a proposal from someone they prefer. A participant will also reject a previously-accepted proposal if they later receive a proposal that they prefer. In this case, the rejected participant will then propose to the next person on their list, continuing until a proposal is again accepted. If any participant is eventually rejected by all other participants, this indicates that no stable matching is possible. Otherwise, Phase 1 will end with each person holding a proposal from one of the others.

Consider two participants, q and p. If q holds a proposal from p, then we remove from q's list all participants x after p, and symmetrically, for each removed participant x, we remove q from x's list, so that q is first in p's list; and p, last in q's, since q and any x cannot be partners in any stable matching. The resulting reduced set of preference lists together is called the Phase 1 table. In this table, if any reduced list is empty, then there is no stable matching. Otherwise, the Phase 1 table is a stable table. A stable table, by definition, is the set of preference lists from the original table after members have been removed from one or more of the lists, and the following three conditions are satisfied (where reduced list means a list in the stable table):

(i) p is first on q's reduced list if and only if q is last on p's
(ii) p is not on q's reduced list if and only if q is not on p's if and only if q prefers the last person on their list to p; or p, the last person on their list to q
(iii) no reduced list is empty

Stable tables have several important properties, which are used to justify the remainder of the procedure:

Any stable table must be a subtable of the Phase 1 table, where subtable is a table where the preference lists of the subtable are those of the supertable with some individuals removed from each other's lists.
In any stable table, if every reduced list contains exactly one individual, then pairing each individual with the single person on their list gives a stable matching.
If the stable roommates problem instance has a stable matching, then there is a stable matching contained in any one of the stable tables.
Any stable subtable of a stable table, and in particular any stable subtable that specifies a stable matching as in 2, can be obtained by a sequence of rotation eliminations on the stable table.

These rotation eliminations comprise Phase 2 of Irving's algorithm.

By 2, if each reduced list of the Phase 1 table contains exactly one individual, then this gives a matching.

Otherwise, the algorithm enters Phase 2. A rotation in a stable table T is defined as a sequence (x₀, y₀), (x₁, y₁), ..., (x_k-1, y_k-1) such that the x_i are distinct, y_i is first on x_i's reduced list (or x_i is last on y_i's reduced list) and y_i+1 is second on x_i's reduced list, for i = 0, ..., k-1 where the indices are taken modulo k. It follows that in any stable table with a reduced list containing at least two individuals, such a rotation always exists. To find it, start at such a p₀ containing at least two individuals in their reduced list, and define recursively q_i+1 to be the second on p_i's list and p_i+1 to be the last on q_i+1's list, until this sequence repeats some p_j, at which point a rotation is found: it is the sequence of pairs starting at the first occurrence of (p_j, q_j) and ending at the pair before the last occurrence. The sequence of p_i up until the p_j is called the tail of the rotation. The fact that it's a stable table in which this search occurs guarantees that each p_i has at least two individuals on their list.

To eliminate the rotation, y_i rejects x_i so that x_i proposes to y_i+1, for each i. To restore the stable table properties (i) and (ii), for each i, all successors of x_i-1 are removed from y_i's list, and y_i is removed from their lists. If a reduced list becomes empty during these removals, then there is no stable matching. Otherwise, the new table is again a stable table, and either already specifies a matching since each list contains exactly one individual or there remains another rotation to find and eliminate, so the step is repeated.

Phase 2 of the algorithm can now be summarized as follows:

T = Phase 1 table;
while (true) {
    identify a rotation r in T;
    eliminate r from T;
    if some list in T becomes empty,
        return null; (no stable matching can exist)
    else if (each reduced list in T has size 1)
        return the matching M = {{x, y} | x and y are on each other's lists in T}; (this is a stable matching)
}

To achieve an O(n) running time, a ranking matrix whose entry at row i and column j is the position of the jth individual in the ith's list; this takes O(n) time. With the ranking matrix, checking whether an individual prefers one to another can be done in constant time by comparing their ranks in the matrix. Furthermore, instead of explicitly removing elements from the preference lists, the indices of the first, second and last on each individual's reduced list are maintained. The first individual that is unmatched, i.e. has at least two in their reduced lists, is also maintained. Then, in Phase 2, the sequence of p_i "traversed" to find a rotation is stored in a list, and an array is used to mark individuals as having been visited, as in a standard depth-first search graph traversal. After the elimination of a rotation, we continue to store only its tail, if any, in the list and as visited in the array, and start the search for the next rotation at the last individual on the tail, and otherwise at the next unmatched individual if there is no tail. This reduces repeated traversal of the tail, since it is largely unaffected by the elimination of the rotation.

Example

The following are the preference lists for a Stable Roommates instance involving 6 participants: 1, 2, 3, 4, 5, 6.

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

A possible execution of Phase 1 consists of the following sequence of proposals and rejections, where → represents proposes to and × represents rejects.

1 → 3
2 → 6
3 → 2
4 → 5
5 → 3; 3 × 1
1 → 4
6 → 5; 5 × 6
6 → 1

So Phase 1 ends with the following reduced preference lists: (for example we cross out 5 for 1: because 1: gets at least 6)

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

In Phase 2, the rotation r₁ = (1,4), (3,2) is first identified. This is because 2 is 1's second favorite, and 4 is the second favorite of 3. Eliminating r₁ gives:

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

Next, the rotation r₂ = (1,2), (2,6), (4,5) is identified, and its elimination yields:

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

Hence 1 and 6 are matched. Finally, the rotation r₃ = (2,5), (3,4) is identified, and its elimination gives:

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

Hence the matching {1, 6}, {2,4}, {3, 5} is stable.

Implementation in software packages

Python: An implementation of Irving's algorithm is available as part of the matching library.
Java: A constraint programming model to find all stable matchings in the roommates problem with incomplete lists is available under the CRAPL licence.
R: The same constraint programming model is also available as part of the R matchingMarkets package.
API: The MatchingTools API provides a free application programming interface for the algorithm.
Web Application: The "Dyad Finder" website provides a free, web-based implementation of the algorithm, including source code for the website and solver written in JavaScript.
Matlab: The algorithm is implemented in the assignStableRoommates function that is part of the United States Naval Research Laboratory's free Tracker Component Library.

References

Wilde, H.; Knight, V.; Gillard, J. (2020). "Matching: A Python library for solving matching games". Journal of Open Source Software. 5 (48): 2169. Bibcode:2020JOSS....5.2169W. doi:10.21105/joss.02169.
Prosser, P. (2014). "Stable Roommates and Constraint Programming" (PDF). Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science. Vol. 8451. pp. 15–28. doi:10.1007/978-3-319-07046-9_2. ISBN 978-3-319-07045-2.
"Constraint encoding for stable roommates problem". Java release.
Klein, T. (2015). "Analysis of Stable Matchings in R: Package matchingMarkets" (PDF). Vignette to R Package MatchingMarkets.
"matchingMarkets: Analysis of Stable Matchings". R Project. 2019-02-04.
"MatchingTools API".
"Dyad Finder". dyad-finder.web.app. Retrieved 2020-05-06.
"Tracker Component Library". Matlab Repository. Retrieved January 5, 2019.

Sources

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

Fleiner, Tamás; Irving, Robert W.; Manlove, David F. (2007), "An efficient algorithm for the "stable roommates" problem", Theoretical Computer Science, 381 (1–3): 162–176, doi:10.1016/j.tcs.2007.04.029
Gusfield, Daniel M.; Irving, Robert W. (1989), The Stable Marriage Problem: Structure and Algorithms, MIT Press
Irving, Robert W.; Manlove, David F. (2002), "The Stable Roommates Problem with Ties" (PDF), Journal of Algorithms, 43 (1): 85–105, CiteSeerX 10.1.1.108.7366, doi:10.1006/jagm.2002.1219

v t e Topics of game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Pairing strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Search optimizations	Alpha–beta pruning Aspiration window Principal variation search max^n algorithm Paranoid algorithm Lazy SMP
Miscellaneous	Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons

Categories:

Solution

Algorithm

Example

Implementation in software packages

References

Sources

Further reading