Stable roommates problem

from Wikipedia, the free encyclopedia

In mathematics , economics and computer science , especially in the areas of combinatorics , game theory and algorithms , the stable roommate problem ( SRP ) is the problem of finding a stable matching for an even set. A matching is a separation of the quantity into disjoint pairs ( "roommate"). The matching is "stable" when there are no two elements that are not roommates and, under the matching, prefer each other to their roommate. This differs from the stable marriage problem in that the stable roommate problem allows any two elements to be matched, not just between the classes “men” and “women”.

It is broadly described as:

In a certain case of the stable roommate problem (SRP), each of the 2n participants places the others in a strict order of preference. A matching is a set of n disjoint participant pairs. 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 its partner in M. It is said that such a couple blocks M or a blocking pair in terms of M .

solution

In contrast to the stable marriage problem, there may be no stable matching for certain groups of participants and their preferences. For a minimal example of a non-existent stable pairing, consider four people A, B, C, and D, whose ranking is as follows:

A: (B, C, D), B: (C, A, D), C: (A, B, D), D: (A, B, C)

In this ranking, each of people A, B, and C is someone's most preferred person. In any solution , one of A, B, or C must pair with D and the other two pair with each other (for example, AD and BC), but for anyone that comes up with D, another participant will have rated them the highest, and D's Partner will again prefer this other participant over D. In this example, AC is a more suitable pairing than AD. But the necessary remaining pairing of BD poses the same problem. This indicates the lack of stable matching for these participants and their preferences.

algorithm

An efficient algorithm was presented by Irving in 1985.

For each example of the problem, the algorithm will determine whether a stable matching exists and, if so, it will find such a matching. The Irving algorithm is of O ( n 2 ) complexity , provided suitable data structures are used to implement the necessary manipulation of the preference lists and the identification of rotations.

The algorithm consists of two phases. In phase 1, participants propose to each other in a similar way to the Gale-Shapley algorithm for the stable marriage problem. Each participant arranges the other participants according to their preferences. This results in a preference list - an ordered set of other participants. Participants then propose, in order, to each person on their list and move on to the next person if their current application is denied. A participant will reject an application if they already have an application from someone they prefer. A participant will also reject a previously accepted proposal if they later receive a proposal they prefer. In this case, the rejected entrant will propose to the next person on their list until a request is re-accepted. If a participant is finally rejected by all other participants, this shows that stable matching is not possible. Otherwise, phase 1 ends with each person holding an application from one of the others.

