Faculty Candidate  Antoine Desir [Columbia] 

Title  Capacity Constrained Assortment Optimization under the Markov Chain based Choice Model 
Date & Time  Monday, February 13, 2017 
Place  UCLA Anderson School of Management Room A301 
Abstract 
Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In such settings, the goal is to select a subset of items to offer from a universe of substitutable items in order to maximize expected revenue when consumers exhibit a random substitution behavior. We consider a capacity constrained assortment optimization problem under the Markov Chain based choice model, recently considered in Blanchet et al. (2016). In this model, the substitution behavior of customers is modeled through transitions in a Markov chain. Capacity constraints arise naturally in many applications to model reallife constraints such as shelf space or budget limitations. We show that the capacity constrained problem is APXhard even for the special case when all items have unit weights and uniform prices, i.e., it is NPhard to obtain an approximation ratio better than some given constant. We present constant factor approximations for both the cardinality and capacity constrained assortment optimization problem for the general Markov chain model. Our algorithm is based on a "localratio" paradigm that allows us to transform a nonlinear revenue function into a linear function. The localratio based algorithmic paradigm also provides interesting insights towards the optimal stopping problem as well as other assortment optimization problems.
