## 7 Discussion
While particularly suitable for game theoretic studies, this approach does not offer a way to quantify the potential of possible connections and evaluate potential matchings. The algorithms proposed here are, to our knowledge, the first to address the b-matching with the preferences problem from an optimization-oriented perspective, suitable for overlay networks. Furthermore, they are the first to support dynamic operations for the same problem and offer convergence and approximation guarantees. Proposal-Refusal SchemesIn the literature, many of the algorithms for matching with preferences are inspired by the proposal-refusal algorithm of [PERSON] [20]. Here, we also utilize the proposal-refusal scheme, but in order to address a different problem with unique characteristics: while the Gale-Shapley algorithm is focused on absolute stability, we aim at solving an optimization problem with the maximum possible satisfaction. For example, in the case of the Gale-Shapley algorithm, it is important to guarantee that no cycles exist, since, given the distributed nature of the algorithm, a reply may not be possible to be given immediately by a node to another node's proposal. This is not necessary here, since any cycles in preference lists are broken by reducing the original problem to an acyclic weighted many-to-many matching, upon which the algorithm operates (cf. also Lemma 8). On the other hand, by focusing on optimization, we are able to develop both non-adaptive and adaptive variations of our algorithm in order to tolerate and work under changes in the underlying network (_cf._ Lemma 10). The best mate initiative described in [5] has certain similarities to the way nodes propose connections to their neighbors according to the AdaptiveLID algorithm. In particular, according to the best mate initiative, a node knows at every moment which of its edges is the best blocking edge and chooses to propose to that neighbor. By contrast, according to the AdaptiveLID algorithm, a node proposes to its neighbors by descending order of ranking (related to their truncated satisfaction), but these edges might not be the best blocking edges at that point in time (_i.e._, the neighbors might not reciprocate with a proposal of their own). However, by the termination of the AdaptiveLID algorithm, it is indeed the case that every node would be connected to the endpoints of the best blocking edges related to the truncated satisfaction metric. Finally, the AdaptiveLID algorithm needs only local information, does not utilize the notion of blocking pairs and can operate in a fully distributed setting. ApproximationIn Theorem 3, we proved that the proposed distributed algorithm in both variations is a \(\frac{1}{4}\left(1+b_{\max}^{-1}\left(1+\frac{1-b_{\max}^{-1}}{2s+b_{\max}^{- 1}}\right)\right)\)-approximation algorithm for the maximizing satisfaction b-matching problem. This approximation breaks down into: (a) \(\frac{1}{2}\left(1+b_{\max}^{-1}\left(1+\frac{1-b_{\max}^{-1}}{2s+b_{\max}^{- 1}}\right)\right)\)-approximation between the original maximizing satisfaction b-matching problem and the modified version we are using (Theorem1); and (b) \(\frac{1}{2}\)-approximation of a distributed many-to-many weighted matching using the LID or AdaptiveLID algorithms (see proof of Theorem 3). The first of these approximations is due to the satisfaction estimation in Lemma 1, and there is no indication whether it is a tight bound or not. The second term is due to the specific approximation algorithm used to compute a many-to-many weighted matching, in this case, the simple distributed algorithm, LID of Section 5, which is based on the one-to-one weighted matching algorithm found in [8]. Although there is a rather limited choice of algorithms for distributed many-to-many weighted matchings, it may be possible to convert some algorithms, such as the ones in [21,24] mentioned above for the simple (one-to-one) weighted matching.