Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.)

share|improve this answer
    
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)? –  KJ. Jan 29 '13 at 0:58
    
Definitely not. There could be exponentially many stable matchings. –  Yuval Filmus Jan 29 '13 at 1:06
    
You can check the book by Gusfield and Irving, The Stable Marriage Problem: Structure and Algorithms, or the lecture notes by Knuth. –  Yuval Filmus Jan 29 '13 at 1:12
    
does it depend on the order of men picked to propose? –  KJ. Jan 29 '13 at 1:32
    
Any implementation of the Gale-Shapley algorithm produces a single stable matching. However, there are lots more stable matchings out there. –  Yuval Filmus Jan 29 '13 at 2:52
add comment

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.

share|improve this answer
    
thank you, yes it is new, much appreciated. –  KJ. Jan 29 '13 at 0:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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