3
$\begingroup$

Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:

In a man-optimal version of stable matching, each woman has worst partner that she can have in any stable matching.

Proof:

Suppose not. Let $M_0$ be the man-optimal stable matching, and suppose there is a stable matching $M’$ and a woman $w$ such that $w$ prefers $m = p_{M_0}(w)$ to $m' = p_{M'}(w)$ . But then $(m,w)$ blocks $M'$ unless $m$ prefers $p_{M'}(m)$ to $w = p_{M_0}(m)$, in contradiction of the fact that $m$ has no stable partner better than his partner in $M_0$.

I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying? From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$. But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction. Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The claim is not that every woman ends with the last man on her list. Rather, consider all stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ ok I see now, that you. In this case, is it true that with the G-S algorithm, there can only be 2 sets of stable matching (with stable matching set 1 with man-optimal and the other one coming from woman-optimal)? $\endgroup$
    – KJ.
    Jan 29, 2013 at 0:58
  • $\begingroup$ Definitely not. There could be exponentially many stable matchings. $\endgroup$
    – Yuval Filmus
    Jan 29, 2013 at 1:06
  • $\begingroup$ You can check the book by Gusfield and Irving, The Stable Marriage Problem: Structure and Algorithms, or the lecture notes by Knuth. $\endgroup$
    – Yuval Filmus
    Jan 29, 2013 at 1:12
  • $\begingroup$ does it depend on the order of men picked to propose? $\endgroup$
    – KJ.
    Jan 29, 2013 at 1:32
  • $\begingroup$ Any implementation of the Gale-Shapley algorithm produces a single stable matching. However, there are lots more stable matchings out there. $\endgroup$
    – Yuval Filmus
    Jan 29, 2013 at 2:52
1
$\begingroup$

There is a very nice lecture video on Youtube which describes all properties. I recommend you to watch is if you are new to the concept.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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