On October 15, 2012,
the Royal Swedish Academy of Sciences announced that Alvin Roth of Harvard
Business School, and currently a visiting Professor at Stanford University, and
Lloyd Shapley affiliated with departments of Mathematics and Economics of University
of California, Los Angeles, have jointly won the 2012 Nobel Prize for Economics.
Though it has by now become
a common practice of the Academy to award Nobel Prize jointly to two or more
than two academicians, interestingly, this year’s pairing is cheered by
everyone for it is quite apt since both the awardees have made their name by
developing theories of “stable allocations and the practice of market design”,
though independently and at different periods of time.
Lloyd Shapely is a
grand old man of game theory—that part of economics which deals with strategic
decision making which was brought into limelight by John von Neumann and became
popular in the field of economics after World War II—making his presence felt
quite often across the spectrum of economics with his fundamental contributions
to economic theory and game theory ever since he took his PhD from Princeton
University in the year 1953. His thesis and postdoctoral work that introduced ‘Shapely
value’—the payoff that each agent participating in a cooperative game gets—and
the ‘core’ solution has become central to the modern understanding of
competitive behavior and its game theoretic underpinnings. This paper, “A Value for N-Person Games”, has been
enormously influential by virtue of the widespread use of the Shapley value in
several fields and also the inspiration it created in others to come up with
newer values by tweaking the Shapley’s original axioms.
That aside, the
development of the concept ‘core’—an allocation is said to be in the core if no
coalition can improve on its members’ utilities—which is today the most
commonly used cooperative solution concept in economics, has made economists
believe that game theory provides a useful set of tools for analyzing economic
problems. This was followed by another important paper in 1967—“On Balanced Sets
and Cores”—in which Shapely introduced the notion of “balanced”, which remained
a key notion to this day for understanding when games have nonempty cores.
Now coming to his prize-winning
work, it is his seminal paper, “College Admissions and the Stability of
Marriage”, which he published in 1962 along with Gale studying matching games
with nontransferable utility that won him the day. The central idea of this
game theory is that a group of many pairings will be stable, if nobody in any
pair has any incentive to square off with anyone else. For instance, let us
assume there are two sets of agents, say workers and employers that are to be
paired with each other. Presume a particular worker ‘A’ from the set is hired
by the employer ‘X’, but A prefers to be employed by ‘Y’. And also presume that
employer ‘Y’ too likes to employ ‘A’, but did not. This situation, Shapely says, would result in
unexploited gains from trade. On the
other hand, if A had been hired by Y, both of them would have been better
off. And according to Gale and Shapley,
such a pairing would become stable, for there remained no unexploited gains
from the trade.
In an ideal market, workers
and employers might work for such stable outcomes, provided they have
unrestricted time and ability to make deals. But real-world markets are
different from this. It is to overcome
this limitation, Gale and Shapley devised a “deferred acceptance algorithm” for
finding a stable matching. To understand its functioning, let us take the
example of hospitals as one set of agents of the market and medical students
seeking internships as the other set. Now, presume that the hospitals make
offers to medical students. Each student evaluates the offer that he received
and holds on to the one that he prefers and rejects the rest. The critical
element of this whole algorithm is that the desirable offer is not accepted
immediately by the student but he simply holds on to it: deferred acceptance.
The hospital whose offer was rejected by a student can make a new offer to a
different student.Of course, hospitals
enjoy the right not to issue an offer to an unacceptable student.This procedure continues till there is no hospital wishing
to make another offer. It is at this time that the students accept the
proposals they hold.
This way, each hospital
starts offering internship to the best student it wants to hire, and in case it
is rejected, it then makes an offer to the next best student. As this process
is continued, the operation of the algorithm lowers the hospital’s expectations
further and further down till its requirements are met. Conversely, since
students always hold on to the most desirable offer they have received and as
the hospitals cannot withdraw the offer once made, students’ satisfaction too
monotonically increases as the algorithm operates. Thus Gale and Shapley proved
that their deferred-acceptance algorithm will always produce a stable matching.
As Shapley claims, this algorithm can be applied to any market such as school
admissions, even to mass weddings. It is this algorithm that won him the Nobel
for Economics, though Shapley considers himself “a mathematician” and claims to
have “never, never in my life took a course in economics.”
It is about twenty
years later, Alvin Roth, with a PhD in Operations Research from Stanford
University, noticing that something very close to Gale and Shapley's algorithm is
in fact being used in the US market for new doctors, undertook an empirical
investigation and came up with an article in 1984, clarifying how the concept of
stability provides an organizing principle which enables us to understand why
markets sometimes work well and sometimes fail. Using this frame work in
combination with empirical studies, controlled laboratory studies and computer
simulations, Roth studied the functioning of markets and, based on these
findings and using Gale and Shapley algorithm in modified/improved form, came
up with newer institutions that help markets function better. Thus emerged a
new branch of economics: Market Design
.
Designing a new
algorithm—applicant-proposing deferred-acceptance algorithm—which is not only
fully incentive compatible for the applicants, but also applicant optimal, Roth
solved the most daunting problem of matching New York City public high schools
with the preferences of students to the satisfaction of all the parties
involved in 2003, and the Boston public school system in 2005.
Lloyd
Shapley’s work on cooperative game theory has strengthened its theoretical foundations
besides enhancing its utility in policy making. Launching the theory of
matching markets, Shapley hoped that one day it would have practical
applications. His hope has been fulfilled by subsequent researchers, notable
among them being Alvin Roth. These two game theorists, Lloyd Shapley and Alvin
Roth, having thus made socially enriching contributions, richly deserve the Nobel.
No comments:
Post a Comment