Gale-Shapley Algorithm and Designing Matching Markets

Al Roth won the Nobel Prize for "matching" and the design of new types of markets. The Gale-Shapley algorithm is a cornerstone of the matching methods Al Roth pioneered. The algorithm has been extended by Roth and others to apply "Matching Theory" to design matching markets solving real world problems like matching students to the right schools.

Pioneering public schools employing "school choice" programs use custom modifications of this algorithm to provide fair and efficient methods for matching students to their preferred schools. For example, the Denver Public Schools is a world-wide leader in school choice processes and uses the algorithm to successfully match students with their first choice of school over 90% of the time. Roberta Walker - one of the innovators and leaders of this program - has developed school choice matching processes that uses a modification of the algorithm to ensure fairness and to make sure the student is a good match for a particular school. Of course there is a supply and demand challenge for different schools - with some schools in high demand and others in low demand. This program includes both state public schools and charter schools and is a respected model now being copied around the world.

Roth has applied "Matching Theory" to matching doctors to residency programs, children to schools, economists to departments and kidneys to patients in a way that is stable, incentive-compatible, and maximizes the gains from exchange.

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 (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.

Yes, I know, the application to men and women is crazy - but the application to students and schools is very real. 

Indeed, this is exactly what has happened. Students in Denver, New York, Boston and others 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 has been picked up and extended by data scientists for use in many domains.

I said above 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 (G-S) 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. For example, 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 Alvin Roth and co-authors describe just such a mechanism and show that it could save many lives. 

While free and open markets are proven to allocate resources efficiently and optimally, sometimes free markets fail in certain situations and data scientists will be asked to design better markets using algorithms.