What Mathematics Is
Two Americans, Alvin E. Roth and Lloyd S. Shapley, were awarded the Nobel Memorial Prize in Economic Science on Monday for their work on market design and matching theory, which relate to how people and companies find and select one another in everything from marriage to school choice to jobs to organ donations.
Their work primarily applies to markets that do not have prices, or at least have strict constraints on prices. The laureates’ breakthroughs involve figuring out how to properly assign people and things to stable matches when prices are not available to help buyers and sellers pair up.
Mr. Shapley, 89, a mathematician long associated with game theory, is a professor emeritus at the University of California, Los Angeles. He made some of the earliest theoretical contributions to research on market design and matching, in the 1950s and 1960s.
In a paper with David Gale in 1962, Mr. Shapley explained how individuals could be paired together in a stable match even when they disagreed about what qualities made the right match. The paper focused on designing an ideal, perfectly stable marriage market: having mates find one another in a fair way, so that no one who is already married would want (and be able) to break off and pair up with someone else who is already married.
I wish to say more about the 1962 Shapley-Gale paper. First, more background, from David Henderson’s WSJ article on the award.
Matching theory can be applied to many aspects of life in which matches need to be made—in marriages, for instance, or the job market, or student placement in colleges. In 1962, Mr. Shapley and co-author David Gale published a short but pathbreaking article titled “College Admissions and the Stability of Marriage” in a mathematical journal.
The article presented what is now called the “Gale-Shapley deferred choice algorithm.” The key word is “deferred.” They showed that if each “girl” (yes, people wrote differently then) rejects all but her favorite of the “boys” who propose, but leaves her favorite hanging to allow for someone even better to come along later—and if each boy who is rejected proceeds to his second choice—then letting this process play out yields stability.
What is stability? It means that there is no boy-girl pair who would both rather be married to each other than to the person they did marry.
Of course, letting that algorithm run is unrealistic. Many girls will accept the boy who is good enough rather than wait until a long sorting-out process is over. But other uses for matching theory make more sense. It turns out that doctors had been using the algorithm to allocate residents to hospitals even before the Gale-Shapley article came along.
You can find the article in Volume 69 of the American Mathematical Monthly, the January 1962 issue. (There’s a link here.) It’s quite readable for such an influential paper, in the sense that no specific mathematical background is required. Gale and Shapley begin by describing a general matching problem, the one that arises in college admissions. They then turn to a special case, the marriage problem. After giving a solution to this simpler problem, they return to the general situation and solve it.
You may enjoy looking at their their treatment of the marriage problem. It’s section 3 of the paper. They pose the problem as follows:
A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all members of the community. Imitating our earlier definition, we call a a set of marriages unstable … if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates.
Question: For any pattern of preferences is it possible to find a stable set of marriages.
We don’t ask that everyone is married to his or her first choice. That’s not going to happen except in the most contrived of examples. We simply ask that no male-female pair is stuck in marriages they prefer less than a marriage to each other. Gale and Shipley proceed to show, in everyday English, how to set up an algorithm that provides a solution.
In the paper’s “concluding remarks,” they reflect on the fact that their theorem and its proof are, in principle, understandable to any reader, with no need for numbers, geometry, calculus, or what people might typically imagine are the tools of a mathematician:
Finally, we call attention to one additional aspect of the preceding analysis which may be of interest to teachers of mathematics. This is the fact that our result provides a handy counterexample to some of the stereotypes which non-mathematicians believe mathematics to be concerned with.
Most mathematicians at one time or another have probably found themselves in the position of trying to refute the notion that they are people with “a head for figures, “or that they “know a lot of formulas.” At such times it may be convenient to have an illustration at hand to show that mathematics need not be concerned with figures, either numerical or geometrical. For this purpose we recommend the statement and proof of our Theorem 1. The argument is carried out not in mathematical symbols but in ordinary English; there are no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly needs to know how to count. Yet any mathematician will immediately recognize the argument as mathematical, while people without mathematical training will probably find difficulty in following the argument,though not because of unfamiliarity with the subject matter.
What, then, to raise the old question once more, is mathematics? The answer, it appears, is that any argument which is carried out with sufficient precision is mathematical, and the reason that your friends and ours cannot understand mathematics is not because they have no head for figures,but because they are unable to achieve the degree of concentration required to follow a moderately involved sequence of inferences. This observation will hardly be news to those engaged in the teaching of mathematics, but it may not be so readily accepted by people outside of the profession. For them the foregoing may serve as a useful illustration.
Fifty years later, their message still rings true (though one might prefer to rewrite some of the harsh-sounding bits). If only I had read it years ago. Now I’ll be prepared for the next party, when someone asks what I do.