I am currently reading an algorithm book and came across the Stable Matching Problem. And a question came to mind that I'm curious about, but the book doesn't answer.
The question is:
For any matching, if it is not stable, pick any blocking pair(w, m), and match them. And also match their previous partners. And repeat. Is this a correct algorithm to reach a stable matching?
It seems the answer is no. But I can not think out a counter example. Is there anyone who can help?
I think I have found the answer. Suppose we have 3 women and 3 men. The preference list of them are:
w1: m3 > m2 > m1
w2: m2 > m3 > m1
w3: don't care
m1: don't care
m2: w1 > w2 > w3
m3: w2 > w1 > w3
The initial matching: (w1,m1) (w2,m2) (w3,m3)
Step 1: w1 and m2 match, then (w1,m2) (w2,m1) (w3,m3)
Step 2: w1 and m3 match, then (w1,m3) (w2,m1) (w3,m2)
Step 3: w2 and m3 match, then (w2,m3) (w1,m1) (w3,m2)
Step 4: w2 and m2 match, then (w1,m1) (w2,m2) (w3,m3)
After 4 steps, the matching goes to the initial state, which leads to an infinite loop.