counter example of a stable matching
Solution 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.