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) [algorithm](http://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm)ic [proof](http://www.artofproblemsolving.com/Forum/viewtopic.php?t=58865). 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?



Gale-Shapley stable marriage theorem: can we entrust matchmaking to monkeys?
Regarding (2), the answer is still "no". The following counter-example is from:



> 
> Tamura, Akihisa [Transformation from
>  arbitrary matchings to stable
>  matchings](http://www.ams.org/mathscinet-getitem?mr=1207740) 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.


