Near Feasible Stable Matchings
The National Resident Matching program seeks a stable matching of medical students to teaching hospitals. With couples, stable matchings need not exist. Nevertheless, for any student preferences, we show that each instance of a matching problem has a `nearby' instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Given a reported capacity $k_h$ for each hospital $h$, we find a redistribution of the slot capacities, $k^*_h$, satisfying $|k_h-k^*_h| <= 2$ for all hospitals $h$ and $\sum_h k_h <= \sum_h k^*_h <= \sum_h k_h+4$, such that a stable matching exists with respect to $k^*$. The approach is based on Scarf’s lemma. We also show how it can be adapted to deal with side constraints imposed by diversity considerations. This is joint work with Thanh Nguyen.