## 4 Approximating B-Matchings with Weighted Matchings
### Converting to a Maximum Weighted Matching  
The truncatedS b-matching problem, as defined above, assumes privately kept preference lists and cannot be considered a maximum weighted matching problem, which needs the weights associated with edges to be known and common to both endpoints. In order to convert it, we will create edge weights by adding the satisfaction gleaned by the two endpoints for the specific link. For an edge \(e=\left(i,j\right)\in E\), the weight should be:  
\[w\left(i,j\right) = \Delta\overline{S}_{i}^{j}+\Delta\overline{S}_{j}^{i}=S_{i,j}^{s} +S_{j,i}^{s}= \tag{24}\] \[= \left(\frac{1-R_{i}\left(j\right)/L_{i}}{b_{i}}\right)+\left( \frac{1-R_{j}\left(i\right)/L_{j}}{b_{j}}\right)\]  
By using these weights to construct and solve a many-to-many weighted matching problem, we also get a solution for the truncatedS b-matching problem, as the following lemma suggests. **Lemma 2**: _We consider the truncatedS b-matching problem that uses Equation (6) for satisfaction calculations. A solution derived from a many-to-many maximum weighted matching on the same graph, with edge weights given by Equation (24), is also a solution for the truncatedS b-matching problem, and vice versa._  
**Proof:** Let \(A\subseteq E\) be the edge set that is the solution of a many-to-many maximum weighted matching on a graph \(G(V,E)\) with edge weights defined by Equation (24). This set \(A\) corresponds to a collection \(C\) of connection lists \(C_{i}\)\(\forall i\in V\), and maximizes the expression \(\sum\limits_{(i,j)\in A}w\left(i,j\right)\) to a value \(w(A)\):  
\[w\left(A\right)=\sum\limits_{(i,j)\in A}w\left(i,j\right)=\sum\limits_{(i,j) \in A}\left(\Delta\overline{S}_{i}^{j}+\Delta\overline{S}_{j}^{i}\right) \tag{25}\]  
Let also \(A^{{}^{\prime}}\subseteq E\) be the corresponding edge set for the truncatedS b-matching problem (using Equation (6)) on the same graph. This set corresponds to a collection \(C^{{}^{\prime}}\) of connection lists \(C^{{}^{\prime}}_{i}\)\(\forall i\in V\), and maximizes the expression, \(\sum\limits_{i\in V}\sum\limits_{j\in C^{{}^{\prime}}_{i}}\Delta\overline{S}_{ i}^{j}\), to a value \(w(A^{{}^{\prime}})\) where \(\sum\limits_{j\in C^{{}^{\prime}}_{i}}\Delta\overline{S}_{i}^{j}\) is the satisfaction gleaned by node \(i\) for the connections of list \(C^{{}^{\prime}}_{i}\):  
\[w\left(A^{{}^{\prime}}\right)=\sum\limits_{i\in V}\sum\limits_{j\in C^{{}^{ \prime}}_{i}}\Delta\overline{S}_{i}^{j} \tag{26}\]  
We will prove that these solutions \(w\left(A\right)\) and \(w(A^{{}^{\prime}})\) are equal. Assume that \(w(A)>w(A^{{}^{\prime}})\). If we group the satisfaction increases \(\Delta\overline{S}_{i}^{j}\) in Equation (25) for a node \(i\), we can write:  
\[w\left(A\right)=\sum\limits_{(i,j)\in A}\left(\Delta\overline{S}_{i}^{j}+ \Delta\overline{S}_{j}^{i}\right)=\sum\limits_{i\in V}\sum\limits_{j\in C_{i} }\Delta\overline{S}_{i}^{j} \tag{27}\]  
By the assumption and Equation (27), we have:  
\[w\left(A\right)>w\left(A^{{}^{\prime}}\right)\Rightarrow\sum\limits_{i\in V} \sum\limits_{j\in C_{i}}\Delta\overline{S}_{i}^{j}>\sum\limits_{i\in V}\sum \limits_{j\in C^{{}^{\prime}}_{i}}\Delta\overline{S}_{i}^{j}\]  
implying that the collection \(C\) achieves a greater value than \(C^{{}^{\prime}}\) for the maximizing expression of the truncatedS b-matching problem. However, this contradicts the definition of \(C^{{}^{\prime}}\). Symmetrically, assuming that \(w(A)<w(A^{{}^{\prime}})\) also leads to a contradiction, meaning that any solution for the many-to-many maximum weighted matching we are considering is also a solution for the corresponding truncatedS b-matching problem, and _vice versa_. \(\square\)  
The following theorem follows directly from Lemmas 1 and 2. **Theorem 1**: _We consider the maximizing satisfaction b-matching problem that uses Equation (4) to maximize the total satisfaction.