## 4 Extension to Bipartite Stable \(b\)-Matchings  
Suppose we have a simple bipartite graph \(G=(V,E)\), where \(V=U\cup W\) and \(U,W\) are disjoint sets, and a function \(b\): \(V\rightarrow\mathbb{N}\). Then a subset \(M\subseteq E\) is called a \(b\)-matching if for each \(v\in V\) it is \(deg_{M}(v)\leq b(v)\), where \(deg_{M}(v)\) denotes the degree of vertex \(v\) in the graph \(G_{M}=(U\cup W,M)\). We refer to the vertices of \(U\) and \(W\) as \(U\)-agents and \(W\)-agents, respectively. Each \(U\)-agent \(u\) of \(U\) has a preference list \(L_{u}\) of a subset of \(W\)-agents, and analogously, each \(W\)-agent \(w\) has a preference list \(L_{w}\) of a subset of \(U\)-agents. The preference lists are linearly ordered lists of ties. The majority of the terminology for stable matchings goes through for stable \(b\)-matchings. Instead of saying that some agent or vertex is free, we will use the term **unsaturated**: agent \(v\) is unsaturated in a \(b\)-matching \(M\) if \(deg_{M}(v)<b(v),\) and if \(deg_{M}(v)=b(v)\), then we will say that \(v\) is **saturated**. For any agent \(v\) we will denote the set \(\{w\in U\cup W\text{:}(v,w)\in M\}\) by \(M(v)\). A pair \((u,w)\) is **blocking** for a \(b\)-matching \(M\) if (1) \(u\) and \(w\) are mutually acceptable; (2) \(u\) is unsaturated or prefers \(w\) to one of the \(W\)-agents of \(M(u)\); and (3) \(w\) is unsaturated or prefers \(u\) to one of the \(U\)-agents of \(M(w)\). A \(b\)-matching \(M\) is said to be stable if it does not admit a blocking pair. As previously, we are interested in finding a stable \(b\)-matching of largest size. Let us also note that if for each \(u\) in \(U\) we have \(b(u)=1\), then the problem is known under the name Hospitals-Residents problem or one-to-many stable matching problem. Alternating paths and cycles are defined for \(b\)-matchings in an analogous way as for matchings, but we do not require paths and cycles to be simple, _i.e._, an **alternating path \(P\) w.r.t. ** a \(b\)-matching \(M\) is defined as any sequence of edges \((v_{1},v_{2}),(v_{2},v_{3}),\ldots,(v_{k-1},v_{k})\) such that the edges alternate between \(M\)-edges and edges of \(E\backslash M\), and an **alternating cycle \(C\) w.r.t. **\(M\) is defined as an alternating path (w.r.t. \(M\)) that ends and begins with the same vertex, _i.e._, the sequence of edges has the form \((v_{1},v_{2}),(v_{2},v_{3}),\ldots,(v_{k},v_{1})\). As before, for any two \(b\)-matchings\(M\) and \(M^{\prime}\), the symmetric difference \(M\oplus M^{\prime}\) can be partitioned into maximal alternating paths and cycles (_i.e._, no two alternating paths from the partition can be combined to form one alternating path). A given stable \(b\)-matching \(M\) might not be a 3/2-approximation of \(M_{opt}\), where \(M_{opt}\) denotes a stable \(b\)-matching of maximum size, only if the underlying graph contains a dangerous path defined as follows. If \(M\) is a stable \(b\)-matching, then a path \(P=(w,u_{1},w_{1},u)\) is called **dangerous with respect to \(M\)** if \(u\) and \(u_{1}\) are \(U\)-agents, \(w\) and \(w_{1}\) are \(W\)-agents, \((u_{1},w_{1})\) is in \(M\), \((w,u_{1}),(w_{1},u)\) are not in \(M\), \(w\) and \(u\) are unsaturated in \(M\), \(u_{1}\) and \(w_{1}\) are saturated in \(M\), and \((u_{1},w_{1})\) is not a blocking pair for the \(b\)-matching \(M^{\prime}=(M\setminus(u_{1},w_{1}))\cup\{(w,u_{1}),(w_{1},u)\}\). Since \((w,u_{1})\) is not blocking for \(M\), \(w\) is not better for \(u_{1}\) than any of the \(W\)-agents currently belonging to \(M(u_{1})\), and analogously, \(u\) is not better for \(w_{1}\) than any of the \(U\)-agents currently belonging to \(M(w_{1})\). Thus if \(P\) is dangerous, then either \(w\) and \(w_{1}\) are equally good for \(u_{1}\) and then \(P\) is called a **masculine dangerous path**, or \(u\) and \(u_{1}\) are equally good for \(w_{1}\) and then \(P\) is called a **feminine dangerous path**. An approximation algorithm for finding stable \(b\)-matchings is constructed analogously to the algorithm for finding stable matchings.