The Nobel in Economics
And the winners are Alvin E. Roth Lloyd S. Shapley:
Stable allocations – from theory to practice, Nobelprize.org: This year's Prize concerns a central economic problem: how to match different agents as well as possible. For example, students have to be matched with schools, and donors of human organs with patients in need of a transplant. How can such matching be accomplished as efficiently as possible? ... The prize rewards two scholars who have answered these questions...
Lloyd Shapley used so-called cooperative game theory to study and compare different matching methods. A key issue is to ensure that a matching is stable in the sense that two agents cannot be found who would prefer each other over their current counterparts. Shapley and his colleagues derived specific methods – in particular, the so-called Gale-Shapley algorithm – that always ensure a stable matching. These methods also limit agents' motives for manipulating the matching process. Shapley was able to show how the specific design of a method may systematically benefit one or the other side of the market.
Alvin Roth recognized that Shapley's theoretical results could clarify the functioning of important markets in practice. In a series of empirical studies, Roth and his colleagues demonstrated that stability is the key to understanding the success of particular market institutions. Roth was later able to substantiate this conclusion in systematic laboratory experiments. He also helped redesign existing institutions for matching new doctors with hospitals, students with schools, and organ donors with patients. These reforms are all based on the Gale-Shapley algorithm, along with modifications that take into account specific circumstances and ethical restrictions, such as the preclusion of side payments.
Even though these two researchers worked independently of one another, the combination of Shapley's basic theory and Roth's empirical investigations, experiments and practical design has generated a flourishing field of research and improved the performance of many markets. This year's prize is awarded for an outstanding example of economic engineering.
I am short on time, and this is outside my main area, so I am going ot rely upon others for now (I hope to say more later, but we'll see...):
... When I talk about economists, one of the greatest compliments I give is to say that they changed the way people think about the world. Al Roth definitely fits into that category. The type of economics he is best known for is what is called “Market Design.” Essentially, it means bringing market-type thinking to areas in which historically non-market allocation mechanisms have been used. A few examples of the areas Roth has explored are matching fledgling doctors to hospitals for their residency, matching students to public schools in school choice programs, and matching kidney donors with those who need a kidney.
I know Roth changed my thinking because the first time I read Roth’s work in this area I had a strong reaction: this isn’t really economics. His applications, while based on general theories and principles, involve solutions that are highly dependent on the particular institutions and quirks of the setting he is studying. In my youth, I was under the illusion that economic principles should be universal. It was in part through my appreciation of Roth’s work, that I came to think very differently about the world and appreciate how critical it is to think about the specifics of the setting when coming up with solutions. Now, when I read Roth’s work, it definitely feels to me like economics. ...
...the Nobel prize decided to focus on matching markets — that is, markets essentially without a price mechanism — and gave the award to Roth and Shapley.
Interestingly, Lloyd Shapley is best known in economics for the Shapley value which is a way of thinking about who might capture value in a multi-lateral negotiation. I personally have spent a good portion of the last decade thinking about how that value could be practically applied to the theory of oligopoly. And Al Roth too had his beginnings in negotiation and bargaining theory. But it was Shapley’s work (with Gale) on an algorithm to generate stable allocations when two groups of people are to be matched with one another that turned out to lead to the greatest practical applications. The easiest way to describe this is to consider the market for marriage. Nowadays we can consider this as a market without prices (well at least not ex ante prices) but a market nonetheless as there are only a certain number of ways you can match equal numbers of men and women. As it turns out, if you imagined the market as organised — something that surely takes a ton of imagination — you might consider each side ranking the people they would like to marry of the other gender in the population. Then the algorithm would pick one side, say, women, and give them their preferences first. If several women ranked the same man as No.1, then the men’s preferences would come into play. Without going into full details, this simple procedure led to three things. First, the matching outcome was stable in that you could not find individual pairs of men and women who were not married to one another who would prefer to be so over their matched partners. Second, and related, the outcome was Pareto optimal in that there was no other stable allocation where everyone could be made better off. Finally, whichever side got to propose first (say, the women in my discussion above) got, loosely, the better deal. ...[much more]...
In honor of the Nobel prizes to Al Roth and Lloyd Shapley, here is a primer on matching theory. Matching is a fundamental property of many markets and social institutions. Jobs are matched to workers, husbands to wives, doctors to hospitals, kidneys to patients.
The field of matching may be said to start with the Gale-Shapley deferred choice algorithm. Here is how it works, applied to men and women and marriage (n.b. the algorithm is also good for gay marriage but it’s a little easier to explain with men and women). Each man proposes to his first ranked choice. Each woman rejects any unacceptable proposals but defers accepting her remaining suitors. Each rejected man proposes to his second ranked choice. Each woman now rejects again any unacceptable proposals, which may include previous suitors who have now become unacceptable. The process repeats until no further proposals are made; each woman then accepts her most preferred suitors and the matches are made.
A similar process works when proposal receivers may accept more than one suitor, not that useful for marriage in most of the United States but very useful for when students are applying to schools and each school accepts many students.
Now what is good about this algorithm? First, Gale and Shapley proved that the algorithm converges to a solution for a very wide range of preferences. Second, the algorithm is stable in the sense that ... no mutually preferable match is possible. Thus, the algorithm produces a stable match. ...
Another question is whether the algorithm can be strategically manipulated. In an Impossibility Theorem with much the same flavor as Arrow’s Theorem and the Gibbard-Satterthwaite theorem, Roth and Roth and Sotomayor proved that there is always some possibility for manipulation but the G-S algorithm can be said to minimize the opportunity for strategic manipulation...
What Roth has done is extend the Gale-Shapley algorithm to more complicated matches and to actually design such algorithms to solve real problems. ...
There will be many posts summarizing the modern market design aspect of Roth and Shapley, today’s winners of the Econ Nobel. So here let me briefly discuss certain theoretical aspects of their work, and particularly my read of the history here as it relates to game theory more generally. I also want to point out that the importance of the matching literature goes way beyond the handful of applied problems (school choice, etc.) of which most people are familiar. ...
...Congratuations, you crazy kids. At the very least, the rest of us can rest comfortably knowing that the prize money is going to make the world a more efficient place. Hopefully your experiences aren’t quite as exhausting as what Krugman reports on the Nobel festivities:
SAGAL: You know, you started with the New York Times around 1999 - if not mistaken - writing about economic issues, primarily. And you became very well-known and very influential. You won the Nobel Prize. By the way, winning the Nobel Prize - does that shut up one’s critics?
KRUGMAN: Well, no, it doesn’t shut them up. I mean - but it does mean that people stop saying that you’re an idiot, for about two weeks.
(LAUGHTER)
SAGAL: Two weeks? Because…
KRUGMAN: Two weeks.
SAGAL: I mean…
KRUGMAN: Then it’s right back.
ROCCA: It’s the honeymoon period.
SAGAL: Because I remember at the time, you were engaged in all of these debates, very - sometimes intense, about the Bush economic program and what it would do. And you had a lot of people criticizing you and dismissing you. And then you won the Nobel Prize. And I, in your shoes, would have such a hard time not saying “a-ha!” to everybody.
ROCCA: You should wear it when you go on Stephanopoulos’ show.
KRUGMAN: Yeah. It’s - when it happens, it’s such a blur. They worked me like a dog. I mean, the thing is all for the sake of the Swedes, not for you. And as my wife said, you know, the two great things are first, that you won this; second, that we’re never going to have to do this again.
SAGAL: Really?
KRUGMAN: Oh, yeah.
SAGAL: So you’re saying it’s a pain in the butt to have to win a Nobel?
KRUGMAN: Well, the actual going through the process of collecting it, is thrilling but exhausting and…
SAGAL: Do they make you like, run and chase it? I mean, what are you talking about?
(LAUGHTER)
KRUGMAN: I maybe talked to about eight different - or 10 different groups a day. Oh yeah, I shouldn’t complain.
SAGAL: Right.
KRUGMAN: But it was a very strange, out-of-body experience.
Update: I will keep a list of particularly interesting Nobel commentary here as it unfolds. ...
Two Americans, Alvin E. Roth and Lloyd 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. ...
Posted by Mark Thoma on Monday, October 15, 2012 at 08:57 AM in Economics |
Permalink
Comments (19)
You can follow this conversation by subscribing to the comment feed for this post.