The Stable Matching Problem

Abstract

How would you pair up individuals from 2 groups so that everyone is happy with their match, given that individuals have different preferences? While a solution to this problem would be useful for a match maker, it also has practical applications when matching residents to residency programs, or students to internship positions. In this talk I will define the stable matchings problem and present the famous Gale-Shapley algorithm that solves it (proof included, of course.) The ideal audience member is an undergrad that has taken a data structures and discrete math class, but this is by no means a necessity.

Bio:

Alexa Sharp, born in Canada on August 30th, believed for many years that she was born on the 31st. After a childhood growing up in both Canada and Indonesia, Alexa chose to attend the University of Waterloo, where she was able to mix school and "real work" in their Co-op program. After six years she received a Bachelor of Math in Computer Science and Combinatorics and Optimization, and since the degree had so many words in it, decided to keep collecting them. Another six years later she received a Ph.D. in Computer Science from Cornell University with a thesis on incremental algorithms, advised by Dexter Kozen. Keeping the academic streak alive, Alexa moved on to Oberlin College in Ohio, this time as a professor of Computer Science. There she stayed until 3 years ago, when she unexpectedly decided to try her hand at software engineering at Google in Cambridge. Alexa estimates she has run enough miles to circle the globe around the 28th parallel, and eaten enough candy to feed, but not nourish, a small nation. She lives in Cambridge with her family.