Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/108306 
Year of Publication: 
2013
Series/Report no.: 
IEHAS Discussion Papers No. MT-DP - 2013/30
Publisher: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
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 well-known 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.
Subjects: 
Scarf lemma
stable allocation
hospitals residents problem
couples
JEL: 
C71
C78
ISBN: 
978-615-5243-89-9
Document Type: 
Working Paper

Files in This Item:
File
Size
317.84 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.