Technical note-capacitated assortment optimization under the multinomial logit model with nested consideration sets

We study capacitated assortment problems when customers choose under the multinomial logit model with nested consideration sets. In this choice model, there are multiple customer types, and a customer of a particular type is interested in purchasing only a particular subset of products. We use the term consideration set to refer to the subset of products that a customer of a particular type is interested in purchasing. The consideration sets of customers of different types are nested in the sense that the consideration set of one customer type is included in the consideration set of another. The choice process for customers of different types is governed by the same multinomial logit model except for the fact that customers of different types have different consideration sets. Each product, if offered to customers, occupies a certain amount of space. The sale of each product generates a certain amount of revenue. Given that customers choose from among the offered products according to the multinomial logit model with nested consideration sets, the goal of the assortment problem is to find a set of products to offer to maximize the expected revenue obtained from a customer, while making sure that the total space consumption of the offered products does not exceed a certain limit. We show that this assortment problem is NP-hard, even when there is no limit on the total space consumption of the offered products. Motivated by this complexity result, we give a fully polynomial time approximation scheme for the problem.