## 2 Problem Model  
We represent a connectivity network as an undirected graph \(G(V,E)\), with \(|V|=n,\;|E|=m\), where \(V\) is the set of overlay peers and \(E\) the set of potential connections. Each node \(i\) has degree \(d_{i}\) and keeps a preference list \(L_{i}\) of all nodes in its neighborhood \(\Gamma_{i}\) (in the rest of the paper and when it is clear from the context, we will use notation \(L_{i}\) to denote both the list and its length). Let \(R_{i}(j)\) denote the rank of node \(j\) in node \(i\)'s preference list, with \(R_{i}(\cdot)\in\{0,1,\ldots,|L_{i}|-1\}\), attributing zero to its most desirable neighbor. Each node \(i\) wants to maintain at most \(b_{i}\) connections (in order to form the overlay) to the best possible nodes according to its preference list and rank function, and at no point can it exceed this number. Clearly, it must be \(b_{i}\leq|L_{i}|\). In the following sections, we will refer to two nodes as _neighboring nodes_ when they are connected by an edge in graph \(G\) and _connected nodes_ when they are matched by a matching algorithm. The problem of trying to find a many-to-many matching that respects the individual preferences and connection quotas \(b_{i}\) is a form of a generalized stable roommates problem called the _stable fixtures problem_[6] or _b-matching_[5]. We call _adaptive b-matching_ the dynamic form of b-matching, where nodes can join, leave or change preferences at any time. In the remainder of this paper, we will refer to these events simply as _changes_. We will also consider an asynchronous model for messages and will not consider link or node failures, _i.e._, messages arrive asynchronously, but do not get lost, and nodes depart gracefully or their absence can be detected by other means (for example, special periodic \"alive\" messages). In order to measure the success of node \(i\)'s efforts in establishing its \(b_{i}\) connections, we make use of the notion of _satisfaction_, \(S_{i}\), which is defined in [5] by the following formula:  
\[S_{i}=\frac{c_{i}}{b_{i}}+\frac{c_{i}\left(c_{i}-1\right)}{2b_{i}L_{i}}-\frac{ \sum\limits_{j\in C_{i}}R_{i}\left(j\right)}{b_{i}L_{i}} \tag{1}\]  
where \(C_{i}\) (with \(|C_{i}|=c_{i}\leq b_{i}\)) is an _ordered list of node \(i\)'s connections_ in decreasing preference. Satisfaction, due to its significance in the context of this paper, is discussed and analyzed separately in Section 3. We define an optimization variation of the b-matching problem, which we call the _maximizing satisfaction b-matching problem_, where the objective is to find a b-matching that maximizes the total sum of the nodes' satisfaction. Later on, we also define a _truncatedSmaximizing satisfaction b-matching problem_, which is based on the same basic b-matching problem, but tries to maximize a different (truncated) satisfaction function (see Section 4) (although we may refer to them simply as the b-matching problem and the truncatedS b-matching problem, respectively, it will be clear from the context that we are referring to the optimization versions). Consider that edges \(e=\left(i,j\right)\in E\) in the previously defined graph \(G(V,E)\) have assigned weights \(w(i,j)=w_{ij}\). A _weighted matching problem_ on this graph is the problem of finding a set of edges, such that their weight sum is maximized and there are no common endpoints between them. The many-to-many variant that we will use replaces the last constraint on no common endpoints with node capacities that need to be respected, which, in this case, are the connection quotas \(b_{i}\) per node \(i\).