When you think of a marketplace, you may tend to assume money drives all deals. But what if the market item can’t be sold, like a kidney or a placement in a good public elementary school?
These are the markets that new Management Science and Engineering (MS&E) Professor Itai Ashlagi studies—markets where no money changes hands. Instead of monetary deals, the goal of these markets is to arrange agreeable matches between parties. As an expert in the design of these specific markets, Ashlagi assumes the role of matchmaker.
“MS&E is a natural place for my work,” said Ashlagi, who joined the MS&E team this fall after five years at MIT’s Sloan School of Management. “A lot of people here are concerned with market design and the interaction between operations and economics.”
Professor Ashlagi grew up in Israel, went to Haifa University for his B.A., and then received his master’s and PhD in Operations Research at Technion, Israel’s premier technology research institute. It was at Technion that he studied game theory and mechanism design.
But it was during his postdoc at Harvard University that Ashlagi worked with Professor Alvin Roth, and this work spurred his interest in the design of matching markets.
Roth, who is also now at Stanford, helped to establish the first centralized kidney exchange organization. This resulted in many more kidney transplants than had previously been possible through the traditional method of one-to-one matching. For his innovative work in matching markets, Roth shared a Nobel Prize in 2012.
Ashlagi joined Roth during this work to help design rules in this marketplace that would encourage every hospital’s maximum participation in the centralized kidney exchange pool. A large pool is important, because while some patients will match to a variety of kidneys, others are highly sensitized and require a very rare one.
Because we only need one kidney to function, a living donor can give his or her spare kidney to help a sick loved one; but alas, they may not be compatible. In the past, if you couldn’t find a matching living donor on your own, you were relegated to the deceased donor waiting list—and you could be waiting a long time.
This is where “donor pairs” come in. A husband may desire to donate a kidney to his wife, but he is incompatible. Meanwhile, in the same town, a sister may want to donate a kidney to her brother, but she is also incompatible. But perhaps the sister’s kidney is a match for the wife, and the husband’s kidney is a match for the brother. Now you have a paired donation.
Previously, hospitals would perform transplants on these donor pairs without submitting the details of the donors and recipients to the centralized pool. After all, they already have a successful match.
This helps the patients under their care, but if every hospital instead used the centralized kidney exchange pool to enter their possible donors and recipients, more transplants would result. For example, it’s possible that the brother’s and wife’s bodies could have accepted other kidneys in the system, while the husband is offering a rare kidney type desperately needed by someone at another hospital. Through the pool, you could pair not just two sets of donors and patients, but many more.
“There is a big efficiency loss when hospitals don’t put their donors into the pool, and it costs lives,” said Ashlagi. “I thought about how I could organize the rules in this market so that more hospitals would participate in the database.”
Ashlagi and Roth came up with a solution that employs a points system for participating hospitals, which alters the matching algorithm. “It’s like a frequent flyer program for hospitals. Hospitals that bring more donors to the system get more points, which then gives preference to that hospital’s list of patients waiting the longest,” said Ashlagi.
By being “good players,” hospitals have a better chance at performing transplants on their most difficult-to-match patients. His idea was adopted by the largest kidney exchange organization in 2014.
Ashlagi has also contributed to the body of research about the benefits of non-simultaneous donation chains using altruistic donors. An altruistic donor is somebody who wants to donate a kidney to help a person without expecting to receive a donation back for a loved one. The chain can start with their gift of the kidney to a needy recipient, then, in the event of an alternate donor for that same recipient, that donor gives one to another different needy recipient, and so on.
In this manner, all kidney recipients receive their kidneys first, before their willing donor gives theirs. This overcomes the nervousness of donors to give a kidney without knowing with certainty that their loved one will receive one in return. According to Ashlagi, it also allows for more matches to be made to save more people.
“This allows for bigger and more flexible chains, as it relaxes the simultaneity constraint in cyclic exchanges,” said Ashlagi. Bigger chains mean more transplants.
However, maximizing the number of transplants in a pool together when long chains are allowed is an extremely computationally difficult problem. Ashlagi, with his team, developed algorithms to solve this in practice, which have been adopted by various kidney exchange programs around the world.
After his postdoc at Harvard, Ashlagi became an assistant professor at MIT. With his students there, he began studying another matching market: public school systems with centralized school assignments.
Ashlagi and his students used data from the city of Boston in an attempt to theoretically fix Boston’s school transportation budget problem. Boston offered each family a large menu of elementary school choices, and parents could rank their choices. Parents often ranked desirable schools that happened to be in another part of town at the top of their preference lists, which led to ballooning transportation costs for the city; about ten percent of the city’s education budget went to buses.
To solve this problem, the logical answer would be to require students to attend schools closer to home. And yet, basing school placement just on geography could perpetuate an achievement gap, since the best schools seemed to be in the highest-income neighborhoods and the lower-performing schools in the lower-income neighborhoods.
Likewise, a simplistic algorithm based only on geography to reduce bus miles, like offering choices within a wider but restricted boundary, could result in great choices for some, but poor options for others.
“We thought that a more sophisticated system of rules could optimize these assignments, so I conducted a project with one of my students at MIT, Peng Shi. Given a budget constraint, we were able to come up with a set of optimal choice menus based on past-preferences data,” said Ashlagi. Every family still saw some high-performing schools on their menus and got to rank their schools (though fewer of them), but the menu options they received were strategically located to, on balance, reduce the school transportation budget.
Peng Shi submitted a simplified version of this idea as a proposal to the city of Boston, and Boston implemented his strategy last year.
Ashlagi is currently working on a study with researchers at Columbia University on two-sided matching markets, such as the National Resident Matching Program (NRMP). This program pairs hospitals with new doctors needing to serve the residency phase of their medical training. It uses a matching algorithm that takes the preferences of each party into account.
The algorithm adopted by the NRMP finds, based on doctors’ and programs’ preferences, a stable matching – this means that once all of the matches have been made, there are no instances of a doctor and hospital mutually preferring each other over their assigned matches.
Theoretically, many stable matchings may exist. However, Ashlagi, with his collaborators, is able to show such a matching is typically unique. This work resolves the issue of which stable matching to implement. Furthermore, if there were many stable matchings possible, participants could manipulate their outcome by the order in which they rank their preferences. The uniqueness of the outcome eliminates any need for “strategic behavior” that could disrupt the system.
In addition to dedication to his research, Professor Ashlagi is enthusiastic about teaching his MS&E classes. “This program has very strong students. It was one of the many factors that attracted me to MS&E at Stanford.”
To read more about him, check out his Stanford MS&E profile: http://web.stanford.edu/~iashlagi/
In the news… California Pacific Medical Center and UCSF recently performed a nine-way kidney swap using an altruistic donor to start the chain. Read more.