Problem of the Week
Hilton Memorial Lecture
Given the set of hospitals nationwide, and a set of potential residents, an element of each set has a preference list for the other set. The Extended Gale-Shapley Algorithm produces a “nice” way to match each hospital to some number of residents, such that no resident nor hospital is utterly dissatisfied with their lot. This can be generalized, allowing our “residents” to be assigned to multiple “hospitals”, as well as vice versa, in a way that preserves all the nice properties mentioned previously.
I will present the algorithm to accomplish this, and its many properties.
The presentation is based on the book The Stable Marriage Problem: Structure and Algorithms by D. Gusfield and R. W. Irving.
The Gale-Shapley algorithm has just won the Nobel Prize in Economics for Shapley. See ”2 From U.S. Win Nobel in Economics”, The New York Times, Oct. 15, 2012.