题　目：Batching and Optimal Multi-stage Bipartite Allocations

嘉　宾：Yiding Feng, Ph.D. Research, Northwestern University

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

时　间：2022年11月4日（周四）9:00-10:30am

地　点：腾讯会议（校内师生如需获取会议号和密码，请于11月3日下午17点前发送电邮至managementscience@acem.sjtu.edu.cn）

内容简介:

In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems in the adversarial setting, where online vertices arrive stage- wise and in K batches—in contrast to online arrival. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratio bound known for the online variants of these problems (Mehta et al., 2007; Aggarwal et al., 2011).

Our main technique at high-level is developing algorithmic tools to vary the trade-off between “greedyness” and “hedging” of the matching algorithm across stages. We rely on a particular family of convex- programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight matching linear program to form these convex programs. At each stage, our fractional multi-stage algorithm returns the corresponding regularized optimal solution as the matching of this stage (by solving the convex program). By providing structural decomposition of the underlying graph using the optimal solutions of these convex programs and recursively connecting the regularizers together, we develop a new multi-stage primal-dual framework to analyze the competitive ratio of this algorithm. We further show this algorithm is optimal competitive, even in the unweighted case, by providing an upper- bound instance in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem, AdWords problem, and configuration allocation problem with large budgets/small bid over budget ratios assumptions. This talk is based on joint work with Rad Niazadeh.

演讲人简介：

Yiding Feng is a postdoctoral researcher at Microsoft Research New England, where he is a member of Economics and Computation group. He previously received his PhD from Department of Computer Science, Northwestern University in 2021 where his advisor was Jason D. Hartline. Before that, he received his BS degree from ACM Honors Class at Shanghai Jiao Tong University.

欢迎广大师生参加!