Introduction

These notes are on the COP4533 Algorithm Abstraction & Design with Professor Ungor at the University of Florida. What I have learned from this course has been compounded into these notes.

Stable Matching Problem

• Given a set of preferences among hospitals and med-school students, we have to design a self-reinforcing admissions process.

• A matching $M$ is a set of ordered pairs, $h-s$, where $h \in H$ and $s \in S$, such that:

  • 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$.

• For a given matching, $M$, it is perfect if $|M| = |H| = |S| = n$

• Unstable pair: Given a hospital $h$ and a student $s$, they form an unstable pair if both:

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

• Stable assignment: A group of pairs, an assignment, in which there is no unstable pairs.

• Stable matching: A perfect matching with no unstable pairs.

• Tl;dr given the a list of preferences with $n$ hospitals and $n$ students, return a stable matching.

Input

• The input to the stable matching problem is 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.

An example:

• A set of hospitals, $H$ with $n = 2$ students:

  • Ranking is in order of preference, i.e. Chicago prefers Coleton over Daniel, but Tampa prefers Daniel over Coleton

• A set of students, $S$ with $n = 2$ hospitals:

  • Ranking, just like before, is in order of preference.

Perfect Matching

What is a perfect matching for the above table example? It could be:

• $M = \{ \text{Chicago} - \text{Coleton},~ \text{Tampa} - \text{Daniel}\}$

The following is also a perfect matching, but an inverse example:

• $M = \{ \text{Tampa} - \text{Coleton},~ \text{Chicago} - \text{Daniel}\}$

Unstable Pair

• In the above example, both possible matchings are perfect and lack unstable pairs (i.e. both are stable matchings.)

  • In the first example, although Coleton preferred Tampa and Daniel preferred Chicago, it is still stable as each $h \in H$ recieved a preferred student.

  • In the second example, although Tampa preferred Daniel and Chicago preferred Coleton, it is still stable as each $s \in S$ recieved a preferred hospital.

How about an example where this is not the case?

A possible perfect matching for this would be:

• $M = \{ \text{Columbus} - \text{Ella},~\text{Tampa} - \text{Daniel},~\text{Chicago} - \text{Coleton} \}$

A possible unstable pair for $M$ would be $\text{Chicago} - \text{Ella}$, in this case a hospital $h$ (Chicago) prefers matched student $s$ (Ella), and a student $s$ (Ella) prefers matched hospital $h$ (Chicago). This means although the matching is, indeed, perfect, it is not a stable matching.

• The key point: An unstable pair $h - s$ could each improve by a joint action, which we want to avoid.

Stable Roomate Problem

Given a different set of problem, do stable matchings always exist? This question is, even with the prior example of stable matching problem, not exactly obvious.

This brings us to the stable roommate problem:

• $2n$ people; each person ransk others from $1$ to $2n - 1$.

• The goal: assign the roommate pairs such that there are no unstable pairs.

Let’s take a look at an example where a stable matching does not exist:

• $\text{Anthony}-\text{Bailey},~\text{Carl}-\text{Darryl} \rightarrow \text{Bailey}-\text{Carl}~\text{unstable}$

• $\text{Anthony}-\text{Carl},~\text{Bailey}-\text{Darryl} \rightarrow \text{Anthony}-\text{Bailey}~\text{unstable}$

• $\text{Anthony}-\text{Darryl},~\text{Bailey}-\text{Carl} \rightarrow \text{Anthony}-\text{Carl}~\text{unstable}$

• $\Rightarrow$ No perfect matching is stable.

• $\Rightarrow$ Stable matchings need not exist.

• Key point: even changing a little about a problem can cause the conditions to make it impossible to guarantee a criteria.

Gale-Shapley deferred acceptance algorithm

This is a method that guarantees to find a stable matching:

