Combinatorial Optimization Reading Group - Akshay Ramachandran

Title: A Fixed-Point Approach to Stable Matchings

Abstract:

This talk will be independent of the previous reading group talk. Three classical results in stable matching are the correctness of Gale Shapley’s deferred acceptance algorithm, the result of Conway that Stable Matchings form a distributive lattice, and Vande Vate and later Rothblum’s result that the convex hull of stable matchings has a polynomial-sized linear description. We will used Fixed Point theorems to give unified proofs of these results. The beauty of the Fixed Point approach is not only that it gives this unified perspective, but that the techniques extend to vastly more general settings. We will conclude the talk mentioning some of these settings.