The big 5-0—celebrated in 2012—proved a banner year for a certain unassuming seven-page article that appeared in the American Mathematical Monthly back when John F. Kennedy occupied the White House and a stamp cost four cents.
News that researchers from Scotland and Hungary had organized an interdisciplinary workshop in celebration of the 50th anniversary of a paper's publication would have sufficed to thrill the MAA, but, for one Monthly piece, a yet greater honor awaited: widespread citation in coverage of the 2012 Nobel Prize in economics.
"This year's Prize to Lloyd Shapley and Alvin Roth extends from abstract theory developed in the 1960s, over empirical work in the 1980s, to ongoing efforts to find practical solutions to real-world problems," explains the Royal Swedish Academy of Sciences.
As subsequent text makes clear, the abstract theory to which the academy alludes grew out of the short paper Shapley coauthored in 1962 with the now-deceased David Gale. Known to fans simply as Gale and Shapley (1962), "College Admissions and the Stability of Marriage" graced pages 9-15 in the January 1962 issue of the American Mathematical Monthly.
"College Admissions and the Stability of Marriage" dives directly into a "typical problem," that of a college having to decide how many and which applicants to admit to most nearly achieve a desired class size, or quota.
Having defined key terms—what it means for an assignment of applicants to colleges to be unstable and for a stable assignment to be optimal—Gale and Shapley consider "a special case, in which there are the same number of applicants as colleges and all quotas are unity." The authors note that this scenario corresponds "quite readily" to the situation of would-be brides and grooms.
Gale and Shapley then establish that, no matter how members of a community comprising n men and n women rank their potential spouses, a stable matching exists. Their existence proof gives "an iterative procedure for actually finding the stable set of marriages."
The so-called deferred acceptance algorithm can be executed one of two ways: either the men propose or the women do. If the women do the asking, each woman pops the question to the man she would most like to marry. Each man considers any and all proposals he receives, tells the most desirable would-be wife that he needs to think it over, and turns down all other offers. Any woman who has been rejected then proposes to her second-choice man, with each man again retaining as a potential spouse only his favorite among the women who have presented themselves so far. When no woman wants to make any more proposals and each man agrees to wed the woman he is currently stringing along, the process terminates and a stable pairing has been achieved.
"Many big discoveries have humble beginnings," declared Tore Ellingsen of the Stockholm School of Economics as part of the Nobel announcement in October. And, indeed, as the chairman of the Economic Sciences Prize Committee, Per Krusell, indicated in an interview with journalist Joanna Rose, Gale and Shapley could not have fathomed at the time of writing the long-term impact their work would have.
As Marilda Sotomayor—herself an expert in matching theory—tells the story of the paper's origins, then-Brown University professor David Gale formulated the college admissions problem in its now-familiar form. Struggling to solve it, however, he sent a copy to several mathematicians, Lloyd Shapley of the RAND Corporation among them.
"It was Shapley who answered him," Sotomayor reports, "presenting a proof of the existence of stable matchings obtained with the construction of the famous algorithm." Gale organized the paper that appeared in the Monthly, a paper praised for its clarity, brevity, and accessibility, sure, but also for its subtle touch of impish whimsy.
In the conclusion of "College Admissions and the Stability of Marriage," the authors confess to having "abandoned reality altogether and entered the world of mathematical make-believe." They maintain, though, the utility of the results presented. "It is our opinion," Gale and Shapley state modestly, "that some of the ideas introduced here might usefully be applied to certain phases of the admissions problem."
Gale and Shapley sold themselves short.
Game theorist Peter Biró, co-organizer of the MATCH-UP 2012 workshop held in honor of Gale and Shapley (1962), says that Hungary, Ireland, Spain, and Turkey all use a version of the Gale-Shapley algorithm in their college admissions processes.
When New York City implemented an applicant-proposing version of Gale-Shapley to assign students to public high schools, it saw a 90 percent reduction in the number of students sent to schools not among their top five.
A deferred acceptance algorithm not only immune to strategic manipulation but also mindful of the dependent preferences of dual-doctor couples is used to place medical residents at hospitals.
Also in the medical arena, "College Admissions and the Stability of Marriage" put in motion research that led to the development of an improved system for matching available kidneys with patients who need them.
And the list goes on.
Consistently among the most frequently accessed Monthly articles, "College Admissions and the Stability of Marriage" has, according to Google Scholar, been cited more than 2,500 times.
As Shapley's Nobel co-laureate Alvin Roth wrote in a 2007 overview of the past, present, and future of deferred acceptance algorithms, "Gale and Shapley (1962) initiated and advanced what has grown into not only a substantial academic literature on matching models and mechanisms, but also an emerging empirical literature on market failure and market organization, and a growing 'economic engineering' practice of market design."
Roth made even fewer bones about his high regard for Gale and Shapley's seminal paper in a footnote to the sentence just quoted: "Nobel committee, take note."
"College Admissions and the Stability of Marriage" will be reprinted in the May 2013 issue of the Monthly. An introduction by game theorist and mathematical economist Ehud Kalai will accompany the reprint. —Katharine Merow
This article appeared in the April/May 2013 issue of MAA FOCUS.