Finding Stable Matchings that are Robust to Errors in the Input

03/30/2018

∙

by   Tung Mai, et al.

∙

0

∙

share

Given an instance A of stable matching, let B be the instance that results after introducing one error from a polynomially large class of errors, and chosen via a discrete probability distribution. We want to find a stable matching for A that maximizes the probability of being stable in B as well. Via new structural properties, related to the lattice of stable matchings, we give a polynomial time algorithm for this problem. To the best of our knowledge, this is the first work to explore the issue of robustness to errors for this problem.