## 4 \(\alpha\)-Stability
### Relations with Classical Stability Notions  
Given an SMW \(P\), let us denote with \(c(P)\) the classical SM problem obtained from \(P\) by considering only the preference orderings induced by the preference values of \(P\). The fact that \(\alpha\)-stability leads to a larger number of stable marriages w.r.t.the classical case is important to allow new stable marriages where some men, for example, the most popular ones or the least popular ones, may be married with partners better than all the feasible ones according to the classical notion of stability. \(I_{\alpha}(P)\) denotes the set of the \(\alpha\)-stable marriages of \(P\) and with \(I(c(P))\), the set of the stable marriages of \(c(P)\). **Proposition 1**: _Given an SMW \(P\), and a natural number, \(\alpha\), with \(\alpha\geq 1\), if \(\alpha=1\), \(I_{\alpha}(P)=I(c(P))\) and if \(\alpha>1\), \(I_{\alpha}(P)\supseteq I(c(P))\)._  
Given an SMP, \(P\), the set of \(\alpha\)-stable marriages of \(P\) contains the set of stable marriages of \(c(P)\), since the \(\alpha\)-blocking pairs of \(P\) are a subset of the blocking pairs of \(c(P)\). Let us denote with \(\alpha(P)\) the stable marriage problem with incomparable pairs obtained from an SMW, \(P\), by setting as incomparable every pair of people that do not differ for at least \(\alpha\), and with \(I_{w}(\alpha(P))\) the set of the weakly stable marriages of \(\alpha(P)\). It is possible to show that the set of the weakly stable marriages of \(\alpha(P)\) coincides with the set of the \(\alpha\)-stable marriages of \(P\). This means that, given an SMW \(P\), every algorithm that is able to find a weakly stable marriage for \(\alpha(P)\) provides an \(\alpha\)-stable marriage for \(P\). **Theorem 1**: _Given an SMW \(P\), \(I_{\alpha}(P)=I_{w}(\alpha(P))\)._  
**Proof:** We first show that \(I_{\alpha}(P)\subseteq I_{w}(\alpha(P))\). Assume that a marriage \(M\
ot\in I_{w}(\alpha(P))\), we now show that \(M\
ot\in I_{\alpha}(P)\). If \(M\
ot\in I_{w}(\alpha(P))\), then there is a pair (man,woman), say \((m,w)\), in \(\alpha(P)\), such that \(m\) prefers \(w\) to his partner in \(M\), say \(w^{\prime}\), and \(w\) prefers \(m\) to her partner in \(M\), say \(m^{\prime}\). By definition of \(\alpha(P)\), this means that \(m\) prefers \(w\) to \(w^{\prime}\) by at least degree \(\alpha\) and \(w\) prefers \(m\) to \(m^{\prime}\) by at least degree \(\alpha\) in \(P\), and so, \(M\
ot\in I_{\alpha}(P)\). Similarly, we can show that \(I_{\alpha}(P)\supseteq I_{w}(\alpha(P))\). In fact, if \(M\
ot\in I_{\alpha}(P)\), then there is a pair (man,woman), say \((m,w)\), in \(P\), such that \(m\) prefers \(w\) to \(w^{\prime}\) by at least degree \(\alpha\) and \(w\) prefers \(m\) to \(m^{\prime}\) by at least degree \(\alpha\). By definition of \(\alpha(P)\), this means that \(m\) prefers \(w\) to \(w^{\prime}\) and \(w\) prefers \(m\) to \(m^{\prime}\) in \(\alpha(P)\), and so, \(M\
ot\in I_{w}(\alpha(P))\), _i.e._, \(M\) is not a weakly stable marriage for \(\alpha(P)\). \(\square\)  
**Example 2**: _Assume that \(\alpha\) is two. Let us consider the following instance of an SMW, say \(P\): \(\{m_{1}:w_{1}^{[3]}>w_{2}^{[2]}\), \(m_{2}:w_{1}^{[4]}>w_{2}^{[2]}\), \(w_{1}:m_{1}^{[8]}>m_{2}^{[5]}\), \(w_{2}:m_{1}^{[3]}>m_{2}^{[1]}\}\). The set of the \(\alpha\)-stable marriages of \(P\), that coincides with the set of the weakly stable marriages of \(\alpha(P)\), by Theorem 1, contains the following marriages: \(M_{1}=\{(m_{1},w_{1}),(m_{2},w_{2})\}\) and \(M_{2}=\{(m_{1},w_{2}),(m_{2},w_{1})\}\). \(\square\)_  
On the other hand, not all stable marriage problems with partially ordered preferences can be expressed as stable marriage problems with weighted preferences, such that the stable marriages in the two problems coincide.