Maximum locally stable matchings (Q1736563)

Summary: Motivated by the observation that most companies are more likely to consider job applicants referred by their employees than those who applied on their own, Arcaute and Vassilvitskii modeled a job market that integrates social networks into stable matchings in an interesting way. We call their model HR+SN because an instance of their model is an ordered pair \((I, G)\) where \(I\) is a typical instance of the Hospital/Residents problem (HR) and \(G\) is a graph that describes the social network (SN) of the residents in \(I\). A matching \(\mu\) of hospitals and residents has a \textit{local blocking pair} \((h, r)\) if \((h, r)\) is a blocking pair of \(\mu\), and there is a resident \(r'\) such that \(r'\) is simultaneously an employee of \(h\) in the matching and a neighbor of \(r\) in \(G\). Such a pair is likely to compromise the matching because the participants have access to each other through \(r'\): \(r\) can give her resume to \(r'\) who can then forward it to \(h\). A \textit{locally stable matching} is a matching with no local blocking pairs. The cardinality of the locally stable matchings of \(I\) can vary. This paper presents a variety of results on computing a locally stable matching with maximum cardinality.