Let's jump right in and see what kinds of things we'll be doing for the rest of the quarter.
A common problem in many domains is matching. There are lots of such scenarios:
If we have $n$ of one group and $n$ of the other group, then we just have to find a way to find $n$ distinct pairs between the groups. However, there is an additional complication: people (and Pokémon) have preferences.
The scenario we want to avoid is the following: Alice gets matched with G◯◯gle but would rather go to Faceb◯◯k for the summer while Bob got matched with Faceb◯◯k but would be much happier at G◯◯gle. Now, if both G◯◯gle and Faceb◯◯k both had the same preferences as Alice and Bob, then arranging this switch is not so bad. But what happens if their preferences are in conflict? Furthermore, this scenario only deals with two pairs, but one can easily see how such a situation could unravel and cause a chain reaction of adjustments if it involved conflicting preferences among more people.
We can begin by abstracting the problem. These scenarios all have the same sorts of constraints:
For the sake of discussion, let's fix one of these scenarios. We'll let $U$ be the set of available positions and $V$ is the set of interns vying for those positions.
A matching $M$ is a set of pairs $(u,v)$ with $u \in U$ and $v \in V$ such that
We say a matching is perfect if $|M| = |U| = |V| = n$.
Some of you may remember from discrete math that this sounds oddly similar to the idea of a complete matching. In fact, perfect matchings are complete matchings, with the additional property that every vertex in both sets of the bipartition are matched (since they're both the same size).
The goal is to find a matching that will make everyone "happy". Of couse, happy is not mathematically precise. Let's think about what makes an "unhappy" match.
A pair $(u,v)$ is unstable with respect to a matching $M$ if both
In other words, an unstable pair is a pair that's not in the matching which would abandon their assigned matches for each other. Then it makes sense to try to come up with a matching or assignment that doesn't exhibit any unstable pairs.
A matching $M$ is stable if it there are no unstable pairs with respect to $M$.
That is, in a stable matching, there are no pairs $(u,v)$ that would be willing to abandon their assigned match. In that sense, the matching is stable.
The stable matching problem takes as input a set $U$ of size $n$ and a set $V$ of size $n$. Each $u \in U$ ranks elements of $V$ and each $v \in V$ ranks elements of $U$. The output is a stable matching $M$.
Here, we can view our input as a list of lists or a table. Suppose we have interns $A,B,C$ and employers $D,E,F$. Then their preferences may look something like
| $\quad$ | 1st | 2nd | 3rd | $\quad$ | $\quad$ | 1st | 2nd | 3rd |
|---|---|---|---|---|---|---|---|---|
| A | D | E | F | D | B | A | C | |
| B | E | D | F | E | A | B | C | |
| C | D | E | F | F | A | B | C |
Consider the matching $\{(A,D), (B,F),(C,E)\}$. We observe that $(B,D)$ forms an unstable pair with respect to this matching.
It isn't clear that we can always come up with a stable matching. For example, consider the following scenario. Suppose instead of internships, we're in an introductory programming class and we want to pair up all the students for a pair programming exercise. Again, every student has a ranking of everyone else in the class.
| $\quad$ | 1st | 2nd | 3rd |
|---|---|---|---|
| A | B | C | D |
| B | C | A | D |
| C | A | B | D |
| D | A | B | C |
In this example, we can never come up with a matching that is stable (try it yourself!).
This scenario differs slightly from the one we started out with. First of all, matchings are defined for graphs in general, and not just bipartite graphs. However, we can see that for general graphs, a stable matching does not need to exist. It turns out the fact that we can define our matching on two well-defined groups is important!
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).