<p>There's a nice post by <a href="https://gilkalai.wordpress.com/2013/04/09/test-your-intuition-19-the-advantage-of-the-proposers-in-the-stable-matching-algorithm/" rel="nofollow noreferrer">Gil Kalai</a> which outlines the inherent bias in stable matching algorithms quantitatively. </p>

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

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

<p>Trivially  <span class="math-container">$d(n) \le \frac{n}{\log n}$</span> but i'm curious how much lower <span class="math-container">$d(n)$</span> has been bounded by current research.</p>

CC BY-SA 4.0
2018-12-27T07:51:58.173Z
This question is partially addressed in the comments on Gil's blog post...
usul
CC BY-SA 4.0
2018-12-28T12:58:31.417Z
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)
Mathijs
<reference-request><graph-algorithms><lower-bounds><matching><upper-bounds>
Optimally fair stable matching
Sidharth Ghoshal
# Optimally fair stable matching

(Asked by: username_0 on 2018-12-24)

There's a nice post by [Gil Kalai](https://gilkalai.wordpress.com/2013/04/09/test-your-intuition-19-the-advantage-of-the-proposers-in-the-stable-matching-algorithm/) 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.

**Tags:** reference-request, graph-algorithms, lower-bounds, matching, upper-bounds

> **Comments:**
> **username_1**: This question is partially addressed in the comments on Gil's blog post...  
> **username_2**: 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)  

---

## 0 answers