Consider two participants, q and p . If q holds a request from p , then we remove from q 's list all participants x who would come after p . Symmetrically, we remove x , q from the list of x for each remote participant , so that q is first in the list of p ; and p at the last position in q 's list, since q and each x can not be partners in a stable matching. The resulting reduced number of preference lists is referred to as a phase 1 table. If a reduced list is empty in this table, there is no stable matching. Otherwise the phase 1 table is a stable table. By definition, a stable table is the set of preference lists from the original table after members have been removed from one or more lists and the following three conditions are met (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 list.
(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 his list to p ; or p prefers the last person on his list to q .
(iii) No reduced list is empty.

Stable tables have several important properties that are used to justify the further procedure:

1. Each stable table must be a subtable of the phase 1 table, the subtable being a table in which the subtable's preference lists are those of the supertable, with some individuals removed from each other's lists.

2. If every reduced list contains exactly one person in every stable table, then the pairing of each person with the individual person on their list results in a stable matching.

3. If the Stable Roommates problem example has a stable matching, there is a stable matching contained in one of the stable tables.

4. Any stable sub-table of a stable table, and in particular any stable sub-table indicating a stable matching as in Figure 2, can be obtained by a sequence of rotation eliminations in the stable table.

These rotation eliminations include phase 2 of the Irving algorithm.

According to FIG. 2, there is a match if each reduced list in the phase 1 table contains exactly one individual.

Otherwise the algorithm enters phase 2. A rotation in a stable table T is defined as a sequence ( x 0 , y 0 ), ( x 1 , y 1 ), ..., ( x k-1 , y k-1 ) with pairwise different x i and the condition, that y i is in the first position on the reduced list of x i (or x i is in the last position on y i 's reduced list) and y i + 1 in the second position on x i ' s reduced list stands for i = 0 ,…, K-1, where the indices are taken modulo k. It follows that in a stable table with a reduced list that contains at least two individuals, such a rotation always exists. To find them, start at p 0 , with at least two individuals in their reduced list, and recursively define q i + 1 as the second person on the list of p i and p i + 1 as the last person the list of q i + 1 until this sequence repeats any p j , thus finding a rotation: it is the sequence of pairs starting with the first occurrence of ( p j , q j ) and with the pair before the last Occurrence ends. The sequence from p i to p j is called the end of the rotation. The fact that this search takes place in a stable table guarantees that every p i has at least two people on its list.

To eliminate the rotation, y i rejects x i so that x i y i + 1 proposes; this applies to every i . To restore the stable table properties (i) and (ii), for each i, all descendants of x i-1 are removed from the list of y i , and y i is removed from their lists. If a collapsed list becomes empty during this removal, there is no stable matching. Otherwise the new table is again a stable table and either already indicates a matching, since each list contains exactly one person, or another rotation can be found and eliminated so that this step is repeated.

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

T = Phase 1 Tabelle;
while (true) {
    identifiziere eine Rotation r in T;
    eliminiere r aus T;
    if eine Liste in T leer wird,
        return null; (kein stabiles Matching kann existieren)
    else if (jede reduzierte Liste in T hat die Größe 1)
        return das Matching M = {{x, y} | x und y sind auf des anderen Liste in T}; (das  ist ein stabiles Matching)
}

In order to achieve an O ( n 2 ) running time, a ranking matrix whose entry in row i and column j is the position of the j th individual in the i th list; this takes O ( n 2 ) long. The ranking matrix can be used to check at constant time intervals whether a person prefers another by comparing their ranks in the matrix. Also, instead of explicitly removing items from the preference lists, the indexes of the first, second, and last on each person's collapsed list are retained. The first person not matched , i.e. H. has at least two in their reduced list is also retained. Then in phase 2 the sequence of p i is "traversed" to find that a rotation is stored in a list and an array is used to mark individuals as visited, as in a standard depth-first graph traversal. After eliminating a rotation, we still only store its end, if any, in the list and as visited in the array. And then start looking for the next rotation with the last person at the end and otherwise with the next unmade person if there is no ending. This reduces repetitive traversal of the end as it is largely unaffected by the removal of the rotation.

example

Below are the preference lists for an example of the stable roommate problem with 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

One possible implementation of phase 1 consists of the following sequence of applications and rejections, where → makes application represents and × rejects represents.

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

Phase 1 ends with the following reduced preference lists:

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

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

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

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

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

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

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

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

Implementation in software packages

  • Java : A constraint programming model to find all stable matchings in the stable roommates problem with incomplete lists is available under the CRAPL license.
  • R : The constraint programming model is also available as part of the R package matchingMarkets.
  • API : The MatchingTools API makes the algorithm available via a free programming interface.

Individual evidence

  1. ^ Robert W. Irving: An efficient algorithm for the "stable roommates" problem . In: Journal of Algorithms . 6, No. 4, 1985, pp. 577-595. doi : 10.1016 / 0196-6774 (85) 90033-1 .
  2. ^ P. Prosser: Stable Roommates and Constraint Programming . In: Lecture Notes in Computer Science, CPAIOR 2014 Edition, Springer International Publishing . 8451, 2014, pp. 15-28.
  3. ↑ constraint encoding for stable roommates problem- . In: Java release .
  4. ^ Thilo Klein: Analysis of Stable Matchings in R: Package matchingMarkets . In: Vignette to R Package matchingMarkets . 2015.
  5. ^ MatchingMarkets: Analysis of Stable Matchings . In: R Project .
  6. ↑ MatchingTools API .

literature

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