Combinatorial Optimization Reading Group - Cedric Koh

Title: A Fixed-Point Approach to Stable Matchings

Abstract:

We describe a xed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's xed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, and the monochromatic path theorem of Sands et al. Time permitting, we will also formulate a matroid-generalization of the stable marriage theorem in this framework.