Abstract

Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various nonstationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover the dual subgradient descent and dual multiplicative weights update algorithm. The resulting algorithms are simple, fast, and do not require convexity in the revenue function, consumption function, and action space, in contrast to existing methods for online allocation problems. We discuss applications to network revenue management, online bidding in repeated auctions with budget constraints, online proportional matching with high entropy, and personalized assortment optimization with limited inventory.
Joint work with Haihao Lu (University of Chicago) and Vahab Mirrokni (Google Research)
Paper: https://pubsonline.informs.org/doi/abs/10.1287/opre.2021.2242

Biography

Santiago R. Balseiro is an Associate Professor of Business at the Graduate School of Business, Columbia University, and a senior research scientist at Google Research. His research develops novel methodological approaches that combine dynamic optimization, stochastic modeling, and game theory to address fundamental problems in the digital economy. His work tackles central problems in internet advertising while making methodological contributions to the area of large-scale sequential decision-making in the face of uncertainty and dynamic optimization with incentives. His research has been recognized by numerous awards, including a best dissertation award and multiple best paper awards. He serves as an associate editor for the INFORMS flagship journals Management Science, Operations Research, and Manufacturing & Service Operations Management.

• Admission

Zoom Meeting ID: 878 3052 1709

Password: 221104