Assortment Planning with Nested Preferences : Dynamic Programming with Distributions as States?

The main contribution of this paper is to develop new techniques in approximate dynamic programming, along with the notions of rounded distributions and inventory filtering, to devise a quasi-PTAS for the capacitated assortment planning problem, originally studied by Goyal, Levi, and Segev (2009). Motivated by real-life applications, their nested preference lists model stands as one of very few settings, where near-optimal assortments and inventory levels can be computed efficiently. However, these findings crucially depend on certain distributional assumptions, leaving the general problem wide open in terms of approximability prior to this work. In addition to proposing the first rigorous approach for handling the nested preference lists model in its utmost generality, from a technical perspective, we augment the existing literature on dynamic programming with a number of promising ideas. These are novel algorithmic tools for efficiently keeping approximate distributions as part of the state description, while losing very little information and while accumulating only small approximation errors throughout the overall computation. From a conceptual perspective, at the cost of losing an eps-factor in optimality, we show how to dramatically improve on the truly exponential nature of standard dynamic programs, which seem essential for the purpose of computing optimal inventory levels