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
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 mi and wi like each other more than their currently assigned ones! 8
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 8
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. 9
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 9
Real applications If you think marriage is a bit artificial since there is no centralized arranger,here is a real application. Medical students work as interns at hospitals. In the US more than 20,000 medical students and 4,000 hospitals are matched through a clearinghouse,called NRMP (National Resident Matching Program) 10
Real applications ◼ If you think marriage is a bit artificial since there is no centralized arranger, here is a real application. ◼ Medical students work as interns at hospitals. ❑ In the US more than 20,000 medical students and 4,000 hospitals are matched through a clearinghouse, called NRMP (National Resident Matching Program). 10