Finding Robust Solutions to Stable Marriage

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

doi:10.24963/ijcai.2017/88

Finding Robust Solutions to Stable Marriage

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

Download BibTeX Cite

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. Main track. Pages 631-637.

https://doi.org/10.24963/ijcai.2017/88

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

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.

Begum Genc, Mohamed Siala, Barry O'Sullivan, and Gilles Simonin. 2017. Finding Robust Solutions to Stable Marriage. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. IJCAI, 631–637. https://doi.org/10.24963/ijcai.2017/88

@inproceedings{ijcai2017p88,
  title     = {Finding Robust Solutions to Stable Marriage},
  author    = {Genc, Begum and Siala, Mohamed and O'Sullivan, Barry and Simonin, Gilles},
  booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on
               Artificial Intelligence, {IJCAI-17}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Carles Sierra, IIIA-CSIC},
  pages     = {631--637},
  year      = {2017},
  month     = {8},
  note      = {Main track},
  doi       = {10.24963/ijcai.2017/88},
  url       = {https://doi.org/10.24963/ijcai.2017/88},
}

TY  - CPAPER
TI  - Finding Robust Solutions to Stable Marriage
AU  - Genc, Begum
AU  - Siala, Mohamed
AU  - O'Sullivan, Barry
AU  - Simonin, Gilles
T2  - Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2017
SP  - 631
EP  - 637
DO  - 10.24963/ijcai.2017/88
UR  - https://doi.org/10.24963/ijcai.2017/88
ER  -