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) 11
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). 11
Real applications ■ Students and hospitals submit preference rankings to the clearinghouse,who uses a specified rule to decide who works where. Question:What is a good way to match students and hospitals? 12
Real applications ◼ Students and hospitals submit preference rankings to the clearinghouse, who uses a specified rule to decide who works where. ◼ Question: What is a good way to match students and hospitals? 12
More than one question Question:Does a stable matching always exist? Question:Ifyes,how to find one? Question:What mathematical /economic properties it has? 13
More than one question ◼ Question: Does a stable matching always exist? ◼ Question: If yes, how to find one? ◼ Question: What mathematical / economic properties it has? 13
Good news:Stable matchings always exist. Theorem (Gale-Shapley)For any given preference lists,there always exists a stable matching. They actually gave an algorithm,which bears some resemblance to real marriages. 14
Good news: Stable matchings always exist. ◼ Theorem (Gale-Shapley) For any given preference lists, there always exists a stable matching. ◼ They actually gave an algorithm, which bears some resemblance to real marriages. 14
Consider a simple dynamics ■廿matching f,廿blocking pair(m,w), o Remove the old pairing (m,f(m))and (w,f(w)) f(m):the woman matched to m in f.(f(w):similar.) Match m and w ▣Match f(m)andf(w) ■ Question:Would repeating this finally lead to a stable matching? W1>W2 mi m1>m2 W1>W2 m2 W2 m1>m2 15
Consider a simple dynamics ◼ ∀ matching 𝑓, ∀ blocking pair (𝑚, 𝑤), ❑ Remove the old pairing 𝑚, 𝑓 𝑚 and 𝑤, 𝑓 𝑤 ◼ 𝑓(𝑚): the woman matched to 𝑚 in 𝑓. (𝑓(𝑤): similar.) ❑ Match 𝑚 and 𝑤 ❑ Match 𝑓 𝑚 and 𝑓(𝑤) ◼ Question: Would repeating this finally lead to a stable matching? 𝑚1 𝑤2 𝑤1 𝑚2 𝑤1 > 𝑤2 𝑤1 > 𝑤2 𝑚1 > 𝑚2 𝑚1 > 𝑚2 15