Distributive Lattices, Stable Matchings, and Robust Solutions

  • Vijay Vazirani | University of California, Berkeley

Our results are:

** Introduce the problem of finding stable matchings that are robust to errors in the input.

** An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of any one boy or any one girl. This algorithm uses insights from our proof of the next result.

** A generalization of the classic theorem of Birkhoff (1937) on finite distributive lattices, first proved within Category Theory. Our combinatorial proof, given in the setting of stable matchings, yields key notions that are useful in our algorithm.

Joint work with Tung Mai.

Speaker Details

Vijay Vazirani received his BS at MIT and his Ph.D. from University of California, Berkeley. He is currently Distinguished Professor at University of California, Irvine. He has made seminal contributions to the theory of algorithms, in particular to the classical maximum matching problem, approximation algorithms, and complexity theory. Over the last decade and a half, he has contributed widely to an algorithmic study of economics and game theory.

Vazirani is author of a definitive book on Approximation Algorithms, published in 2001, and translated into Japanese, Polish, French and Chinese. He was McKay Fellow at U. C. Berkeley in Spring 2002, and Distinguished SISL Visitor at Caltech during 2011-12. He is a Guggenheim Fellow and an ACM Fellow.

Series: Microsoft Research Talks