Online Assortment Optimization with Reusable Resources

Wednesday, October 3, 2018 - 4:00pm - 4:45pm
Keller 3-180
Vineet Goyal (Columbia University)
We consider an online assortment optimization problem with n substitutable products with reusable capacities. In each period, a user with a preference model (potentially adversarially chosen) arrives to the platform, and is offered an assortment of products that have available capacity. The user selects a product p from the offered assortment according to her choice model and uses it for a random number of periods $T_p$. We assume that $T_p$ that is distributed i.i.d. according to some distribution that depends only on p. Each usage of product p generated a revenue $R_p$ for the platform.

The goal here 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, that 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 novel coupling argument that allows us to bound the expected revenue of the optimal algorithm in terms of the expected revenue of the myopic policy.

Joint work with Garud Iyengar (IEOR, Columbia) and Shuangyu Wang (IEOR, Columbia)