  We study the problem of finding "fair" stable matchings in the Stable
Marriage problem with Incomplete lists (SMI). For an instance $I$ of SMI there
may be many stable matchings, providing significantly different outcomes for
the sets of men and women. We introduce two new notions of fairness in SMI.
Firstly, a regret-equal stable matching minimises the difference in ranks of a
worst-off man and a worst-off woman, among all stable matchings. Secondly, a
min-regret sum stable matching minimises the sum of ranks of a worst-off man
and a worst-off woman, among all stable matchings. We present two new efficient
algorithms to find stable matchings of these types. Firstly, the Regret-Equal
Degree Iteration Algorithm finds a regret-equal stable matching in $O(d_0 nm)$
time, where $d_0$ is the absolute difference in ranks between a worst-off man
and a worst-off woman in the man-optimal stable matching, $n$ is the number of
men or women, and $m$ is the total length of all preference lists. Secondly,
the Min-Regret Sum Algorithm finds a min-regret sum stable matching in $O(d_s
m)$ time, where $d_s$ is the difference in the ranks between a worst-off man in
each of the woman-optimal and man-optimal stable matchings. Experiments to
compare several types of fair optimal stable matchings were conducted and show
that the Regret-Equal Degree Iteration Algorithm produces matchings that are
competitive with respect to other fairness objectives. On the other hand,
existing types of "fair" stable matchings did not provide as close an
approximation to regret-equal stable matchings.
