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|\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(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.)