Recitation 3

Recitation notes for the week of Feb 5, 2025.

Homework reminders

Here are some gentle reminders about HW policies:

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

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

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 2

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.

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.

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 of 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)

  1. Find all perfect matchings.
  2. 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.

HW 1 Question 1

Problem Statement

  • There are two teams, $Y$ and $Z$
  • Each team has $n$ players
  • $Y$ and $Z$ generate schedules $S$ and $T$ respectively
  • $S[i]$ and $T[i]$ denote the player from $Y$ and $Z$, respectively, that are assigned to match $i$
  • For a given match, the player with the better ranking always wins
  • Teams are trying to win as many matches as possible

Our goal is to determine, given a set of player rankings, whether there exists a pair of schedules that are stable. We define a stable pair of schedules to be one in which neither team can change their schedule unilaterally and win more matches.

As an example, let's suppose that team $Y$ has players two players, $y_1$ and $y_2$ with rankings $2$ and $6$ respectively, and team $Z$ has players $z_1$ and $z_2$ with rankings $8$ and $9$, repspectively.

Here is an example pair of schedules: $S=[y_1, y_2]$ and $T=[z_1, z_2]$. A visual is below, with the player and ranking in each cell, and the winning player highlighted.

In this case, we see $y_1$ and $z_1$ are matched against each other, and $y_2$ and $z_2$ are matched against each other. This particular match-up is a stable match-up, because neither team can change their schedule to win more match-ups. For example, if we changed the order of $Z$’s players, we would get:

And in this schedule, $Y$ still wins both matchups.

What if player $z_1$ has a ranking of $5$ instead of $8$? If we keep the same player schedule, then the matchups become:

Right now, $Y$ still wins both match-ups, but what if $Z$ were to swap the players its schedule:

Now $Y$ only wins one match, and $Z$ also wins one. This means the original pair of schedules was not stable, since $Z$ managed to win more matches by changing their schedule. Furthermore, $Y$ could then react back and change their schedule to also be flipped, and win both match-ups again.

Part (a)

Problem Statement

Let’s look at a pair of schedules such that the worst ranked player in team $Y$ still has a better ranking than the best ranked player in team $Z$. What can we say about the stability of pairs of schedules? Can we say that given the input as described above, all pairs of schedules are stable? What would we need in order to say this?

Proof Idea

Well, we know that the worst ranked $Y$ player is still better than the best ranked $Z$ player, so we could say that in any match in this scenario, $Y$ would come out winning.

Lemma

If the worst ranked $Y$ player is better than the best ranked $Z$ player, then in all possible schedules, $Y$ wins all matches.

If this lemma is true (proving it is your job), then we know that no matter the schedule $Z$ makes for its players, $Y$ will win all matches, making the schedules stable.

Proof Details

If the lemma is true, then we know that in this problem, $Y$ will always win all matches. If $Y$ always wins all matches, then no change could be made to the schedule of team $Z$ to make them win more matches (in fact, they will always have zero wins). This would mean that all schedules are stable, since $Y$ cannot win more than the number of match-ups, and $Z$ cannot alter their schedule in any meaningful way.

Exercise

Finish this proof by proving the lemma above to be true.

Part (b)

It is possible that on some inputs of players and rankings for each team, there is no stable pair of schedules. What would this require? Remember, an unstable pair of schedules is one where one team can change their schedule unilaterally to create a different set of matches where that team then wins more of the matches than before. This only applies to one pair of schedules. We need to show that ALL pairs of schedules are unstable. If all pairs of schedules are unstable, that means that after some team changes their schedule from the original schedule, the resulting pair of schedules is still unstable. You need to describe an input that follows this behavior across all schedules.

For example, let’s say that $n=3$, so each team has $3$ players. That means for one team, there are $6$ ($n!$) possible schedules for their own players, and for the pairs of schedules for both teams there are $36$ possibilities ($n!^2$). We could show how each and every one of these schedules is unstable, but as n grows, this becomes a very difficult task. Instead, we could find a pattern in the way that these matches are unstable, and in the way that a new unstable match is created when one team changes their schedule. Once we know this pattern, we can give an example set of rankings (for one value of $n$) such that all of the pairs of schedules are unstable.

HW 1 Question 2

Previously we have looked at specific examples when discussing inputs for algorithms. A different way to consider the input is in terms of a family of examples. The difference between a specific example and a family is that a family represents many examples all at once, usually by having some rules on how to construct new examples as the input size grows. Families are generally used to show a trend or property in the algorithm or in the family of inputs.

Part (a)

Let us consider a family of inputs for the stable matching problem that allows for $\Omega(n)$ stable matchings. This means that for any input size, the list of men, women, and their preference lists create at least $cn$ different stable matches ($c$ is a constant, but gets simplified when talking about asymptotic complexity).

