GSAS: Stable Matching

Hyojeong Son (University of Washington, Seattle)
-
PDL C-401

Since its introduction in 1962, the Gale Shapley algorithm has guaranteed the existence of at least one stable matching for every instance of the matching problem. This breakthrough has enabled numerous practical applications. These include job placements, school admissions, and organ transplants where stability and optimality are essential. In this talk, we review two significant developments in the analysis of stable matchings. First, we examine the work of Karlin, Oveis Gharan, and Weber, who proved that for any instance with $n$ participants, the number of stable matchings is bounded above by $C^n$ for some universal constant $C$, establishing a simply exponential upper bound. Second, we explore the research of Hoffman, Levy, and Mossel, which shows that under Mallows distributed preferences the number of stable matchings grows exponentially, with the growth rate depending continuously on the Mallows parameter $q$.

Event Type
Event Subcalendar