**Maintainer:**admin

Introduction to the course. First topic: the stable marriage problem.

*1*About the course¶

Office hours are on Fridays, from 13:00-14:30, in Burnside 1118.

Grading scheme: 20% assignments, 20% midterm, 60% final OR 20% assignments, 80% final. there will be six assignments; the best 5 marks will be taken. No late assignments will be accepted.

There is no required textbook. There will occasionally be readings, available through the course webpage.

*2*The stable marriage problem¶

Suppose there are $n$ men and $n$ women and that each person has an ordered list of marriage partner preferences (containing all the members of the opposite sex, and only those). A set of marriages, or **matching**, $M$, is stable if there does not exist an unmarried pair $(m_i, f_j)$ such that $m_i$ prefers $f_j$ to his own partner and $f_j$ prefers $m_i$ to her own partner.

This problem has many applications, including:

- Economics (in fact, the original application of the problem was for non-traditional markets, e.g., employment markets)
- Hospital/resident matchings (though this requires tweaking the problem formulation slightly, as hospitals can have more than one open position)
- Biology (comparing the structures of two proteins)
- Kidney exchange

*2.1*Existence proof¶

Does a stable matching always exist for any instance of this problem? The answer is yes, and we can prove this via construction proof, using the Gale-Shapley algorithm. The concept is simple: each man proposes to the first woman on his list. Each woman accepts a proposal if 1) she is unmarried or 2) the proposer is higher up in her list than her current partner.

To prove that this results in a stable matching, note the following:

- Women's partners only improve (according to each woman's list of preferences) as the algorithm runs. Men's partners only get worse.
- Men cannot break off engagements. Women will only break off engagements if this results in a better partner.

We will now prove that this algorithm results in a stable matching by contradiction. Suppose there exist $m_1, f_1, m_2, f_2$ such that $f_1$ and $m_1$ are paired together and $f_2$ and $m_2$ are paired together, but $f_1$ prefers $m_2$ and $m_2$ prefers $f_1$ (i.e., the matching is not stable). Well, $m_2$ must have proposed to $f_1$ before he proposed to $f_2$, since $f_1$ is higher up on his list. Suppose $f_1$ accepted his proposal. Then, since she prefers $m_2$ to $m_1$, she would not have left $m_2$ for $m_1$. So $f_1$ must not have accepted his proposal. But then $f_1$ must have been paired up with a man whom she preferred to $m_2$. And yet, if that were the case, she would not have left that man for $m_1$. Contradiction. So this method will always output a stable matching. $\blacksquare$

*2.2*Comments on optimality¶

*2.2.1*Male optimality¶

Let $\mathcal S = \{M_1, \ldots, M_k\}$ be the set of all stable matchings. We say that $x$ is a **valid partner** for $y$ if there exists a $x$-$y$ pair in at least one of the matchings in $S$. For each male $m$, let $f^+(m)$ be his most preferred valid partner, and for each female $f$, let $m^-(f)$ be her least preferred valid partner. A method is **male-optimal** if each male $m$ is paired up with $f^+(m)$. A method is **female-pessimal** if each female $f$ is paired up with $m^-(f)$.

We posit that the Gale-Shapley algorithm shown above is indeed male-optimal. Furthermore, *it does not matter in which order you allow men to propose*. The algorithm will always converge to the same male-optimal, female-pessimal output. We will prove this now, using a lemma.

Lemma: No woman ever rejects or leaves a valid partner.

Proof by contradiction: Consider the first time that any woman rejects/leaves a valid partner. We'll refer to the woman as $f$, the man as $m$, and this time as time $t$. At this time, $f$ must have rejected/left $m$ so that she could be with $m'$ instead, who is some other male, higher up in her preference list. So $m' > m$ for $f$.

Now, since $m$ is a valid partner for $f$, there must exist some stable matching, $S$, in which $f$ and $m$ are paired. In this matching, $m'$ must be paired with some other woman, whom we'll call $f'$.

Next, let's return to time $t$ in the execution of Gale-Shapley. Recall that this is the *first* time any woman rejects/leaves a valid partner. What does this reveal about the preferences of $m'$? Well, since $m'$ is going down his preference list, and has never been rejected or left by any valid partner, $f$ must be his best valid partner. Specifically, $m$ must prefer $f$ to $f'$.

What does this tell us about $S$? Well, in $S$, we have $m$ and $f$ paired, and $m'$ and $f'$ paired. However, as we deduced above, $m'$ prefers $f$ to his current partner; furthermore, $f$ prefers $m'$ to *her* current partner. But then this matching is not stable! This is a contradiction. So it must be that no woman ever rejects or leaves a valid partner. $\blacksquare$

You can find additional notes here.

A corollary to the above is the fact that each man $m$ is matched with $f^+(m)$, i.e., his most optimal valid partner. If there were someone else, higher in his preference list, who were also a valid partner for him, then they would just be together, since she wouldn't have rejected a valid partner. Thus Gale-Shapley is male-optimal.

*2.2.2*Female pessimality¶

Next, we prove that the output is female-pessimal, via proof by contradiction. Consider some arbitrary woman $f$. Suppose that her worst valid partner is $m'$, and that she is *not* paired up with him by the end of the algorithm's run - instead, she is paired up with $m$. By the corollary above, $m$ must be paired with his most optimal valid partner. So $m$ must prefer $f$ to any other valid partners he may have. Furthermore, since $m'$ is the worst valid partner for $f$, then $f$ must prefer all her other valid partners to $m'$. Specifically, $f$ must prefer $m$ to $m'$.

Now, since $m'$ is a valid partner for $f$, there must be some stable matching, $S$, in which $m'$ and $f$ are paired up. In this matching, $m$ must be paired up with some other woman, whom we'll call $f''$. Recall that $m$ must prefer $f$ to any other valid partner he may have, and thus must prefer $f$ to $f''$. Recall also that $f$ prefers $m$ to $m'$. But then we have an unstable matching, for each of $f$ and $m$ prefers the other to his or her current partner. This is a contradiction. So there is no woman who is not paired up with her worst valid partner, and thus the output of Gale-Shapley is indeed female-pessimal. $\blacksquare$