Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/108306 
Erscheinungsjahr: 
2013
Schriftenreihe/Nr.: 
IEHAS Discussion Papers No. MT-DP - 2013/30
Verlag: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
Zusammenfassung: 
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.
Schlagwörter: 
Scarf lemma
stable allocation
hospitals residents problem
couples
JEL: 
C71
C78
ISBN: 
978-615-5243-89-9
Dokumentart: 
Working Paper

Datei(en):
Datei
Größe
317.84 kB





Publikationen in EconStor sind urheberrechtlich geschützt.