Lect 3: Stable Marriage Problem

Posted by: atri | September 5, 2009

Lect 3: Stable Marriage Problem

(This post is typeset using LaTeX2WP)

Today’s lecture gave a formal definition of the resident matching problem that we saw last lecture.

We first made the following two simplifying assumptions:

Every employer wants to employ exactly one applicant; and
Each of the ${n}$ applicants applies to each of the ${n}$ employers.

We next saw that the problem above can be interpreted in terms of getting ${n}$ men married to ${n}$ women. (This was first proposed by Gale and Shapley in 1962.)

We then formalized the problem as follows. Let ${M=\{m_1,\dots,m_n\}}$ denote the set of men and ${W=\{w_1,\dots,w_n\}}$ denote the set of women. The set of all possible pairs is denoted by ${M\times W}$ . We next defined certain terminology that was used to define the problem (and will be used later on in the course).

Definition 1 (Matching) A matching ${S}$ is a subset of ${M\times W}$ such that every man ${m\in M}$ and every woman ${w\in W}$ appears in at most one pair in ${S}$ .

As Andrew quipped in class, when you draw out a matching properly, you get a bunch of straight couples.

Definition 2 (Perfect Matching) A perfect matching ${S}$ is a matching such that every man ${m\in M}$ and woman ${w\in W}$ appears in some pair in ${S}$ .

Note that our output needs to be a perfect matching. Next, we formalized the notion of preferences.

Definition 3 (Preferences) The preference list for a man ${m\in M}$ (woman ${w\in W}$ resp.), denoted by ${L_m}$ ( ${L_w}$ resp.), is a total ordering on ${W}$ ( ${M}$ resp.).

Finally, we defined the notion of stability of a matching (by defining its negation):

Definition 4 (Instability) Given a matching ${S}$ , a pair ${(m,w')\in M\times W}$ is an instability with respect to ${S}$ if there exist ${m'\in M}$ and ${w\in W}$ such that

${(m,w)}$ and ${(m',w')}$ are pairs in ${S}$ ;

${m}$ prefers ${w'}$ to ${w}$ (i.e. ${w'>w}$ in ${L_m}$ );

${m>m'}$ in ${L_{w'}}$ .

Note that if ${(m,w')}$ is an instability with respect to a matching ${S}$ , then they have the incentive to break their current matchings and form a pair on their own.

Finally, we defined a stable matching:

Definition 5 (Stable Matching) A stable matching ${S\subseteq M\times W}$ is a perfect matching such that there does not exist ${(m,w)\in M\times W}$ which is an instability with respect to ${S}$ .

Thus, the stable matching problem can be formally defined as follows:

Input: The set of men ( ${M}$ ) and women ( ${W}$ ) with ${|M|=|W|=n}$ along with the preference lists ${L_m}$ ( ${L_w}$ resp.) for every ${m\in M}$ ( ${w\in W}$ resp.)
Output: A stable matching ${S\subseteq M\times W}$ .

We concluded the lecture with the following two natural questions:

Does there exist a stable marriage for any set of preference lists?
If so, can we compute such a stable marriage efficiently?

The slides for the lecture have been uploaded.

About these ads

Posted in Lectures

Responses

S is a subset of M X W, such that every man m∈ M and every woman w∈W. Since, we already defined S is a subset of M X W. Why we using same subset ‘S’ in all of the definition of Matching, Perfect Matching, Preferences, Instability and Stable Matching. Each of these sets have different elements. Hence, I guess if we used the subscript in set notation. It will be much more easy to understand, like for Matching (Sm), Perfect Matching, (Spm), Preferences (Sp), Instability (Si) and Stable Matching (Ssm).

I have write this first on MS Word, in order to type subscript on each subset S.
By: Santosh Thapa on September 5, 2009
at 8:22 pm

Reply
Hi Santosh,

Generally in a definition only the terms or notations that are defined are assumed to have a global scope while the rest are just local to the definition. In all the definitions above $S$ is a local variable and should be interpreted to have scope only limited to the definition it appears in. E.g., in Definition 1, the term “matching” is the only thing being defined and $S$ appearing in it should be interpreted to have local scope.

Of course, we could use your terminology of $S_m, S_{pm}, S_p, S_i$ and $S_{sm}$ but I think in this case doing so will make the notation more cumbersome without much benefit. (As a general rule, I try to use as little notation as possible.)

Thanks for binging this up: now everyone knows what convention I had in mind.
By: atri on September 6, 2009
at 1:54 am

Reply

	atri on Grades submitted and final…
	dachichk on Grades submitted and final…
	Greyjacket on HW8 Statistics
	atri on Clarification on Q1 on HW…
	Andrew Wong on Clarification on Q1 on HW…

Introduction to Algorithm Analysis and Design

Lect 3: Stable Marriage Problem

Like this:

Responses

Leave a Reply Cancel reply

Categories

Follow the blog

Lectures

Discuss

Feedback

Handouts

Course Webpage

Related Blogs

Search this blog

Featured posts

Recent Posts

Archives

Recent Comments

Categories

Follow “Introduction to Algorithm Analysis and Design”