Abstract
The Robust Stable Matching (RSM) problem involves finding a stable matching that allows getting another stable matching within a minimum number of changes when a pair becomes forbidden. It has been shown that such a problem is NP-Hard. In this paper, we enrich the mathematical model for the RSM problem based on new theoretical properties. We derive from these properties new polynomial time pre-solving algorithms which both reduce the search space and speed up the exploration. We also extend our results to the instances of the Many-to-Many problem and give its corresponding constraint programming (CP) model. We show how the use of our algorithms improve the state-of-the-art results and make it possible to obtain proofs of optimality on large instances via the CP model.
Keywords
- Game Theory and Economic Paradigms: GTEP: Computational social choice
- Knowledge Representation and Reasoning: KRR: Preference modelling and preference-based reasoning
- AI Ethics, Trust, Fairness: ETF: Safety and robustness
- Constraint Satisfaction and Optimization: CSO: Modeling
