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{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.)