The algorithm for finding stable matchings is due to Gale and Shapley in 1962. We can describe the algorithm as follows.
\begin{algorithmic}
\FUNCTION{stable-match}{preference lists for all $u \in U$ and $v \in V$}
\STATE Initialize matching $M = \emptyset$
\WHILE{there is an open position $u \in U$ that has not made an offer to every intern}
\STATE $v = $ the top intern on $u$'s list, who hasn't yet been made an offer by $u$
\IF{$v$ is unmatched}
\STATE add $(u,v)$ to $M$
\ELIF{$v$ prefers $u$ to current position $u'$}
\STATE replace $(u',v)$ with $(u,v)$ in $M$
\ELSE
\STATE $v$ rejects $u$
\ENDIF
\ENDWHILE
\RETURN{$M$}
\ENDFUNCTION
\end{algorithmic}
This, like most of the algorithms we'll see in this class, is described in pseudocode. You'll be expected to present algorithms in pseudocode as well. As you can see, the standards are quite loose as to what constitutes "code", so we'll have more specific guidance on what we're looking for later.
For now, let's to try to understand what it is this algorithm does. All of the action happens inside the while loop, which is executed as long as some position $u$ is unfilled (unmatched with an intern). So let's consider an unfilled position $u$.
For $u$, we go down the preference list for $u$ and choose the first (i.e. the highest ranked) intern $v$ that $u$ has not offered a job to. There are three possibilities.
There are a number of questions that this algorithm raises. First, how do we know this algorithm will terminate? It seems like it might be possible for interns to keep swapping indefinitely. Secondly, how do we know this will give us a correct stable matching? Again, since everyone's swapping all the time, how do we know we haven't missed someone?
We begin with the following observations about the status of each position $u$ and intern $v$:
First, we'll show that the algorithm is guaranteed to terminate.
The Gale–Shapley algorithm terminates after at most $n^2$ iterations of the while loop.
Consider the set $P(t)$, \[P(t) = \{(u,v) \mid \text{$u$ made an offer to $v$ by iteration $t$}\}.\] On each iteration, an open position $u$ gives out an offer to some intern $v$ which was not made before, in order of preference. This means that on each iteration, some position $u$ will proceed down its preference list until it runs out of interns to make offers to. This also means that on each iteration, there is a new $(u,v)$, so we have that $|P(t+1)| \gt |P(t)|$. But there are $|U||V| = n^2$ such pairs, so the algorithm must terminate after all such offers have been made.
Now, we'll work on showing that the algorithm gives us what we want: a stable perfect matching.
The Gale–Shapley algorithm produces a matching.
First, we note that a position makes an offer only if it isn't matched, which means that it can be matched to at most one intern. Similarly, an intern only ever accepts an offer for one position, and they only ever trade up.
The Gale–Shapley algorithm produces a perfect matching.
We have to argue that every position $u \in U$ is matched to an intern and that every intern $v \in V$ is matched to a position.
First, we will show that every position $u \in U$ gets matched. Suppose, for contradiction, that the Gale–Shapley algorithm produces a matching $M$ with some unmatched position $u \in U$. Since the algorithm terminated, this means we exited the While loop and therefore, $u$ had made an offer to every intern $v \in V$ and remained unmatched.
In order for $u$ to remain unmatched, it must be the case that every $v \in V$ has already been matched. Since $M$ is a matching, each $v$ must be matched to a unique $u' \in U$. Since $|V| = n$, there must be $n$ positions matched to each intern. But there are only $n$ positions in total, while $u$ is unmatched, so this is a contradiction. Therefore, every $u \in U$ is matched.
Now, to see that every intern $v \in V$ must also be matched, we observe that since $M$ is a matching and every position $u \in U$ has been matched, by counting, we must have that all $n$ interns are also matched. Therefore, Gale–Shapley produces a perfect matching.
The Gale–Shapley algorithm produces a stable matching.
Suppose for contradiction that there is an unstable pair $(u,v)$ with respect to the matching $M$ produced by Gale–Shapley. In other words, there exist two pairs $(u,v')$ and $(u',v)$ such that $u$ prefers $v$ to $v'$ and $v$ prefers $u$ to $u'$.
Since $(u,v)$ is not in $M$, there are two scenarios that can have occurred: either $u$ did not make an offer to $v$ at all or $u$ made an offer to $v$ which was then later swapped.
If $u$ did not make an offer to $v$, this means that $u$ prefers $v'$ to $v$, since $u$ makes offers in decreasing order of preference. Therefore, $(u,v)$ is not unstable.
If $u$ did make an offer to $v$, this means that at some point $v$ either rejected the offer immediately or traded up later. That means that $v$ prefers $u'$ to $u$ and so $(u,v)$ is not unstable.
Thus, we have shown in both cases that $(u,v)$ is not actually unstable.
Putting all of the propositions we proved together, we have the following algorithm.
The Gale–Shapley algorithm will terminate and produce a stable matching for any instance.
Gale and Shapley were economists and game theorists. For this algorithm, they won the Nobel Prize in Economics. This happens to be the closest thing we have to a Nobel in computer science (because there's no Nobel Prize for Mathematics since Alfred Nobel didn't think mathematics was that important).