Women's preference Women also have their preference lists. Assume no tie. The general case can be handled similarly. 6
Women’s preference ◼ Women also have their preference lists. ◼ Assume no tie. ❑ The general case can be handled similarly. 6
Setting n men.n women Each man has a preference list of all women Each woman has a preference list of all men We want to match them. W1>W2>W3>W4 W1 m3>m1>m2>m4 W1>W2>W3>W4 m2 W2 m3>m4>m1>m2 W2>W1>W3>W4 m3 W3 m1>m4>m2>m3 W3>W2>W4>W1 m4 m4>m1>m3>m2 7
Setting ◼ 𝑛 men, 𝑛 women ◼ Each man has a preference list of all women ◼ Each woman has a preference list of all men ◼ We want to match them. 𝑚3 > 𝑚1 > 𝑚2 > 𝑚4 𝑚3 > 𝑚4 > 𝑚1 > 𝑚2 𝑚1 > 𝑚4 > 𝑚2 > 𝑚3 𝑚4 > 𝑚1 > 𝑚3 > 𝑚2 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑚1 𝑤1 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑤2 > 𝑤1 > 𝑤3 > 𝑤4 𝑤3 > 𝑤2 > 𝑤4 > 𝑤1 𝑚2 𝑚3 𝑚4 𝑤2 𝑤3 𝑤4 7
Setting Consider this matching. And this pair (m1,W1). 口 m is matched to w2,but he likes wi more. wi is matched to mz,but she likes wi more. What if m and wi meet one day? W1>W2>W3>W4 m W1 m3>m1>m2>m4 W1>W2>W3>W4 m2 W2 m3>m4>m1>m2 W2>W1>W3>W4 m3 W3 m1>m4>m2>m3 W3>W2>W4>W1 m4 m4>m1>m3>m2 8
Setting ◼ Consider this matching. ◼ And this pair 𝑚1,𝑤1 . ❑ 𝑚1 is matched to 𝑤2, but he likes 𝑤1 more. ❑ 𝑤1 is matched to 𝑚2, but she likes 𝑤1 more. ◼ What if 𝑚1 and 𝑤1 meet one day? 𝑚3 > 𝑚1 > 𝑚2 > 𝑚4 𝑚3 > 𝑚4 > 𝑚1 > 𝑚2 𝑚1 > 𝑚4 > 𝑚2 > 𝑚3 𝑚4 > 𝑚1 > 𝑚3 > 𝑚2 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑚1 𝑤1 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑤2 > 𝑤1 > 𝑤3 > 𝑤4 𝑤3 > 𝑤2 > 𝑤4 > 𝑤1 𝑚2 𝑚3 𝑚4 𝑤2 𝑤3 𝑤4 8
A stability property Suppose there are two couples with these preferences. W1>W2 mi m1>m2 W1>W2 m2 W2 m1>m2 The marriage is unstable,because m and wi like each other more than their currently assigned ones！ 9
A stability property ◼ Suppose there are two couples with these preferences. ◼ The marriage is unstable, because 𝑚1 and 𝑤1 like each other more than their currently assigned ones! 𝑚1 𝑤2 𝑤1 𝑚2 𝑤1 > 𝑤2 𝑤1 > 𝑤2 𝑚1 > 𝑚2 𝑚1 > 𝑚2 9
Stability Such a pair is called a blocking pair. W1>W2 m W1 m1>m2 W1>W2 m2 W2 m1>m2 Question:Can we have a matching without any blocking pair? Such a matching is then called a stable matching. 10
Stability ◼ Such a pair is called a blocking pair. ◼ Question: Can we have a matching without any blocking pair? ❑ Such a matching is then called a stable matching. 𝑚1 𝑤2 𝑤1 𝑚2 𝑤1 > 𝑤2 𝑤1 > 𝑤2 𝑚1 > 𝑚2 𝑚1 > 𝑚2 10