(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 applicants applies to each of the employers.
We next saw that the problem above can be interpreted in terms of getting men married to women. (This was first proposed by Gale and Shapley in 1962.)
We then formalized the problem as follows. Let denote the set of men and denote the set of women. The set of all possible pairs is denoted by . 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 is a subset of such that every man and every woman appears in at most one pair in .
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 is a matching such that every man and woman appears in some pair in .
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 (woman resp.), denoted by ( resp.), is a total ordering on ( resp.).
Finally, we defined the notion of stability of a matching (by defining its negation):
Definition 4 (Instability) Given a matching , a pair is an instability with respect to if there exist and such that
- and are pairs in ;
- prefers to (i.e. in );
- in .
Note that if is an instability with respect to a matching , 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 is a perfect matching such that there does not exist which is an instability with respect to .
Thus, the stable matching problem can be formally defined as follows:
- Input: The set of men () and women () with along with the preference lists ( resp.) for every ( resp.)
- Output: A stable matching .
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.