  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.
