Stable Matching

Problem

Input: A set of $n$ hospitals $H$ and a set of $n$ students $S$

• Each hospital $h\in H$ ranks students
• Each student $s\in S$ ranks hospitals

Definition (Matching)

A matching $M$ is a set of ordered pairs $h-s$ with $h\in H$ and $s\in S$

• Each hospital $h\in H$ appears in at most one pair of $M$
• Each student $s\in S$ appears in at most one pair of $M$

A matching is perfect if $|M|=|H|=|S|=n$

A matching is stable if it is a perfect matching with no unstable pairs

Definition (Unstable Pair)

Hospital $h$ and student $s$ form an unstable pair $h-s$ if both

• $h$ prefers $s$ to one of its admitted students
• $s$ prefers $h$ to assigned hospital

Note: Unstable pairs are the pair that the hospital and student would prefer. That means when a matching has unstable pairs, the actual unstable pairs are just associated with the matching, not actually in the matching.

Goal: Find a stable matching (if one exists)

Gale-Shapley Algorithm

One algorithm to find a stable matching

Algorithm

Hospitals propose to their top ranked student. Students accept if the proposing hospital is ranked higher than their existing accepted proposal and rejects their previously accepted proposal. If student rejects a proposal, hospital moves down their ranking.

M = empty matching
while some hopspital h is unmatched and hasn't proposed to every student
	s = first student on h's list to whom h has not yet proposed
	if s is unmatched
		add h-s matchig to M
	else if s prefers h to current partner h'
		replace h'-s with h-s in matching M
	else
		s rejects h
return stable matching M

Observations

1. Hospitals propose to students in decreasing order of preference
2. Once a student is matched, the student never becomes unmatched, only trades up

Properties

Claim

Gale-Shapley terminates after at most $n^2$ iterations of while loop

Proof: Each time through the while loop, a hospital proposes to a new student. There are $n$ students and $n$ hospitals, so $n^2$ possible proposals. $\square$

Claim

Gale-Shapley always outputs a matching

Proof: Hospitals propose only if unmatched. So every hospital is matched to at most 1 student.

Students keep only the best hospital. So every student is matched to a most 1 hospital. $\square$

Claim

In Gale-Shapley matching, all hospitals are matched.

Proof: Assume by way of contradiction, some hospital $h\in H$ is unmatched upon termination. Then some student, say $s\in S$ is unmatched upon termination. By observation 2, $s$ was never proposed to. But, $h$ proposes to every student, since $h$ ends up unmatched ↯ $\square$

Claim

In Gale-Shapley matching, all students are matched.

Proof: By previous claim, all $n$ hospitals get matched. Thus, by counting, all $n$ students get matched. $\square$

Claim

In Gale-Shapley matching $M^{\ast }$, there are no unstable pairs

Proof: Consider any pair $h-s\notin M^{\ast }$ Case 1: $h$ never proposed to $s$ $h$ prefers is current partner to $s$ Case 2: $h$ proposed to $s$ $s$ rejected $h$ (either right away or later) $s$ prefers current partner to $h$ $h-s$ is not an unstable pair of $M^{\ast }$ $\square$

Theorem (Gale-Shapley 1962)

The Gale-Shapely algorithm guarantees to find a stable matching for any problem instance

Proof: Follows from the above claims $\square$

Favoring the Proposer

Definition (Valid Partner)

Student $s$ is a valid partner for hospital $h$ if there exists any stable matching in which $h$ and $s$ are matched

Definition (Hospital-optimal Assignment)

Matching where each hospital receives its best valid partner

Definition (Student-pessimal Assignment)

Matching where each student receives its worst valid partner

Claim

Gale-Shapley matching $M^{\ast }$ is hospital-optimal

Intuition: If a student swaps, then the matching before that swap would have been unstable. Hospitals make proposals based on their preference, so each pair ends up being the best valid partner for the hospital.

Proof:

• Assume by way of contradiction that a hospital is matched with a student other than the best valid partner.
• Hospitals propose in decreasing order of preference, so some hospital is rejected by a valid partner during Gale-Shapley.
• Let $h$ be the first such hospital that is rejected by a valid partner, and let $s$ be the first valid partner that rejects $h$.
• Let $M$ be a stable matching where $h$ and $s$ are matched.
• When $s$ rejects $h$ in Gale-Shapely, $s$ forms (or re-affirms) commitment to a hospital, say $h^{\prime }$. Hence, $s$ prefers $h^{\prime }$ to $h$ because students only trade up.
• Let $s^{\prime }$ be partner of $h^{\prime }$ in $M$
• Because this is the first rejection by a valid partner, $h^{\prime }$ had not been rejected by any valid partner (including $s^{\prime }$) at the point when $h$ is rejected by $s$.
• Thus, $h^{\prime }$ had not yet proposed to $s^{\prime }$ when $h^{\prime }$ proposed to $s$. So $h^{\prime }$ prefers $s$ to $s^{\prime }$
• Thus $h^{\prime }-s$ is a unstable pair in $M$, a contradiction.
• Hence, every hospital is matched with its best valid partner. $\square$

Corollary

Any hospital-optimal assignment is a stable matching

Theorem

Gale-Shapley finds student-pessimal stable matching $M^{\ast }$

Proof: Suppose by way of contradiction that $h-s$ matched in $M^{\ast }$ but $h$ is not the worst valid partner for $s$.

There exists stable matching $M$ in which $s$ is paired with a hospital, say $h^{\prime }$, whom $s$ prefers less than $h$, so $s$ prefers $h$ to $h^{\prime }$.

Let $s^{\prime }$ be the partner of $h$ in $M$.

By hospital-optimality, $s$ is the best valid partner for $h$. So $h$ prefers $s$ to $s^{\prime }$. Thus, $h-s$ is an unstable pair in $M$, a contradiction. $\square$