## 5 Correctness of Algorithm ASBM  
The correctness of Algorithm ASBM is proved in a very similar way as the correctness of Algorithm GS Modified. **Lemma 3**. :
1. _If a_ \(W\)_-agent becomes saturated, she will stay saturated._
2. _A co-satellite_ \(W\)_-agent_ \(w\) _accepts every proposal. Once a saturated_ \(W\)_-agent is not co-satellite, she cannot become co-satellite later._
3. \(A\) \(W\)_-agent_ \(w\in M(u)\) _can reject_ \(u\) _only if_ \(w\) _is saturated and a)_ \(u\) _is satellite w.r.t._ \(w\) _(_\(w\) _is co-satellite), or b)_ \(w\) _is not co-satellite,_ \(u\) _is one of the worst_ \(U\)_-agents belonging to_ \(M(w)\)_, and_ \(w\) _receives a proposal from_ \(u^{\prime}\) _who is better for_ \(w\) _than_ \(u\)_, or c)_ \(w\) _is not co-satellite and_ \(u\) _is oneof the worst \(U\)-agents belonging to \(M(w)\), \(u\) is subsatellitic, and \(w\) is co-subsatellite w.r.t. \(u^{\prime}\) who proposes from \(L^{\prime}_{u^{\prime}}\)_
4. _A saturated \(W\)-agent \(w\) who is not co-satellitic can accept a \(U\)-agent \(u^{\prime}\) only if \(u^{\prime}\) is at least as good for \(w\) as a worst \(U\)-agent \(u\in M(w)\); moreover if \(u^{\prime}\) is equally good for \(w\) as \(u\), then \(w\) accepts \(u^{\prime}\) only if \(w\) is co-subsatellite w.r.t. \(u^{\prime}\) and \(u^{\prime}\) proposes from \(L^{\prime}_{u^{\prime}}\)._  
The proof of Lemma 3 is very similar to that of Lemma 1 and follows directly from the description of Algorithm ASBM. **Theorem 2**. : _Let \(M\) denote a \(b\)-matching computed by Algorithm ASBM. Then \(M\) is a \(3/2\)-approximation of an optimal stable \(b\)-matching._  
Proof. : We will show that the underlying graph does not contain blocking pairs and dangerous paths with respect to \(M\). The non-existence of a dangerous path for the stable matching found guarantees the approximation ratio \(3/2\). Suppose that \((u,w)\) is a blocking pair. Agent \(u\) is either unsaturated or there exists \(w^{\prime}\in M(u)\) worse for \(u\) than \(w\). It means that at some point \(u\) proposed to \(w\) from \(L_{u}\) when edge \((u,w)\) was not special. If \(u\)'s proposal to \(w\) was rejected, then at that point \(w\) was saturated and not co-satellitic, and the worst \(u^{\prime}\in M(w)\) was at least as good as \(u\) for \(w\) (by Lemma 3), and thus (also by claim 4 of Lemma 3) \(w\) could not later become matched to some \(u^{\prime\prime}\) who is worse for \(w\) than \(u\). Therefore \(u\) got accepted then and later got rejected. Since at the moment of that proposal edge \((u,w)\) was not special, \(u\) was not satellitic w.r.t. \(w\) (and clearly could not become satellitic later.) By claim 3 of Lemma 3, \(W\)-agent \(w\) was not co-satellitic at the moment of rejecting \(u\), and the worst \(U\)-agent belonging to \(M(w)\) was \(u\). Therefore by claim 4 of Lemma 3, \(w\) could not later become matched to some \(u^{\prime\prime}\) who is worse for her than \(u\). A contradiction. Suppose now that the graph contains a masculine dangerous path \((u^{\prime},w,u,w^{\prime})\) such that \(u\in M(w)\). Thus \(u\) is satellite w.r.t. \(w\) and \(w\) is co-satellitic. It means that at some point \(u^{\prime}\) proposed to \(w\) from \(L_{u^{\prime}}\) when edge \((u^{\prime},w)\) was not special. Then \(w\) was either co-satellite, because she is co-satellitic now, or unsaturated. Therefore \(u^{\prime}\) got accepted. Later on he was clearly rejected. However, by claim 3 of Lemma 3 and the description of the algorithm ABSM, this is impossible, because a co-satellitic \(w\) rejects only \(U\)-agents who are satellitic w.r.t. \(w\). Finally, suppose that the graph contains a feminine dangerous path \((u^{\prime},w,u,w^{\prime})\) such that \(u\in M(w)\). Thus \(w\) is co-subsatellitic w.r.t. \(u^{\prime}\), and \(u\) is subsatellitic. At some point \(u^{\prime}\) proposed to \(w\) from \(L_{u^{\prime}}\) when edge \((u^{\prime},w)\) was not special.