# Why does the last phase of Irving's Stable Roommates Matching work

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.