Final doctoral examination and defense of dissertation of Tung Mai

Thursday, May 17, 2018 - 12:30pm
Skiles 005
Title: Distributive Lattices, Stable Matchings, and Robust Solutions
Advisor: Dr. Vijay Vazirani, Computer Science Department, University of California, Irvine 
Committee: Dr. Jugal Garg, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign
  Dr. Milena Mihail, School of Computer Science
  Dr. Robin Thomas, School of Mathematics
  Dr. Mohit Singh, School of Industrial and Systems Engineering
Reader: Dr. Ioannis Panageas, Computer Science and Artificial Intelligence Laboratory (CSAIL), MIT

The stable matching problem, first presented by mathematical economists Gale and Shapley, has been studied extensively since its introduction. As a result, a remarkably rich literature on the problem has accumulated in both theory and practice. We further extend our understanding on several algorithmic and structural aspects of stable matching. Our contributions can be summarized as follows:

- Generalizing stable matching to maximum weight stable matching.
- Finding stable matchings that are robust to shifts (a class of error introduced to the input).
- Generalizing Birkhoff's theorem for distributive lattices, and an application to robust stable matching on a larger class of error, namely permutations of any preference list of a boy or a girl.

The structural and algorithmic results introduced in this thesis naturally lead to a number of new questions. We believe that, considering the deep and pristine structure of stable matching, many of these questions do get settled satisfactorily.