initialize $M$ as empty matching;
while some hospital $h$ is unmatched and hasn’t proposed to every student do
$\quad S \leftarrow$ first student on $h$’s list to whom $h$ has not yet proposed;
$\quad$if $s$ is unmatched then
$\qquad$Add $h-s$ to matching $M$;
$\quad$else if $s$ prefers $h$ to current partner $h'$ then
$\qquad$Replace $h'-s$ with $h-s$ in matching $M$;
$\quad$else
$\qquad s$ rejects $h$;
$\quad$end
end
return stable matching $M$;

Effectively, what this does is iterate as long as a hospital $h$ exists such that it is unmatched and hasn’t ran out of students to propose to. It will grab the first student $s$ that hasn’t been proposed to yet by $h$. This means that as this algorithm continues, it will iterate over 1st, 2nd, etc. for each $h \in H$. Next, a few conditions are checked. If $s$ is unmatched, add the match to our matching $M$. If it is matched but $s$ prefers $h$ over its current partner (i.e. the hospital $h'$ that matched with it previously) replace this old pair $h'-s$ with $h-s$ in $M$. Finally, if $s$ doesn’t prefer $h$ over $h'$ (i.e. both $s$ and $h$ prefer each other) then reject and continue. Finally, return the stable matching.

Proof of Correctness: Termination

Some observations, for one the hospitals always propose in decreasing order of preference (i.e. start with most preferred, then go down). Second, once a student is matched, the student will never become unmatched. At worst, (or best I guess), they will just trade up to a more preferred hospital.

• Claim: Algorithm terminates after at most $n^2$ iterations of while loop.
• Proof:
  • There are $n$ students and $n$ hospitals.
  • Each time through the while loop, a hospital $h$ will propose to a new student $s$.
  • Thus, there are at most n^2 possible proposals, and the loop will terminate. $\blacksquare$

Proof of Correctness: Perfect Matching

• Claim: Gale-Shapley outputs a matching $M$.

• Proof:

  • A hospital will propose only if it is unmatched $\Rightarrow$ matched to $\le 1$ student
  • A student keeps only the best hospital $\Rightarrow$ matched to $\le 1$ hospital

• Claim: With Gale-Shapley, all hospitals will be matched.

• Proof: [by contradiction]

  • There are $n$ students and $n$ hospitals.
  • Suppose that some hospital $h \in H$ is unmatched once Gale-Shapley terminates.
  • Then, subsequently, because $|H| = |S| = n$, some student $s \in S$ is also unmatched.
  • This means that $s$ was never proposed to.
  • But, $h$ proposes to every student, so $h$ is unmatched. $\Rightarrow\!\Leftarrow$

• Claim: With Gale-Shapley, all students will be matched.

• Proof: [by counting]

  • There are $n$ students and $n$ hospitals.
  • By previous claim, all $n$ hospitals will be matched.
  • $|H| = |S| = n$
  • Thus, all $n$ students get matched as well. $\blacksquare$

Proof of Correctness: Stability

• Claim: With Gale-Shapley returned matching $M$, there are no unstable pairs.
• Proof: Consider any pair $h-s$ that is not in $M$. Remember, an unstable pair has to be not in $M$ to prove that it is not a stable matching.
  • Case 1: $h$ never proposed to $s$:
    • Due to the fact that hospitals propose in a decreasing order of preference, $h$ must prefer its Gale-Shapley partner, $s'$, over $s$.
    • $\Rightarrow$ $h-s$ is not unstable.
  • Case 2: $h$ proposed to $s$:
    • $s$ must have rejected $h$, either right away or at a subsequent iteration.
    • Due to the fact students only trade up, $s$ must prefer its Gale-Shapley partner, $h'$, over $h$.
    • $\Rightarrow$ $h-s$ is not unstable.
  • With either case, any pair $h-s \notin M$ is not unstable. $\blacksquare$

Hospital Optimality

• For a given problem, there may be several stable matchings:

• Two stable matchings:

  • First possible stable matching: $\{ \text{Anthony}-\text{Atlanta},~\text{Bailey}-\text{Boston},~\text{Carl}-\text{Chicago} \}$.

  • Second possible stable matching: $\{ \text{Anthony}-\text{Boston},~\text{Bailey}-\text{Atlanta},~\text{Carl}-\text{Chicago} \}$.

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

  • Atlanta and Boston are valid partners for Anthony.

  • Atlanta and Boston are valid partners for Bailey.

  • Chicago is the only valid partner for Carl.

• The best valid partner is the most preferred valid partner, i.e. the best valid partner for Anthony is Atlanta.

• Hospital-optimal assignment: Each hospital receives the best valid partner (i.e. best valid student!)

  • Some interesting questions: is such an assignment perfect, and is it even stable?

• This leads to the claim: All executions of Gale-Shapley yield hospital-optimal assignment.

  • Subsequent corollary: Hospital-optimal assignment is a stable matching :)

  • Proof: [by contradiction]

    • Suppose a hospital is matched with a student other than its’ best valid partner.

    • Hospitals propose in a decreasing order of preference.

      • $\Rightarrow$ so, some hospital is rejected by a valid partner during the runtime of Gale-Shapley

    • Let $h$ be first such hospital, 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-Shapley, $s$ forms (or re-affirms) commitment to a hospital, say $h'$.

      • $\Rightarrow$ $s$ prefers $h'$ to $h$. Remember, students trade up.

    • Let $s'$ be partner of $h'$ in $M$.

    • $h'$ had not been rejected by any valid partner (including $s'$) at the point when $h$ is rejected by $s$. This is because this is the first rejection by a valid partner.

    • Thus, $h'$ had not yet proposed to $s'$ when $h'$ proposed to $s$.

      • $\Rightarrow$ $h'$ prefers $s$ to $s'$. This is because hospitals propose, again, in a decreasing order of preference.

    • Thus, $h'-s$ is unstable in $M$, which is a contradiction. $\blacksquare$

  • In a bit more understandable phrasing, if a stable matching $M = \{h-s, h'-s'\}$, then for it to be stable, $h'$ and $s$ must not prefer each other. Though, $s$ is the first valid partner that rejects a hospital, $h$, in our example. Since this is the first rejection by a valid partner, $h'$ had not been rejected by any valid partner (including $s'$) whenever $h'$ proposed to $s$. This must mean that $h'$ prefers $s$ to $s'$ and as a result, $h'-s$ form an unstable pair in $M$ and contradicts the fact it a stable matching.

Student Pessimality

• Does hospital-optimality come at the expense of the students? Yes!

• Student-pessimal assignment: The inverse of Hospital-optimal, this means each student receives its worst valid partner.

• Claim: Gale–Shapley finds student-pessimal stable matching $M^*$.

  • Proof: [by contradiction]

    • Suppose $h-s$ is matched in $M^*$ 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'$, whom $s$ prefers less than $h$.

      • $\Rightarrow~s$ prefers $h$ to $h'$.

    • Let $s'$ be the partner of $h$ in $M$.

    • By hospital-optimality, $s$ is the best valid partner for $h$.

      • $\Rightarrow~h$ prefers $s$ to $s'$.

    • Thus, $h-s$ is an unstable pair in $M$, a contradiction. $\blacksquare$

  • In a more understandable phrasing, let’s just assume $h-s$ is matched in $M^*$ and that $h$ is not the worst valid partner for $s$. Notice, this does not mean $h$ is the best, just not $s$’ worst. Let’s next assume that there exists a stable matching $M$ such that $M = \{ h'-s,~h-s' \}$ and $s$ prefers $h'$ less than $h$. In this case $s$ must prefer $h$ to $h'$. Note, this means that for it to be unstable, $h$ must also prefer $s$ over $s'$. By previous hospital-optimal, $s$ is the best valid partner of $h$, and that means that does mean that $h$ prefers $s$ to $s'$ and that means $h-s$ is an unstable pair in $M$.

Deceit

• Fact 1: No hospital can improve by lying about its preference list.

• Fact 2: A devious student can possibly improve by lying.

• Fact 3: There isn’t a stable-matching algorithm that exists such that truth-telling works for all agents.