June 22, 2016
The problem posed by a hypothetical (heterosexual) dating pool is referred to as the “stable marriage problem”: the objective is to arrange marriages (of the "one man one woman" variety) in such a way that no unmatched couple would rather elope with each other. Remarkably this can always be done: a 1962 Nobel-prize winning paper of David Gale and Lloyd Shapley “College admissions and the stability of marriage” describes an algorithm that can be applied to arrange stable marriages for any dating pool. I will begin by defining this two-sided matching problem and describing the algorithm that can be used to find a solution. I’ll then explain why heteronormativity is an essential feature of the algorithm and speculate that the sexism of the mathematical literature obscured the inherent sexism of the Gale-Shapley matching, which wasn’t observed until many years after a proof of this result was known. I will also describe a clever argument due to John Conway that illuminates the rich structure inherent in the space of stable matchings.
Gale and Shapley wrote that “in discussing the marriage problem, we abandoned reality altogether and entered the world of mathematical make-believe” but on this point they were mistaken: the National Resident Matching Program implements a minor (polyamorous) variation of this algorithm to match graduating medical students to residency programs every year. Motivated by this practical application, I’ll conclude with a warning about misguided attempts to “strategically” manipulate the medical match.
Emily Riehl is an Assistant Professor in the Department of Mathematics at Johns Hopkins University, specializing in category theory (aka abstract nonsense) particularly as related to homotopy theory (the study of spaces up to a possibly non-invertible continuous deformation). She received her PhD in 2011 from the University of Chicago and spent four years as an NSF and Benjamin-Peirce Postdoctoral Fellow at Harvard University. She is the author of Categorical Homotopy Theory (Cambridge University Press 2014) and the forthcoming Category Theory in Context (Dover 2016). When not thinking about math, she plays Australian Rules Football for the Baltimore-Washington Eagles and the USA Freedom (a sport picked up while on a pilgrimage to the Centre for Australian Category Theory) and is searching for a new band (an EP recorded with her former Boston-based band Unstraight should be available soon).