In many application of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching, where online vertices arrive in K batches. 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 ratios known for the online variant of these problems (Mehta et al., 2007; Aggarwal et al., 2011).

Our main technique is identifying a particular sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers. We then show the fractional online algorithm that returns the corresponding regularized maximum weight fractional matchings in each stage (by solving a convex program) is (1-(1-1/K)^K)-competitive. We further show a matching upper bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to more general settings including the AdWords problem, assortment problem, and configuration allocation problem.

This talk is based on the joint work with Rad Niazadeh (Chicago Booth). The preliminary conference version and final journal version appear in ITCS 2021 and Management Science 2024.

Yiding Feng is an assistant professor at HKUST IEDA. Previously, he worked as a principal researcher at the University of Chicago Booth School of Business, and postdoctoral researcher at Microsoft Research New England. He received his Ph.D. from the Department of Computer Science, at Northwestern University in 2021. His research focuses on operations research, economics & computation, and theoretical computer science. He was the recipient of the INFORMS Auctions and Market Design (AMD) Michael H. Rothkopf Junior Researcher Paper Prize (second place), and the APORS Young Researcher Best Paper Award.