First, let’s look at two ways to represent a family of inputs:

Explicit/Algorithmic

This way involves just explaining what the family is in plain words or algorithmically, like pseudo-code.

For our problem, our family has two groups, $M$ (men) and $W$ (women), each containing $m_i$ and $w_i$ such that $0 < i ≤ n$ and each m and w have preference lists as follows:

Men

  • $m_1: w_1 > w_2 > ... > w_{n-1} > w_n$
  • $m_2: w_2 > w_3 > ... > w_{n} > w_1$
  • $...$
  • $m_n: w_n > w_1 > ... > w_{n-2} > w_{n-1}$

Women

  • $w_1: m_2 > m_3 > ... > m_n > m_1$
  • $w_2: m_3 > m_4 > ... > m_1 > m_2$
  • $...$
  • $w_n: m_1 > m_2 > ... > m_{n-1} > m_n$

Functional

Same as before, we have $M$, $W$, $m_i$, $w_i$, and $i$ such that $0<i≤n$.

For men, we show:

$L_{m_1} = w_1 > w_2 > ... > w_n$

$L_{m_{i+1}} = L_{m_i}$ shifted one left (with wraparound). That is, the same as $L_{m_i}$, but with the first woman moved to the end.

For women we show:

$L_{w_1} = m_2 > m_3 > ... > m_n > m_1$

$L_{w_{i+1}} = L_{w_i}$ shifted one left (with wraparound).

We could also show an inductive definition of the family, but this does not work very well for this particular case.

As an exercise:

Compare the two representations, and verify that they convey the same information.

Now with this family, we want to show there are at least $n$ stable matchings. So how can we prove that this family satisfies this? Well this is where working with a family of inputs helps, as we can find some property of this input that is repeatable and helps prove there are at least $n$ stable matches. In this case, we will help prove this be outlining a lemma (which you will then prove for your proof of correctness).

Proof Idea

Let’s say that for our stable matching, let’s consider an input of size $4$ ($n=4$). This gives us preference lists as follows:

In these charts, the person whose preference list we are referencing is noted on the left side, followed by their preference list in order of most preferred to least preferred.

One stable matching we can consider is if all of the men get their most preferred choice. Looking at the preference lists as a grid, we notice that matching each man with their most preferred choice means all of their matches are in column $1$, and the corresponding matches for the women are in column $4$.

This is the other way around if the women get their most preferred choices $-$ their choices are in their column $1$, and the men’s are in column $4$.

Now imagine the men all get their second most preferred woman. That is, $m_1$ to $w_2$, $m_2$ to $w_3$, etc. This puts all of their matches in column $2$ in their lists, and in the women’s list, the men are all in column $3$.

We can expand this further if we would like, but we are already noticing a trend. That is, for a given stable matching, the matches represent some column i in one list, and column $n-i+1$ in the other. We can present this as a lemma:

Lemma

If you match one group with their preferences in a specific column $i$, then the other group is matched with their preferences in column $n-i+1$.

Using this lemma, we can quickly create $4$ different potential stable matchings:

  • $(m_1,w_1),(m_2,w_2),(m_3,w_3),(m_4,w_4)$
  • $(m_1,w_2),(m_2,w_3),(m_3,w_4),(m_4,w_1)$
  • $(m_1,w_3),(m_2,w_4),(m_3,w_1),(m_4,w_2)$
  • $(m_1,w_4),(m_2,w_1),(m_3,w_2),(m_4,w_3)$

These are all stable, since no man prefers a woman who has that man higher on her preference list than her current match, and vice versa for the women.

If this lemma is true (you must prove it yourself), then we can say that there are at least $n$ stable matchings, which is $\Omega(n)$ stable matchings.

Proof Details

If the given lemma is true, then we can generate n matchings by going through the preference lists column by column. These matchings are stable since no man prefers a woman who has that man higher on her preference list than her current match, and vice versa for the women. For example, if we match each man to their second most preferred woman, then we get:

  • $(m_1,w_2),(m_2,w_3),(m_3,w_4),(m_4,w_1)$

For $m_1$, his only more preferred woman is $w_1$. She is matched to $m_4$, and would prefer either $m_2$ or $m_3$ to this match, but NOT $m_1$, as he is ranked lower than $m_4$, her current match. This holds for the other $3$ men as well, as well as for each man should we match them to a different column.

We can then say that there are n stable matchings, which is $\Omega(n)$ stable matchings.

Your job will be to:

Finish this proof by proving the above lemma.

Note

Note that this lemma is for this one given family of inputs, and (probably) will not work for others.

Part (b)

Now we need to find a family that produces $\exp(n)$ matches (exponentially many). Here, the family we used in part (A) may provide some inspiration. It also might help you to think of the way the family looks visually -- draw a picture and see if there’s something similar to note like we had with the columns lemma for part (A).

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.

Further Reading