View source for Noble Matching

<!-- you can have any number of categories here -->
[[Category:Alex Tabarrok]]
[[Category:Matching Theory]]
<!-- 1 URL must be followed by >= 0 Other URL and Old URL and 1 End URL.-->
{{URL | url = http://marginalrevolution.com/marginalrevolution/2012/10/noble-matching.html}}
<!-- {{Other URL | url = }} -->
<!-- {{Old URL | url = }} -->
{{End URL}}
{{DES | des = [[Alex Tabarrok]] provides an explanation of Matching Theory, provides some examples, and discusses work beyond that of the Nobel prize winners. | show=}}
<!-- DPL has problems with categories that have a single quote in them.  Use these explicit workarounds. -->
<!-- normally, we would use {{Links}} and {{Quotes}}  -->
{{Quotations|Noble Matching|quotes=true}}

{{Text |
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.

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 there is no man and no woman who would rather be matched to each other than to their current match. There are of course, men who would prefer to marry other women and there are women who would prefer to marry other men but no mutually preferable match is possible. Thus, the algorithm produces a stable match.

The application to men and women is somewhat fanciful, although Match.com should clearly adopt this idea!, but the application to students and schools is very real. Gale and Shapley concluded their paper by writing:

It is our opinion, however, that some of the ideas introduced here might usefully be applied to certain phases of the admissions problem.

Indeed, this is exactly what has happened. Students in New York and in Boston are now matched to schools using versions of this algorithm. Even before Gale and Shapley the algorithm had been used, without much theorizing, by doctors allocating residents to hospitals and since Gale-Shapley and Roth the idea has been used much more extensively all over the world .The algorithm, by the way, has been picked up and extended by computer scientists notably including Knuth.

I said above that the men propose to the women–this matters because when the women propose to the men you also get a stable match but it may be a somewhat different match and in general it is better to be the one proposing. Matching becomes more difficult when, as in modern times, both men and women may propose. Fortunately, in many problems, such as with students and schools, the proposers and receivers can be fixed.

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; in particular for the proposers, men or say students applying to schools. it is a dominant strategy to reveal one’s true preferences.

The importance of a stable matching algorithm can be seen in what happens when such algorithms are not used. In trying to allocate residents to hospitals, for example, what typically happens when a stable algorithm is not used is unraveling and chaos. Unraveling occurs when offers are made earlier and earlier in an attempt to get a jump on the competition. Prior to the currently used National Residency Matching Program, for example, hospitals were making offers to residents up to two years in advance! All kinds of chaos arose as hospitals would make exploding offers, accept now or the offer explodes! Such offers would inevitable lead to recriminations and backing out of the offers as better matches were sought.

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.

Most famously, Roth has worked on improving kidney allocation. I first wrote about this in 2004 (see also these posts):

Your spouse is dying of kidney disease. You want to give her one of your kidneys but tests show that it is incompatible with her immune system. Utter anguish and frustration. Is there anything that you can do? Today the answer is yes. Transplant centers are now helping to arrange kidney swaps. You give to the spouse of another donor who gives to your spouse. Pareto would be proud. Even a few three-way swaps have been conducted.

But why stop at three? What about an n-way swap? Let’s add in the possibility of an exchange that raises your spouse on the queue for a cadaveric kidney. And let us also recognize that even if your kidney is compatible with your spouse’s there may be a better match. Is there an allocation system that makes all donors and spouses better off (or at least no worse off) and that maximizes the number of beneficial swaps? In an important paper (Warning! Very technical. Requires NBER subscription.) Alvin Roth and co-authors describe just such a mechanism and show that it could save many lives. Who says efficiency is a pedestrian virtue?

Since that time we have seen many such swaps including this record of 60 people and 30 kidneys. Truly a noble match.
}}