Posted by: Jesse | September 9, 2010

## Lect 4: Stable Marriage Problem

(Guest Post by Jesse Hartloff)

In this lecture we introduced the stable marriage problem and defined several terms related to it.

As an introduction to the stable marriage problem we discussed the real world example of resident matching.  This is accomplished by the National Resident Matching Program(NRMP) by gathering the preferences of each resident and hospital as well as information about the hospitals.  The NRMP then processes this data and determines which hospital each resident should be matched with.  The goal is to find a set of matches such that no resident or hospital will want to change their arrangement.  If this is accomplished the matching is said to be stable.

To analyze the stable marriage problem mathematically we looked at the problem of marrying a set of women $W$ with a set of men $M$ and introduced a few simplifications.

Simplifications:

1. Each $w\in W$ can only marry one $m\in M$ and vice-versa (No polygamy).
2. $|W|=|M|=n$.  There are $n$ men and $n$ women.
3. Every women is matched with a man and vice-versa (everyone gets married).
4. All preferences are known up front.

We labeled the men and women as follows:

$M=\{m_1, m_2, \ldots , m_n\}$

$W=\{w_1, w_2, \ldots , w_n\}$

$M\times W =$  the set of all possible pairs.

For $n=2, M\times W=\{(m_1, w_1), (m_1, w_2), (m_2, w_1), m_2, w_2)\}$.

The problem is to find a set $S$ such that $S\subseteq M\times W$ and $S$ is a stable perfect matching.

Perfect Matching: A matching that contains every element in exactly one pair.

Preferences: Each man and women will have a complete list of preferences where they rank every member of the opposite sex against each other.

Instability: Instability exists within a set of pairings if a man and woman who are not paired together both prefer the other more than the person they are currently paired with.  This definition will be formalized on Friday.