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

Responses

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

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 84 other followers

%d bloggers like this: