RAND Corporation
Lloyd Stowell Shapley made profound contributions to almost every area of game theory — a field of mathematics that tries to understand how people's choices influence others'. His findings have been applied to all sorts of settings, from politics to hospitals. His whimsically titled 1962 paper — 'On College Admissions and the Stability of Marriage'— published in The American Mathematical Monthly and co-authored with the late mathematician David Gale, won Shapley the 2012 Nobel prize in economics, which I shared with him.
Shapley, who died on 12 March, was born in 1923 in Cambridge, Massachusetts, to the astronomer Harlow Shapley and his wife Martha. He pursed a mathematics degree at Harvard University in Cambridge. In 1943, during his third year and at the height of the Second World War, he was drafted into the US Army. In his years of service, he worked at an air base in China and won the Bronze Star, a US military decoration, for breaking a code for Soviet weather reports.
After the war, Shapley graduated from Harvard and worked for two years at the RAND Corporation, which at the time provided research and analysis to the US military. There, he began his work on game theory and came to the attention of the field's founder, John von Neumann.
In 1949, Shapley entered the PhD programme in mathematics at Princeton University in New Jersey — then a hotbed for game theory. There, he overlapped with the mathematician John Nash and the economist Martin Shubik (who would become his long-term collaborator), among many others. Shapley rejoined RAND in 1954, and stayed with the organization for 27 years. In 1981, he moved to the University of California, Los Angeles, where he retired in 2001.
Game theory describes any situation in which the pay-offs that participants receive from their actions are at least partly determined by the actions of other people. Shapley was one of the first to formulate and study the 'core of the game' — the set of outcomes (consequences for everyone in the group) with the property that no coalition of players can do better for themselves by coordinating to produce a different outcome.
Not every game has a core outcome. But for those that do, it often indicates how competition will play out. Shapley's paper with Gale explored this concept in the context of two-sided 'matching games' (
D. Gale and L. S. Shapley Am. Math. Mon. 69, 6–15; 1962). In these situations, two sets of players (in the paper, boys and girls seeking marriages, and colleges seeking students and students seeking colleges) have preferences about whom they would like to match with.
In a simple model of one-to-one matching — as applies when each player seeks one spouse, for instance — the core outcomes are those that are stable. After everyone in the game has chosen, there are no pairs (of girls and boys, in the 1960s partnering example) who are not matched to each other but would both prefer to be.
In a note written to Shapley in 1960, Gale asked, “For any pattern of preferences, is it possible to find a stable set of marriages?” Shapley gave his answer in a letter to him: “Let each boy propose to his best girl. Let each girl with several proposals reject all but her favorite, but defer acceptance until she is sure no one better will come her way. The rejected boys then propose to their next-best choices, and so on, until there are no girls with more than one suitor. Marry. The result is stable, since the extramarital liaisons that were previously rejected will be disliked by the girl partners, while all others will be disliked by the boy partners.”
Thus was born the 'deferred acceptance algorithm', variants of which are used today to assign US medical graduates to their first jobs, and children to state schools in a growing number of US cities.
Other work from the 1970s by Shapley and the late economist Herbert Scarf on the money-free exchange of indivisible goods ('barter exchange') later helped to organize kidney transplants when donors cannot directly donate to the patient of their choice because of incompatibilities. And starting in the 1990s, Shapley's ideas about two-sided matching and extended barter exchange led to a branch of economic engineering called market design, which seeks to find practical ways to fix broken markets.
In the early 1960s, Shapley and John Milnor (an undergraduate at Princeton when Shapley was a graduate student) initiated the study of 'oceanic games'. In these, there is an 'ocean' of many small players each alone having insignificant influence, so only the actions of people en masse can affect the overall outcome. He later explored these with Robert Aumann, another Nobel economics laureate, in their volume Values of Non-Atomic Games (RAND Corporation, 1968).
Although Lloyd and I shared the Nobel prize, we never worked together. But his work was fundamental to my own — for instance, on the practical design of marketplaces. He was a forbidding presence at meetings; I suspect shyness was to blame for his apparent fierceness.
There is a crater on the Moon named Shapley, in honour of Lloyd's astronomer dad. In game theory, Lloyd will likewise be remembered for the mammoth impact he had on the field.
Posts
