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 and a set of
errors that can be introduced into . Each error consists of
applying a specific permutation to the preference list of a chosen boy
or a chosen girl. Assume that is being transmitted over a channel
that introduces one error from set ; as a result, the channel
outputs this new instance. We wish to find a matching that is stable for
and for each of the possible new instances. If is
picked from a special class of errors, we give an
time algorithm for this problem. We call the
obtained matching a fully robust stable matching with respect to
. In particular, if 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.)