Stable roommates problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 — 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 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 his partner in M. Such a pair is said to block M, or to be a blocking pair with respect to M.

Solution[edit]

Unlike the stable marriage problem, a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal counterexample, 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 favorite of someone. In any solution, one of A, B, or C must be paired with D and the other 2 with each other (for example AD and BC) yet D's partner and the one for whom D's partner is most favorite would each prefer to be with each other. In this example, AC is a more favorable pairing.

Algorithm[edit]

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.

Irving's algorithm has O(n2) complexity, provided suitable data structures are used to facilitate 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. Participants propose to each person on their preference list, in order, continuing to the next person if and when their current proposal is rejected. A participant rejects a proposal if he already holds, or subsequently receives, a proposal from someone he prefers. In this first phase, one participant might be rejected by all of the others, an indicator that no stable matching is possible. Otherwise, Phase 1 ends with each person holding a proposal from one of the others.

If q holds a proposal from p, then we remove from q's list all the x after p, and symmetrically, for each of those 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 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 together (the original table) with some entries removed, satisfying the following three conditions (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 his list to p; or p, the last person on his 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:

1. Any stable table must be a subtable of the Phase 1 table, where subtable is defined in the obvious sense, i.e. that the preference lists of the subtable are those of the supertable with some individuals removed from each other's lists.

2. In any stable table, if every reduced list contains exactly one individual, then pairing each individual with the single person on his list gives a stable matching.

3. If the stable roommates problem instance has a stable matching, then there is a stable matching contained in any one of the stable tables.

4. 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 (x0, y0), (x1, y1), ..., (xk-1, yk-1) such that the xi are distinct, yi is first on xi's reduced list (or xi is last on yi's reduced list) and yi+1 is second on xi'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 p0 containing at least two individuals in his reduced list, and define recursively qi+1 to be the second on pi's list and pi+1 to be the last on qi+1's list, until this sequence repeats some pj, at which point a rotation is found: it is the sequence of pairs starting at the first occurrence of (pj, qj) and ending at the pair before the last occurrence. The sequence of pi up until the pj is called the tail of the rotation. The fact that it's a stable table in which this search occurs guarantees that each pi has at least two individuals on his list.

To eliminate the rotation, yi rejects xi so that xi proposes to yi+1, for each i. To restore the stable table properties (i) and (ii), for each i, all successors of xi-1 are removed from yi's list, and yi 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(n2) 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(n2) 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 his reduced lists, is also maintained. Then, in Phase 2, the sequence of pi "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[edit]

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:

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 r1 = (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 r1 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 r2 = (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 r3 = (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.

References[edit]

Further reading[edit]

  • 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