Posted by: atri | September 4, 2011

## Lect 3: Stable Marriage problem

In Friday’s class, we formalized the problem solved by the NRMP. We started off with the more general problem of assigning applicants to employers in a way such that for every applicant $a$ that is not assigned to a employer $e$ either

• $e$ prefers all of its assigned applicants to $a$; or
• $a$ prefers her current employer to $e$.

We then made some simplifying assumptions:

1. There are $n$ employers and applicants;
2. Each employer has exactly one position open; and
3. Each applicant applies to every employer.

The above are simplifying assumptions but they retain the essence of computing a stable assignment. With the above assumption one can also model the problem as $n$ men and $n$ women having preferences for the members of the opposite sex and marrying them off in such a way that no two men and women who are not married to each other have an incentive to break off their current marriages and get married to each other. (Important note: both the man and the woman should prefer each other over their current partners for an instability to happen.)

We formally defined the notions of matching, perfect matching, instability and stable matching. We then looked at some simple examples.

John asked the following question that we will consider in the next lecture (also in Sec 1.1 in the textbook):

1. Does every problem instance have a stable matching?
2. A natural follow-up question: if an instance has a stable matching, can we compute it efficiently?