EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3937. Locally Stable Roommate Problem

Invited abstract in session TD-29: Exact Algorithms and Formulations for Combinatorial Optimization Problems, stream Combinatorial Optimization.

Tuesday, 14:30-16:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Elise Vandomme
HEC - Management School, University of Liège
2. Marie Baratto
Technology and Operations management, Rotterdam School of Management, Erasmus University
3. Yves Crama
HEC - Management School, University of Liège

Abstract

In 1962, Gale and Shapley initiated the study of stable matching problems, introducing the Stable Marriage Problem (SMP). The aim is to match men and women based on their preferences for all members of the opposite gender. A matching is deemed stable if there are no pairs of unmatched individuals who prefer each other to their partners in the matching. We say that there are no blocking pairs. A natural generalization of SMP is to consider non-bipartite models. For instance, consider a set of n individuals where each one ranks all the others in order of preference. In this context, a matching can be assimilated to pairing individuals to share living spaces, leading to the formulation of the Stable Roommate Problem (SRP). While there always exists a stable matching in SMP, it is not the case in some instances of SRP. However, Irving provided a polynomial algorithm that, for any instance of SRP, determines whether a stable matching exists or not. If it exists, it produces one. We focus on a different definition of stability, namely local stability, recently introduced in the context of kidney exchange programs (KEPs). The decision problem's complexity for non-empty locally stable exchanges remains open. When the exchange is a matching, this is equivalent to a local version of SRP. Here, a matching achieves local stability if no blocking pairs intersect with it. In this talk, we explore the trade-offs between global and local stability and discuss the complexity of local SRP.

Keywords

Status: accepted

Back to the list of papers