Posted by: Eric Mikida | September 9, 2010

## Lect 4: Stable Marriage Problem

(Guest Post by Eric Mikida)

Overview

In lecture 4 we went back and looked at the main steps for algorithm design and began applying them to a real world problem. From a high level overview, the steps as we have them defined go as follows:

Problem statement as given by a real world problem

Problem definition (redefine the problem with a precise mathematical definition)

Algorithm

Implement using data structures

Analysis (test for correctness)

The Stable Marriage Problem

The actual problem we are going to apply these steps to is the Stable Marriage Problem, which was first solved by David Gayle and Lloyd Shapely. In class we were given the problem statement in terms of the NRMP and matching residents to hospitals, but the problem can be used in its general form and applied to multiple different situations.

Problem Statement:

Given a pool of males and females, pair them off such that the system is stable. We define the system to be stable if for any male and female, breaking off with their current pairing would not benefit both of them. This way there would be no incentive for anyone to break their prior arrangements to make new ones, and the system would be constant. For the majority of this class, we took this problem statement and began to formulate a problem definition using precise mathematical language.

Problem Definition:

Before we defined the problem, we needed to make a few simplifications to make the problem more precise.

Every man can only be paired with one woman (and vice versa; no polygamy)

– There are n men, and n women

– Every man gets paired with a woman (no single people/no same sex marriage)

All preferences are known up front

Now that we have defined the problem more precisely we can start getting even more specific by using mathematical notation

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

– The set of all men

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

– The set of all women

$MxW = \{(m,w) | m \in M, w \in W\}$

– The set of all pairs of men and women

Other Definitions:

Matching: $S \subseteq MxW$ such that any $m \in M$ and $w \in W$ only appear in at most one pair

Perfect Matching: A matching where every $m \in M$ and $w \in W$ is in exactly one pair

In the next lecture we are going to continue with the problem definition by including the two missing pieces: stability, and preferences. Presumably, once we finish with the problem definition we will continue with the process and start looking at actual algorithms to solve this problem.