19 What about Stable Matching for allocations between two groups ?

Setting:

• Two groups, say hospitals and students, each of size $n$
• Each hospital has a ranking of the $n$ residents
• Each student has a ranking of the $n$ hospitals
• Assumption : The list of preferences are strict and complete

Not all matchings are stable!

• Consider two hospitals $h_1,h_2$ and two students $s_1,s_2$
• Preferences

The Stable Matching problem asks to find a stable matching, if one exists.