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.

  • $\begingroup$ This question is partially addressed in the comments on Gil's blog post... $\endgroup$
    – usul
    Dec 27, 2018 at 7:51
  • 1
    $\begingroup$ 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) $\endgroup$
    – Mathijs
    Dec 28, 2018 at 12:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.