2021/10/06 by Sofia Simola, Simola, Sofia, David F. Manlove +1
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2110.02555
openalex publication_date 2021/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The stable roommates problem can admit multiple different stable matchings. We have different criteria for deciding which one is optimal, but computing those is often NP-hard. We show that the problem of finding generous or rank-maximal stable matchings in an instance of the roommates problem with incomplete lists is NP-hard even when the preference lists are at most length 3. We show that just maximising the number of first choices or minimising the number of last choices is NP-hard with the short preference lists. We show that the number of Rth choices, where R is the minimum-regret of a given instance of SRI, is 2-approximable among all the stable matchings. Additionally, we show that the problem of finding a stable matching that maximises the number of first choices does not admit a constant time approximation algorithm and is W[1]-hard with respect to the number of first choices. We implement integer programming and constraint programming formulations for the optimality criteria of SRI. We find that constraint programming outperforms integer programming and an earlier answer set programming approach by Erdam et. al. (2020) for most optimality criteria. Integer programming outperforms constraint programming and answer set programming on the almost stable roommates problem.