# Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?

Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying around, but they are too much to read at the moment, and from a quick look they don't seem to answer this.

We have $n$ ladies $L_1$, $L_2$, ..., $L_n$ and $n$ gentlemen $G_1$, $G_2$, ..., $G_n$. Each lady ranks all gentlemen in order of preferability (no ties are allowed), and each gentleman does the same to the ladies. A stable marriage means a permutation $\sigma \in S_n$ such that there are no $j\in\left\lbrace 1,2,...,n\right\rbrace$ and $k\in\left\lbrace 1,2,...,n\right\rbrace$ for which $L_j$ prefers $G_k$ to $G_{\sigma\left(j\right)}$ whereas $G_k$ prefers $L_j$ to $L_{\sigma^{-1}\left(k\right)}$.

Okay, I should have said that it is a matching where we cannot find a lady and a gentlemen which prefer each other to their respective matching partners. But is it combinatorics if there are no symmetric groups in it?...

Anyway, this is known to have a simple (but very hard to find) algorithmic proof. What I am wondering is whether the following stupid algorithm can also be forced to terminate:

We choose some arbitrary matching between the ladies and the gentlemen. Then, at each step, we randomly pick a pair that prefers each other to their respective partners, and marry them to each other, simultaneously marrying their respective partners to each other (no matter what they think about it). Repeat until no such steps are possible anymore.

(1) Can this "algorithm" loop endlessly if we choose our pairs in a stupid enough way?

(2) Can we make this algorithm terminate by giving a reasonable choice tactic for the pairs?

-
no real research; so you have not tried matchmaking with monkeys? –  Will Jagy Jul 12 '11 at 17:38

Regarding (2), the answer is still "no". The following counter-example is from:

Tamura, Akihisa Transformation from arbitrary matchings to stable matchings J. Combin. Theory Ser. A 62 (1993), no. 2, 310–323

Consider $n$ men and $n$ women. With indices periodic modulo $n$, the first four choices of each person are:

For $m_i$: First choice is $w_i$, then $w_{i-2}$, then $w_{i+1}$, then $w_{i-1}$.

For $w_i$: First choice is $m_{i+1}$, then $m_{i-1}$, then $m_i$, then $m_{i+2}$.

Start with the matching that pairs $m_i$ to $w_i$ for $1 \leq i \leq n-2$, pairs $m_{n-1}$ and $w_n$ and $m_n$ and $w_{n-1}$. I leave it as an exercise that there is only one unstable pair, swapping them leaves a situation where there is only one unstable pair, and swapping those brings you back to the original situation with indices shifted.

-
I don't think so. Yes, there is only one unstable pair. But this is $(m_n,w_1)$, and swapping them removes the edges $(m_n,w_{n-1})$ and $(m_1,w_1)$, instead adding the edges $(m_n,w_1)$ and $(m_1,w_{n-1})$. Now we have three skew edges... –  darij grinberg Jul 12 '11 at 18:19
Right. Now the only unstable pair is $(m_{n-1}, w_{n-1})$. Swap them to get $(m_n, w_1)$, $(m_1, w_n)$, and everyone else with $(m_k, w_k)$. –  David Speyer Jul 12 '11 at 18:23
Now it works (I have checked it). Thanks a lot! –  darij grinberg Jul 12 '11 at 18:39