Match Day: A new approach to couples in MD residencies

Wednesday, May 15, 2019

Every year, about 20,000 seniors at U.S. medical schools eagerly await the third Friday of March. It's known as Match Day, the day when these soon-to-be doctors learn which hospitals they've been matched with for their residency training.

For more than 65 years, the matches have largely been made through the National Resident Match Program (NRMP), also known as The Match, which owes its longevity and high rate of participation to its effectiveness.

Doctors and hospitals submit lists of their top choices, known as "rank order lists," and the NRMP uses an algorithm to match them. The matching is considered stable if no doctor and hospital can both fare better (move to a higher preference on their lists) by matching with each other outside the NRMP.

When individual doctors submit preference lists, the algorithm, based on the famous Gale-Shapley “deferred acceptance” method, can always find stable matches.

But it gets more complicated when couples are involved. In 2019, about 1,100 couples asked to be matched, hoping to attain positions in the same geographical location. Each couple links its rank order lists through NRMP, which matches them to the most preferred pair of programs where they've been offered positions.

When couples enter the picture, stable matchings are not always possible. However, since the late 1990s, the Roth-Peranson algorithm, a modified version of the deferred acceptance algorithm, has been successful in producing stable matchings. The algorithm is first run without couples, then couples are added one at a time, and anyone displaced is allowed to re-enter.

"The algorithm is still very heuristic," says Thanh Nguyen, assistant professor of management in Purdue's Krannert School of Management. "Theoretically, we don’t really understand why it works so well."

Researchers attribute the success of this algorithm partly to its application in a large market with random preferences and a small proportion of couples. They've shown that when the proportion of couples increases, stable matchings are far less likely. This is important because the proportion of couples (or pairs) varies in other countries or other settings. Without stable matchings, participants may abandon the centralized market, triggering a string of departures that lead to the collapse of the market.

Nguyen and his co-author, Rakesh Vohra of University of Pennsylvania, have proposed an entirely different approach to couples matching, one that finds stable matchings regardless of market size, randomness and the proportion of couples.

In their paper "Near-Feasible Stable Matchings with Couples," published in the November 2018 issue of The American Economic Review, they show that stable matchings can be achieved for couples by altering the initial capacities of hospitals.

It's not uncommon, they state, for hospitals to adjust their capacities. The NRMP lets a hospital choose an even or odd number of physician residents, which suggests that the hospital can reduce its capacity by one. Residency slots sometimes go unfilled or get transferred to another hospital, which also shows flexibility in the number of positions available.

The researchers use an algorithm that, unlike prior algorithms employed in matching problems, does not use the Gale-Shapley deferred acceptance algorithm. It instead uses a combination of Scarf's lemma and the iterative rounding method.

They acknowledge that even a change of two slots can be dramatic at certain hospitals, particularly those in rural areas, where a small number of slots may be available. To mitigate this, they've designed their algorithm to preserve the capacity of a rural hospital if no couple applies to it.

Their initial simulations of the algorithm show that only a small proportion of the hospitals need to adjust their capacities for all the matches to be stable. In their first set of experiments, based on 200 randomly generated instances involving 270 doctors and 18 hospitals, they found that when the proportion of couples is 30 percent, only 7.39 percent of hospitals need to adjust their capacity. Of those, 7.17 percent need to change by one position (up or down) and only 0.22 percent need to change by two positions.

Even when the proportion of couples increases to 90 percent, more than 75 percent of hospitals need not change their capacities, and only 2.53 percent need to make a change by two positions.

"Essentially by reallocating the jobs a little bit, we can make sure that the market is stable," Nguyen says.

What's also notable is that hospitals with low capacities are largely able to maintain their capacities. At a couple proportion of 30 percent, only about 2 percent of hospitals with a capacity of two or smaller needed to change their capacities.

The researchers also conducted a set of experiments based on 1,000 incidents involving 500 doctors. The couples in these incidents had weakly responsive preferences and were thus known to produce stable matchings. These experiments allowed the researchers to see how their algorithm would perform in instances where stable matchings are known to exist. Their algorithm returned stable matchings in all cases. The Roth-Peranson algorithm, on the other hand, often fails to find stable matches when a high proportion of couples are involved.

Nguyen's and Vohra's methodology may be used to redesign the resident matching programs in countries where the proportion of couples is high. It can also be used in other settings, such as when siblings are choosing schools or when teachers are assigned to pairs of majors.

"The methodology applies to a broad range of other problems," Nguyen says.

Citation

Nguyen, Thành, and Rakesh Vohra. 2018. "Near-Feasible Stable Matchings with Couples." American Economic Review, 108 (11): 3154-69. https://www.aeaweb.org/articles?id=10.1257/aer.20141188