Bounds, Heuristics, and Prophet Inequalities for Assortment Optimization

Assortment managers are often concerned with the problem of finding optimal or near-optimal assortments subject to side constraints. To address this concern, we develop easily computable bounds and heuristics for the traditional assortment optimisation problem (TAOP) with totally unimodular (TUM) constraints. Our heuristics use minimal choice information, are very fast, perform very well and have performance guarantees. Managers are also concerned with assessing the benefits of personalised assortments. To upper-bound such benefits we introduce a clairvoyant firm that sells to each consumer the most profitable product that she is willing to buy (if any). For regular discrete-choice models, we show that the clairvoyant firm can earn up to $n$ times more than a TAOP firm, where $n$ is the number of products. However, for choice models with independent value gaps, we show that the prophet inequality applies, so a clairvoyant firm can make at most twice as much as a TAOP firm. We develop sufficient conditions to extend the prophet inequality for products with dependant value gaps, and show that it holds for the $\alpha$-shaken multinomial logit (MNL) model that includes the MNL and the generalised attraction model (GAM) as special cases. For the latent-class MNL, we show that the ratio is at most 1.5 when the coefficients of variation of the product’s utilities go to infinity. Personalised assortments can improve consumers’ surplus. This is not the case for pricing, where a clairvoyant firm can earn extract all consumers’ surplus and earn arbitrarily more than a firm that does not personalise prices. For the MNL, however, the clairvoyant firm can earn only up to $\exp(1)$ times more than a firm that does not personalise prices.