A First Problem: Stable Matching
As an opening topic, we look at an algorithmic problem that nicely illustrates many of the themes we will be emphasizing. It is motivated by some very natural and practical concerns, and from these we formulate a clean and simple statement of a problem. The algorithm to solve the problem is very clean as well, and most of our work will be spent in proving that it is correct and giving an acceptable bound on the amount of time it takes to terminate with an answer. The problem itself—the Stable Matching Problem—has several origins.
The Problem
The Stable Matching Problem originated, in part, in 1962, when David Gale and Lloyd Shapley, two mathematical economists, asked the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? What did they mean by this?
To set up the question, let’s first think informally about the kind of situation that might arise as a group of friends, all juniors in college majoring in computer science, begin applying to companies for summer internships. The crux of the application process is the interplay between two different types of parties: companies (the employers) and students (the applicants). Each applicant has a preference ordering on companies, and each company—once the applications come in—forms a preference ordering on its applicants. Based on these preferences, companies extend offers to some of their applicants, applicants choose which of their offers to accept, and people begin heading off to their summer internships.
Gale and Shapley considered the sorts of things that could start going wrong with this process, in the absence of any mechanism to enforce the status quo. Suppose, for example, that your friend Raj has just accepted a summer job at the large telecommunications company CluNet. A few days later, the small start-up company WebExodus, which had been dragging its feet on making a few final decisions, calls up Raj and offers him a summer job as well. Now, Raj actually prefers WebExodus to CluNet—won over perhaps by the laid-back, anything-can-happen atmosphere—and so this new development may well cause him to retract his acceptance of the CluNet offer and go to WebExodus instead. Suddenly down one summer intern, CluNet offers a job to one of its wait-listed applicants, who promptly retracts his previous acceptance of an offer from the software giant Babelsoft, and the situation begins to spiral out of control.
Things look just as bad, if not worse, from the other direction. Suppose that Raj’s friend Chelsea, destined to go to Babelsoft but having just heard Raj’s story, calls up the people at WebExodus and says, “You know, I’d really rather spend the summer with you guys than at Babelsoft.” They find this very easy to believe; and furthermore, on looking at Chelsea’s application, they realize that they would have rather hired her than some other student who actually is scheduled to spend the summer at WebExodus. In this case, if WebExodus were a slightly less scrupulous company, it might well find some way to retract its offer to this other student and hire Chelsea instead.
Situations like this can rapidly generate a lot of chaos, and many people— both applicants and employers—can end up unhappy with the process as well as the outcome. What has gone wrong? One basic problem is that the process is not self-enforcing—if people are allowed to act in their self-interest, then it risks breaking down.
We might well prefer the following, more stable situation, in which selfinterest itself prevents offers from being retracted and redirected. Consider another student, who has arranged to spend the summer at CluNet but calls up WebExodus and reveals that he, too, would rather work for them. But in this case, based on the offers already accepted, they are able to reply, “No, it turns out that we prefer each of the students we’ve accepted to you, so we’re afraid there’s nothing we can do.” Or consider an employer, earnestly following up with its top applicants who went elsewhere, being told by each of them, “No, I’m happy where I am.” In such a case, all the outcomes are stable—there are no further outside deals that can be made.
So this is the question Gale and Shapley asked: Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E, and every applicant A who is not scheduled to work for E, at least one of the following two things is the case?
(i) E prefers every one of its accepted applicants to A; or
(ii) A prefers her current situation over working for employer E.
If this holds, the outcome is stable: individual self-interest will prevent any applicant/employer deal from being made behind the scenes.
Gale and Shapley proceeded to develop a striking algorithmic solution to this problem, which we will discuss presently. Before doing this, let’s note that this is not the only origin of the Stable Matching Problem. It turns out that for a decade before the work of Gale and Shapley, unbeknownst to them, the National Resident Matching Program had been using a very similar procedure, with the same underlying motivation, to match residents to hospitals. Indeed, this system, with relatively little change, is still in use today.
This is one testament to the problem’s fundamental appeal. And from the point of view of this book, it provides us with a nice first domain in which to reason about some basic combinatorial definitions and the algorithms that build on them.
Formulating the Problem To get at the essence of this concept, it helps to make the problem as clean as possible. The world of companies and applicants contains some distracting asymmetries. Each applicant is looking for a single company, but each company is looking for many applicants; moreover, there may be more (or, as is sometimes the case, fewer) applicants than there are available slots for summer jobs. Finally, each applicant does not typically apply to every company.
It is useful, at least initially, to eliminate these complications and arrive at a more “bare-bones” version of the problem: each of n applicants applies to each of n companies, and each company wants to accept a single applicant. We will see that doing this preserves the fundamental issues inherent in the problem; in particular, our solution to this simplified version will extend directly to the more general case as well.
Following Gale and Shapley, we observe that this special case can be viewed as the problem of devising a system by which each of n men and n women can end up getting married: our problem naturally has the analogue of two “genders”—the applicants and the companies—and in the case we are considering, everyone is seeking to be paired with exactly one individual of the opposite gender.
So consider a set M = {m1,..., mn} of n men, and a set W = {w1,..., wn} of n women. Let M × W denote the set of all possible ordered pairs of the form (m, w), where m ∈ M and w ∈ W. A matching S is a set of ordered pairs, each from M × W, with the property that each member of M and each member of W appears in at most one pair in S. A perfect matching S is a matching with the property that each member of M and each member of W appears in exactly one pair in S
Matchings and perfect matchings are objects that will recur frequently throughout the book; they arise naturally in modeling a wide range of algorithmic problems. In the present situation, a perfect matching corresponds simply to a way of pairing off the men with the women, in such a way that everyone ends up married to somebody, and nobody is married to more than one person—there is neither singlehood nor polygamy.
Now we can add the notion of preferences to this setting. Each man m ∈ M ranks all the women; we will say that m prefers w to w if m ranks w higher than w. We will refer to the ordered ranking of m as his preference list. We will not allow ties in the ranking. Each woman, analogously, ranks all the men.
Given a perfect matching S, what can go wrong? Guided by our initial motivation in terms of employers and applicants, we should be worried about the following situation: There are two pairs (m, w) and (m , w ) in S (as depicted in Figure 1.1) with the property that m prefers w to w, and w prefers m to m . In this case, there’s nothing to stop m and w from abandoning their current partners and heading off together; the set of marriages is not selfenforcing. We’ll say that such a pair (m, w ) is an instability with respect to S: (m, w ) does not belong to S, but each of m and w prefers the other to their partner in S.
Our goal, then, is a set of marriages with no instabilities. We’ll say that a matching S is stable if (i) it is perfect, and (ii) there is no instability with respect to S. Two questions spring immediately to mind:
Does there exist a stable matching for every set of preference lists? .
Given a set of preference lists, can we efficiently construct a stable matching if there is one?
Some Examples To illustrate these definitions, consider the following two very simple instances of the Stable Matching Problem.
First, suppose we have a set of two men, {m, m
}, and a set of two women, {w, w }. The preference lists are as follows:
m prefers w to w
m prefers w to w
w prefers m to m
w prefers m to m
If we think about this set of preference lists intuitively, it represents complete
agreement: the men agree on the order of the women, and the women agree
on the order of the men. There is a unique stable matching here, consisting
of the pairs (m, w) and (m
, w
). The other perfect matching, consisting of the
pairs (m
, w) and (m, w
), would not be a stable matching, because the pair
(m, w) would form an instability with respect to this matching. (Both m and
w would want to leave their respective partners and pair up.)