In this duality between theory and application, Lloyd Shapley is cast as the theorist. Indeed, in an interview with the AP on Monday, he said: "I consider myself a mathematician and the award is for economics. I never, never in my life took a course in economics." But of course, economists view their field as a big enough tent to include at least some mathematicians--and in particular those that study game theory, like the 1994 Nobel prize to John Nash and others.
In Shapley and co-author David Gale published a famous paper in 1962 in the American Mathematical Monthly called "College Admissions and the Stability of Marriage (69:1, pp. 9-15). It can be read for free (with registration) at JSTOR, or it is available on the web various places like here.
They begin by offering college admission as an example of the kind of problem they are considering. There are a number of colleges and a number of applicants. Colleges have preferences over who they wish to admit, and applicants have preferences over where they would like to attend. How can they be matched in a way that will, in some sense we need to define, "satisfy" both sides? Before going further, notice that this problem of multiple parties on each side, with a problem of matching them so as to "satisfy" all parties, is a characteristic of marriage markets--although in that case the two groups are looking for only one partner apiece--and also of employers and potential employees in the job market.
As a starting point, it is clearly impossible to "satisfy" all parties in the sense that everyone will get their first choice. The college can't assure that all its preferred applicants will want to attend; not all applicants are likely to get their first choice. Thus, Gale and Shapley focused instead on finding a solution that would be "stable," which means in the context of the college admissions choice that once everyone is matched up, there is no combination of a student who would rather be at a college other than the one they are attending AND that college would also prefer to have that student above one of the students it had already attracted. In other words, no student or college will seek to make an end-run around a stable mechanism.
Gale and Shapley proposed a "deferred acceptance" procedure to get a stable result to their matching problem. Here is how the Nobel committee describes the process:
"Agents on one side of the market, say the medical departments, make offers to agents on the other side, the medical students. Each student reviews the proposals she receives, holds on to the one she prefers (assuming it is acceptable), and rejects the rest. A crucial aspect of this algorithm is that desirable offers are not immediately accepted, but simply held on to: deferred acceptance. Any department whose offer is rejected can make a new offer to a different student. The procedure continues until no department wishes to make another offer, at which time the students fi…nally accept the proposals they hold.Here's how the procedure would work in the marriage market:
In this process, each department starts by making its fi…rst offer to its top-ranked applicant, i.e., the medical student it would most like to have as an intern. If the offer is rejected, it then makes an offer to the applicant it ranks as number two, etc. Thus, during the operation of the algorithm, the department’'s expectations are lowered as it makes offers to students further and further down its preference ordering. (Of course, no offers are made to unacceptable applicants.) Conversely, since students always hold on to the most desirable offer they have received, and as offers cannot be withdrawn, each student’s satisfaction is monotonically increasing during the operation of the algorithm. When the departments’decreased expectations have become consistent with the students’increased aspirations, the algorithm stops."
"The Gale-Shapley algorithm can be set up in two alternative ways: either men propose to women, or women propose to men. In the latter case, the process begins with each woman proposing to the man she likes the best. Each man then looks at the different proposals he has received (if any), retains what he regards as the most attractive proposal (but defers from accepting it) and rejects the others. The women who were rejected in the first round then propose to their second-best choices, while the men again keep their best offer and reject the rest. This continues until no women want to make any further proposals. As each of the men then accepts the proposal he holds, the process comes to an end."Gale and Shapley prove that this procedure leads to a "stable" outcome. Again, this doesn't mean that everyone gets their first choice! It means that when the outcome is reached, there is no combination of medical school and applicant, or of man and woman in the marriage example, who would both prefer a different match from the one with which they ended up. But Gale and Shapley went further. It turns out that there are often many stable combinations, and in comparing these stable outcomes, the question of who does the choosing matters. If women propose to men, women will view the outcome as the best of all the stable matching possibilities, while men will view it as the worst; if men propose to women, men as a group will view it as the best of all stable matching possibilities, while women will view it as the worst. As the Nobel committee writes, "stable institutions can be designed to systematically favor one side of the market."
There are many other potential tweaks and twists here. What if monetary payments are part of the match? What if traders are trading indivisible objects? These sorts of issues and many others kept a generation of game theorists busy. But for present purposes, the next key insight is that although I've explained the deferred-acceptance procedure as a step-by-step process, where parties make one offer at a time, an equivalent process can be run by a clearinghouse, if the parties submit sufficient information.
And this is where Alvin Roth enters the picture, bringing in detailed practical implications for analysis. He pointed out in a 1984 paper that the National Resident Matching Program for matching residencies and medical school students was actually a close cousin to the Gale-Shapley procedure. Roth's theoretical analysis pointed out that the form of the match they were using allowed the medical schools, rather than the students, to be the "proposers," and thus created outcomes that the medical schools viewed as the best of the stable options and the students viewed as the worst of the stable options. He redesigned the "match" both to let students be the proposers, and also to address the issue that in a number of cases a married or committed couple wanted to end up at the same school or in the same geographic location.
Roth then found other applications for what he has called the "market design" approach. (It is ironic but true that the market design approach can include prices if desired, but doesn't actually need prices to function.) The key problems in these matching scenarios often involve timing. There is often pressure on various parties--whether marriage or college admissions--to commit early, which can lead to situations where the outcome will "unravel" as people seek a way out of their too-early commitments. On the other side, if the process slogs along too late, then "congestion" can result when an offer is turned down and it becomes too late to make other offers.
Roth found applications of the Shapley matching approach in a wide variety of academic matching settings, both in the U.S. and in other countries. He also applied a similar process to students choosing between public schools in New York City and Boston. More recently, he has sought to apply these insights to the problem of matching kidney donors with those in need of a kidney transplant. (In fairness, it should be pointed out that Roth has written a number of strong theoretical papers as well, but the Nobel committee emphasized his practical concerns, and I will follow their lead here.) As one might expect, these real-world cases raise various practical problems. Are there ways of gaming the system by not listing your first choice, which you are perhaps unlikely to get anyway, and pretending great enthusiasm for your fifth choice, which you are more likely to get? Such outcomes are sometimes possible in practical settings, but it proves much harder to game these mechanisms than one might think. Usually, you're better off just giving your true preferences and seeing how the mechanism plays itself out.
The Nobel prize to Shapley and Roth is one of those prizes that I suspect I will have a hard time explaining to non-economists. The non-economists I know ask practical questions. They want to know how the work done for the prize will spur the economy, or create jobs, or reduce inequality, or help the poor, or save the government money. Somehow, better matching for medical school students won't seem, to some non-economists like it's "big enough" to deserve a Nobel. But economics isn't all about today's public policy questions. The prize rewards thinking deeply about how a matching process works. In a world of increasingly powerful information-processing technology, where we may all find ourselves "matched" in various ways based on questions we answer by software we don't understand, I suspect that Alvin Roth's current applications are just the starting point for ways to apply the insights developed from Lloyd Shapley's "deferred acceptance" mechanism.