Assortment planning arises in many industries such as retailing and airlines. A key challenge in assortment planning is to identify the “right model” for the substitution behavior of customers from the data. Model selection error can lead to highly sub-optimal decisions. We present a new choice model that is a simultaneous approximation for all random utility based discrete choice models including the multi-nomial 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 surprising as we can not 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%.
(After the seminar, the speaker will be available to discuss the IEOR graduate program with students)
Vineet Goyal joined the IEOR Department at Columbia University in 2010. He received his Bachelor's degree in Computer Science from IIT Delhi in 2003 and his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University in 2008. Before coming to Columbia, he spent two years as a Postdoctoral Associate at the Operations Research Center at MIT. He is interested in the development of tractable approaches for dynamic optimization problems under uncertainty and their applications in electricity markets and revenue management.