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 medschool students, we have to design a selfreinforcing admissions process.

A matching $M$ is a set of ordered pairs, $hs$, 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
Hospitals  1st  2nd 

Chicago  Coleton  Daniel 
Tampa  Daniel  Coleton 

A set of students, $S$ with $n = 2$ hospitals:
 Ranking, just like before, is in order of preference.
Students  1st  2nd 

Coleton  Tampa  Chicago 
Daniel  Chicago  Tampa 
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?
Hospitals  1st  2nd  3rd 

Chicago  Ella  Daniel  Coleton 
Tampa  Daniel  Coleton  Ella 
Columbus  Daniel  Ella  Coleton 
Students  1st  2nd  3rd 

Coleton  Tampa  Chicago  Columbus 
Daniel  Chicago  Tampa  Columbus 
Ella  Chicago  Columbus  Tampa 
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:
People  1st  2nd  3rd 

Anthony  Bailey  Carl  Darryl 
Bailey  Carl  Anthony  Darryl 
Carl  Anthony  Bailey  Darryl 
Darryl  Anthony  Bailey  Carl 

$\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.
GaleShapley 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 $hs$ to matching $M$;
$\quad$else if $s$ prefers $h$ to current partner $h'$ then
$\qquad$Replace $h's$ with $hs$ 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 $hs$ 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: GaleShapley 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 GaleShapley, 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 GaleShapley 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 GaleShapley, 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 GaleShapley returned matching $M$, there are no unstable pairs.
 Proof: Consider any pair $hs$ 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 GaleShapley partner, $s'$, over $s$.
 $\Rightarrow$ $hs$ 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 GaleShapley partner, $h'$, over $h$.
 $\Rightarrow$ $hs$ is not unstable.
 With either case, any pair $hs \notin M$ is not unstable. $\blacksquare$
 Case 1: $h$ never proposed to $s$:
Hospital Optimality
 For a given problem, there may be several stable matchings:
People  1st  2nd  3rd 

Anthony  Atlanta  Boston  Chicago 
Bailey  Boston  Atlanta  Chicago 
Carl  Atlanta  Boston  Chicago 
Hospitals  1st  2nd  3rd 

Atlanta  Baily  Anthony  Carl 
Boston  Anthony  Baily  Carl 
Chicago  Anthony  Baily  Carl 

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.

Hospitaloptimal 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 GaleShapley yield hospitaloptimal assignment.

Subsequent corollary: Hospitaloptimal 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 GaleShapley

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 GaleShapley, $s$ forms (or reaffirms) 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 = \{hs, 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 hospitaloptimality come at the expense of the students? Yes!

Studentpessimal assignment: The inverse of Hospitaloptimal, this means each student receives its worst valid partner.

Claim: Gale–Shapley finds studentpessimal stable matching $M^*$.

Proof: [by contradiction]

Suppose $hs$ 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 hospitaloptimality, $s$ is the best valid partner for $h$.
 $\Rightarrow~h$ prefers $s$ to $s'$.

Thus, $hs$ is an unstable pair in $M$, a contradiction. $\blacksquare$


In a more understandable phrasing, let’s just assume $hs$ 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,~hs' \}$ 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 hospitaloptimal, $s$ is the best valid partner of $h$, and that means that does mean that $h$ prefers $s$ to $s'$ and that means $hs$ 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 stablematching algorithm that exists such that truthtelling works for all agents.