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. 13Good 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. 13