Finding Robust Solutions to Stable Marriage

Begum Genc, Mohamed Siala, Barry O'Sullivan, Gilles SimoninIJCAI 2017 · DOI

TL;DR

This paper introduces the concept of "(a,b)-supermatches" to quantify the robustness of stable marriage matchings. They develop efficient algorithms to find the most robust stable matching, demonstrating that local search outperforms constraint programming and genetic algorithms in practice.

What Problem Does This Paper Address?

The Stable Marriage problem (SM) is a classic matching problem where two sets of agents (e.g., men and women) are matched based on their preferences, ensuring no blocking pairs exist. While stable matchings are desirable, they can be brittle. If a few agents decide to break their matches, the entire matching might need significant re-shuffling to restore stability. This paper addresses the challenge of finding stable matchings that are "robust" to such changes, meaning they can be repaired with minimal disruption. They define this robustness by introducing the notion of (a,b)-supermatches, where a small number of initial disruptions (a pairs breaking up) can be fixed by changing only a limited number of additional partners (b pairs). The goal is to find a stable matching that minimizes this 'b' value, thus being the most robust.

Methods

The authors introduce the concept of (a,b)-supermatches as a formal measure of robustness. A stable matching is an (a,b)-supermatch if, after 'a' pairs break up, a new stable matching can be found by changing at most 'b' additional partners. They focus on the (1,b)-supermatch case, where only one pair breaks up.

Their core technical contribution is a polynomial-time procedure to check if a given stable matching is a (1,b)-supermatch. This procedure relies on understanding the structure of stable matchings through rotations and their associated rotation poset. They leverage this procedure to design three approaches for finding the most robust stable matching (i.e., minimizing 'b'):

  1. Constraint Programming (CP) Model: Formulates the problem using decision variables representing pairs and rotations, with constraints ensuring stability and the (1,b)-supermatch property.
  2. Local Search (LS): An iterated local search algorithm that explores the space of stable matchings by making small changes (modifying one rotation at a time) to find a more robust solution.
  3. Genetic Algorithm (GA): A population-based metaheuristic that evolves a set of stable matchings over generations, using crossover and mutation operators to find better solutions.

Datasets

The authors use a sample Stable Marriage instance of size 7 for illustrative purposes throughout the paper. For empirical evaluation, they generate two sets of random instances:

  • 500 instances with sizes ranging from 300 to 500 men/women.
  • 600 large instances with sizes ranging from 1200 to 1500 men/women. They generated 100 instances for each size within these sets.

Key Insights and Ideas

  • Quantifying Robustness: The introduction of (a,b)-supermatches provides a concrete, quantifiable measure for the resilience of stable matchings, moving beyond qualitative notions of stability.
  • Rotations as Building Blocks: The paper effectively utilizes the concept of rotations in stable marriage theory to define and manipulate stable matchings, which is crucial for both checking (1,b)-supermatches and for the metaheuristic approaches.
  • Polynomial-Time Verification: The ability to check (1,b)-supermatch properties in polynomial time is a significant theoretical result, enabling the development of more sophisticated search algorithms.
  • Local Search Dominance: Empirically, local search emerges as the most effective method for finding robust stable matchings, outperforming CP and GA in terms of both solution quality and runtime, especially for larger instances.

Key Results

The paper demonstrates that:

  • Checking if a stable matching is a (1,b)-supermatch can be done in polynomial time.
  • Local search significantly outperforms constraint programming and genetic algorithms in finding the most robust stable matching, particularly on larger instances.
  • In experimental evaluations, local search consistently finds high-quality solutions with competitive runtimes, while the GA struggles to find the best solutions and takes longer. The CP model, while capable of finding optimal solutions, becomes computationally infeasible for larger instances.

Limitations and Future Work

  • CP Scalability: The CP model, while theoretically sound, struggles with scalability for larger instances, running out of memory.
  • GA Performance: The Genetic Algorithm did not perform as well as expected, taking longer and not always finding the best solutions.
  • Future Work: The authors suggest that their work opens up new avenues for research in robust matching problems, implying that further exploration of robustness notions and algorithms in various matching contexts would be valuable. The paper also hints at potential improvements in the metaheuristic approaches.

Summary updated

BibTeX
@inproceedings{genc2017finding,
  author = {Begum Genc and Mohamed Siala and Barry O'Sullivan and Gilles Simonin},
  title = {{Finding Robust Solutions to Stable Marriage}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/88},
}
Figure