Online Assortment Optimization with Reusable Resources

Professor Garud Iyengar
D3 W122

We consider an online assortment optimization problem with n substitutable products with reusable capacities. In each period, a user with a preference model arrives to the platform, and is offered an assortment of products. The user selects a product p from the offered assortment according to her choice model and uses it for a random number of periods Tp, where Tp is i.i.d. distributed based on some distribution depending only on p. Each usage of product p generates a revenue (Rp) for the platform. The goal is to compute a policy that maximizes the expected revenue of the platform over a finite horizon. In this talk we show that a simple myopic policy, which does not require any information about future arrivals or the distributions of usage time, provides a good approximation with respect to a clairvoyant optimal that has full information about the sequence of user types (or choice models) and the usage time distributions. In particular, we show that our myopic policy is 1/2-competitive. Our analysis is based on a coupling argument that allows us to bound the expected revenue of the optimal algorithm in terms of the expected revenue of the myopic policy.


Garud Iyengar is a Professor in the Industrial Engineering and Operations Research Department in the School of Engineering and Applied Science at Columbia University. He received his B. Tech. in Electrical Engineering from IIT Kanpur, and an MS and PhD in Electrical Engineering from Stanford University. His research interests are broadly in information theory, control and optimization. His published works span a diverse range of fields, including information theory, applied mathematics, computer science, operations research, and financing engineering. His current projects focus on the areas of large scale portfolio selection, sports analytics, quantitative marketing, smart grids, and systems biology.