There may be many stable matchings in any given instance of smi, and there are several different criteria that may be used to describe an optimal or “fair" stable matching. The rank of an agent \(a\)  in a stable matching \(M\)  is the position \(a\) 's partner on \(a\) 's preference list, while the degree \(d\)  of \(M\)  is the highest rank of any agent in \(M\) . We might wish to limit the number of agents with large rank. A minimum regret stable matching is a stable matching that minimises \(d\)  and can be found in \(O(m)\)  time [1]}. Another type of optimality criteria, uses an arbitrary weight function to find a minimum (maximum) weight stable matching, which is a stable matching that has minimum (maximum) weight among the set of all stable matchings. A special case of this is known as the egalitarian stable matching which minimises the sum of ranks of all agents. [2]} gave an algorithm to find an egalitarian stable matching in \(O(m^2)\)  time and discussed how to generalise their method to the minimum (and maximum) weight stable marriage problem. Let \(K\)  be the weight of an optimal stable matching. [3]} later improved on the time complexities detailed above showing that any minimum weight stable matching (including an egalitarian stable matching), where \(K \le m\) , may be found in \(O(m^{1.5})\)  time using weighted sat, where \(m\)  is the number of possible man-woman pairs. In the general case where \(m < K\)  and \(K = O(m^{c})\) , and \(c\)  is a constant value, this rises to \(O(nm \log m)\)  time. A sex-equal stable matching seeks to minimise the difference in the sum of ranks between men and women. Finding a sex-equal stable matching was shown to be NP-hard [4]}. A median stable matching, defined formally in Section , describes a stable matching in which each agent gains their median partner (if the partners of an agent for all stable matchings were lined up in order of preference) [5]}. Computing the set of median stable matchings is #\(¶\) -hard [6]}.
