A Markov Chain Approximation for Choice Modeling

Assortment planning is an important problem that arises in many industries such as retailing and airlines. One of the key challenges in an assortment planning problem is to identify the ``right model'' for the substitution behavior of customers from the data. Error in model selection can lead to highly sub-optimal decisions. In this paper, we present a new choice model that is a simultaneous approximation for all random utility based discrete choice models including the multinomial logit, the nested logit and mixtures of multinomial logit models. Our model is based on a new primitive for substitution behavior where substitution from one product to another is modeled as a state transition of a Markov chain.
 
We show that the choice probabilities computed by our model are a good approximation to the true choice probabilities of any random utility discrete based choice model under mild conditions. Moreover, they are exact if the underlying model is a Multinomial logit model. We also give a procedure to estimate the parameters of the Markov chain model that does not require any knowledge of the latent choice model. Furthermore, we show that the assortment optimization problem under our choice model can be solved efficiently in polynomial time. This is quite surprising as we can not even express the choice probabilities using a functional form. Our numerical experiments show that the average maximum relative error between the estimates of the Markov chain choice probability and the true choice probability is less than 3% (the average being taken over different offer sets). Therefore, our model provides a tractable data-driven approach to choice modeling and assortment optimization that is robust to model selection errors.