# Optimally fair stable matching

There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively.

In the traditional loyd shapeley algorithm for $$n$$ men and $$n$$ women, given randomly generated preference lists its expected that the average place of a man's wife will be $$\log n$$ and the expected place of a woman's husband will be $$\frac{n}{\log n}$$ on their preference lists (after pairing).

We can look at the pair $$\left( \log n , \frac{n}{\log n} \right)$$ and ask, given unlimited computing resources what is the smallest possible $$d(n)$$ for which we can guarantee that a stable matching of $$n$$ men and $$n$$ women with uniform randomly generated preference lists both have expected place of their partner equal to: $$\left(d(n), d(n) \right)$$?

Trivially $$d(n) \le \frac{n}{\log n}$$ but i'm curious how much lower $$d(n)$$ has been bounded by current research.

• This question is partially addressed in the comments on Gil's blog post...
– usul
Dec 27, 2018 at 7:51
• There is a O(n^4) algorithm to compute such a matching: Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the ”optimal” stable marriage. Journal of the Association for Computing Machinery 34(3), 532–543 (1987) Dec 28, 2018 at 12:58