Finding Stable Matchings that are Robust to Errors in the Input
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.
READ FULL TEXT