مدل های انتخاب زنجیره مارکوف
Abstract
۱٫ Introduction
۲٫ Model and notation
۳٫ Main result
۴٫ Proof of Theorem 1
۵٫ Sample complexity
۶٫ Discussion
Declaration of Competing Interest
Acknowledgements
References
Abstract
This work studies the parameter identification problem for the Markov chain choice model of Blanchet, Gallego, and Goyal used in assortment planning. In this model, the product selected by a customer is determined by a Markov chain over the products, where the products in the offered assortment are absorbing states. The underlying parameters of the model were previously shown to be identifiable from the choice probabilities for the all-products assortment, together with choice probabilities for assortments of all-but-one products. Obtaining and estimating choice probabilities for such large assortments is not desirable in many settings. The main result of this work is that the parameters may be identified from assortments of sizes two and three, regardless of the total number of products. The result is obtained via a simple and efficient parameter recovery algorithm.
Introduction
In assortment planning, the seller’s goal is to select a subset of products (called an assortment) to offer to a customer so as to maximize the expected revenue. This task can be formulated as an optimization problem given the revenue generated from selling each product, along with a probabilistic model of the customer’s preferences for the products. Such a discrete choice model must capture the customer’s substitution behavior when, for instance, the offered assortment does not contain the customer’s most preferred product. Our focus in this paper is the Markov chain choice model (MCCM) proposed by Blanchet et al. [2]. This MCCM chooses to model the product selected by the customer as a Markov chain over products where the products in the offered assortment are absorbing states. The current state represents the desired product; if that product is not offered, the customer transitions to another product according to the Markov chain probabilities, and the process continues until the desired product is offered or the customer leaves. MCCM generalizes widely-used discrete choice models such as the multinomial logit model [6,8], as well as other generalized attraction models [5]; it also well-approximates other random utility models found in the literature such as mixed multinomial logit models [7]. At the same time, the MCCM permits computationally efficient unconstrained assortment optimization as well as efficient approximation algorithms in the constrained case [2,4]; this stands in contrast to some richer models such as mixed multinomial logit models [9] and the nested logit model [3] for which assortment optimization is generally intractable. This combination of expressiveness and computational tractability makes MCCM very attractive for use in assortment planning. A crucial step in this overall enterprise—e.g., before assortment optimization may take place—is the estimation of the choice model’s parameters from observational data. Parameter estimation for MCCM is only briefly considered in the original work of Blanchet et al. [2].