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.
@cite_12: We study a class of assortment optimization problems where customers choose among the offered products according to the nested logit model. There is a fixed revenue associated with each product. The objective is to find an assortment of products to offer so as to maximize the expected revenue per customer. We show that the problem is polynomially solvable when the nest dissimilarity parameters of the choice model are less than one and the customers always make a purchase within the selected nest. Relaxing either of these assumptions renders the problem NP-hard. To deal with the NP-hard cases, we develop parsimonious collections of candidate assortments with worst-case performance guarantees. We also formulate a convex program whose optimal objective value is an upper bound on the optimal expected revenue. Thus, we can compare the expected revenue provided by an assortment with the upper bound on the optimal expected revenue to get a feel for the optimality gap of the assortment. By using this approach, our computational experiments test the performance of the parsimonious collections of candidate assortments that we develop.
In the study of assortment optimization problem, an important class of assortment is called the revenue-ordered assortment, in which the assortment is selected according to the revenue order of each product. Revenue-ordered assortment has been shown to be optimal in many assortment optimization problems or has a worst-case performance guarantee (see, e.g., Talluri2004 , rusmevichiengtong_robust , rusmevichiengtong_mmnl , wang_wang ). Indeed, as shown in @cite_12 , the optimal revenue-ordered assortment achieves a worst-case ratio of the optimal revenue under a class of regular discrete choice models''. In this paper, we show that the revenue-ordered assortment is optimal under a special case of the MCST model, and has a worst-case performance guarantee under the general case. Furthermore, in our numerical experiments, we show that the revenue-ordered assortment generally achieves good performance.