The Stability of Dynamic Consumption under the Multinomial-Logit Model and its Algorithmic Implications

We study the joint assortment planning and inventory management problem, where stock-out events elicit

dynamic substitution effects, described by the Multinomial Logit (MNL) choice model. Up until the recent work of Aouad, Levi, and Segev (Operations Research, forthcoming), where a constant-factor approximation is proposed for demand distributions with an increasing failure rate, this problem was not known to admit efficient algorithms with analytical performance guarantees, and most of its computational aspects still remain wide open. 

Our main contribution is to show that MNL-based dynamic assortment planning admits a polynomial-time approximation scheme, for any demand distribution. This two-fold improvement is attained subject to a realistic assumption, asking the preference weights of all products to be within an O(1)-factor of each other. Our algorithmic approach relies on understanding how the expected revenue function behaves under small perturbations to the preference weights, which enables us to employ efficient enumeration ideas.

This talk is based on a joint work with Ali Aouad (London Business School and Uber).