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?

  • $\begingroup$ 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? $\endgroup$ Oct 4 '20 at 8:39
  • $\begingroup$ I think that was what I was intending, yes. $\endgroup$ Oct 5 '20 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.