Distributive Lattices, Stable Matchings, and Robust Solutions

Опубликовано 6 сентября 2018, 15:25

Our results are:

** Introduce the problem of finding stable matchings that are robust to errors in the input.

** An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of any one boy or any one girl. This algorithm uses insights from our proof of the next result.

** A generalization of the classic theorem of Birkhoff (1937) on finite distributive lattices, first proved within Category Theory. Our combinatorial proof, given in the setting of stable matchings, yields key notions that are useful in our algorithm.

Joint work with Tung Mai.

See more at microsoft.com/en-us/research/v...