33
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

19
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ +1: nice answer. I agree; David's question is more precise---but I wanted to point out that others have also long thought of somehow unifying assignment and stable matching! $\endgroup$
    – Suvrit
    Nov 14, 2010 at 19:48
  • $\begingroup$ Why are these inequalities strict? $\endgroup$
    – Will Sawin
    Jul 22, 2014 at 0:32
12
$\begingroup$

A related question is "Can linear programming solve stable marriage?" John H. Vande Vate proved in 1989 ("Linear programming brings marital bliss") that the answer is "Yes." He found a set of linear inequalities whose extreme points are precisely the stable marriages. His results were both generalized and simplified by Uriel Rothblum three years later ("Characterization of stable matchings as extreme points of a polytope"). Rothblum's characterization uses the standard assignment problem constraints and some additional constraints that rule out the unstable marriages. This isn't quite what you're asking for, but it is related and so I thought you might be interested.

$\endgroup$
1
  • 2
    $\begingroup$ Actually, another relevant reference here is: jstor.org/pss/3690124 (this paper is also avail directly via google); this paper makes the following interesting observation: "while the marriage model and arguments concerning it are discrete and ordinal in nature, the formulation of the assignment model and arguments associated with it are cardinal in nature, and typically involve linear programming") The paper then proposes to construct a "unified" view. But I have not digested this view yet. $\endgroup$
    – Suvrit
    Nov 14, 2010 at 16:35
11
$\begingroup$

Unless I am mistaken or if in the meanwhile things have been resolved, your question seems to be essentially the same as Problem 10 listed in:

http://books.google.com/books?id=HqyCIky3bHwC&pg=PA64&dq=stable+marriage+assignment+problem&hl=en&ei=_VrdTLvuGsq34gaC0cQu&sa=X&oi=book_result&ct=result&resnum=7&ved=0CFAQ6AEwBg#v=onepage&q=stable%20marriage%20assignment%20problem&f=false

(In case link does not work: this is Problem 10, in the book Stable marriage and its relation to other combinatorial problems by Don Knuth)

$\endgroup$
5
  • 1
    $\begingroup$ Ah, thanks! And I even own that book! That's a pretty old reference though -- 1981 with an appendix added in 1997. So any more recent answers would still be useful. $\endgroup$ Nov 12, 2010 at 15:28
  • $\begingroup$ David, perhaps Knuth has updated information in his fasciles for volume 4 of TAOCP? I don't have those at hand, so cannot say. I will post an update if I find anything interesting. $\endgroup$
    – Suvrit
    Nov 12, 2010 at 15:32
  • $\begingroup$ Hmmm. This should logically be in Volume 4B www-cs-faculty.stanford.edu/~uno/taocp.html , which I don't think is out yet... $\endgroup$ Nov 12, 2010 at 15:38
  • $\begingroup$ Ahh..one more thing, perhaps over at cstheory.stackexchange someone has a more up-to-date answer? $\endgroup$
    – Suvrit
    Nov 12, 2010 at 15:40
  • $\begingroup$ At the link @David gave two comments above, it says, Volume 4B Combinatorial Algorithms, Part 2 (Upper Saddle River, New Jersey: Addison-Wesley, 2023), xviii+714pp. ISBN 0-201-03806-4 (This volume is currently in press and scheduled for publication on 11 October 2022.) (Preliminary drafts were previously published as paperback fascicles; see below.) $\endgroup$ Sep 20, 2022 at 8:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.