Title: Assortment Optimization under a Single Transition Model,
Abstract: In this paper, we consider a Markov chain choice model with single
transition. In this model, customers arrive at each product with a certain
probability. If the arrived product is unavailable, then the seller can
recommend a subset of available products to the customer and the customer will
purchase one of the recommended products or choose not to purchase with certain
transition probabilities. The distinguishing features of the model are that the
seller can control which products to recommend depending on the arrived product
and that each customer either purchases a product or leaves the market after
one transition.
We study the assortment optimization problem under this model. Particularly,
we show that this problem is generally NP-Hard even if each product could only
transit to at most two products. Despite the complexity of the problem, we
provide polynomial time algorithms for several special cases, such as when the
transition probabilities are homogeneous with respect to the starting point, or
when each product can only transit to one other product. We also provide a
tight performance bound for revenue-ordered assortments. In addition, we
propose a compact mixed integer program formulation that can solve this problem
of large size. Through extensive numerical experiments, we show that the
proposed algorithms can solve the problem efficiently and the obtained
assortments could significantly improve the revenue of the seller than under
the Markov chain choice model.