Optimality of The Offer-everything Policy

We study a sequential 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. Finally, we discuss extensions to non-identical prices and randomized policies.