---
title: "Finding Robust Solutions to Stable Marriage"
authors:
  - "Begum Genc"
  - "Mohamed Siala"
  - "Barry O'Sullivan"
  - "Gilles Simonin"
doi: "10.24963/ijcai.2017/88"
url: "https://ijcai.org/proceedings/2017/88"
pdf: "https://ijcai.org/proceedings/2017/0088.pdf"
venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"
year: 2017
pages: "631-637"
track: "Main track"
keywords:
  - "Agent-based and Multi-agent Systems: Social Choice Theory"
  - "Combinatorial & Heuristic Search: Heuristic Search"
  - "Knowledge Representation, Reasoning, and Logic: Preferences"
  - "Constraints and Satisfiability: Modeling/Formulation"
---

# Finding Robust Solutions to Stable Marriage

Begum Genc, Mohamed Siala, Barry O'Sullivan, Gilles Simonin

*Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 631-637. DOI: [10.24963/ijcai.2017/88](https://doi.org/10.24963/ijcai.2017/88)

## Abstract

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.