CS W1007 Introduction to Computer Science

The Stable Marriage Problem

by Harry Mairson

orginally appeared in "The Brandeis Review" Vol. 12, No. 1 (Summer 1992)

Universities have been filled in recent years with heated debate over what undergraduates ought to be taught, but no one has ever suggested that it would be politically correct, or even appropriate, to lecture about marriage in a computer science class. Even so, it's not such a crazy idea. The search for an ideal marriage turns out to be a very appropriate and motiviating setting for discussing many computational issues that are at the intellectual heart of computer science, with interesting connections to the commercial world of computers, and even to the politics of health care.

We all know about computers, because they are everywhere. The world may not be permeated with political correctness, but it is filled with personal computers. Everyone knows about word processors, spelling checkers, spreadsheets, laser printers -- even those who do not consider themselves ``computer literate'' (whatever that means) are aware that this avalanche of consumer electronics has changed the way we conduct daily life. The speed with which this change has occurred is staggering: the state-of-the-art prototypes I used in graduate school have become consumer items.

Notice, though, that all of these electronic ``essentials'' are meant to relieve some kind of daily tedium: they don't help us do or think anything new, except in freeing us from some laborious activity. We could in principle type correctly and not misspell words, and balance checkbooks, but why not have computers manage these mundane tasks for us? Even though we may not know anything about hardware, integrated circuits, or microcode, we all know in principle how to do these things ourselves, and if we imagine the computer as some sort of homunculus, a miniature ``man in the machine,'' we can easily fantasize how such a myriad of detail is managed by a computer. For example, a computer balances a checkbook the same way that we do, only it doesn't make mistakes when it's adding and subtracting.

But this mundane activity, even if wrapped up in a chip the size of your thumbnail, is not worth inclusion in a university curriculum, as a counterpart to Thackeray, Thucydides, or thermodynamics. What is intellectually important about the computer is the idea of a computer, the variety of computational processes that inhabit it, and how these can make us think in new ways that we might have never before considered. Solving the problem of stable marriage is an example of such new thinking.

Here is the problem of stable marriage: Imagine you are a matchmaker, with one hundred female clients, and one hundred male clients. Each of the women has given you a complete list of the hundred men, ordered by her preference: her first choice, second choice, and so on. Each of the men has given you a list of the women, ranked similarly. It is your job to arrange one hundred happy marriages.

It should be immediately apparent that everyone is not guaranteed to get their first choice: if a particular man is the first choice of more than one woman, only one can be matched with him, and the other women will have to make do with less. Rather than guarantee the purest of happiness to everyone --- a promise that almost surely would subject you to eventual litigation --- your challenge is to make the marriages stable. By this, we mean that once the matchmaker has arranged the marriages, there should be no man who says to another woman, ``You know, I love you more than the woman I was matched with -- let's run away together!'' where the woman agrees, because she loves the man more than her husband. In the spirit of equality, no woman should make such a successful proposal to a man: should she so propose, we want the man to respond, ``Madam, I am flattered by your attention, but I am married to someone I love more than you, so I am not interested.'' Is it always possible for a matchmaker to arrange such a group of marriages, regardless of the preference lists of the men and women? If so, how? Were it not for computers, no one might have thought of the solution we will describe.

While finding and keeping a mate is a good deal more complicated then the mathematically simple problem stated, methods for achieving stable marriage have real uses. Perhaps the most well known is ``The Match,'' spoken of with fear and reverance by medical students everywhere in the United States. When a student finishes medical school and wants to specialize in, say, cardiology, she interviews for cardiology residency programs at hospitals across the country. After all the interviews, she makes a list of the programs she visited, in order of preference. Each of the medical programs, after having interviewed many candidates for the job, makes a similar preference list of students. Everyone sends their list to be processed by a big computer, which matches students and jobs. Once again, no medical program or student is guaranteed their first choice: the matching is done to achieve stability, so that no student and hospital can successfully conspire to outwit the national medical establishment. Once we understand how to compute a stable marriage, we will return to the politics of residency selection, because there is a very interesting story to be told: an unusual controversy about resident assignments that actually spilled over into the pages of the New England Journal of Medicine.

