Your search
Theme
Location
Publication year
Matching couples with Scarf’s algorithm
Resource type
Journal Article
Authors/contributors
- Biró, Péter (Author)
- Fleiner, Tamás (Author)
- Irving, Robert W. (Author)
Title
Matching couples with Scarf’s algorithm
Abstract
Scarf’s algorithm [18] provides fractional core elements for NTU-games. Biró and Fleiner [3] showed that Scarf’s algorithm can be extended for capacitated NTU-games. In this setting agents can be involved in more than one coalition at a time, cooperations may be performed with different intensities up to some limits, and the contribution of the agents can also differ in a coalition. The fractional stable solutions for the above model, produced by the extended Scarf algorithm, are called stable allocations. In this paper we apply this solution concept for the Hospitals Residents problem with Couples (HRC). This is one of the most important general stable matching problems due to its relevant applications, also wellknown to be NP-hard. We show that if a stable allocation yielded by the Scarf algorithm turns outto be integral then it provides a stable matching for an instance of HRC, so this method can be used as a heuristic. In an experimental study, we compare this method with other heuristics constructed for HRC that are applied in practice in the American and Scottish resident allocation programs, respectively. Our main finding is that the Scarf algorithm outperforms all the other known heuristics when the proportion of couples is high.
Publication
Annals of Mathematics and Artificial Intelligence
Volume
77
Issue
3-4
Pages
303-316
Date
8/2016
Journal Abbr
Ann Math Artif Intell
Language
en
ISSN
1012-2443, 1573-7470
Accessed
07/03/2021, 13:58
Library Catalogue
DOI.org (Crossref)
Citation
Biró, P., Fleiner, T., & Irving, R. W. (2016). Matching couples with Scarf’s algorithm. Annals of Mathematics and Artificial Intelligence, 77(3–4), 303–316. https://doi.org/10.1007/s10472-015-9491-5
Theme
Location
Link to this record