First, we look at cost-based optimality. An egalitarian stable matching is a stable matching \(M\)  such that \(c(M)\)  is minimised taken over all stable matchings in \(\mathcal {M}_S\) . Let \(w(M)\)  define some arbitrary weight function of stable matching \(M\) . A matching \(M\)  is minimum (maximum) weight if \(w(M)\)  is minimum (maximum) taken over all stable matchings in \(\mathcal {M}_S\) . Thus the minimum weight function \(w(M)\)  is a generalisation of the cost function \(c(M)\) . [1]} showed that an egalitarian stable matching can be found in \(O(m^2)\)  time and a minimum weight stable matching in \(O(m^2 \log n)\)  time. Recall that \(K\)  is the weight of an optimal stable matching. [2]} improved on the methods above, giving an \(O(m^{1.5})\)  algorithm for finding a minimum weight stable matching when \(K\le m\) . In the general case when \(m < K\)  and \(K = O(m^{c})\)  the time complexity for this algorithm rises to \(O(nm \log m)\) , where \(c\)  is a constant value. A stable matching \(M\)  is balanced if \(\max \lbrace c_U(M),c_W(M)\rbrace \)  is minimised, taken over all stable matchings in \(\mathcal {M}_S\) . The problem of finding a balanced stable matching was shown to be \(\) -hard [3]}. A sex-equal stable matching is a stable matching \(M\)  such that the difference \(|c_U(M)-c_W(M)|\)  is minimum, taken over all stable matchings in \(\mathcal {M}_S\) . [4]} showed that the problem of finding a sex-equal stable matching is also NP-hard.
