# Are stable matchings (noise-)stable?

Suppose a group of computer scientists have entrusted their dating lives to a computer. Specifically, there are $$n$$ men and $$n$$ women, all of whom are cis-het. Being educated people, they of course apply the Gale-Shapley algorithm to this problem.

A mathematician then objects: But your preferences may change with time -- won't you have to change partners constantly to stay in an optimal matching?

So, to make this into a formal mathematical problem, let $$f_n: S_n^{2n} \to S_n$$ be the function that maps the $$2n$$ preferences of the people involved to the assignment of a man to each woman, in such a way that there are no two people who want to leave their current partners and marry each other instead.

Call the initial preferences of the people involved $$X_0$$, and assume for simplicity that $$X_0$$ is uniform on $$S_n^{2n}$$. The preferences of the people evolve through that a random person randomly swaps the place of two people in their ordering, at unit times. That is, $$X_t$$ does a random walk on the Cayley graph of $$S_n^{2n}$$ with the obvious generators $$Id\times Id\times \ldots \times (ab)\times \ldots \times Id$$.

The way to mathematically formalize the question we asked in the title is, I believe, to ask what the relation is asymptotically between $$f_n(X_0)$$ and $$f_n(X_{\epsilon t_n})$$, where $$t_n$$ is some appropriate timescale for the random walk on $$S_n^{2n}$$ (relaxation time?) $$-$$ are they independent for every $$\epsilon$$, or very near to each other?

• The stable matching is generally not unique. If you apply, for example, the version of the Gale-Shapley algorithm where the women propose, then you obtain the extreme point of the set of stable matchings which is optimal for the women. Is that the $f_n$ that you'd like to consider? Oct 4 '20 at 8:39
• I think that was what I was intending, yes. Oct 5 '20 at 21:00