And the Nobel Prize Goes To...

by Deepthi Sai

Traditionally, economics suggests that markets have an innate tendency to work efficiently. Keeping supply constant, if demand for a good rises, then prices automatically start rising so that only the handful of people willing to pay the higher price can get the good. This self-regulating ability of markets was called the ‘invisible hand’ by Adam Smith, the pioneer of political economics. But what about something like dating? How exactly is one allocated the right partner? Surely there exist allocations that are not governed by prices. Dr. Alvin E. Roth of Harvard University and Dr. Lloyd Shapley of UCLA answered questions regarding efficient allocations in such cases for which they were awarded a Nobel Memorial Prize in Economic Sciences in 2012. So what exactly did their research entail?

Back in 1962, Dr. Lloyd Shapley, along with David Gale, came up with the Gale-Shapley algorithm. They said that if individuals are allowed to trade infinitely in a mutually beneficial manner, the result of the trade would be efficient. If any individual feels he can be better off, he will trade further to improve his outcome. Individuals eventually reach a stage where they feel further trade will not make them better off. At this stage, the individual is said to be ‘stable.’

Shapley and Gale attempted to pair ten women with ten men to form stable matches (that is, having no tendency to break up and form a new pair). They came up with an algorithm that always led to stable matches. This was called the Gale-Shapley ‘deferred acceptance’ algorithm. According to this, if women were given the right to propose, every man who received a number of proposals chose the one he thought was best for him and rejected the rest. The women who got rejected by their first preference pursued their next best alternative. This resulted in an efficient allocation. An interesting aspect of the algorithm is that the proposing side of the market (in this case, women) is generally favoured.

Courtesy The Guardian

The practical grounds for the Gale-Shapley algorithm were set much later in the ‘80s by Dr. Alvin E. Roth, who set out to study the market for newly examined doctors. Most graduates from medical schools are picked up as interns by hospitals. In the 1940s, a situation arose where increased competition among hospitals for these interns resulted in offers for internships several years before graduation. The problem with this is that the hospital did not know the true credentials of the students they were making the offer to and students had not decided their field of specialization. Many times, students declined offers at a time when the hospitals could not find any other replacement since other students had already taken up offers from other institutions. Thus, a stable allocation was absent in this situation. To combat the problem, hospitals began issuing deadlines for responses to their offers which resulted in early decision on the part of the indecisive students who were unaware of opportunities that may come their way in the future.

To resolve the issue, a centralized ‘clearinghouse,’ called the National Resident Matching Programme (NRMP), was set up. The procedure used to find the best-fit resident was similar to the Gale-Shapley algorithm. Roth suggested that the basis for success of a programme such as the NRMP was the ability to provide ‘stable’ matches. He studied different algorithms adopted by medical markets in the UK and rejected algorithms that failed to provide stable matches.

While the NRMP was successful, it failed to accommodate certain demands of interns. Dual-doctor couples wished to work in the same hospital or at least in close proximity. Since the NRMP failed to cater to their demands, many interns chose not to apply through it, hampering the stability it had once achieved. The NRMP also favoured hospitals over students since they were the ones making the proposal.

Courtesy The Royal Swedish Academy of Sciences

Roth developed a new algorithm, along with Elliott Peranson, which accommodated couples and did not excessively favour the hospitals. Roth came up with the applicant-proposing algorithm, a variant of the Gale-Shapley algorithm. According to this, interns were paired with programs within a pool and each ranked their preferences. Interns and programs from different pools could not be matched. Thus, every program listed interns in increasing order of preference and interns gave a list of programs they prefered. This list was called the ‘rank order list’ (ROL). Every applicant reviewed his/her list until he/she reached a program which had a vacancy and preferred him/her to the current tentative match. When an applicant found such a match, he/she was matched to the program on a tentative basis and the previous ‘tentative match’ was displaced and became a part of the ‘applicant stack,’ now available for other programs to pick up. Similarly, interns who left a tentative program for some other led to the program being placed in the ‘program stack.’ Now, this displaced applicant reviews his/her ROL to find his/her next best program. The algorithm worked and resolved the issues plaguing the NRMP.

The applicant-proposing algorithm has been useful in other settings also. Until 2003, applicants to public schools in New York were asked to list their five most preferred schools. In three rounds, schools decided whether students would be admitted, rejected or waitlisted. After the third round, students who had not been placed anywhere were randomly assigned schools through an administrative procedure. The result was that around 30,000 students every year were placed in schools that were not even on the list they had initially constructed. This problem was successfully resolved through the applicant-proposing algorithm with a 90 percent reduction in the number of students being assigned schools that they were not inclined toward.

In the cases of programs and interns, and schools and students, preferences of both sides of the market were taken into consideration. However, in the case of organ transplants, only one side (the ‘buyer,’ if you will) of the ‘market’ is active. Shapley figured out how a patient in need for a transplant could be matched with an organ. The proposed algorithm in this case is called the ‘top trading cycle algorithm.’ All patients are allocated organs and they keep swapping potential organs with other patients until their needs are met. Since the organ and the patient pair must be compatible, the process can be rather time-consuming, but it does ensure a stable match.

The application of these algorithms does not end here and continues to benefit individuals in various fields. For instance, search engines have gained tremendously from it in matters of auctioning space to advertisers. The algorithms proposed by Shapley and Roth have been able to establish a theoretical and practical ground, giving rise to a field that holds great promise for the future. There is no doubt that a Nobel Prize for their contribution is well-deserved.

References

"Stable Allocations and the Practice of Market Design." Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences, 15 Oct. 2012. Web. 23 Oct. 2012. <http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/advanced-economicsciences2012.pdf>.

Roth, Alvin E. "Design of Applicant Proposing Matching Algorithm; Comparison with Existing NRMP Algorithm." Harvard University, 25 Oct. 1996. Web. 23 Oct. 2012. <http://kuznets.fas.harvard.edu/~aroth/phase1.html>.

The Royal Swedish Academy of Sciences. The Prize in Economic Sciences 2012. Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences, n.d. Web. 23 Oct. 2012. <http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf>.