Posted by: atri | September 11, 2010

Lect 5: Stable Marriage Problem-II

In today’s lecture, we finished formally defining the stable marriage problem and looked at a few example to build some intuition about the problem. Finally, we considered the “dumb” algorithm for the problem that runs in time $O(n! n^3)$.

The slides are now online.

We went over the following quickly in class and I won’t have much time to talk about this in class, so try to figure out the following with your group:

• Describe an algorithm that outputs all the \$n!\$ perfect matchings given a set of men $\{m_1,\dots,m_n\}$ and women $\{w_1,\dots,w_n\}$.
• Prove that there is an algorithm that verifies whether a given perfect matching is stable or not runs in time $O(n^3)$.

Based on the group leader scribes, here are some responses to some questions that seem to have been bothering some of you

• We saw examples of a stable matching where a pair was matched to their least favorite potential spouse. Wouldn’t it make sense for these pairs to remain single? One answer is: in real life perhaps but this is too imprecise for an algorithms course. However, remember in the problem definition everyone needs to get married (i.e. everyone prefers to be married, even it is their least favorite choice, than remaining single). Again remember, this is a simplifying assumption and I do not claim that the version of the problem we defined in class mirrors real life. This is an important thing to remember: once we have formally defined a problem, throw away all you think you know about the problem from real life and just concentrate on the problem definition. So in short the answer to the question of why does a stable matching have to be a perfect matching, is well, because that is how it is defined.
• If there are multiple stable matching, can we choose one that is the best in some sense: e.g. one that maximizes total happiness? Of course the answer will depend on how we define happiness. Once we have looked at the Gale-Shapley algorithm, I will mention (without proof) one possible answer to this question.

As always, feel free to use the comments section, if you have any question.

Responses

1. These questions have more to do with HW#1 then Lecture 5, but since I don’t see a thread for HW#1 I’ll post them here.

First, I’m confused as to why there are “points” associated with problems that we are not suppose to turn in. The first problem of HW#1 (problems one and two in the first chapter) is not to be turned in, yet it’s worth 40 pts. The questions are relatively easy: will it just be assumed that we got the questions right? Are the points more of an indication as to how much the questions would be worth on a test?

Also, I’m not sure I understand why we’re not allowed to collaborate on problems that we don’t hand in. Is it more of a suggestion (as in it would be better to take the time to answer the questions ourselves)? If there’s a problem that I’m not suppose to turn in and I can’t figure it out, wouldn’t it be better to ask a group member how he/she answered the question instead of remaining confused? I mean, if a TA “catches” me asking a group member how he/she answered question one, is that some kind of breach of the HW policy? Sounds silly, but the rule is boldfaced and capitalized, so it’s obviously important. I realize we can and should bring up our questions in class or recitation, but that’s not always as convenient as asking a group member who’s studying the same material right next to me.

• Hi Nick,

Thanks a lot for your question. The instruction was carried over from last year’s HW 1 and should have been modified to read that no collaboration is allowed on the first problem. So all problems have to be turned in and collaboration is only allowed on the last two problems. The copy of HW 1 on the webpage has been updated with this information.