Generating satisfiable benchmark instances for stable roommates problems with optimization

Official URL: https://dx.doi.org/10.1017/S1471068425100240

While the existence of a stable matching for the stable roommates problem possibly with incomplete preference lists (SRI) can be decided in polynomial time, SRI problems with some fairness criteria are intractable. Egalitarian SRI that tries to maximize the total satisfaction of agents if a stable matching exists, is such a hard variant of SRI. For experimental evaluations of methods to solve these hard variants of SRI, several well-known algorithms have been used to randomly generate benchmark instances. However, these benchmark instances are not always satisfiable and usually have a small number of stable matchings if one exists. For such SRI instances, despite the NP-hardness of Egalitarian SRI, it is practical to find an egalitarian stable matching by enumerating all stable matchings. In this study, we introduce a novel algorithm to generate benchmark instances for SRI that have very large numbers of solutions, and for which it is hard to find an egalitarian stable matching by enumerating all stable matchings.