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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.