Performance of the Offer-Everything Policy

We study a dynamic assortment optimization problem over a finite selling horizon with exogenously fixed initial inventory for multiple products. The manager offers an assortment in each period. The assortment cannot depend on arriving customer types because the manager does not see the customer type before making the assortment decision and thus cannot treat customer types differently. Focusing on an online setting where all products have the same price, we show a competitive ratio cannot be higher than 1/2 against an adversary. This adversary knows the sequence of arrivals and also knows exactly which product each customer purchases depending on the assortment offered. We show that a commonly used policy that offers all available products in each period achieves a competitive ratio of 1/2, matching the upper bound. In fact, we prove a stronger result. For each problem instance, this policy achieves the best worst-case performance over all possible customer arrival sequences. We discuss extensions to nonidentical prices and randomized policies. We also extend our model to the case where the manager decides the initial inventory levels in addition to assortments in each period.

Funding: W. T. Huh was supported by Canada Research Chair Program and the Natural Sciences and Engineering Research Council (NSERC) of Canada [Discovery Grant RGPIN 2020-04213]. J. Paat was supported by the NSERC [Discovery Grant RGPIN-2021-02475].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2021.0417.