Huseyin Topaloglu
School of Operations Research and Information Engineering
Cornell University
Friday, August 31, 2011
Assortment Optimization under Variants of the Nested Logit Model
Nested logit model allows us to build on a utility-maximization principle to describe how customers choose within an offered assortment of products. Under the nested logit model, a customer associates a random utility with each product, and this random utility has some type of generalized extreme value distribution. In this case, the customer chooses the product that provides the largest utility. The attractive feature of the nested logit model is that it allows the random utilities to be correlated with each other. The products whose utilities are correlated with each other are said to be in the same nest. In this talk, we study assortment optimization problems under the nested logit model. In the canonical assortment optimization problem, a firm chooses an assortment of products to offer to its customers. There is a fixed revenue associated with each product. Customers choose within the offered assortment according to the nested logit model. The goal is to find an assortment that maximizes the expected revenue extracted from each customer. We show that the optimal assortment can be found by solving a linear program. We demonstrate that this result breaks under slight generalizations of the nested logit model, and the assortment optimization problem becomes NP-hard. We give approximation methods for the NP-hard cases.
This is joint work with James Davis from Cornell and Guillermo Gallego from Columbia.