Some Representative Problems
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 gender1.
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, eachfrom M × W, with the property that each member of M and each member ofW appears in at most one pair in S. A perfect matching S is a matching withthe property that each member of M and each member of W appears in exactlyone 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 andw would want to leave their respective partners and pair up.).
Next, here’s an example where things are a bit more intricate. Suppose
the preferences are
m prefers w to w
.
m prefers w to w.
w prefers m to m.
w prefers m to m
What’s going on in this case? The two men’s preferences mesh perfectly with each other (they rank different women first), and the two women’s preferences likewise mesh perfectly with each other. But the men’s preferences clash completely with the women’s preferences.
In this second example, there are two different stable matchings. Thematching consisting of the pairs (m, w) and (m, w) is stable, because bothmen are as happy as possible, so neither would leave their matched partner. But the matching consisting of the pairs (m, w) and (m, w) is also stable, forthe complementary reason that both women are as happy as possible. This is an important point to remember as we go forward—it’s possible for an instance to have more than one stable matching.
Designing the Algorithm
We now show that there exists a stable matching for every set of preference lists among the men and women. Moreover, our means of showing this will also answer the second question that we asked above: we will give an efficient algorithm that takes the preference lists and constructs a stable matching.
Let us consider some of the basic ideas that motivate the algorithm.. Initially, everyone is unmarried. Suppose an unmarried man m chooses the woman w who ranks highest on his preference list and proposes to her.Can we declare immediately that(m, w) will be one of the pairs in our final stable matching? Not necessarily: at some point in the future, a man dangerous for w to reject m right away; she may never receive a proposal from someone she ranks as highly as m. So a natural idea would be to have the pair (m, w) enter an intermediate state—engagement.m whom w prefers may propose to her. On the other hand, it would be
.dangerous for w to reject m right away; she may never receive a proposal from someone she ranks as highly as m. So a natural idea would be to have the pair (m, w) enter an intermediate state—engagement.
. Suppose we are now at a state in which some men and women are free— not engaged—and some are engaged. The next step could look like this. An arbitrary free man m chooses the highest-ranked woman w to whom he has not yet proposed, and he proposes to her. If w is also free, then m and w become engaged. Otherwise, w is already engaged to some other man m . In this case, she determines which of m or m ranks higher on her preference list; this man becomes engaged to w and the other becomes free.
. Finally, the algorithm will terminate when no one is free; at this moment, all engagements are declared final, and the resulting perfect matching is returned.
Here is a concrete description of the Gale-Shapley algorithm, with Figure 1.2 depicting a state of the algorithm.
Initially all m ∈ M and w ∈ W are free
While there is a man m who is free and hasn’t proposed to
every woman
Choose such a man m
Let w be the highest-ranked woman in m’s preference list
to whom m has not yet proposed
If w is free then
(m, w) become engaged
Else w is currently engaged to m
If w prefers m to m then
m remains free
Else w prefers m to m
(m, w) become engaged
m becomes free
Endif
Endif
Endwhile
Return the set S of engaged pairs
An intriguing thing is that, although the G-S algorithm is quite simple to state, it is not immediately obvious that it returns a stable matching, or even a perfect matching. We proceed to prove this now, through a sequence of intermediate facts.