Computing at Glasgow University
Paper ID: 9399
DCS Tech Report Number: TR-2013-340

The Hospitals / Residents problem with Free Pairs
Kwanashie,A. Manlove,D.F.

Publication Type: Tech Report (internal)
Appeared in: SoCS Technical Report Series
Page Numbers : 1-19
Publisher: Dept of Computing Science, University of Glasgow
Year: 2013

In the classical Hospitals/Residents problem, a stable matching M is sought which ensures that no blocking pair can exist in which a resident r and hospital h can improve relative to M by becoming assigned to each other. Such a situation is undesirable as it could naturally lead to r and h forming a private arrangement outside of the matching. This however assumes that a blocking pair that exists in theory would invariably lead to a matching being undermined in practice. However such a situation need not arise if the lack of social ties between agents prevents an awareness of certain blocking pairs in practice. Relaxing the stability definition to take such a scenario into account can yield larger stable matchings.

In this paper, we define the Hospitals/Residents problem with Free Pairs (HRF) in which a subset of acceptable resident-hospital pairs are defined as free. This means that they can belong to a matching M but they can never block M. Free pairs correspond to resident and hospitals that do not know one another. Relative to a relaxed stability definition for HRF, called local stability, we show that locally stable matchings can have different sizes and the problem of finding a maximum locally stable matching is NP- hard, though approximable within 3/2. Furthermore we give polynomial time algorithms for two special cases of the problem

Keywords: Locally stable matching; NP-hard problem; Approximation algorithm; Admissible pair; Free pair

PS/PS.GZ PDF Bibtex entry Endnote XML