*(Guest Post by Kyle Marcus)*

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

= Man

= Woman

= match between and

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

**Perfect Matching:** everyone gets paired up with someone else.

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

**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 and Women

Preferences (rankings)

Matching (no polygamy in )

Perfect Matching (everyone gets married)

Instability (breaking up and pairing with another person)

Stable Matching (perfect matching with no instability)

Input: & with preferences

Output: stable matching

**Natural Questions that can be asked about this problem**

(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.

instance 1:

: :

: :

instance 2:

: :

: :

There are 2 perfect matchings for each of the instances:

instance 1:

(1a) ~ stable

(1b) ~ unstable

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

instance 2:

(2a) ~ stable

(2b) ~ unstable

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

Note: for an instability to be present, both parties (ie. and ) 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

*IF* is stable then stop

*ELSE* move to next matching

This algorithm works but it would take a long time to run because there are 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* and **both** prefer each other to their current matchings

*IF* so then matching is unstable

## Leave a Reply