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?