Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM seminar] - Advancements in Dynamic Matching: Approximation Schemes and Simple Policies
In many real-world markets and supply chains, the central planner does not control the availability of suppliers or resources. Instead, the “market thickness” is the result of a dynamic process, which affects matching efficiency. Motivated by ride-hailing, digital labour markets in the gig economy, and organ donation schemes, we study the dynamic (or stationary) bi-partite matching problem. Customers arrive according to a Poisson process and must be immediately matched to available suppliers within a network of queues. Suppliers replenish independently and abandon the market after some time.
This talk will present new results on the design and performance analysis of matching policies. Previous literature concentrates on static policies—where the matching decisions do not use real-time information. We develop a tighter linear programming (LP) framework that enables near-optimal adaptive matching policies. Our main result is a fully polynomial-time approximation scheme for both Euclidean networks and small networks. A key insight is that the network can be roughly divided into a “thin” market and a “thick” market. Our LP-rounding approach is hybrid as it combines dynamic programming for the “thin” component and fluid drift analysis for the “thick” component.
Additionally, we will briefly mention improved results for the general case using simple adaptive policies. Each supplier may randomly propose to match with an arriving customer, who selects the best proposal. Modelling the correlation structure in the design of the proposals and the analysis of the system is critical for beating the best-known performance guarantees.
Our theoretical findings pave the way for developing more efficient and effective matching policies applicable to a range of dynamic, real-world markets.
The first part is a joint paper with Alireza AmaniHamedani (London Business School) and Amin Saberi (Stanford)
The second part is a joint paper with Alireza AmaniHamedani (London Business School), Tristan Pollner (Stanford), and Amin Saberi (Stanford)
Ali Aouad is currently an Assistant Professor of Sloan School of Management at MIT. He is an associate editor in Operations Research and Management Science. In 2018-2019, he was an applied scientist in the Marketplace Optimization group at Uber Technologies. He received a PhD in Operations Research from MIT. Before MIT, I earned an MS in Applied Mathematics from the Ecole Polytechnique (Paris) in 2013.
His research primarily focuses on algorithms under uncertainty and data-driven decision-making with applications in supply chains, market design, and public sector issues. A central objective of his work is to improve the efficiency and equity of digital marketplaces, particularly using assortment and matching optimization.