What happens when everyone has an opinion about whom they’d like to be paired with? Whether matching students to schools, residents to hospitals or roommates to one another, accommodating everyone’s preferences is a surprisingly difficult mathematical problem.
That challenge is at the heart of a paper by Christine Cheng, associate professor, computer science, who recently received a best paper award at an international algorithms conference, the MATCH-UP 2026 conference. In the paper, Cheng and coauthor William Rosenbaum of the University of Liverpool ask a deceptively simple question: How do you pair people or organizations so that everyone ends up with the best possible outcome? Their answer is a faster algorithm to solve complex matching problems.
When preferences compete
“Matching is a field that’s of interest primarily to economists, computer scientists, mathematicians, and industrial engineers,” Cheng said. “It’s really multidisciplinary.”
The same mathematical principles can help assign medical residents to hospitals, students to schools of choice, scarce vaccines to priority populations, and other complex problems where people or organizations have competing preferences.
But there are two versions of this problem: In the “Stable Marriage” version, a member from each of two distinct groups is being paired by preference. In the “Stable Roommates” version, anyone can be paired with anyone else.
Cheng and Rosenberg’s paper tackles the latter, more difficult version of the problem, which is more complex and not as well-studied.
A little background on matching
The foundation for modern matching theory dates back to a landmark 1962 paper by David Gale and Lloyd Shapley, who developed an algorithm to solve what became known as the “Stable Marriage” problem where you’re pairing up two sides – men and women in this case.
Decades later, economist Alvin Roth showed that the same approach matched medical residents with hospitals in the United States, demonstrating a remarkable case where mathematical theory and real-world practice converged, said Cheng. Roth and Shapley shared the 2012 Nobel Prize in Economic Sciences for that work.
But neither of these examples describes the “Stable Roommate” problem.
In their paper, Cheng and Rosenbaum dig into the “Stable Roommate” case by first assuming that each person in one large pool assigns a cost, or weight, to every possible partner. The goal is not only to find a stable matching, but the optimal stable matching – the one with the lowest total cost across all pairs.
Generalizing math structure
They do this by looking at the underlying mathematical structure of the easier “Stable Marriage” case. By quantifying how similar a “Stable Roommates” instance is to a “Stable Marriage” instance, the authors designed an algorithm that performs well whenever that gap is small.
“The idea is, if your problem instance is very close to the bipartite, or the two-sided version of the problem, the algorithm will run fast,” Cheng said. “And as you get further and further away, it will be slower.”
The algorithm could influence far more than matching theory if it resolves the matching in a short time frame.
Cheng credits her sabbatical last year with allowing her to focus on this research.
“The sabbatical gives you that downtime where you can have much less interruption,” she said. “And you’re much more able to pursue problems that are more difficult because of that.”