This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy.
Recall the set up of the stable marriage problem. We have $n$ men and $n$ women. Each man has sorted the women into some order, according to how much he likes them, and each women has likewise ranked the men. We want to pair off the men with the women so that there do NOT exist any pairs $(m,w)$ and $(m', w')$ where
- $m$ prefers $w'$ to $w$ and
- $w'$ prefers $m$ to $m'$.
It is a theorem of Gale and Shapley that such an assignment is always possible.
Here is a potential way you could try to find a stable matching. Choose some function $f: \{ 1,2,\ldots, n \}^2 \to \mathbb{R}$. Take the complete bipartite graph $K_{n,n}$, with white vertices labeled by men and black vertices by women, and weight the edge $(m,w)$ by $f(i,j)$ if $w$ is $m$'s $i$-th preference, and $m$ is $w$'s $j$-th preference. Then find a perfect matching of minimal weight, using standard algorithms for the assignment problem.
Is there any function $f$ such that this method works for all preference lists?
Best Answer
David's question is sufficiently more precise than the question of Donald Knuth referred to in the answer below. I believe it can be answered in the negative for $n \geq 3$, as follows.
Let $\{m_1,m_2,\ldots,m_n\}$ and $\{w_1,w_2,\ldots,w_n\}$ be the vertices of the parts of our graph $K_{n,n}$. Consider a choice of preferences where for $i\geq 3$ the man $m_i$ and the woman $w_i$ are each other's top choice. Then any stable marriage must match them to each other.
We consider now the preferences of $m_1,m_2,w_1$ and $w_2$. I will write $m_1 : w_1 \to 1, w_2 \to 3$ to denote that $w_1$ is $m_1$-th first choice and $w_2$ is his third, etc.
$m_1 : w_1 \to 1, w_2 \to 2,$
$m_2 : w_1 \to 2, w_2 \to 3,$
$w_1 : m_1 \to 2, m_2 \to 3,$
$w_2 : m_1 \to 1, m_2 \to 2.$
Here $m_1w_1, m_2w_2$ is a stable matching and therefore if the function $f$ is as desired then we must have
$f(1,2)+f(3,2) < f(2,1)+f(2,3),$
where on the left we have the weight of the stable matching and on the right is the weight of the matching $m_1w_2, m_2w_1$.
But the left and right side of the inequality above are symmetric and so by switching the $m$'s and $w$'s we can design another set of preferences implying
$f(2,1)+f(2,3) < f(1,2)+f(3,2).$
It follows that the function $f$ as specified in the question can not exist.