Abstract
Recently a robustness notion for matching problems based on the concept of a (a, b)-supermatch is proposed for the Stable Marriage problem (SM). In this paper we extend this notion to another matching problem, namely the Stable Roommates problem (SR). We define a polynomial-time procedure based on the concept of reduced rotation poset to verify if a stable matching is a (1, b)-supermatch. Then, we adapt a local search and a genetic local search procedure to find the (1, b)-supermatch that minimises b in a given SR instance. Finally, we compare the two models and also create different SM and SR instances to present empirical results on the robustness of these instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The parentheses are used to indicate priority.
- 2.
Our datasets are publicly available at: github.com/begumgenc/rsmData.
- 3.
The reader is referred to the online version for coloured version.
References
Ashlagi, I., Gonczarowski, Y.A.: Dating strategies are not obvious. CoRR abs/1511.00452 (2015)
Aziz, H., Biró, P., Gaspers, S., de Haan, R., Mattei, N., Rastegari., B.: Stable matching with uncertain linear preferences. CoRR abs/1607.02917 (2016)
Drummond, J., Boutilier, C.: Elicitation and approximately stable matching with partial preferences. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI 2013, pp. 97–105. AAAI Press (2013)
Genc, B., Siala, M., O’Sullivan, B., Simonin, G.: Finding robust solutions to stable marriage. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19–25 August 2017, pp. 631–637 (2017)
Genc, B., Siala, M., O’Sullivan, B., Simonin, G.: Finding robust solutions to stable marriage. CoRR abs/1705.09218 (2017)
Genc, B., Siala, M., Simonin, G., O’Sullivan, B.: Complexity study for the robust stable marriage problem. In: Theoretical Computer Science (2019)
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)
Hebrard, E.: Robust solutions for constraint satisfaction and optimisation under uncertainty. PhD thesis, University of New South Wales (2007)
Holland, A., O’Sullivan, B.: Super solutions for combinatorial auctions. In: Faltings, B.V., Petcu, A., Fages, F., Rossi, F. (eds.) CSCLP 2004. LNCS (LNAI), vol. 3419, pp. 187–200. Springer, Heidelberg (2005). https://doi.org/10.1007/11402763_14
Irving, R.W.: An efficient algorithm for the “stable roommates” problem. J. Algorithms 6(4), 577–595 (1985)
Irving, R.W., Leather, P.: The complexity of counting stable marriages. SIAM J. Comput. 15(3), 655–667 (1986)
Jacobovic, R.: Perturbation robust stable matching. CoRR abs/1612.08118 (2016)
Kolen, A., Pesch, E.: Genetic local search in combinatorial optimization. Discret. Appl. Math. 48(3), 273–284 (1994)
Lebedev, D., Mathieu, F., Viennot, L., Gai, A.-T., Reynier, J., De Montgolfier, F.: On using matching theory to understand P2P network design. In: INOC 2007, International Network Optimization Conference (2007)
Lussier, B., Chatila, R., Ingrand, F., Killijian, M.O., Powell, D.: On fault tolerance and robustness in autonomous systems. In: Proceedings of the Third IARP/IEEE-RAS/EURON Joint Workshop on Technical Challenge for Dependable Robots in Human Environments, Manchester, GB, 7–9 September 2004
Pittel, B.: The “stable roommates” problem with random preferences. Ann. Probab. 21, 1441–1477 (1993)
Siala, M., O’Sullivan, B.: Rotation-based formulation for stable matching. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 262–277. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_17
Ulder, N.L.J., Aarts, E.H.L., Bandelt, H.-J., van Laarhoven, P.J.M., Pesch, E.: Genetic local search algorithms for the traveling salesman problem. In: Schwefel, H.-P., Männer, R. (eds.) PPSN 1990. LNCS, vol. 496, pp. 109–116. Springer, Heidelberg (1991). https://doi.org/10.1007/BFb0029740
Acknowledgement
This material is based upon works supported by the Science Foundation Ireland under Grant No. 12/RC/2289 which is co-funded under the European Regional Development Fund.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Genc, B., Siala, M., Simonin, G., O’Sullivan, B. (2019). An Approach to Robustness in the Stable Roommates Problem and Its Comparison with the Stable Marriage Problem. In: Rousseau, LM., Stergiou, K. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019. Lecture Notes in Computer Science(), vol 11494. Springer, Cham. https://doi.org/10.1007/978-3-030-19212-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-19212-9_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19211-2
Online ISBN: 978-3-030-19212-9
eBook Packages: Computer ScienceComputer Science (R0)