Posted by: kmarcus2 | September 11, 2010

## Lect 5: Stable Marriage Problem-II

(Guest Post by Kyle Marcus)

In class today we first went over the matching problem that we worked on last time

$M$ = Man
$W$ = Woman
$(MW)$ = match between $M$ and $W$

Matching: Consists of pairing up a $M$ and a $W$, and 1 $M$ can only match up with 1 $W$ and vice verca.

Perfect Matching: everyone gets paired up with someone else.

Preferences: Every $M$ has a strictly ordered list that ranks every $W$ from most preferable to least preferable, and every $W$ has a similar strictly ordered list that ranks every $M$.

Instability: This happens when two people want to break up and pair up with a different person that is higher on their preference list.

Stable Marriage problem:
Set of men $M$ and Women $W$
Preferences (rankings)
Matching (no polygamy in $MxW$)
Perfect Matching (everyone gets married)
Instability (breaking up and pairing with another person)
Stable Matching (perfect matching with no instability)

Input: $M$ & $W$ with preferences
Output: stable matching

(1) Does stable matching always exist?
(2) Can we efficiently compute one?

We will prove both (1) and (2) to be true by first generating a algorithm and then proving that there is always a stable matching.

We then looking at a sample pairing and two different preference lists and looked to see what paring was stable and which was not stable.

$M=\{m, m'\}$    $W=\{w, w'\}$

instance 1:
$L_m$ : $w > w'$                $L_w$ : $m > m'$
$L_m'$ : $w > w'$                $L_w'$ : $m > m'$

instance 2:
$L_m$ : $w > w'$                $L_w$ : $m > m'$
$L_m'$ : $w' > w$                $L_w'$ : $m' > m$

There are 2 perfect matchings for each of the instances:

instance 1:
(1a)  $(mw) (m'w')$ ~ stable
(1b)  $(mw') (m'w)$ ~ unstable
The matching (1a) is stable because $m$ and $w$ both prefer each other $w'$ and $m'$, therefore neither $m$ or $w$ will want to break up and pair up with a different person.  The matching (1b) is unstable because $m$ and $w$ will want to break up with their original partners and pair up with each other.

instance 2:
(2a) $(mw) (m'w')$ ~ stable
(2b) $(mw') (m'w)$ ~ unstable
The matching (2a) is stable because $m$ and $w$ both prefer each other $w'$ and $m'$, therefore neither $m$ or $w$ will want to break up and pair up with a different person, also $m'$ and $w'$ prefer each other over $w$ or $m$ so they will not want to break up either.  The matching (2b) is unstable because $m$ and $w$ will want to break up with their original partners and pair up with each other, same with $m'$ and $w'$.

Note: for an instability to be present, both parties (ie. $m$ and $w$) must want to break up and form a different union.

Note: stable matching does not mean people are always with other people who they prefer, we are assuming everyone wants to get married no matter what.

In the final part of class we came up with a general algorithm that could go through all the perfect matchings and check to see if it is stable

algorithm:
go through all perfect matchings $S$
IF $S$ is stable then stop
ELSE move to next matching

This algorithm works but it would take a long time to run because there are $n!$ perfect matchings that the algorithm would have to check.

To check if the perfect matching is stable run the following algorithm:

go through all pairs
check IF $m$ and $w$ both prefer each other to their current matchings
IF so then matching is unstable