## 5 Link-Based Stability Notions
### Finding Link-Based Stable Marriages with the Highest Weight
#### 5.2.1 Max-Weight  
We assume now that the weight of a marriage is computed by taking the maximum of the links of its pairs. We will now provide a general polynomial algorithm that is able to find the link-max stable marriage with the highest max-weight. We will show that this algorithm can be also adapted to find link-additive stable marriage and \(\alpha\)-stable marriage with the highest max-weight.  
We will first present the Max-link-max algorithm (Algorithm 3). It takes as input an instance, \(P\), of an SMW with \(n\) men and \(n\) women and returns a marriage, \(\mu\). We will show that such a marriage, \(\mu\), is the link-max stable marriage of \(P\) with the highest max-weight. The algorithm works as follows. First, it initializes \(\mu\) with the empty set and \(M\) with the set of all the pairs (man,woman) that can be built with the men and women of \(P\). Then, it performs the following steps until \(M\) is not empty: it looks for the pair with the highest link,_i.e._, with the highest link-max strength; it adds such a pair, say \((m^{*},w^{*})\), to \(\mu\); and it removes from \(M\) all the pairs containing \(m^{*}\) or \(w^{*}\). Notice that with a suitable data structure, it is possible to find the pair with the highest link by only saving for every woman and for every man the partner who gives the maximum weight and the value of this maximal weight. This can be done in _O_(\(n^{2}\)) time.  
```
Input: \(P\): an SMW with \(n\) men \(\{m_{1},\ldots,m_{n}\}\) and \(n\) women \(\{w_{1},\ldots,w_{n}\}\) Output: \(\mu\): a marriage \(\mu\leftarrow\emptyset\) \(M\leftarrow\{(m_{i},w_{j})\), for \(i,j=1,\ldots,n\}\) while\(M\
eq\emptyset\)do \((m^{*},w^{*})\leftarrow\) the pair of \(M\) with the maximum link-max strength; \(\mu\leftarrow\mu\cup(m^{*},w^{*})\); \(M\gets M\setminus\{(m^{*},w_{j}),(m_{i},w^{*}),i,j=1,\ldots,n\}\); return\(\mu\)
```  
**Proposition 7**: _Given an SMW, \(P\), Max-link-max applied to \(P\) returns the link-max stable marriage of \(P\) with the highest max-weight._  
**Proof:** Let us denote with \(\mu\) the marriage returned by Max-link-max. We first show that \(\mu\) is link-max stable, and then, we show that it has the highest max-weight. To show that \(\mu\) is link-max stable, we have to show that there are no link-max blocking pairs. Assume that there is a link-max blocking pair for \(\mu\), say \((m,w)\). Then, it must be that \(lm(m,w)\geq max\{lm(m^{\prime},w),lm(m,w^{\prime})\}\). Thus, the pair \((m,w)\) is picked in the **while**-loop before \((m^{\prime},w)\) and \((m,w^{\prime})\). Thus, if \((m^{\prime},w)\) and \((m,w^{\prime})\) are in \(\mu\), both \(m\) and \(w\) must have been matched to partners that cannot be \(m^{\prime}\) and \(w^{\prime}\). The link-max stable marriage \(\mu\) returned by Max-link-max has the highest max-weight, since in the first step, the algorithm puts in \(\mu\) the pair with the maximum link-max strength, and, by definition, such a value is the max-weight of \(\mu\). \(\Box\)  
**Proposition 8**: _Given an SMW, \(P\), with \(n\) men and \(n\) women, the complexity of Max-link-max applied to \(P\) is \(O(n^{2})\)._  
To find a link-additive stable marriage with the maximum weight, we can adopt an algorithm similar to Max-link-max. In such a case, the link strength of a pair is computed by considering the sum of thescores of the pair elements, rather than their maximum. The only difference in the algorithm is that in the while-cycle, we have to find one of the pairs of \(M\) with the maximum link-additive strength, rather than one of the pairs with the maximum link-max strength.  
Max-link-max works also for stable marriage procedures that return an \(\alpha\)-stable marriage. More precisely, it returns the \(\alpha\)-stable marriage with the highest max-weight.