ICS 269, Spring 2022: Theory Seminar
Bren Hall 1423, 1:00 – 1:50


22 April 2022: Rohith Reddy Gangam

An efficient algorithm for fully robust stable matchings via join semi-sublattices

We are given a stable matching instance A and a set S of errors that can be introduced into A. Each error consists of applying a specific permutation to the preference list of a chosen boy or a chosen girl. Assume that A is being transmitted over a channel that introduces one error from set S; as a result, the channel outputs this new instance. We wish to find a matching that is stable for A and for each of the |S| possible new instances. If S is picked from a special class of errors, we give an O(|S|poly(n)) time algorithm for this problem. We call the obtained matching a fully robust stable matching with respect to S. In particular, if S is polynomial sized, then our algorithm runs in polynomial time. Our algorithm is based on new, non-trivial structural properties of the lattice of stable matchings; these properties pertain to certain join semi-sublattices of the lattice. Birkhoff’s representation theorem for finite distributive lattices plays a special role in our algorithms.

(Based on a paper by Tung Mai and Vijay Vazirani.)