A Prize for Priceless Markets

Left: Lloyd Shapley (left) and Ehud Kalai, ca. 2004 (Photo courtesy of Ehud Kalai). Right: Alvin Roth during the 2010 Nancy L. Schwartz Memorial Lecture (Photo © Nathan Mandell).

Lloyd Shapley and Alvin Roth were awarded the 2012 Nobel Prize in Economics this week. Even though the Kellogg/NU poll did not predict this year's winners, in the time since the announcement, many faculty have agreed that this is a well deserved award. The prize was for Shapley's and Roth's work on "the theory of stable allocations and the practice of market design."

Lloyd Shapley is considered one of the founders of game theory, in particular cooperative game theory. "His work is amazing," said Professor Ehud Kalai, founding editor of Games and Economic Behavior and co-founder of the Game Theory Society. "Almost everything we do is influenced by the work of Shapley, Nash and Aumann." In Kalai's view, Shapley created several important areas of research, spanning from Shapley value, to the notion of the core of a game, oceanic games (large games with an ocean of players), stochastic games and matching, among others. According to Professor Robert Weber, who is a co-author of Shapley:

Lloyd Shapley is a beautiful person. He led the development of game theory, both in its mathematical underpinnings, and as a broad field of economic relevance. Most of the key results in its early years benefited from his insights. His work is elegant, and is a delight to read. As well, he has always been gracious with his time, sharing his intensity and interests both with senior colleagues and with students as they first step into the area. I treasure the time I’ve spent with him over the past 40+ years.

Among the work by Shapley cited by the Nobel Prize committee is his research on matching students to colleges with the late David Gale in 1962 ("College Admissions and the Stability of Marriage"). The resulting Gale-Shapley algorithm was a formalization of a mechanism to match elements of two groups (students and colleges, firms and workers, etc), considering their preferences in such a way that the match is "stable" in the sense that there is no alternative matching that would make one of the matched pairs better off. Professor Thomas Hubbard, currently Senior Associate Dean for Strategic Initiatives, was a colleague of Lloyd Shapley at UCLA during the mid 1990s. He highlighted another aspect of Shapley's contributions, the notion of Shapley value in coalition formation. Power in a negotiation depends not just on the best alternative to a negotiated agreement but also on how much value a party contributes to the various coalitions it might form with others. The idea of Shapley value is also used in strategy classes, albeit dubbed 'added value' in MBA teaching (following the book by Adam Brandenburger and Barry Nalebuff, Co-opetition). Alvin Roth is credited with having realized the value of Shapley's work in a number of applications. In joint work with Kellogg School's Professor Keith Murnighan, he started testing the axioms of bargaining theory in the lab. Their collaboration, which dates back to the late 1970s, led to a dozen of published papers and was discussed in a 2006 chapter. In a blog entry on Monday, Murnighan said:

I always claimed that I taught Al how to do an experiment. Truth be told, I didn’t have to tell him much. After we had worked together for a while, I often told him that someday he would do an experiment on his own; he always replied by saying that someday I would prove a theorem on my own. We both actually did that.

In experimental and theory work, Roth and his co-authors extended and applied matching theory to a variety of settings, including kidney exchanges, residency assignments of newly minted doctors in the US, as well as school admissions. His work led to practical applications of game theory in the National Residency Matching Program (which implemented a matching algorithm designed by Roth in 1997), in the New York City public high schools and the Boston Public School system, which use a version of the deferred-acceptance model algorithm. Finally, Roth and co-authors Tayfun Sönmez and Utku Ünver founded the New England Program for Kidney Exchange with doctors Frank Delmonico and Susan Saidman. In his Nancy L. Schwartz Memorial Lecture in May of 2010, Roth discussed kidney exchanges in detail. He was the 28th speaker in this annual lecture series and the 13th Nobel laureate (9 of whom went on to win the Nobel after giving the lecture). The last time Lloyd Shapley gave a lecture at the Kellogg School, was during the Third World Congress of the Game Theory Society, in July of 2008. At that conference, Tim Roughgarden gave the first Shapley Lecture, a newly established lecture series. For more information, see the blog entries by professors Jeff Ely in Cheap Talk and Rakesh Vohra in The Leisure on the Theory Class. Al Roth blogs at Market Design.