Tuesday, January 7, 2014
The stable marriage problem
Introduction to the course. First topic: the stable marriage problem.
1About 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.
2The 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.1Existence 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.2Comments on optimality¶
2.2.1Male 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.2Female 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$