Assortment Optimization Over Time

In this note, we introduce the problem of assortment optimization over time. In this problem, we have a sequence of time periods and can only introduce one new product per time step, and we are not allowed to remove products from our assortment that have already been introduced. The goal is to determine which products to introduce so as to maximize the total revenue realized over all the time steps under some choice model. We show how to give a 1/2-approximation algorithm for this problem under a general choice model, for which the multinomial logit choice model is a special case. We further show a (1 − 1/e)-approximation algorithm if the revenue function is monotone and submodular. Finally, we show that the problem is NP-hard to compute for a natural special case of the general choice model whose revenue function is monotone and submodular.