Recitation 3

Recitation notes for the week of September 11, 2017.

Homework reminders

Here are some gentle reminders about HW policies:

Make sure you submit your HW as a PDF only. Otherwise your submission will not be graded.
Remember to put collaborators and sources during your submission. Using none is also appropriate.
You can only collaborate with 2 other people and the collaboration must be for entire homework.
Proof Idea and Proof Details must be clearly separated and labeled. Not doing so will result in a ZERO for the problem.

Finding all stable matchings

Remember

Gale-Shapley is only helpful for finding one stable matching (two if different depending on if women propose and if men propose) but not all of them.

Example 1

To illustrate the above comment, consider the following instance of the Stable Matching Problem: \[L_{m_1}: w_1 > w_2 > w_3 ~~~~ L_{w_1}: m_2 > m_3 > m_1\] \[L_{m_2}: w_2 > w_3 > w_1 ~~~~ L_{w_2}: m_3 > m_1 > m_2\] \[L_{m_3}: w_3 > w_1 > w_2 ~~~~ L_{w_3}: m_1 > m_2 > m_3\]

It can be verified that the following three are indeed stable matchings for the above instance: \[\{(m_1,w_1),(m_2,w_2),(m_3,w_3)\}\] \[\{(m_2,w_1),(m_3,w_2),(m_1,w_3)\}\] \[\{(m_1,w_2),(m_2,w_3),(m_3,w_1)\}\] In the above, the last one will not be discovered by the Gale-Shapley algorithm (irrespective if whether it is the women or the men doing all the proposing).

What do we need to do to find all stable matchings?

As is the case many times, it is good to go back to the definition:

Stable matching definition

A stable matching is a perfect matching with no instabilities.

The above suggests the following brute-force algorithm:

Brute Force Algorithm (Algorithm Idea)

Find all perfect matchings.
Check if any perfect matching has no instabilities

Step 1: Find all perfect matchings

All perfect matchings can be found based off of the permutations of a set of $n$ elements. (We proved in last week homework that the total number of perfect matchings is $n!$).

Example 2

Consider the set $\{m_1, m_2, m_3\}$.

There are six possible permutations: \[m_1~~ m_2~~ m_3\] \[m_1~~ m_3~~ m_2\] \[m_2~~ m_1~~ m_3\] \[m_2~~ m_3~~ m_1\] \[m_3~~ m_1~~ m_2\] \[m_3~~ m_2~~ m_1\]

But what about the women?

By keeping the women in numerical order, you are creating a different matching every time. Hence why the the total number of perfect matchings is just $n!$.

Step 2: Check for instability

Recall that we have an instability any time there is a pairing $(m,w)$ and $(m',w')$ such that $m$ prefers $w'$ to $w$ and $w'$ prefers $m$ to $m'$. In other words, there is at least one pair of couples where the man from Couple 1 and the woman from Couple 2 (or vice versa) prefer each other to their current spouses.

Your job

Figure out how to turn this information into a somewhat efficient algorithm and implement it.

Example Proof: Chapter 1 Ex. 1

Exercise 1

Decide whether the following is true or false. If true, prove it. If it is false, give a counterexample.

In every instance of the Stable Matching Problem, there is a stable matching containing a pair $(m,w)$ such that $m$ is ranked first on the preference list of $w$ and $w$ is ranked first on the preference list of $m$.

Proof Idea

False.

In order to prove this statement, it is sufficient to provide a counterexample to the statement above. We will show that there is an instance of the stable matching problem that does not contain the pair $(m,w)$ where $m$ is ranked first on the preference list of $w$ and $w$ is ranked first on the preference list of $m$.

Proof Details

The example below is an instance of the stable matching problem since there are $n=2$ men and $n$ women where every $m\in M$ and every $w\in W$ has a preference list of $n$ women and men, respectively. \[L_{m_1} = w_2 > w_1~~~~ L_{w_1} = m_1 > m_2\] \[L_{m_2} = w_1 > w_2~~~~ L_{w_2} = m_2 > m_1\]

There are only 2 possible matchings and only 2 stable matchings for this instance of the stable matching problem \[\{(m_1,w_2), (m_2,w_1)\}\] and \[\{(m_1,w_1), (m_2,w_2)\}\].

A pair such that both partners rank their partner first does not exist for this problem.

Pigeon Hole Principle

The principle

Consider any assignment of $n +1$ pigeons to $n$ holes. Then there exists at least one hole with at least 2 pigeons in it.

Example 3

There are 500 students in a school. By pigeonhole principle, there must be at least 2 students that share a birthday.

For more

For the proof, more examples, and variations of the principle see the support page on the pigeonhole principle.