1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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

0

Reset to default

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.