Match Theory and the Nobel Prize

The Stable Marriage Problem is not a problem for everyone. Being in love means that we've chosen the woman or man we want to be with, and if all goes well, the object of our passion desires us just as much.

Wouldn't it kill the mood if we believed that an economist can come up with an algorithm that determines who should be married to whom? Fate and serendipity and destiny are thrown out the window in favor of a mathematical formula.

D. Gale and L.S. Shapley wrote an article that was published in the January 1962 issue of The American Mathematical Monthly in which they propose exactly that. The article was called "College Admissions and the Stability of Marriage." Here's how the article begins:

The problem with which we shall be concerned relates to the following typical situation: A college is considering a set of n applicants of which it can admit a quota of only q. Having evaluated their qualifications, the admissions office must decide which ones to admit. The procedure of offering admission only to the q best-qualified applicants will not generally be satisfactory, for it cannot be assumed that all who are offered admission will accept. Accordingly, in order for a college to accept q acceptances, it will generally have to offer to admit more than q applicants. The problem of determining how many and which ones to admit requires some rather involved guesswork.

Gale and Shapley contend that they can "describe a procedure for assigning applicants to college...which removes all uncertainties and which, assuming there are enough applicants, assigns to each college precisely its quota."

I do not pretend to understand the mathematical solution to either the stable marriage problem or the college admissions problem. The dilemma is what intrigues me. The thought process is similar in both scenarios. The college admissions example presents the issue in a more pragmatic (and more dispassionate) manner.

The winners of the 2012 Nobel Prize in Economics were announced this week. This was the explanation given by http://marginalrevolution.com/marginalrevolution/2012/10/noble-matching.html:

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 can also work for gay marriage but it’s a little easier to explain and implement with men and women). Each man proposes to his first ranked choice. Each woman rejects any unacceptable proposals but defers accepting her highest-ranked remaining suitor. 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 suitor and the matches are made.

However, Roth was able to go beyond the Gale-Shapley framework. The Marginal Revolution explains:

What Roth has done is extend the Gale-Shapley algorithm to more complicated matches and to actually design such algorithms to solve real problems. In the 1970s, for example, the medical residency algorithm began to run into trouble because of a new development, the dual career couple. How to match couples, both doctors, to hospitals in the same city? By the 1990s assortative matching in the marriage market was beginning to derail matching in the doctor-hospital market! Roth was called in to solve the problem and moved from being a theorist to a market designer. Roth and Peranson designed the matching algorithm that is now used by Orthodontists, Psychologists, Pharmacists, Radiologists, Pediatric surgeons and many other medical specialties in the United States.

Another real-world problem that was resolved by the extension of this algorithm is kidney donation.

Imagine an algorithm that saves lives. Who would be more deserving of a Nobel prize than the two economists who came up with an algorithm that can do that?