Performance of the Offer-Everything Policy

• 成果类型: Article; Early Access
• 署名作者: Huh, Woonghee Tim; Paat, Joseph; Queyranne, Maurice
• 署名单位: University of British Columbia
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.0417
• 发表日期: 2025
• 关键词: Network Revenue Management; assortment planning problem; algorithms; approximation; optimization; MODEL

摘要

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.