counter example of a stable matching

Question

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?

Answer 1

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.

Answer 2

The algorithm you speak of is random matching without any thought to their preference. In this algorithm one partner could have a higher preference making any possible matches in-stable.

Stable matching by definition one where a solution is fair for all.

Also this algorithm doesn't mention avoiding previous matches making an infinite loop possible.

Answer 3

The accepted solution assumes that there is only one path but at Step 1, if m3 and w1 match and their rejected spouses match, we reach a stable matching in one step: (m1, w3), (m2, w2), (m3, w1), so it's not an infinite loop.

In fact the process explained in OP will lead to a stable matching. It was proven in the paper: Roth and Vande Vate. "Random paths to stability in two-sided matching." Econometrica: Journal of the Econometric Society (1990): 1475-1480.

Roth and Vande Vate observed that many real-life matching mechanisms were stable even though no one designed it to be as such. So they conjectured there must be random path to stability for any initial matching. And they proved that starting from an arbitrary matching, the process of allowing randomly chosen blocking pairs to match will converge to a stable matching with probability one.