A Generalized Markov Chain Model to Capture Dynamic Preferences and Choice Overload
This addresses the problem of accurately modeling customer substitution behavior in industries like retail and online advertising, where choice overload can occur, representing an incremental advancement over prior Markov chain models.
The paper tackles the limitation of existing choice models where more options always increase purchase probability, by proposing a generalized Markov chain model that captures choice overload, where sales can decrease with more choices. It shows assortment optimization under this model is NP-hard but presents a fully polynomial-time approximation scheme (FPTAS) under reasonable assumptions.
Assortment optimization is an important problem that arises in many industries such as retailing and online advertising where the goal is to find a subset of products from a universe of substitutable products which maximize seller's expected revenue. One of the key challenges in this problem is to model the customer substitution behavior. Many parametric random utility maximization (RUM) based choice models have been considered in the literature. However, in all these models, probability of purchase increases as we include more products to an assortment. This is not true in general and in many settings more choices hurt sales. This is commonly referred to as the choice overload. In this paper we attempt to address this limitation in RUM through a generalization of the Markov chain based choice model considered in Blanchet et al. (2016). As a special case, we show that our model reduces to a generalization of MNL with no-purchase attractions dependent on the assortment S and strictly increasing with the size of assortment S. While we show that the assortment optimization under this model is NP-hard, we present fully polynomial-time approximation scheme (FPTAS) under reasonable assumptions.