Market Design: The Dialog Between Simple Abstract Models and Practical Implementation

The final day of the 2022 INFORMS Annual Meeting began with the Philip McCord Morse Lecture from Alvin E. Roth, Craig and Susan McCaw Professor of Economics at Stanford University and 2012 Nobel Prize winner in economics. Introduced by 2022 INFORMS President Radhika Kulkarni, Roth presented his plenary virtually to a fully-packed room in Indianapolis.

Roth began his talk about market design saying that models and algorithms lead to new theories and dialog that leads to applications – and complications. The majority of his talk would be discussing the deferred acceptance algorithm using three examples: medical residency match, school choice with active and passive schools, and kidney exchange.

In the early 1960s, researchers Gale and Shapley studied the “college admissions model,” which generalizes the marriage matching model in such a way that colleges have preferences over students and students have preferences over colleges. A matching is stable if there isn’t any blocking pair consisting of a firm (college) and worker (applicant) not matched to each other, but who would both prefer to be matched to each other than to their current matched partner(s). Producing a stable match is an important criteria of success.

The deferred acceptance algorithm proposed by Gale and Shapley (1962) has had a profound influence on market design, both directly, by being adapted into practical matching mechanisms, and, indirectly, by raising new theoretical questions. According to Roth, deferred acceptance algorithms are at the basis of a number of labor market clearinghouses around the world, and have recently been implemented in school choice systems in Boston and New York City.

The basic deferred acceptance algorithm uses rank-order listing. Ultimately, an applicant gets chosen and rejects the rest. Each rejected applicant then applies to their next choice if one remains, and firm tentatively assigns. This goes on until there are no applicants left to reject and each worker is assigned to a final tentative assignment. A stable matching exists for every preference of firms and workers. Roth notes that there is no harm in applying to your first choice because there’s just as much chance that you’ll get accepted to your second or third choice.

Redesign of matching market for American physicians: One important difference from the simple models of matching is that some graduating medical students are couples who must be matched as two positions. The problem and the initial “couples algorithm” began in the 1970s when women in the medical field began to increase. Couples could register for the match as a couple and had to specify one member of the couple as the “leading member.” They submitted a separate rank-order list of positions for each member of the couple. The leading member went through the match as a single. The other member then had their rank-order list edited to remove positions not in the “same community” (or city) as the one the leading member had matched to. This did not work well for couples.

Couples consume pairs of jobs, so an algorithm that only asks for their preference orderings over individual jobs can’t hope to avoid instabilities. Why is the couples problem hard? The ordinary deferred acceptance algorithm won’t, in general, produce a stable match (even when one exists). In the worker proposing algorithm, if firms chose the worker and offers are held, but one in the couple is later displaced by another worker, then the couple has to go to their next choice. This is a blocking pair. Roth noted, there are “random paths to stability in two-sided matching.” Two-sided matching finds the blocking pairs and fixes them. This model runs the National Resident Matching Program for medical residency matching!

This model was next used on school choice with deferred acceptance in New York City. Here, the schools are active players – principals play an active role much like the hospitals in the couple matching. Many children are equally preferred and you have to choose among them, which often leads to using tie-breaking. This would mean playing make believe that one student is better than another in order to introduce blocking pairs, which have to be fixed. Other cities with school choice have passive schools (e.g., Boston), so students are treated as objects in the matching model.

Roth explained, you start by breaking ties and give students a lottery number – priorities of students at schools are augmented with random lottery numbers for tie-breaking, if needed. The next steps remain similar to the basic deferred acceptance algorithm (student applies, firm accepts/rejects, continues on until there are no more applicants to reject).

School choice can also use the housing market model, in which each school is a “house” – each agent has preferences over all the houses and there is no money, trade is feasible only in houses (schools). Gale’s top trading cycles (TTC) algorithm works as follows: each agent chooses their most preferred house (and each house points to its owner). There is at least one cycle in the resulting directed graph (a cycle may consist of an agent pointing to their own house). In each such cycle, the corresponding trades are carried out and these agents are removed from the market together with their assignments. The process continues until no agents and houses remain.

When preferences are strict, Gale’s TTC algorithm yields the unique allocation in the core (this implies that the order in which cycles are removed doesn’t change the outcome).

When working on the school choice problem, Roth’s recommendation to the Boston School Committee was the deferred acceptance algorithm, which was accepted by school superintendent Payzant in 2005. There was a lot of sentiment in Boston for changing to this system. They did not choose TTC because it is less transparent and therefore more difficult to explain to parents.

With that feedback, by 2012, Roth learned that they should offer school districts not just algorithms, but also communications packages.

Another city, New Orleans, chose TTC. How can we better explain TTC to parents? The orders in which you operate your cycles doesn’t matter. TTC operates as if we will consult your preferences only after processing all cycles that do not contain you. So, when looking at your preferences, you will form a cycle with whatever item you point to as your first choice among the remaining items. It is safe to tell your true preferences because you will get whatever you ask for using TTC.

For his final matching market example, Roth looks at kidney exchange and how to allocate them (as it turns out, kidney exchange is too complicated to use TTC). Kidney exchange can increase living donation and the best outcome is transplant. One option is a simple two-pair kidney exchange. For incentive reasons, all surgeries in a simple exchange are conducted simultaneously in the U.S., so a two-way exchange involves four simultaneous surgeries (four operating rooms and four surgical teams). TTC could lead to cycles with 10 pairs, which would be 20 simultaneous surgeries, which is a hard problem.

Suppose exchanges involving more than two pairs are impractical? (TTCs might produce infeasibly long cycles, as noted above.) Initially, kidney exchanges were restricted to pairs, which involves a substantial welfare loss compared to the unconstrained cased. But it also allows Roth to tap into some elegant graph theory for constrained efficient and incentive compatible mechanisms.

Patient-donor pairs by blood type, but this is not the only thing that matters in a match. More than half of kidney exchanges are done through chains (kidney-pair donation). Donor chains work similarly to paired kidney donations, in that they take advantage of healthy and willing – but incompatible – donors. The chain is initiated by what is called a non-directed donor, or someone who offers to donate a kidney without a designated recipient, but with the explicit wish to donate to someone in need of a transplant. Kidneys from non-directed donors are used to initiate a cluster of kidney transplants for incompatible donor/recipient pairs.

Roth concluded the kidney exchange example by sharing a photo of himself present for the very first kidney exchange between Abu Dhabi and Israel in 2021. He noted that international kidney exchange is not as far along as in the U.S., but he’s working on that. And as a reminder, kidney donation/transplant is cheaper than dialysis! For more about this fascinating effort, read his joint work in Management Science, “Kidney Exchange: An Operations Perspective.”