## 4 Hardness Results
Otherwise, if it is matched to some worker \(w_{1}\) then \(f\) must strictly prefer \(w\) over \(w_{1}\) so that \(w\) and \(w_{1}\) are adjacent in \(G\). In \((I^{\prime},G)\), \((f,w)\) has \(w_{1}\) as a point of contact, implying that \(\mu^{\prime}\) cannot be a locally stable matching because \((f,w)\) is alocal blocking pair. Since this is a contradiction, \(f\) has to be unmatched in \(\mu^{\prime}\). Next, if \(w\) is unmatched in \(\mu^{\prime}\), let \(\mu^{\prime\prime}=\mu^{\prime}\cup\{(f,w)\}\); otherwise, let \(\mu^{\prime\prime}=\mu^{\prime}-\{(\mu^{\prime}(w),w)\}\cup\{(f,w)\}\). If \(\mu^{\prime\prime}\) has a local blocking pair, it will involve either \(f\) or \(w\). By our choice of \(w\), no worker will form a local blocking pair with \(f\). If \((f_{1},w)\) is a local blocking pair of \(\mu^{\prime\prime}\), then \((f_{1},w)\) must be a local blocking pair of \(\mu^{\prime}\) too--a contradiction. Hence, \(\mu^{\prime\prime}\) is still a locally stable matching of \((I^{\prime},G)\). What we have shown is that as long as a locally stable matching of \((I^{\prime},G)\) has a blocking pair with respect to \(I\), the matching can be modified to a new matching (which no longer admits that blocking pair with respect to \(I\)) such that (i) its size stays the same or is larger by \(1\); and (ii) the modified matching is still a locally stable matching of \((I^{\prime},G)\) where one worker's employer improved while everyone else's stayed the same. If we keep applying this modification, at some point there will be no more worker whose employer can be improved. The locally stable matching of \((I^{\prime},G)\) obtained after this process will also be a stable matching of \(I\). Checking whether \(\mu^{\prime}\) is a stable matching of \(I\), finding a blocking pair of \(\mu^{\prime}\) if it is not, and finding a worker that \(f\) prefers the most among those that form a blocking pair with \(f\) can be done in time polynomial in the size of \(I\). Since the number of modifications cannot be more than \(|F|\times|W|\), it follows that starting at a locally stable matching \(\mu^{\prime}\) of \((I^{\prime},G)\), we can arrive at a stable matching \(\mu\) of \(I\) such that \(|\mu|\geq|\mu^{\prime}|\) in time polynomial in the size of \(I\). Finally, we note from (i) that a maximum locally stable matching of \((I^{\prime},G)\) is at least as large as a maximum stable matching of \(I\). Hence, if a maximum locally stable matching of \((I^{\prime},G)\) is _also_ a stable matching of \(I\), it must be a maximum stable matching of \(I\). Our argument in the previous paragraphs shows that the last part of (ii) is true. In the statement of Theorem 5, we simply described what edges should be in \(G\): whenever two workers \(w\) and \(w^{\prime}\) appear together in some firm's preference list in \(I\), \(w\) and \(w^{\prime}\) are adjacent if and only if they are not in a tie. That is, we are ambivalent about edges formed by workers that do not appear together in a firm's preference list in \(I\) since according to Proposition 4, the absence or presence of these edges in \(G\) have no effect on the set of locally stable matchings of \((I,G)\). Consistent ties arise naturally when firms and/or workers derive their preference lists from a _master list_[13]. A master list of workers \(L_{W}\) is an ordering of all the workers that may or may not contain ties. Each firm's preference list contains all the workers acceptable to it and ranked in accordance with the master list. Thus, when \(w\) and \(w^{\prime}\) is part of the preference list of a firm \(f\), they are in a tie in \(f\)'s list if and only if they are in a tie in \(L_{W}\). A master list of firms \(L_{F}\) is defined similarly, and each worker's preference list is obtained in the same way. Let SMTI-2 ML denote the SMTI problem where both groups of participants derived their preference lists from a master list. The following result is known about SMTI -2 ML. **Fact 1**. : _([PERSON] et al.