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

Question

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 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?

Answer 1

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.

Answer 2

For (1), yes, it can loop endlessly. Here's a demonstration with 8 people.

Suppose you have 3 ladies and 3 gentlemen standing in a circle, along with one more lady and gentleman (the pariahs) inside the circle. Here are the preferences you need to know about: everyone around the circle prefers to person to his or her right over the person to his or her left, and prefers either of them to the oppositely-sexed pariah in the center. (The compatibility of people diagonally opposite each other and the opinions of those in the center won't matter for the purposes of this solution.)

Initially, choose a pair of diagonally opposite people and pair each of them up with the appropriate pariahs in the center. Pair up the remaining four people around the circle in adjacent pairs. This is unstable: those matched with pariahs would prefer to be matched with the neighbor to the left, and the feelings are reciprocated (since everyone around the circle prefers right over left).

Performing both of these swaps, however, only serves to rotate the whole picture 120° while preserving the symmetry of the preferences we care about. Do it two more times and you've got the original matching again.