Finding Robust Solutions to Stable Marriage
This addresses the need for more resilient matching solutions in applications like job markets or school assignments, though it is incremental as it builds on existing stable matching concepts.
The paper tackles the problem of finding robust stable matchings by defining (a,b)-supermatches, where a stable matching can recover from a pairs breaking up by changing at most b other pairs, and they develop algorithms to find the most robust matching, with local search outperforming other methods in empirical tests on large instances.
We study the notion of robustness in stable matching problems. We first define robustness by introducing (a,b)-supermatches. An $(a,b)$-supermatch is a stable matching in which if $a$ pairs break up it is possible to find another stable matching by changing the partners of those $a$ pairs and at most $b$ other pairs. In this context, we define the most robust stable matching as a $(1,b)$-supermatch where b is minimum. We show that checking whether a given stable matching is a $(1,b)$-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.