## 2 Related Work  
In this paper, we consider the fairness of the methodology to generate stable marriages. Other works have considered the fairness with the meaning of finding stable marriages where the overall happiness of the persons is maximized. One kind of fairer stable marriage that has been considered, is the _minimum regret_ stable marriage [5; 10]. The regret for each person is the position in his/her preference list of the persons to whom he/she is married. The regret of a marriage, \(M\), is the maximum regret of any person. Another way to characterize the overall happiness of a marriage is to consider the sum of the regret of every person. The _egalitarian_ stable marriage [11] minimizes the total sum of the regrets. Both minimum regret and egalitarian stable marriage can be found in polynomial time [10; 11]. In [12], [PERSON] and [PERSON] show that, beginning from an arbitrary marriage and satisfying a blocking pair at random, we will eventually reach a stable marriage with a probability of one. Our local search approaches exploit this result by building sequences of blocking pair removal that rapidly lead to stability thanks to the use of undominated blocking pairs. In this paper, we consider also the solution of stable marriage problems with ties and incomplete lists. It is known that weakly stable matchings may have different cardinality. Furthermore, finding the maximum (or minimum) cardinality weak stable matching for a given instance of SMTI is NP-hard. This holds even if the ties are at the tails of lists and on one side only, and each tie has a length of two [4], though the largest matching is at most twice the size of the smallest [4]. It has also been established that these problems are not approximable within \(\delta\), unless P= NP, for some \(\delta>1\); even if the preference lists are of a constant length, there is at most one tie per list, and the ties occur on one side only [13]. Above, we noted that a maximum cardinality weak stable matching is at most twice the size of a minimum cardinality weak stable matching. Therefore, if we break all ties in an arbitrary way and apply the GS (Gale and Shapley) algorithm to the resulting instance of SMI, we get what is simultaneously an approximation algorithm for the problem of finding a maximum (resp., minimum) stable matching with a performance ratio of two. In [13,14], an improved performance bound is shown for instances of SMTI with sparse ties. Three other pieces of work related to approximating maximum cardinality weak stable matchings have appeared in the literature. In [15], [PERSON] _et al._ present a randomized approximation algorithm with expected performance guarantee \(\frac{10}{7}\) for instances of SMTI in which ties occur on one side only; there is at most one tie per list, and each tie has a length of two. In [16], the same authors present an approximation algorithm with performance guarantee \(\frac{2}{(1+\frac{1}{L^{2}})}\) for instances of SMTI in which ties occur on one side only and each tie has a length of at most L. Additionally, they show a ratio of \(\frac{13}{7}\), where ties are allowed on both sides and are of a length of two. In [17], [PERSON] _et al._ present an approximation algorithm for a general instance of SMTI with guarantee \(2-c\frac{log(n)}{n}\), for an instance of size \(n\), where \(c\) is an arbitrary positive constant. Recently, in [18], [PERSON] _et al._ improve the approximation ratio to \(\frac{25}{17}\) for instances with one-sided ties. This approximation ratio also holds for the hospitals/residents problem (i.e., many-one variant) with one-sided ties (see [19] for the relationship between the approximability of the stable marriage problem and the hospitals/residents problem). Other approximation results with a higher ratio have been shown in [20, 21, 22]. A detailed overview of approximation algorithms is presented on pages 136-137 of [23]. In our paper, we consider a local search approach to solve SMTI instances.