## 5 Link-Based Stability Notions
### Relations with Other Stability Notions  
Given an SMW, \(P\), let us denote with \(Linka(P)\) the stable marriage problem with ties obtained from \(P\) by changing every preference value that a person, \(x\), gives to a person, \(y\), with the value, \(la(x,y)\), by changing the preference rankings accordingly and by considering only these new preference rankings.  
Let us denote with \(I_{la}(P)\) the set of the link-additive-stable marriages of \(P\) and with \(I_{w}(Linka(P))\) the set of the weakly stable marriages of \(Linka(P)\). It is possible to show that these two sets coincide.  
**Theorem 2**: _Given an SMW, \(P\), \(I_{la}(P)=I_{w}(Linka(P))\)._  
**Proof:** Let us consider a marriage, \(M\). We first show that if \(M\in I_{w}(Linka(P))\), then \(M\in I_{la}(P)\). If \(M\
ot\in I_{la}(P)\), there is a pair \((m,w)\) that is a link-additive-blocking pair, _i.e._, \(la(m,w)>la(m,w^{\prime})\) and \(la(m,w)>la(m^{\prime},w)\), where \(w^{\prime}\) (resp., \(m^{\prime}\)) is the partner of \(m\) (resp., \(w\)) in \(M\). Since \(la(m,w)>la(m,w^{\prime})\), \(m\) prefers \(w\) to \(w^{\prime}\) in the problem, \(Linka(P)\), and, since \(la(m,w)>la(m^{\prime},w)\), \(w\) prefers \(m\) to \(m^{\prime}\) in the problem, \(Linka(P)\). Hence, \((m,w)\) is a blocking pair for the problem, \(Linka(P)\). Therefore, \(M\
ot\in I_{w}(Linka(P))\).  
We now show that if \(M\in I_{la}(P)\), then \(M\in I_{w}(Linka(P))\). If \(M\
ot\in I_{w}(Linka(P))\), there is a pair \((m,w)\) that is a blocking pair for \(I_{w}(Linka(P))\),_i.e._, \(m\) prefers \(w\) to \(w^{\prime}\) in the problem, \(Linka(P)\), and \(w\) prefers \(m\) to \(m^{\prime}\) in the problem, \(Linka(P)\). By definition of the problem, \(Linka(P)\), \(la(m,w)>la(m,w^{\prime})\) and \(la(m,w)>la(m^{\prime},w)\). Therefore, \((m,w)\) is a link-additive-blocking pair for the problem, \(P\). Hence, \(M\
ot\in I_{la}(P)\). \(\Box\)  
When no preference ordering changes in \(Linka(P)\) w.r.t. \(P\), then the link-additive-stable marriages of \(P\) coincide with the stable marriages of \(c(P)\).  
**Proposition 4**: _Given an SMW, \(P\), if \(Linka(P)=c(P)\), then \(I_{la}(P)=I(c(P))\)._  
If there are no ties in \(Linka(P)\), then there is a unique link-additive-stable marriage with the highest weight.  
**Proposition 5**: _Given an SMW, \(P\), if \(Linka(P)\) has no ties, then there is a unique link-additive-stable marriage with the highest additive-weight._  
If the link strength of a pair is computed by using the maximum of the scores, rather than the sum of the scores, all the results shown above hold, and it is also possible to define a class of SMWs where there is a unique link-maximal stable marriage with the highest weight, where the weight is given by the maximum of the links of its pairs.  
**Definition 7** (link maximal-strength): _Given a man, \(m\), and a woman, \(w\), the link maximal-strength of the pair \((m,w)\), denoted by \(lm(m,w)\), is the value obtained by taking the maximum between the preference value that \(m\) gives to \(w\) and the preference value that \(w\) gives to \(m\),i.e., \(lm(m,w)=max(p(m,w),p(w,m))\)._  
**Definition 8** (max-weight): _Given a marriage, \(M\), the max-weight of \(M\), denoted by \(w_{m}(M)\), is the maximum of the links of all its pairs, i.e., \(max_{\{(m,w)\in M\}}lm(m,w)\)._  
**Definition 9** (link-maximal-stability): _Given a marriage, \(M\), a man, \(m\), and a woman, \(w\), the pair \((m,w)\) is a link-maximal-blocking pair for \(M\) if it does not belong to \(M\) and the following conditions hold:_  
* \(lm(m,w)>lm(m^{\prime},w)\)_,_
* \(lm(m,w)>lm(m,w^{\prime})\)_,_  
_where \(m^{\prime}\) is the partner of \(w\) in \(M\) and \(w^{\prime}\) is the partner of \(m\) in \(M\). A marriage is link-maximal-stable if it does not contain link-maximal-blocking pairs._  
**Proposition 6**: _In an SMW, \(P\), where the preference values are all different, there is a unique link-maximal-stable marriage with the highest max-weight._