Constant regret dynamic matching
Prof. Sophie H. Yu
Assistant Professor of Operations, Information and Decisions
The Wharton School
University of Pennsylvania
Dynamic matching problems arise when heterogeneous agents arrive over time and must be matched under compatibility constraints, with applications ranging from kidney exchange to mobility and service platforms. A central question is how to design online matching policies that perform nearly as well as an offline benchmark throughout the horizon. In this talk, I will discuss two recent papers that address this question from complementary perspectives. The first develops a primal-dual policy for multi-way dynamic matching that uses adaptive shadow prices, achieves constant regret at all times under unknown arrival rates, and attains optimal dependence on the general position gap when arrival rates are known. The second studies two-way dynamic matching under limited state information and shows that availability-based policies — using only whether queues are empty, rather than queue lengths — can still achieve optimal all-time regret scaling. Together, these works illustrate that near-optimal dynamic matching is possible even when either model parameters are unknown or state information is severely limited, pointing to new design principles for simple, robust, and implementable matching policies.
The first paper is available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4357216
the second paper is available at https://arxiv.org/abs/2503.09762
Sophie H. Yu is an assistant professor at The Wharton School of the University of Pennsylvania. She was a postdoctoral scholar in Management Science and Engineering at Stanford University. She holds a Ph.D. in Decision Sciences from Duke University’s Fuqua School of Business in 2023, an M.S. in Statistical and Economic Modeling from Duke University in 2017, and a B.S. in Economics from Renmin University of China in 2015. Her research focuses on matching, inference, and algorithm design in large-scale networks and stochastic systems. Her research has been recognized by the Thomas M. Cover Dissertation Award from IEEE Information Theory Society, the Fuqua School of Business Best Dissertation Award, and a finalist for the George Nicholson Student Paper Competition.
