1

Pertaining to the Stable Roommates Problem and the algorithm developed by Robert W. Irving.

There are two (sometimes broken into three) phases in which we may come to a stable pairing of everyone in a set and their stated preferences. The first, and sometimes recognized second, simple rejection phase(s) are pretty self explanatory as to how and why they work. But the final rotation/cyclic phase has been hard to grasp. The goal is to find rotations and eliminate/reject pairs found in the rotations until stable matching is found/not found. This phase is pretty hard to explain in words so I'll try my best and hope someone already knows this problem.

My wording:

We will start with any person's remaining preference list and select the second remaining preference person1[2]. Use person1[2]'s own list and select their last remaining preference person2[L]. We use these as our starting pair (person1[2],person2[L]). With person2[L] we will repeat the above process (by selecting person2[L]'s second preference, and that persons last preference) and continue until we have once again rotated around back to our original pair of (person1[2],person2[L]). At that point we will reject all diagonal pairs (personI[2],previous personJ[L]). The rotation/reject-diagonal-pairs repeats until everyone has a single match or until it is declared that not everyone can be matched.

Algorithm's pseudocode:

FOR all rotations in (p1...pn) and (q1...qn)
such that qi is second preference of pi and pi+1 is last preference of qi 
DO:
    FOR i = 1...n -1 DO:
    reject(qi,pi+1)
    END
END

The code seems fine to implement, but is pretty hard to grasp as to why it works. I have yet to find a good video or article explaining this phase.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.