Abstract:
We build a new unified modeling and analysis framework for a broad class of online matching problems. The proposed unified framework encompasses a number of classical online matching problems and accommodates three practical features: reusable resources, network resources and decaying rewards. Under the unified framework, we provide a unified performance analysis tool for greedy and greedy-like policies, measured by competitive ratios under the adversarial environment, and prove that greedy-like policies can achieve near-optimal performances. We then dig deeper into several representative special classes of online matching problems, which impose additional realistic structural assumptions on top of the unified framework. We prove that slight modifications to greedy-like policies can successfully utilize additional information of action spaces and resource structures to greatly enhance policy performances.
Bio:
Feng Zhu is currently a second-year PhD student at MIT, affiliated with Institute for Data, Systems, and Society (IDSS) and Laboratory for Information and Decision Systems (LIDS). He is advised by Prof. David Simchi-Levi. His research interests lie in understanding simple algorithms and designing efficient policies for online matching and online learning problems, with applications to operations research and revenue management. On the practical side, he has been working on supply chain resiliency for different companies. Prior to coming to MIT, Feng received a bachelor degree in Statistics and a minor degree in Economics from Peking University in 2020.