## 5 Link-Based Stability Notions
### Additive-Weight  
We assume now to compute the link of a marriage as the sum of the links of all its pairs. First, we will show how to find the link-additive stable marriage with the highest additive-weight for some classes of SMWs (i.e., for SMWs \(P\), such that \(Linka(P)\) has no ties), and then, we will show a procedure that can be used for any class of SMWs. By Proposition 2, we know that the set of the link-additive-stable (resp., link-maximal-stable) marriages of an SMW, \(P\), coincides with the set of the weakly stable marriages of the SMP, \(Linka(P)\) (resp., \(Linkm(P)\)). Therefore, to find a link-additive-stable (resp., link-maximal-stable) marriage, we can simply use Algorithm 4 that applies GS to a linearization of \(Linka(P)\) (resp., \(Linkm(P)\)). ```
Input: \(P\): an SMW Output: \(\mu\): a marriage \(P^{\prime}\gets Linka(P)\) (resp., \(Linkm(P)\)); \(P^{\prime\prime}\leftarrow\) a linearization of \(P^{\prime}\); \(\mu\leftarrow\) the marriage obtained by applying GS algorithm to \(P^{\prime\prime}\); return\(\mu\)
```  
**Algorithm 4**_Link-additive-stable-GS (resp., link-maximal-stable-GS)_  
**Proposition 9**: _Given an SMW, \(P\), the marriage returned by algorithm link-additive-stable-GS (link-maximal-stable-GS) over \(P\), say \(M\), is link-additive-stable (resp., link-maximal-stable). Moreover, if there are not ties in \(Linka(P)\) (resp., \(Linkm(P)\)), \(M\) is link-additive-stable (resp.,link-maximal-stable), and it has the highest additive-weight._  
When there are no ties in \(Linka(P)\) (resp., \(Linkm(P)\)), the marriage returned by algorithm _link-additive-stable-GS_ (resp., _link-maximal-stable-GS_) is male-optimal w.r.t. the profile with links. Such a marriage may be different from the classical male-optimal stable marriage of \(c(P)\), since it considers the happiness of the men reordered according to their links with the women, rather than according to their single preferences. This holds, for example, when we assume having an SMW with preference values that are all different and we consider the notion of link-maximal-stability. **Proposition 10**: _Given an SMW \(P\) where the preference values are all different, the marriage returned by algorithm link-maximal-stable-GS algorithm over \(P\) is link-maximal-stable, and it has the highest additive-weight._  
When, instead, there are ties in \(Linka(P)\) (resp., \(Link(P)\)), to find the link-additive stable marriage with the highest additive-weight in SMWs, \(P\), we cannot use Max-link-max, since it may not return the marriage with the highest additive-weight, as shown in the following example. **Example 5**: _Let \(\{w_{1},w_{2}\}\) and \(\{m_{1},m_{2}\}\) be, respectively, the set of women and men. Consider the following instance, \(P\), of an SMW: \(\{m_{1}:w_{1}^{[30]}>w_{2}^{[5]}\), \(m_{2}:w_{1}^{[6]}>w_{2}^{[3]}\), \(w_{1}:m_{2}^{[50]}>m_{1}^{[5]}\), \(w_{2}:m_{2}^{[53]}>m_{1}^{[1]}\}\). The problem \(Link(P)\) is as follows: \(\{m_{1}:w_{1}^{[35]}>w_{2}^{[6]}\), \(m_{2}:w_{1}^{[56]}=w_{2}^{[56]}\), \(w_{1}:m_{2}^{[56]}>m_{1}^{[35]}\), \(w_{2}:m_{2}^{[53]}>m_{1}^{[31]}\}\). Notice that there is a tie in \(Link(P)\). Assume applying the algorithm, Max-link-additive. There are two pairs with the maximal link strength, which are \((m_{2},w_{1})\) and \((m_{2},w_{2})\). If the algorithm chooses first the pair \((m_{2},w_{1})\), then the returned marriage is \(\{(m_{2},w_{1})\),\((m_{1},w_{2})\}\) and its additive-weight is \(56+6=62\). However, if the algorithm chooses first the pair \((m_{2},w_{2})\), then the returned marriage is \(\{(m_{2},w_{2})\),\((m_{1},w_{1})\}\), which has additive-weight = \(56+35=91\). Therefore, Max-link-additive may also not return the link-additive stable marriage with the maximum additive-weight. \(\square\)_  
In [15], the authors have presented an encoding of an SMW as a soft constraint satisfaction problem (soft CSPs) [16]. This encoding is also able to handle SMWs with ties, and it allows, for example, for finding a stable marriage that is optimal in terms of its additive-weight.