题　目：Constant Regret Primal-Dual Policy for Multi-Way Dynamic Matching

嘉　宾：于昊洋，博士后研究员，斯坦福大学

主持人：孙海龙 助理教授 上海交通大学安泰经济与管理学院

时　间：2024年1月10日（周三）10:00-11:30am

地　点：腾讯会议（校内师生如需会议号和密码，请发邮件至yuxin.su@sjtu.edu.cn获取）

内容简介：

We study a discrete-time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to determine an optimal basis of the fluid relaxation, and focus on controlling the number of waiting agents using only matches within the optimal basis (Kerimov et al., 2021a,b; Gupta, 2021). In this paper, we propose a primal-dual policy that schedule matches for future arrivals based on an estimator for the dual solution. Our policy does not require the knowledge of the arrival rates and operates with greater flexibility as it does not restrict matches to only the match types within an optimal basis. We show that our policy is first to achieve constant regret at all times under unknown arrival rates, and when the arrival rates are known, it achieves the optimal scaling as the lower-bound described in Kerimov et al. (2021a,b). Furthermore, when the arrival rates are known, the primal-dual policy significantly outperforms alternative dynamic matching policies in several numerical simulations. Here is the paper link: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4357216 

演讲人简介：

Sophie Yu a Postdoctoral Scholar under Prof. Itai Ashlagi and Prof. Amin Saberi, at Management Science and Engineering, Stanford University. She received her Ph.D. in Decision Sciences from the Fuqua School of Business at Duke University, under Prof. Jiaming Xu and Prof. Yehua Wei. She visited the Simons Institute for the Theory of Computing as a visiting graduate student in Fall 2021. She received her M.S. in statistical and economic modeling under Prof. Jerry Reiter from Duke University in 2017, and her BS in Economics from Renmin University of China in 2015. Her research interests focus on data analysis, algorithm design, and performance evaluation in large-scale networks and stochastic systems. Her works draw inspiration from real-world business, engineering, and natural sciences problems that can be modeled into large and complex networks. She has explored a range of topics, from the fundamental limits and efficient algorithms on network alignment to online platform policy design with bounded regret and data confidentiality protection.

欢迎广大师生参加！