## 4 \(\alpha\)-Stability
### Dominance and Lex-Male-Optimality  
We recall that in SMPs, a weakly-stable marriage dominates another weakly-stable marriage if men are happier (or equally happy) and there is at least a man that is strictly happier. The same holds for \(\alpha\)-stable marriages.  
**Definition 2** (dominance): _Given two \(\alpha\)-stable marriages, say \(M\) and \(M^{\prime}\), \(M\) dominates \(M^{\prime}\) if the following conditions hold:_  
* \(\forall\) _men_ \(m\)_,_ \(M(m)\geq M^{\prime}(m)\)__
* \(\exists\) _man_ \(m^{\prime}\)_,_ \(M(m^{\prime})>M^{\prime}(m^{\prime})\)__  
**Example 3**: _Let us consider the SMW shown in Example 2. We recall that \(\alpha\) is two and that the \(\alpha\)-stable marriages of this problem are \(M_{1}=\{(m_{1},w_{1}),(m_{2},w_{2})\}\) and \(M_{2}=\{(m_{1},w_{2}),(m_{2},w_{1})\}\). It is possible to see that: \(M_{2}\) does not dominate \(M_{1}\), since, for \(m_{1}\), \(M_{1}(m_{1})>M_{2}(m_{1})\) and \(M_{1}\) does not dominate \(M_{2}\), since, for \(m_{2}\), \(M_{2}(m_{2})>M_{1}(m_{2})\). \(\Box\)_  
We now discriminate among the \(\alpha\)-stable marriages of an SMW, by considering the preference values given by women and men to order pairs that differ for less than \(\alpha\). For example, assume that men are students and women are schools; we want order pairs that differ for less than \(\alpha\) among students according to the aggregated opinion the schools have of the students. Then, we want to make sure that best student goes to his favorite (stable) school. To achieve this, in this paper, we will consider a marriage optimal when the most popular men are as happy as possible and they are married with their most popular best \(\alpha\)-feasible women (however, we could also consider a marriage optimal when the least popular men are as happy as possible and they are married with their most popular best \(\alpha\)-feasible women). To compute a strict ordering on the men where the most popular men (resp., the most popular women) are ranked first, we follow a reasoning similar to the one considered in [39,40], that is, we apply a voting rule [28] to the preferences given by the women (resp., by the men). More precisely, such a voting rule takes as input the preference values given by the women over the men (resp., given by the men over the women) and returns a strict total order over the men (resp., women).  
**Definition 3** (lex-male-optimal): _Consider an SMW, \(P\), a natural number, \(\alpha\), and a voting rule, \(r\). Let us denote with \(o_{m}\) (resp., \(o_{w}\)) the strict total order over the men (resp., over the women) computed by applying \(r\) to the preference values that the women give to the men (resp., the men give to the women). An \(\alpha\)-stable marriage, \(M\), is lex-male-optimal w.r.t. \(o_{m}\) and \(o_{w}\), if, for every other \(\alpha\)-stable marriage, \(M^{\prime}\), the following conditions hold:_  
* _there is a man,_ \(m_{i}\)_, such that_ \(M(m_{i})>_{o_{w}}M^{\prime}(m_{i})\)_,_
* _for every man_ \(m_{j}<_{o_{m}}m_{i}\)_,_ \(M(m_{j})\leq_{o_{w}}M^{\prime}(m_{j})\)_._  
**Proposition 2**: _Given an SMW, \(P\), a strict total ordering, \(o_{m}\) (resp., \(o_{w}\)), over the men (resp., women):_  
* _there is a unique lex-male-optimal_ \(\alpha\)_-stable marriage w.r.t._ \(o_{m}\) _and_ \(o_{w}\)_, say_ \(L\)_;_
* \(L\) _may be different from the male-optimal stable marriage of_ \(c(P)\)_;_
* _if_ \(\alpha(P)\) _has a unique undominated weakly stable marriage, say_ \(L^{\prime}\)_, then_ \(L\) _coincides with_ \(L^{\prime}\)_; otherwise,_ \(L\) _is one of the undominated weakly stable marriages of_ \(\alpha(P)\)_._