Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, 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
Stable marriage problem
In mathematics and computer science, the stable marriage problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set...
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.
In mathematics and computer science, the stable marriage problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set...
, 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.
Algorithm
An efficient algorithm was given in . 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 (see below).
The algorithm consists of two phases. In the first phase, participants propose to each other, in a manner similar to that of the Gale Shapley algorithm for the stable marriage problem
Stable marriage problem
In mathematics and computer science, the stable marriage problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set...
. 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 – this situation can be represented as a set S of ordered pairs of the form (p,q), where q holds a proposal from p – we say that q is ps current favorite. In the case that this set represents a matching, i.e., (q,p) is in S whenever (p,q) is, the algorithm terminates with this matching, which is bound to be stable.
Otherwise the algorithm enters Phase 2, in which the set S is repeatedly changed by the application of so-called rotations. Suppose that (p,q) is in the set S but (q,p) is not. For each such p we identify his current second favorite to be the first successor of q in ps preference list who would reject the proposal that he holds in favor of p. A rotation relative to S is a sequence (p0,q0), (p1,q1),. . ., (pk-1,qk-1) such that (pi,qi) is in S for each i, and qi+1 is pi's current second favorite (where i + 1 is taken modulo k). If, such a rotation (p0,q0), . . . , (p2k,q2k), of odd length, is found such that pi = qi+k+1 for all i (where i + k + 1 is taken modulo 2k + 1), this is what is referred to as an odd party, which is also an indicator that there is no stable matching. Otherwise, application of the rotation involves replacing the pairs (pi,qi), in S by the pairs (pi,qi+1), (where i + 1 is again taken modulo k).
Phase 2 of the algorithm can now be summarized as follows:
S = output of Phase 1;
while (true) {
identify a rotation r in S;
if (r is an odd party)
return null; (there is no stable matching)
else
apply r to S;
if (S is a matching)
return S; (guaranteed to be stable)
}
Example
The following are the preference lists for a Stable Roommates instance involving 6 participants p1, p2, p3, p4, p5, p6.
p1 : p3p4p2p6p5
p2 : p6p5p4p1p3
p3 : p2p4p5p1p6
p4 : p5p2p3p6p1
p5 : p3p1p2p4p6
p6 : p5p1p3p4p2
A possible execution of Phase 1 consists of the following sequence of proposals and rejections, where → represents proposes to and × represents rejects.
p1 → p3
p2 → p6
p3 → p2
p4 → p5
p5 → p3; p3 × p1
p1 → p4
p6 → p5; p5 × p6
p6 → p1
So Phase 1 ends with the set S = {(p1,p4), (p2,p6), (p3,p2), (p4,p5), (p5,p3), (p6,p1)}.
In Phase 2, the rotation r1 = (p1,p4), (p3,p2) is first identified. This is because p2 is p1's second favorite, and p4 is the second favorite of p3. Applying r1 gives the new set S = {(p1,p2), (p2,p6), (p3,p4), (p4,p5), (p5,p3), (p6,p1)}. Next, the rotation r2 = (p1,p2), (p2,p6), (p4,p5) is identified, and application of r2 gives S = {(p1,p6), (p2,p5), (p3,p4), (p4,p2), (p5,p3), (p6,p1)}. Finally, the rotation r3 = (p2,p5), (p3,p4) is identified, application of which gives S = {(p1,p6), (p2,p4), (p3,p5), (p4,p2), (p5,p3), (p6,p1)}. This is a matching, and is guaranteed to be stable.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
