Operations Research Seminar - Rad Niazadeh

— 4:00pm

Location:
In Person - Tepper Building 4219

Speaker:
RAD NIAZADEH, Assistant Professor of Operations Management, and Asness Junior Faculty Fellow, Booth School of Business, The University of Chicago
https://faculty.chicagobooth.edu/rad-niazadeh

 In many real-time matching applications in online marketplaces—such as matching riders to drivers in ride-sharing or allocating video ads to YouTube users—the platform allows (or inherently has) some latency to batch demand and improve efficiency in non-stationary environments. Motivated by these scenarios, I investigate the optimal trade-off between batching and inefficiency in designing online allocations under non-stationary arrivals. In particular, I consider a variant of the classic adversarial online bipartite allocation family of problems where demand arrives stage-wise in batches rather than fully online. Our main result is an optimal-competitive (fractional) matching algorithm, improving the classic competitive ratio known for the online variants [Mehta et al., 2007; Aggarwal et al., 2011]. 

Time permitting, I will briefly discuss a generalization to multistage configuration allocations and its applications to video display advertising and AdX.   Our main technique is to develop algorithmic tools that vary the trade-off between “greediness” and “hedging” across stages. We rely on a particular family of convex-programming-based matchings that distribute demand in a specifically balanced way among supply across different stages, while carefully adjusting the resulting matching. More precisely, we identify a unique sequence of polynomials with decreasing degrees to serve as strictly concave regularizers for the basic linear program at each stage. At each stage, our multi-stage algorithm solves the corresponding convex program to obtain the regularized optimal matching. By providing a structural decomposition (tied to these convex programs) of the subgraph at each stage and recursively connecting the regularizers, we develop a new multi-stage primal-dual framework to analyze the competitive ratio. For the extension to multi-stage configuration allocation, we propose a new idea of regularizing separately at different price levels and analyze the resulting price-level convex programming-based multi-stage algorithm with another primal-dual argument. The talk is based on two papers:

  • Paper 1  ( Joint with Yiding Feng, Management Science 2024)
  • Paper 2  ( Joint with Yiding Feng and Amin Saberi, Operations Research 2023)


Rad Niazadeh is an Assistant Professor of Operations Management and Asness Junior Faculty Fellow at The University of Chicago Booth School of Business. He is also part of the faculty at Toyota Technological Institute of Chicago (TTIC) by a courtesy appointment. Prior to joining Chicago Booth, he was a visiting researcher at Google Research NYC and a postdoctoral fellow at Stanford University, Computer Science Department. He finished his PhD in Computer Science (minored in Applied Mathematics) at Cornell University. Rad primarily studies the theory and applications of online algorithms, online learning, and mechanism design. His research aims to design market algorithms and mechanisms for real-time operations of online marketplaces and e-commerce platforms, as well as operations of governmental agencies and non-profit organizations. 

Rad has received several awards for his research, including the INFORMS Auctions and Market Design Rothkopf Junior Researcher Paper Award (2021, 2024: first place, 2023:second place), the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention), IJCAI 2024 Distinguished Paper Award, MSOM Best Student Paper (first place), Service Science Best Student Paper (third place), and the Google PhD Fellowship (in Market Algorithms). 

Add event to Google
Add event to iCal