Display Optimization Under the Multinomial Logit Choice Model : Balancing Revenue and Customer Satisfaction

In this paper, we consider an assortment optimization problem in which a platform mustchoose pairwise disjoint sets of assortments to offer across a series of T stages. Arrivingcustomers begin their search process in the first stage and progress sequentially throughthe stages until their patience expires, at which point they make a multinomial-logit-basedpurchasing decision from among all products they have viewed throughout their searchprocess. The goal is to choose the sequential displays of product offerings to maximizeexpected revenue. Additionally, we impose stage-specific constraints that ensure that as eachcustomer progresses farther and farther through the T stages, there is a minimum level of“desirability” met by the collections of displayed products. We consider two related measuresof desirability: purchase likelihood and expected utility derived from the offered assortments.In this way, the offered sequence of assortment must be both high earning and well-liked,which breaks from the traditional assortment setting, where customer considerations aregenerally not explicitly accounted for.We show that our assortment problem of interest is strongly NP-Hard, thus ruling out theexistence of a fully polynomial-time approximation scheme (FPTAS). From an algorithmicstandpoint, as a warm-up, we develop a simple constant factor approximation scheme inwhich we carefully stitch together myopically selected assortments for each stage. Ourmain algorithmic result consists of a polynomial-time approximation scheme (PTAS), whichcombines a handful of structural results related to the make-up of the optimal assortmentsequence within an approximate dynamic programming framework