## 3 Node Satisfaction: A Metric for Optimization
### Satisfaction and Stability  
The most common way to describe stability in stable roommate problems is through the notion of _blocking pairs_[12]. For example, when indifference is not considered in the preference lists, two nodes form a blocking pair when they both strictly prefer each other over some of their current matches, and a matching configuration is called _stable_ when there are no blocking pairs in the network. The satisfaction definition of Equation (1), together with the interpretation in Section 3.1, can assist in moving beyond the classic stable matchings and towards the overlay network context. Although work in this area has been fairly limited, the notion of satisfaction does seem to stand out as a natural extension to the blocking pairs notion: instead of nodes forming a strict, stable matching, satisfaction gives them the flexibility to make choices of measurable \"goodness\", by assigning real values to their choices and applying algorithms that, e.g., maximize the total satisfaction on a network level. This _maximizing total satisfaction_ criterion introduces a social element to the traditional notion of stability and can be considered stricter than the above definition of blocking pairs, as the following observation suggests.  
**Observation 1**: _If a stable configuration exists, it can differ from a maximizing total satisfaction configuration, but the total satisfaction achieved by the latter is greater than or equal to the total satisfaction of the first._  
An example network that illustrates this observation can be found in Figure 2.  
In this toy example, we assume that every node has only one free connection slot, and the preference lists are shown above the respective nodes. Here, a maximizing total satisfaction configuration is depicted by solid lines connecting nodes \(A\) and \(B\) with \(C\) and \(D\), respectively. However, this configuration is not stable, since nodes \(A\) and \(B\) constitute a blocking pair (each one prefers the other over their current partners). By resolving this blocking pair, we get the stable configuration depicted by a dotted line between nodes \(A\) and \(B\) (see Figure 2). However, using Equation (1) to compute the total satisfaction of the network before (maximizing total satisfaction configuration \(S\)) and after (stable configuration \(S^{\prime}\))  
Figure 2: Example network exhibiting different stable and maximizing total satisfaction configurations.  
the blocking pair resolution, we observe that the loss of satisfaction from nodes \(C\) and \(D\) offsets the gain from the resolved blocking pair, \(A\),\(B\):  
\[S=S_{A}+S_{B}+S_{C}+S_{D}=0.5+0.5+1+1=3\] \[S^{{}^{\prime}}=S^{{}^{\prime}}_{A}+S^{{}^{\prime}}_{B}+S^{{}^{ \prime}}_{C}+S^{{}^{\prime}}_{D}=1+1+0+0=2\]  
It follows that the selfish choices of nodes \(A\) and \(B\) resulted in a network with decreased total satisfaction. This behavior also suggests that total satisfaction maximization may be preferable to traditional stability in overlay collaborative applications, where nodes pool together resources towards a common goal,_i.e._, construct an overlay network, and social characteristics are inherent. Furthermore, in the above example, we showed that it is possible to achieve equal or greater satisfaction to the one achieved by the stable configuration, whose existence cannot be always guaranteed. This is in contrast to the maximizing total satisfaction criterion, which can always be applied, becoming a natural and sensible target goal to strive for in an overlay collaborative environment. Note here that the maximizing total satisfaction criterion need not be applied necessarily to the whole network: any amount of nodes, working closely within the network, can apply it and benefit from it as a group.