A method for computing a particular value --- for example, a stable marriage --- is called an algorithm. The word comes from the name of a Persian textbook author, Abu Ja`far Mohammed ibn Musa al-Khowarizmi (ca. 825), who wrote Kitab al jabr w'al muqabala (``Rules of Restoration and Reduction''). Another familiar word, algebra, derives from the title of his book. The stable marriage algorithm we describe, due to D. Gale and H. S. Shapely, originally appeared in the American Mathematical Monthly in 1962 under the title ``College Admissions and the Stability of Marriage.'' Rather than explain the algorithm in Arabic, or even worse, a computer language, let's do so in English.

The matchmaker arranges marriages in rounds, where in each round, he instructs certain men to propose marriage. In the initial round, he tells all the men to, quite sensibly, go out and propose marriage to their first-choice women. Each man then proposes to the woman he loves most.

Each of the women then receives either no proposal (if she was not the first choice of any man), one proposal (if she was the first choice of exactly one man), or more than one proposal (if many men find her to be their first choice). The matchmaker instructs the women to respond to the proposals according to the following rules. If no one proposed to you, don't worry, says the matchmaker, I promise someone will eventually. If exactly one man proposed to you, accept his proposal of marriage: the man and woman are then considered to be engaged. If more than one man proposed, respond affirmatively to the one you love most, and become engaged to him -- and reject the proposals of the rest. Surely nothing could be more reasonable. This concludes what we'll call the first round.

After one round, certain contented men are engaged, and the other discontented men are unengaged. In round two, the matchmaker says to the unengaged men: Do not despair! Go out and propose again, to your second choice. While the engaged men do nothing, the unengaged men send out another round of proposals. This time, the matchmaker says to the women: use the same rules as before, with one important change--- if you are currently engaged, and receive proposals of marriage from men that you love more than your fiance, you may reject your current intended, and reengage yourself to the new suitor that you love most. Thus a man who is happily engaged at the end of the first round may find himself suddenly unengaged at the end of the second round.

After two rounds, once again the men are divided into the engaged and unengaged. In the next round, the matchmaker tells each unengaged man to propose to the woman he loves most, among those women to whom he has not yet proposed. Again, the matchmaker tells each woman that she can change her mate, if she instead prefers one of the new proposers. Each time a man proposes, it is with greater desperation, since he begins by proposing to his true love, then his second choice, third choice, and so on. Each time a woman changes her fiance, she becomes happier, because her new intended is someone she loves more! This continues in round after round, until finally there is no one left to propose, or be proposed to.

But is this indeed the case? Does this succession of rounds ever come to an end? And is everyone engaged at the end of this romantic variation on ``musical chairs''? And are the arranged marriages indeed stable? It is not hard to prove mathematically that the story does indeed have the happy ending we suggest.

First: does the process ever end? Of course. If there are one hundred men and one hundred women, each man can only make a hundred proposals. During each round, some man proposes, reducing the finite ``supply'' of proposals by at least one. If the rounds continue long enough, then the supply of proposals will descend to zero, and the game has to come to an end, because there is no one left to propose.

At the end, is everyone engaged? Notice that at the end of each round, the number of engaged men is equal to the number of engaged women. (Computer scientists, like doctors, have a name for everything, and call this kind of assertion an invariant.) Notice also that once a woman becomes engaged, she is always engaged, though not necessarily to the same man. So suppose that all the rounds take place, and yet there is some man --- let's call him Bob --- and some woman --- named Carol --- who are both unengaged. Is this possible? No. If Carol is unengaged, no one ever proposed marriage to her. All the other men may not have proposed to Carol if each of them found a woman they loved more than Carol, but the same cannot be said of Bob, who went through his whole list --- which has to include Carol somewhere --- and supposedly came up empty-handed. Clearly he had to propose to Carol at some time, and Carol thus had to accept! Now we know that everyone gets engaged by the matchmaker.

There is only one thing left to verify: stability. Again, suppose that Bob and Carol were engaged by the matchmaker, as were Ted and Alice. Is it possible that Bob loves Alice more than Carol, and Alice loves Bob more than Ted? (This would be an example of what we have called an ``instability.'') Were this indeed the case, Bob must have proposed to Alice before he proposed to Carol, because the matchmaker made Bob send out proposals according to Bob's preference list. What, then, did Alice do with Bob's proposal? One of two things: she accepted it, or rejected it.

Let's consider the first case: when Bob proposed to Alice, she accepted. Then why isn't she now engaged to Bob? There is only one possible reason why: she dumped him to get engaged to someone she loved more! Since every time Alice changes fiances, it is to increase her love in life, she is certainly now engaged to someone she loves more than Bob. As a consequence, even though Bob loves Alice more than his intended Carol, Alice could have no interest in dumping her mate Ted to run off with Bob.

Now let's consider the second case: Alice rejected Bob's proposal. The only possible reason she rejected Bob's proposal was her engagement to someone she loved more than Bob. Once again, Alice must still be engaged to someone she loves more than Bob, namely Ted, so Bob has no hope of convincing Alice to run off with him.

While this excursion into the mathematics of love may seem to have a perfect symmetry about it, the above algorithm has a nasty characteristic that women should object to: it favors men over women. It is merely a social custom that men propose marriage to women --- there is certainly no reason why women can propose instead to men, and the matchmaker could have arranged his directions so that the women indeed did so rather than the men. The following example will show that whoever does the proposing gets a better deal.

Suppose that the men and the women hopelessly disagree about who their first choice is. For instance, imagine that Bob's first choice is Carol, and Ted's first choice is Alice, while Carol's first choice is Ted, and Alice's first choice is Bob. (It should then be clear for each person who their second choice is.) When the matchmaker instructs the men to propose, as described above, in the first round Bob proposes to Carol, and Ted to Alice. Since each woman received exactly one proposal, they accept. Game over: Bob and Ted get their first choice, while Carol and Alice get their second choice.

If the matchmaker exchanged the directions he gave to the men and women, and let the women propose instead, Carol would propose to Ted, and Alice to Bob. Since Ted and Bob each get one proposal, they have to accept. Game over: Carol and Alice get their first choice, while Bob and Ted get their second choice.

It now takes no imagination to imagine why there appeared two articles about ``The Match'' in the New England Journal of Medicine some time ago, addressing inequities in the matching procedure used to assign graduating medical school students to internships. ( See ``Sounding Boards: The Matching Program'' and ``An Analysis of the Resident Match,'' NEJM 304:19 (1981), pp. 1163--1166, and further correspondence in NEJM 305:9 (1981), pp. 525--526.)) The principal anomaly criticized in these articles was precisely the first choice--second choice asymmetry just outlined, that the stable marriage algorithm is ``male optimal.'' As described earlier, in ``The Match,'' medical students list their preferred jobs in order of desirability, while hospital programs do the same, and everyone feeds their list to a computer programmed with the stable marriage algorithm.

Now when the stable algorithm is run, is it the hospitals or the students who get to ``play'' the role of the men? The hospitals, of course. The authors of the NEJM articles asked that either the mathematicians and computer scientists work to find a more equitable matching algorithm, or that the national medical establishment let the students at least occasionally do the proposing. In the words of the authors of the second article, ``all parties are entitled to be informed of the bias of the present algorithm toward [hospital] programs and of the availability of workable, although differently biased, alternatives.'' While there has been continued research in this genre of matching problems, no suitably unbiased replacement for the stable marriage algorithm has been found. To the best of my knowledge, there has been no wavering on the issue of alternating students and hospitals as the proposers. (Perhaps the new President of Brandeis, as a spokesman for national health and education issues, would care to begin by addressing this clear and unconscionable inequity in the training of our nation's doctors.)

The mathematics and politics of love should now be clear, but there are more lessons to be learned about computer science by studying this algorithm. The first and most obvious point to make is that the matchmaker doesn't need to know anything about men, women, or love to do his job.

The stable marriage algorithm was described in terms of a matchmaker instructing a group of men and women to act according to a certain set of rules, like a playwright instructing actors in a piece of theatre. But the matchmaker doesn't need the actual people to compute the matching; he could have figured out the stable matching just by looking at the preference lists. Given that there are 100 men and 100 women, the names of preferences are equally irrelevant: each preference list might as well be a list of the numbers from 1 to 100 in some order. When a ``computer program'' for the stable marriage problem is executed, it manipulates the preference lists precisely as lists of numbers. In fact, when such a computer program is executed, the matchmaker too becomes merely another player on the stage --- were you to be hired as a matchmaker, you too would be following, like an actor, the ``script'' laid out above. Stated otherwise, the computer is a ``general purpose'' device capable of carrying out any precise set of instructions.

A programming language is a precise formalism used to specify computing methods, for example the stable marriage algorithm. A good computer language is one that is easy for people to understand, so that programs can be written that the computer can execute, and people can comprehend. When a computer program has expressions in it that refer to men, women, proposals, and so on, such references mean something to us that is altogether irrelevant to the running of the program. A computer learns nothing about love by running the stable marriage algorithm! (In a similar vein, there is an old joke about a man who wonders how the astronomers ever discovered what the names of the planets were. Clearly the names are useful for astronomers, though the planets themselves are quite indifferent.)

Philosophers have used these kinds of observations to critique the field of artificial intelligence, by arguing that a computer (the ``brain'') cannot become what we call ``intelligent'' by virtue of merely running a computer program. The power of the idea of the computer is as an ideal medium for simulation, not to be confused with the ``real thing.'' This point was expressed beautifully by a philosopher named John Searle, in a book called Minds, Brains, and Science: when a computer is programmed to simulate weather conditions, we would not expect to get wet by standing next to it, and when a computer is used to simulate the spread of a fire in a building, we would not expect it to burst into flames. Why, then, when a computer is used to simulate intelligent behavior, do we jump to assume that the machine is as a consequence intelligent? Many computer scientists who do research in artificial intelligence have been sorely provoked by this argument. The storm of disagreement over this question is as much philosophy as it is science.

The fact that computer languages are designed so that the programmer can explicitly refer to men, women, and so on, is a convenience, but a powerful one. We might imagine a computer processing the preference lists of the stable marriage problem in a variety of ways: for instance, a giant matrix of numbers that are constantly rearranged by the computer, like a spreadsheet. Alternatively, we might visualize the computer solution to the stable marriage problem as the execution of a group of subprograms, one for each man, and each woman. When we start, say, the subprogram for Bob, it causes him to start the subprogram for Carol, where the ``input'' to the Carol subprogram is ``Bob is proposing marriage.'' The Carol subprogram may then return a value to the Bob subprogram like ``proposal rejected,'' and so on. The realization of the matchmaker is then as a ``master program'' which calls the subprograms appropriately.

Like many fields, computer science is not immune to fads, trends, and innovation --- sometimes difficult to discern one from the other --- and one of the current candidates is an idea called object oriented programming. Object oriented programming languages support the style of program construction we have just described. It is interesting that the expression ``object oriented'' has been found for some time in psychiatric literature, which only begs the issues of machine intelligence mentioned earlier. In fact, the jargon is psychoanalyse for ``person oriented,'' since psychoanalysts like to refer to the patient as the ``object.'' Coincidentally, ``people oriented'' programming is very much what advocates of object oriented programming have in mind.

While no one seems sure exactly what ``object oriented'' means --- and in fact some have criticized the phrase as a sound bite with no beef --- the basic idea is that computer programs should be organized as a collection of autonomous objects, each with its own memory to store data, and the ability to communicate with other objects by sending messages to them. Our second description of how to program the stable marriage problem is a perfect example of this kind of object oriented programming.

Another area in computer science of great interest is computer networks and parallel computing. Both of these subjects concern how to take lots of autonomous computers, and link them together. The goal might either be to have a distributed computing facility (like the network of automated bank tellers), or to take complicated problems, parcel out pieces of the problem to many computers, and have the computers work in parallel to solve their respective pieces, and put their solutions together.

If we took our ``object oriented'' solution of the stable marriage problem, and made each of the people a separate computer, then we could have a network of such computers to compute the solution. The matchmaker computer would broadcast a message on the network to all unengaged men to propose; then the men would send proposal messages to particular women, and so on.

There are a host of problems to be solved when trying to implement this ``network'' realization of the stable marriage problem. How are the computers connected in the network? How many pathways are there to send messages? How are messages routed through the network? (One expects that the phone company has solved at least a few of these problems!) How does the matchmaker synchronize the actions of the men and women, so some men do not start round two, for instance, while others are still completing round one?

Many of these problems are mathematically or practically difficult, and there are spectacular stories of failure in systems where they were not correctly solved. For instance, in one of the early space shuttles, there were three identical computers in the shuttle, linked in a network, to protect against failure. Every time a computation was needed, all three computers would compute the answer, and then would ``vote'' using the network. If one of the computers was faulty and produced a wrong answer, the hope was the other two computers would get the right answer and ``outvote'' the faulty one. However, the protocol for how the computers were to communicate via the network was designed improperly, so that each computer was thinking something like, ``I will wait for the other two computers to vote before I vote.'' The result was deadlock: no computer would commit to voting, and the shuttle could not take off.

We began by trying to solve a problem about marriage, which motivated a whirlwind tour of algorithm design, applied combinatorics, program verification, artificial intelligence, programming language design, and parallel and distributed systems. These subjects are a central part of the computer science curriculum, and they are important topics because the concept of a computer, as well as its modern day realization, has made people think differently about how ideas should be organized and developed.

In spite of this progress, what was once said of philosophy is even more true of computer science: to paraphrase, even when all the computational and algorithmic difficulties of marriage have been solved, the real and most profound questions about this most complex form of human relationship remain, and most likely will remain, unaddressed and unresolved. Of these larger and more important questions, which in part give life its mystery and its interest, computer scientists remain decidedly silent.

Harry Mairson is assistant professor of computer science at Brandeis University. He received his Ph. D. at Stanford University in 1984. Prior to coming to Brandeis, he held teaching and research positions at the Institut National de Recherche en Informatique et Automatique in Paris, the American College in Paris, Stanford, and Oxford. His current research on applications of mathematical logic to programming language theory is supported by grants from the National Science Foundation, Texas Instruments, and the Tyson Foundation. For the academic year 1991--1992, he was a Bernstein Faculty Fellow, and on leave at the Cambridge Research Laboratory of Digital Equipment Corporation. He reports that he is stably married and has one son.