Matching couples with Scarf’s algorithm

Biró, Péter and Fleiner, T. and Irwing, RW. (2016) Matching couples with Scarf’s algorithm. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, &. &. ISSN 1012-2443

Preview

Text BFI16amai_last.pdf Download (609kB) | Preview

Abstract

Scarf's algorithm [20] provides fractional core elements for NTU-games. Bir�o 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 di�erent intensities up to some limits, and the contribution of the agents can also di�er 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 out to 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 �nding is that the Scarf algorithm outperforms all the other known heuristics when the proportion of couples is high.

Actions (login required)

Edit Item