Finding robust solutions to stable marriage

Thumbnail Image
4583.pdf(202.83 KB)
Published version
Genc, Begum
Siala, Mohamed
Simonin, Gilles
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
International Joint Conferences on Artificial Intelligence Organization
Published Version
Research Projects
Organizational Units
Journal Issue
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.
Constraints , Satisfiability , Knowledge representation , Reasoning and logic , Preferences , Combinatorial heuristic search , Heuristic search , Agent-based systems , Multi-agent systems , Social choice theory
Genc, B., Siala, M., Simonin, G. and O'Sullivan, Barry (2017) 'Finding Robust Solutions to Stable Marriage ', in: Sierra, C. (ed.) Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) Melbourne, Australia, 19-25 August. doi: 10.24963/ijcai.2017/88
© 2017 International Joint Conferences on Artificial Intelligence All rights reserved.