This month, newly minted doctors and military cadets are leaving the University of Virginia and many other schools for assigned residency and branch assignments around the globe. These movements number in the millions, but most are directed by a simple class of “matching algorithms” – algorithms that one U.Va.-led research team wants to make more efficient and fair.
Peter Troyan, an assistant professor of economics, became interested in the match algorithm while a friend in medical school was anxiously awaiting his residency assignment. Troyan was eager to understand the equation that was driving the next steps of his friend’s life and those of many others worldwide.
As any good economist would, Troyan dove into the numbers, examining the minutiae of the accepted formula. What he found troubled him and spurred him to create a new version of the match algorithm, along with colleagues Daniel Fragiadakis, Atsushi Iwasaki, Suguru Ueda and Makoto Yokoo. Their new algorithm, Troyan contends, is less wasteful, more fair and more satisfying to the students, cadets and employees at its mercy.
Rethinking Maximum Quotas
Every year, students completing medical school submit ranked preferences to the National Resident Matching Program. The traditional match algorithm uses student preferences and maximum quotas for the number of residents assigned to each hospital to determine who goes where. In the medical field, for example, lower maximum quotas might be imposed on popular urban hospitals so that lesser-known rural hospitals have enough doctors to provide care (an approach that is followed by the program’s Japanese equivalent).
This is an admirable goal, but Troyan’s research, soon to be published in the Association for Computing Machinery’s Transactions on Economics and Computation journal, revealed glaring inefficiencies. In many cases, current maximum quotas are determined before preferences are even submitted and therefore regularly eliminate more seats than necessary at popular locations. This tends to result in wasted seats and needless dissatisfaction among cadets, doctors or employees whose preferences are not met.
How, Troyan and his team wondered, can you eliminate this waste while still providing enough doctors for rural hospitals or enough cadets for far-flung military bases?
Their answer is deceptively simple: focus on minimums instead of maximums.
Building a Better Norm
Instead of artificially capping seats at popular positions, Troyan’s new algorithm takes the minimum quota needed to staff each location and uses this information, together with the student preferences, to more flexibly assign the students to positions that they more highly prefer.
“If you eliminate spots using only inflexible maximum quotas, fewer people will be able to go where they want to go,” he said. “Using our mechanism, you allow more people to go where they want to go,” while still giving each area precisely the number of people that it needs.
Troyan and his colleagues designed two versions of their new algorithm, one that prioritized fairness and minimized wastefulness as a secondary goal, and one that minimized wastefulness and promoted fairness as a secondary goal. Both algorithms were, however, designed to be strategy-proof, meaning that individuals can always rest assured that the optimal way to report their preferences would be to state them truthfully. This is a common goal in the field of matching, and prevents enterprising young doctors or employers from gaming the system or having unfair advantages over others who are less able to strategize.
Simulations show that the new algorithm “outperforms the simple solution of artificial caps with respect to nonwastefulness, fairness and student welfare,” Troyan states in his research. He is confident that doctors, cadets and others whose careers and personal lives depend on matching will prefer the new method.
Seeking New Applications
Buoyed by this success, Troyan is currently researching further applications for the new algorithm, especially in primary and secondary school selection procedures that are based in part on parent preferences. Troyan wants to use minimum quotas to ensure appropriate socioeconomic diversity in school assignments by factoring in minimums for different demographic factors. The result, he believes, would help to encourage diversity in schools while maximizing student and parent satisfaction.
“We’re not pushing this as the absolute best way to do this, but if a school district did desire to have some minimum quota that needed to be satisfied, then our way would be a better option than what might currently be happening,” he said. “This is not the only way to get diversity in schools, but we have designed the algorithms and now it becomes a policy question.”
The same is true for medical matching and military cadet assignments. Troyan and his team have provided a new base equation that could change the paradigm of matching assignments. Such a change would widely impact rising generations of students. At U.Va. alone, 156 medical school students from the Class of 2015 were assigned to residency programs and 39 U.Va. ROTC graduates were commissioned for military assignments.
For these students and many more who will follow in their footsteps, the numbers and symbols of Troyan’s match algorithm catalyze a palpable ripple effect that will impact their lives for years to come.