When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications
Abstract
In several applications of real-time matching of demand to supply in online marketplaces ---for example matching delivery requests to dispatching centers in Amazon or allocating video-ads to users in YouTube --- the platform allows for some latency (or there is an inherent allowance for latency) in order to batch the demand and improve the efficiency of the resulting matching. Motivated by these scenarios, I investigate the optimal trade-off between batching and inefficiency in the context of designing robust online allocations in this talk. In particular, I 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 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 extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios. I will also briefly mention a recent extension of these results to the multi-stage configuration allocation problem and its applications to video-ads.
The talk is a based on the following two working papers:
(i) "Batching and Optimal Multi-stage Bipartite Allocations",
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3689448
(ii) "Optimal Multi-stage Configuration Allocation with Applications to Video Advertising"
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3924687
Bio
Rad Niazadeh is an Assistant Professor of Operations Management at The University of Chicago Booth School of Business. Prior to joining Chicago Booth, he was a visiting researcher at Google Research NYC and a Motwani postdoctoral fellow at Stanford University, Computer Science Department. He obtained his PhD in Computer Science (minored in Applied Mathematics) from Cornell University. He primarily studies the interplay between algorithms, incentives, and learning, with the goal of advancing the theoretical methodologies and foundations of market design and operations in dynamic and complex environments. On the practical side, his research aims to build generic frameworks to design faster and economically efficient online marketplaces, and also to help with addressing humanitarian needs (such as equity, fairness, and non-discrimination) in operations of govermnetal agencies and non-profit organizations. Rad has received several awards for his research, including the INFORMS Auctions and Market Design 2021 Rothkopf Junior Researcher Paper Award (first place), the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention), the Google PhD Fellowship in Market Algorithms, the Stanford Motwani fellowship, and the Cornell Jacobs fellowship.
