Prof. David Simchi-Levi
Massachusetts Institute of Technology
Talk:
Online Resource Allocation with Applications to Revenue Management
Abstract:
Online resource allocation is a fundamental problem in OR and CS with applications such as offering products to customers, distributing jobs to candidates, assigning advertisers to ad slots, and matching drivers to passengers. These problems can be abstracted as follows: there are fixed resources, each of which can be sold at multiple known prices. These resources must be allocated on-the-fly, without assuming anything about future demand. In this talk we cover the CS and OR literature on the problem and in particular focus on two techniques: exploration and exploitation methods, as well as competitive analysis. In the latter case, we review new algorithms that achieve tight competitive ratios under the integral or asymptotic settings. Our algorithms are simple, intuitive and robust and our competitive ratios are provably optimal, for every possible set of prices. In the former case, we discuss an efficient and effective dynamic pricing algorithm, which builds upon the Thompson sampling algorithm used for multi-armed bandit problems by incorporating inventory constraints into the pricing decisions. The algorithm proves to have both strong theoretical performance guarantees as well as promising numerical performance results when compared to other algorithms developed for the same setting. Finally, we compare the performance of both techniques, exploration and exploitation methods and competitive analysis, with real-world and synthetic data from various retail applications.
