San Francisco 2014
blog home Home

Alvin Roth’s Plenary Talk

by Chun Ye on November 10th, 2014

It is 9:45am, I am navigating my way through the meeting rooms in Hilton, like a mouse in a maze. My destination: Alvin Roth’s plenary talk. As a student who is interested in market design, I have been looking forward to hear the words of wisdom of this Nobel prize winning economist at this year’s INFORMS Annual Meeting. I remember searching for the abstract of Al Roth’s talk inside the giant directory given to me at registration. To my dismay, his talk has no abstract other than the intriguing title “Market Design & the Economist as Engineer.” The lack of an abstract only adds more suspense to his impending talk, or so I thought.

I arrive at the Continental room 10 minutes prior to the start of the session with the intention of claiming a prime viewing location in the audience, only to find out that the majority of them are claimed by those who have arrived earlier. As a student trained in operations research who is used to taking a shortest path between a source destination pair, I realize that my back of the envelop calculations failed to take into consideration the human factors involved: everyone else chose to take the shortest path as well. It turns out that I (as well as others) experienced firsthand the kind of optimization problems that Al Roth is about to address in his talk.

Al Roth starts off his talk by justifying why an economist is invited to speak in front of an audience of operations researchers: “economist is a label that people associate me with, but I am an engineer at heart.” Al Roth received his PhD from what used to be the OR department in Stanford in 1974. During his PhD days, most people in the department worked on problems involving optimizing the operations of a firm. Many such problems involved a single decision maker. In contrast, Al Roth was interested game theoretic problems, in which multiple decision makers are involved. Game theory was a subject of studies by economists, who were primarily interested in understanding the long run equilibrium behavior of an existing system. Al Roth, on the other hand, was more interested in designing a system that will influence the decisions of each individual agent in the system towards a behavior that is desired by the central planner. In that sense, the term “the economist as engineer” used in Al Roth’s talk title is not an oxymoron. In fact, Al Roth dedicated his career implementing and preaching the philosophy of using engineering techniques to design exchange markets. In doing so, he revolutionized the field of market design.

In his talk, Al Roth presents three applications of market design: the medical labor market, school choice, and kidney exchange. Just as congestion was created by everyone taking the shortest path to attend Al Roth’s plenary presentation, which results some degree of inefficiency, a natural congestion forms in each of the aforementioned applications, whether it be doctors wanting to get into the most popular hospital, students the best schools, or patients a functional kidney. Al Roth explains that under certain simplifying assumptions, beautiful theories developed in the works of Gale and Shapley, Edmond and Gallai, and others can be turned into mechanism that a central planner uses to improve the efficiency of these market exchanges. Unfortunately, beautiful theories do not always work as intended in real-world settings as some of the underlying assumptions that give backbone to these theories are usually not satisfied. Consequently, it is the role of an engineer to monitor how well these mechanisms work in practice, to identify the deficiency of such mechanisms, and to tweak the mechanism in small ways so as to make up for its shortcomings.

For instance, the assignment of doctors to hospitals can be thought of as a two-sided matching problem. In this problem, each hospital wants to hire a number of doctors and each doctor wants to get a job at a hospital. We assume that agents on each side of the market has a preference ordering over members of the opposite site. The Deferred Acceptance algorithm (DA) proposed by Gale and Shapley in the 1960s is a standard method for finding a matching that every agent in the market find acceptable. The standard notion of acceptability used in the two sided matching literature is the stability condition, which states that no pairs of hospital and doctor that are not matched to each other will be better off by choosing to abandon their current partner and get together. The DA algorithm works by having each doctor iteratively propose to their top ranked hospital that has not (yet) rejected him. Each hospital would temporarily hold on to the proposals that it receives until its capacity is fill, in which case it will start rejecting a previously accepted candidate that it finds the least attractive provided that it receives a proposal from a more attractive candidate. The algorithm terminates when either all doctors are matched or all of the unmatched doctors have proposed to every hospital that they find acceptable. In the context of two sided matching, the DA algorithm is guaranteed to return a stable matching and as a result, it quickly became one of the most popular methods for assigning doctors to hospitals in many places around the world.

Nonetheless, in the 1970s, people who run the allocation mechanism started to notice that some people did not show up at the hospital that was assigned to them by the DA algorithm but rather arranged matching with another hospital in a decentralized fashion. In fact, most of the doctor-hospital blocking pairs of involved a doctor who was married to another doctor and the couple jointly participated in the allocation mechanism. Al Roth sums up the “couples’ dilemma” nicely: “the iron law of marriage: You can’t be happier than your spouse.” The existing DA algorithm suffers from the drawback of its assumption: every doctor’s preference over hospitals is independent of the assignment outcome of every other doctor. In the case of couples, it makes more sense for the couple to jointly report a preference ordering over a pair of hospitals, rather than two separate preference orderings over individual hospitals, as their individual assignment does affect the preference of their partner. In the variant of the “couples” two-sided matching problem, a stable matching may not exist. However, it has been observed by practitioners empirically that a stable matching in many large matching markets do exist in real life, and a stable matching can still be computed by a variant of the DA algorithm efficiently. In a recent joint work, Al Roth and several other researchers were able to prove formally, under certain technical assumptions, that a stable matching in large (random) markets exists with high probability. Hence, their theoretical result support the existing empirical findings.

Another application that Al Roth has been actively involved in is the field of kidney exchange. Kidney exchange is a 70 billion industry in the U.S. with 100,000 patients currently on the waiting list for a healthy kidney. Since a family member of a patient cannot always directly donate a kidney to the patient due to incompatibility of blood types and other complications, the scarcity of the supply of kidneys motivates the design of an efficient market for patients and their family members to increase the supply of kidneys that otherwise would have to come from deceased donors. Due to ethical reasons, many countries forbid monetary transactions for kidney, this leads to the natural idea of having a patient-donor pairs exchange kidneys with each other. Unfortunately, even the idea of kidney exchange has its own complications. For instance, the size of the kidney trading cycles involved in an exchange of patient-donor pairs must be small (as in 2 or 3), else hospital will not have enough resources to simultaneously perform the necessary medical operations. Maximizing the number of kidney exchanges involving small trading cycles is a NP-hard problem in general. However, Al Roth and colleague provided some empirical findings and theoretical models to explain why some of algorithms developed work better in practice than the theoretical bounds that one is able to derive. Recently, Al Roth and colleague have been quantifying the effect of exchanges initiated from a voluntary donor. Empirical findings as well as theoretical models are developed to address and explain such an effect.

Al Roth concludes the talk by encouraging operations researchers to collaborate with economists and computer scientists in addressing some of difficult problems that arise in designing an efficient protocol for a multi-agent system. Operation researchers are adapt at designing and optimizing a system involving a single decision maker. However, many real world settings involve multiple agents who simultaneously making distinct decisions, and being able to take these decisions into consideration is the key in designing a functional, robust, and long lasting system. Al Roth has done some great work throughout his career: he has kept marriages stable, put smiles on parents’ faces, and saved countless lives. Al Roth makes the world a better place.

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS