## 2 Algorithm
### Description of Algorithm GS Modified
Therefore he must have been rejected by \(w\) at some point, which means that \(w\) must be now matched to someone at least as good for her as \(m\). (This will also be formally proved in the next section.) _Algorithm GS Modified_  
Each man \(m\)'s preference list \(L_{m}\) is organized in such a way that if \(L_{m}\) contains a tie \(t\), then free women in \(t\) come before matched women in \(t\). At the beginning all women are free and ties on men's lists are broken arbitrarily, and in the course of running the algorithm, whenever woman \(w\) becomes matched for the first time, say to man \(m\), we move her to the end of every tie she belongs to. **while** there exists a free man \(m\) with a nonempty list \(L_{m}\) or a nonempty list \(L^{\prime}_{m}\)  
**if**\(L_{m}\
eq\emptyset\)**, then**  
\(w\leftarrow\) woman at the top of \(m\)' s list \(L_{m}\)  
**if**\((m,w)\) is not special, **then** remove \(w\) from \(L_{m}\)  
**if**\(w\) is free, **then**\(M\gets M\cup(m,w)\)  
**else if**\(w\) is co-satellitic, **then**  
let \(w^{\prime}\) be a satellite of \(M(w)\)  
**if**\((M(w),w^{\prime})\) is not special, **then** remove \(w^{\prime}\) from \(L_{M(w)}\)  
\(M\gets M\cup\{(m,w),(M(w),w^{\prime})\}\backslash(w,M(w))\)  
**else if**\(w\) prefers \(m\) to \(M(w)\), **then**\(M\gets M\cup(m,w)\backslash(w,M(w))\)  
**else if**\(w\) is co-subsatellitic w.r.t. \(m\), **then** add \(w\) to the end of list \(L^{\prime}_{m}\)  
**else**  
\(w\leftarrow\) woman at the top of \(m\)' s list \(L^{\prime}_{m}\)  
remove \(w\) from \(L^{\prime}_{m}\)  
**if**\(w\) is co-subsatellitic w.r.t. \(m\), **then**\(M\gets M\cup(m,w)\backslash(w,M(w))\)  
**Lemma 2**. : _Let \(M\) denote a matching computed by Algorithm GS Modified. Then the underlying graph does not contain blocking pairs and dangerous paths w.r.t. \(M\)._  
**Proof. ** Suppose that \((m,w)\) is a blocking pair. Man \(m\) is either free or \(M(m)\) is worse for him than \(w\). It means that at some point \(m\) proposed to \(w\) from \(L_{m}\) when edge \((m,w)\) was not special. (Clearly, at some point \(m\) proposed to \(w\) from \(L_{m}\). Assume that at that point edge \((m,w)\) was special. Then \(w\) was free and accepted \(m\). However, \(m\) got rejected later and therefore proposed to \(w\) from \(L_{m}\) again, when edge \((m,w)\) was no longer special.) If \(w\) rejected him then, then by claim 2 of Lemma 1, \(w\) was not co-satellite and, by claim 3 of Lemma 1, was matched to someone at least as good for her as \(m\) and thus would have stayed matched to someone as good for her as \(m\). If \(w\) accepted \(m\), then after getting matched to \(m\) she was not co-satellite, and by claim 3 of Lemma 1, would have stayed matched to someone at least as good for her as \(m\). Either way we get a contradiction. Suppose now that the graph contains a masculine dangerous path \((m^{\prime},w,m,w^{\prime})\) such that \(m=M(w)\). Thus \(m\) is satellitic and \(w\) is co-satellite. Since she is co-satellitic, it means that the only proposal she ever got was from \(m\), but \(m^{\prime}\) must have proposed to her too, a contradiction. Finally, suppose that the graph contains a feminine dangerous path \((m^{\prime},w,m,w^{\prime})\) such that \(m=M(w)\). Thus \(m\) is subsatellitic and \(w\) is co-subsatellitic w.r.t. \(m^{\prime}\), also \(m^{\prime}\) is not subsatellitic. At some point, \(m^{\prime}\) proposed to \(w\) from \(L_{m^{\prime}}\) when \((m^{\prime},w)\) was not special. If he got accepted at that moment, then later on he could not become rejected, because by claim 3 of Lemma 1, after accepting \(m^{\prime}\) woman \(w\) was not co-satellitic, and by claim 4 of Lemma 1, could not accept a subsatellitic man equally good for her as her current partner. Therefore he was rejected then, and \(w\) was already matched with \(m\) (by claims 3 and 4 of Lemma 1). Hence \(w\) was co-subsatellitic w.r.t. \(m^{\prime}\) (because \(m\) was subsatellitic), and \(m^{\prime}\) added \(w\) to the end of list \(L^{\prime}_{m^{\prime}}\).