## 2 Preliminaries
### HR+SN and Max-HR+SN  
Following the above terminology, we shall call the problem of finding a locally stable matching and a maximum locally stable matching in the [PERSON]'s model HR+SN and max-HR+SN respectively, where SN stands for _social network_. We will, however, revert back to the original context and use firms in place of hospitals and workers in place of residents. An instance of HR+SN is an ordered pair \((I,G)\) where \(I\) is an HR instance and \(G\) is a social network of the workers. Example continued.In the previous example, suppose \(G\) consists of two cliques, one containing \(r_{1},r_{2},r_{3},r_{4}\) and another containing \(r_{5},r_{6},r_{7},r_{8}\). Then \(\sigma\) is a maximum locally stable matching of \((I,G)\). It has several blocking pairs--\((h_{1},r_{1}),(h_{1},r_{2}),(h_{2},r_{3}),(h_{2},r_{4})\)--but none of the pairs have a point of contact. **Proposition 2**. : _If \(\mu\) is a locally stable matching in the HR+SN instance \((I,G)\), then \(\mu^{(1)}\) is a locally stable matching in the HR+SN instance \((I^{(1)},G)\)._  
Proof. : Assume \(\mu^{(1)}\) is not a locally stable matching of \((I^{(1)},G)\) so it has a local blocking pair \((f_{ik},w_{j})\). Thus, \(f_{ik}\) and \(w_{j}\) have a point of contact, say \(w^{\prime}\), who is also the only employee of \(f_{ik}\) in \(\mu^{(1)}\). If \(w_{j}\) is unmatched or is employed by a firm that is not a clone of \(f_{i}\) in \(\mu^{(1)}\), then \((f_{i},w_{j})\) is a local blocking pair of \(\mu\) with \(w^{\prime}\) as a point of contact--a contradiction. If \(w_{j}\) is employed by a clone of \(f_{i}\) in \(\mu^{(1)}\), say \(f_{ik^{\prime}}\), then the fact that \(w_{j}\) prefers \(f_{ik}\) over \(f_{ik^{\prime}}\) means that \(k<k^{\prime}\). On the other hand, \(f_{ik}\) prefers \(w_{j}\) over its only employee \(w^{\prime}\) means that \(f_{i}\) prefers \(w_{j}\) over \(w^{\prime}\). However, this contradicts the way \(\mu^{(1)}\) is constructed because \(f_{i}\) should prefer the worker matched to \(f_{ik}\) over the worker matched to \(f_{ik^{\prime}}\). Hence, we have shown that all cases lead to a contradiction. Therefore, \(\mu^{(1)}\) is a locally stable matching of \((I^{(1)},G)\). We note though that the converse of Proposition 2 is not always true as shown by this simple instance \((I^{(1)},G)\) where  
\[ \begin{array}{ccccc}f_{11}\text{:}&w_{1}&w_{2}&\hskip 56.905512 ptw_{1}\text{:}&f _{11}&f_{12}\\ f_{12}\text{:}&w_{1}&w_{2}&\hskip 56.905512 ptw_{2}\text{:}&f_{11}&f_{12} \end{array} \]  
and \(G\) consists of the edge \(w_{1}w_{2}\). Consider \(\mu^{(1)}=\{(f_{11},w_{1})\). It has a blocking pair \((f_{12},w_{2})\) but \(f_{12}\) and \(w_{2}\) have no points of contact because \(f_{12}\) has no employee. Hence, \(\mu^{(1)}\) is a locally stable matching of \((I^{(1)},G)\). Now, \(I^{(1)}\) corresponds to the instance \(I\) where \(f_{1}\) has a capacity of two, \(f_{1}\) has the same preference list as \(f_{11}\) and \(f_{12}\) and both \(w_{1}\) and \(w_{2}\) have a preference list with only \(f_{1}\) in it. Thus, \(\mu^{(1)}\) corresponds to the matching \(\mu=\{(f_{1},w_{1})\}\). The latter though is not a locally stable matching of \((I,G)\) because \((f_{1},w_{2})\) is a local blocking pair with \(w_{1}\) as a point of contact. In the next proposition, we provide a bound similar to Proposition 1. **Proposition 3**. : _In the HR+SN instance \((I,G)\), let \(\mu\) be a stable matching and \(\hat{\mu}\) be a maximum locally stable matching. Then \(|\mu|\leq|\hat{\mu}|\leq 2|\mu|\)._  
Proof. : Let \(\sigma\) be a maximum matching of \(I\). By definition, \(|\mu|\leq|\hat{\mu}|\leq|\sigma|\). According to Proposition 1, \(|\sigma|\leq 2|\mu|\). Hence, \(|\hat{\mu}|\leq 2|\mu|\). When we appended our running example with the social network consisting of a clique containing \(r_{1},r_{2},r_{3},r_{4}\) and another clique containing \(r_{5},r_{6},r_{7},r_{8}\), \(\sigma\) is a maximum locally stable matching. Its size is twice that of \(\mu\). This shows that the bound of Proposition 3 is tight.