A Generalization of Birkhoff's Theorem for Distributive Lattices, with Applications to Robust Stable Matchings
share
Birkhoff's theorem, which has also been called the fundamental theorem for finite distributive lattices, states that the elements of any such lattice L are isomorphic to the closed sets of a partial order, say Π. We generalize this theorem to showing that each sublattice of L is isomorphic to a distinct partial order that can be obtained from Π via the operation of compression, defined in this paper. Let A be an instance of stable matching, with L being its lattice of stable matchings, and let B be the instance obtained by permuting the preference list of any one boy or any one girl. Let M_A and M_B be their sets of stable matchings. Our results are the following: - We show that M_A ∩M_B is a sublattice of L and M_A∖M_B is a semi-sublattice of L. - Using our generalization of Birkhoff's Theorem, we give an efficient algorithm for finding the compression of Π that is isomorphic to the lattice of M_A ∩M_B. - Given a polynomial sized domain D of such errors (of permuting one of the preference lists), we give an efficient algorithm that checks if there is a stable matching for A that is stable for each such resulting instance B. We call this a fully robust stable matching. - If yes, the set of all such matchings forms a sublattice of L and our algorithm finds its partial order as well. Using the latter, we can obtain a matching that optimizes (maximizes or minimizes) the weight among all fully robust stable matchings.
READ FULL TEXT