Recitation 2

Recitation notes for the week of September 4, 2017.

Overview

Stable Matching Review

The problem

Input:

  • Set of $n$ men $M = \{m_1, m_2, \dots,m_n\}$
  • Set of $n$ women $W = \{w_1, w_2, \dots, w_n\}$
  • For every $m\in M$, $L_m$ a total ranking of all women
  • For every $w\in W$, $L_w$ a total ranking of all men

Output: A stable matching.

Stable Matching

A perfect matching that has no instabilities.

Perfect Matching

For every $m\in M$, $m$ is assigned exactly $1$ woman AND for every $w\in W$, $w$ is assigned exactly $1$ man.

Instability

Given two pairs $(m, w)$ and $(m', w')$, where $m$ prefers $w'$ to $w$ and $w'$ prefers $m$ to $m'$ the pair $(m, w')$ is an instability.

Exercise 1

(This is to make sure you remember how to propagate negations in first order logic statements). How would you define a perfect matching to be a stable matching, directly in terms of the preferences (i.e. state logically what no instability means).

Proof by Induction

We will review Q2 on Homework 0.

Exercise 2

Prove that the total number of perfect matchings when you have $n$ men and $n$ women is $n!$.

(Recall $n!=n\times(n−1)\times (n−2)\times\cdots\times 2\times 1$.)

Perfect matching $\neq$ Stable matching

In a perfect matching we do not care about preferences, just that every individual has a match

Example 1

Consider the case of $n=3$, i.e. $W=\{w_1, w_2, w_3\}$ and $M=\{m_1,m_2,m_3\}$. In this case an example of a perfect matching will be $\{(m_1, w_1), (m_2, w_2), (m_3, w_3)\}$.

Note that $m_1$ can be with $3$ women, (given $m_1$'s assignment) $m_2$ with $2$, and (given $m_1$ and $m_2$'s assignment) $m_3$ with the last woman. I.e. we have $3\times 2\times 1 = 3!$ choices.

Hint

When thinking about HW problems, its almost ALWAYS super helpful to make and work through examples.

Overview of proof by induction

Induction Proofs have 3 steps:

  1. Base Case (In the current example $n = 1$).
  2. Inductive Hypothesis (In the current example $n = k-1$ for some $k\ge 2$).
  3. Inductive Step (In the current example prove for $n = k$).

Note

The values above (i.e. $n$ and $k$) are not set in stone: they can change depending on problem statement.

Back to Exercise 2

Proof Idea

We'll prove this by induction on $n$, the number of people of each gender that we are matching. Our base case will be $n=1$, where it will be straightforward to show that the number of perfect matchings is $1!=1$. We will assume that for a set of $n=k-1$ people of each gender, the total number of possible perfect matchings is $\left(k-1\right)!$. Then we will use our assumption for $n=k-1$ to show that with one more man and one more woman, that our number of possible perfect matchings is $k\times (k-1)! = k!$.

Proof Details

Base Case (Prove for $n=1$.) Here we have $M=\{m_1\}$ and $W=\{w_1\}$. The only perfect matching is $\{(m_1, w_1)\}$ so there is $1$ perfect matching. $1 = 1!$ so there are $1! = n!$ perfect matchings.

Inductive Hypothesis Assume that for $n = k-1$ there are $(k-1)!$ perfect matchings.

Inductive Step (Prove that for $n = k$ there are $n! = k!$ perfect matchings.) Here we have $M = \{m_1, m_2,\dots, m_k\}$ and $W = \{w_1, w_2,\dots, w_k\}$. Consider $m_1$. There are $k$ possible choices for $m_1$. After the initial matching, regardless of choice there are $(k-1)$ men and $(k-1)$ women left. From the inductive hypothesis, we know that there are $(k-1)!$ perfect matchings when $n = (k-1)$. Therefore the total number of matchings is \[k\times (k-1)! = k\times (k-1)\times(k-2)\times(k-3)\times \cdots\times 1 = k! = n!$.

Goal in proof by induction

Use the inductive hypothesis to help you solve the larger problem at hand.

Proof by Contradiction

(Not to be confused with proof by counterexample.)

Overview

Prove $x$.

Assume $\neg x$ and then come up with a contrdiction.

Aside (proof by counterexample)

Proof by counterexample

When you are able to prove a point by giving an example that makes the statement false, e.g. Prove that blah is or is not true.

If you are proving that a statement is not true, you can often use a counterexample. (This is not always the case, but most common case of where counterexamples are used.

Exercise 3

Argue whether the following statement is true or false: There is no possible stable matching where everyone matches with his/her first choice.

Proof Idea

We will give an example with $n=3$, where all men have a unique most preferred woman and vice-versa. In this case the most preferred pairs form a stable matching.

Proof Details

Let $M = \{m_1, m_2, m_3\}$ and $W = \{w_1, w_2, w_3\}$. Now consider the following preference lists: \[ L_{m_1}: w_1 > w_2 > w_3~~~~ L_{w_1}: m_1 > m_2 > m_3\] \[ L_{m_2}: w_2 > w_3 > w_1~~~~ L_{w_2}: m_2 > m_3 > m_1\] \[ L_{m_3}: w_3 > w_1 > w_2~~~~ L_{w_3}: m_3 > m_1 > m_2\]

In this case, $\{(m_1,w_1), (m_2,w_2),(m_3,w_3)\}$ is a stable matching.

Back to proof by contradiction

Exercise 4

Assume that the following are true:

  • Every blockbuster movie has a hero.
  • Jake Sully and Neytiri are dating.
  • The highest grossing movie ever is a blockbuster.
  • A hero in a movie never dies.
  • The movie Avatar has made the most money ever.
  • The heroine always dates the hero.
  • Neytiri is the heroine of Avatar.

Prove by contradiction that Jake Sully is alive at the end of the movie Avatar. Please clearly state any assumptions that you needed to make in the proof.

Note

In the question above we have color coded the important predicates and constants in the logical statements above. We will not do this in the future and this is soemthing you will have to identify on your own.

Proof Idea

Since we are using proof by contradiction, we assume that Jake Sully is NOT alive at the end of the movie Avatar. Using that as a premise (and statements in the problem we are given to be true), we will show that one of the problem's assumptions must be false, leading to a contradiction.

Proof Details

Assume the opposite of what you are trying to prove. Assume that Jake Sully is NOT alive at the end of the movie Avatar.

Assuming that Jake Sully is dead at the end of the movie Avatar, then we must assume that Jake Sully is not the hero of Avatar since the hero is a movie never dies.

In order to prove that Avatar has a hero at all, we need to show that show that Avatar is a blockbuster movie. Since the highest grossing movie ever is a blockbuster, and the movie Avatar has made the most money ever, we can conclude that it must have a hero, but that hero can not be Jake Sully from our previous assumption.

Now we know that Neytiri is the heroine of Avatar and that the herione always dates the hero. Since Jake Sully is not the hero of Avatar, we can assume that Neytiri is not dating Jake Sully. This directly contradicts the statement from the problem’s assumptions “Jake Sully and Neytiri are dating.” This results in a contradiction and our initial assumption must be false, so we know that Jake Sully must be alive at the end of Avatar.

Further Reading