Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM] seminar - Flexibility Allocation in Random Bipartite Matching Markets
Supporting the below United Nations Sustainable Development Goals:支持以下聯合國可持續發展目標：支持以下联合国可持续发展目标：
We study how a fixed flexibility budget should be allocated across the two sides of a balanced bipartite matching market. On each side, agents are either regular or flexible, with flexible agents being more likely to connect with agents on the opposite side. In this model, we derive an exact variational formula for the size of a maximum matching for any flexibility allocation (the derivation uses the local weak convergence framework of Bordenave, Lelarge and Salez (2011) by extending it to multi-type trees). Using this formula, we analytically characterize when concentrating all flexibility on one side dominates splitting it across both sides, and vice versa. This complements and sharpens the dominance regimes characterized by Freund, Martin and Zhao (2026), now grounded in an exact characterization of the matching rate rather than approximate algorithmic bounds. The paper is available at https://arxiv.org/abs/2604.02295.
We also study a spatial version of the problem, focusing on how to allocate flexibility across agents on one side of the market. In this setting, supply can serve only demand that is sufficiently close in geographic or attribute space, and flexibility determines the size of each supply unit’s admissible service region. We model the system as a bipartite random geometric graph on $[0,1]^k$, where each supply node serves at most one demand unit and fulfilled demand equals the size of a maximum matching. The objective is to allocate a fixed supply-side flexibility budget ex ante to maximize expected fulfilled demand. We establish a uniformity principle: whenever one supply-side allocation is more uniform than another, the more uniform allocation yields a larger expected maximum matching size. This result reflects diminishing marginal returns to expanding service regions and the limited interference induced by bounded ranges, which naturally fragment the graph. For $k=1$, we further characterize the expected matching size via a Markov chain embedding and derive closed-form expressions for boundary cases. The paper is available at https://arxiv.org/abs/2601.13426.
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.