A prize for matchmaking

The 2012 Nobel Prize for economics, or the Sveriges Riksbank prize, as it is formally known, has been awarded to Lloyd S. Shapley of University of California, Los Angeles, and Alvin E. Roth of Stanford University, “for the theory of stable allocations and the practice of market design.”

Prof Shapley is the theorist, while Prof Roth, with a background in operations research, made his name by applying the theory to successfully transforming a number of markets by applying the theory.

Shapley was born in 1923 and received his PhD from Princeton University in 1953. Roth, born in 1951, received his PhD in 1974 from Stanford University. For students of economics, Shapley is an oft-encountered name. In coalitional game theory, the Shapley value and the Shapley-Shubik index provide measures of coalitional power and stability. But it is for the Gale-Shapley algorithm in matching theory that Prof Shapley has won his prize.

A matching, as the name suggests, is the pairing up of elements from two sets. The ‘marriage market’ seeks to match men and women. The ‘admissions market’ tries to allocate students to schools or colleges. The matching framework even applies to unusual things, such as kidney exchange, where kidney donors are matched with recipients for transplant surgery.

In the 1950s, several of these markets existed in the US, but functioned badly. This was mostly because of coordination failures between the two sides of the transaction, and rules that encouraged gaming of the system.

COORDINATION FAILURES

The market for medical residents, for example, was established in 1952. In this, hospitals competed with each other to offer residency positions to medical students. There were initially very few rules.

Students were also few, and the intense competition for them led hospitals to make offers even as much as two years in advance. Students, on the other hand, benefited from waiting as long as possible, in case a better hospital happened to offer them a position.

The result was market failure — students and hospitals remained unmatched, hospitals made fewer offers than they had positions open, and students routinely strategised their applications. Efforts to streamline the process proved useless.

This is where Profs Roth and Shapley made their contribution. In 1962, in a seminal paper with David Gale in the American Mathematical Monthly , Prof Shapley proposed a mechanism that was guaranteed to produce a stable matching. It had the added benefit of encouraging truth-telling by both parties.

The original case made by Gale and Shapley described a marriage market, but it was immediately clear that their proposed solution (called the deferred acceptance, or DA, algorithm) would apply equally well to other similar situations.

But the applications, initially, were few. The first ‘markets’ to seriously implement the DA procedure were, funnily enough, speed dating programmes. It took Alvin Roth to dramatically enhance the scope of the model. But in 1984, Prof Roth applied a practical version of the DA procedure to the medical resident matching problem described above. In 1998, his method was implemented by the medical board.

In other works, he made contributions to overhauling the New York City public school matching system that allocates seats to high school students, as well as the college admissions problem in Boston.

CLEARING HOUSE

He is also co-founder of the New England Kidney Exchange Program. Cases in which a person needs a kidney, but his partner cannot give him or her one because of incompatible blood types, are addressed by this programme. Now the kidney can be put up for exchange, and ‘traded’, as it were, for a compatible one.

In India, too, there are several potential applications, such as the nursery school admissions problem in Delhi. A centralised clearing-house for admissions, based on their procedure, would go a long way towards mitigating much of the criticism of the current process, where parents over-compete for limited schools, schools are accused of fiddling with the results, and the government intervenes frequently.

In any case, whether applied or not, centralised matching will stay relevant, especially in providing research topics for PhD students such as myself.

(The author is a doctoral student of economics at the Indian Statistical Institute, New Delhi, and specialises in matching and allocation problems.)

COMMENT NOW