Which set of products should be offered to arriving consumers to maximize expected revenue? This is a core revenue management problem known as assortment optimization which applies to a wide variety of settings. Discrete choice model theory offers a way to mathematically model the substitution behavior of consumers and provide a key ingredient for this problem. Many choice models have been proposed in the literature, introducing a fundamental tradeoff between model expressiveness and computational complexity. In particular, the assortment optimization problem is notoriously hard for general choice models.

In this talk, we look at a new framework which tries to strike a good balance between expressiveness and tractability. In particular, the substitution behavior of consumers is modeled as transitions in a Markov chain. By doing so, this new model helps alleviate the Independence of Irrelevant Alternatives (IIA) property, a well-known limitation of the popular multinomial logit model. Moreover, it provides a good approximation to the class of random utility models. We show that not only this model has a great predictive power; it is also tractable from a computational perspective. In particular, we give an algorithm framework to derive efficient algorithm for different variants of the assortment optimization problem.