Online Assortment Optimization with Reusable Resources

Xiao-Yue Gong (), Vineet Goyal (), Garud N. Iyengar (), David Simchi-Levi (), Rajan Udwani () and Shuangyu Wang ()
Additional contact information
Xiao-Yue Gong: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Vineet Goyal: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Garud N. Iyengar: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
David Simchi-Levi: Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Rajan Udwani: Industrial Engineering and Operations Research, University of California Berkeley, Berkeley, California 94720
Shuangyu Wang: Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Management Science, 2022, vol. 68, issue 7, 4772-4785

Abstract: We consider an online assortment optimization problem where we have n substitutable products with fixed reusable capacities c 1 , … , c n . In each period t , a user with some preferences (potentially adversarially chosen) who offers a subset of products, S t , from the set of available products arrives at the seller’s platform. The user selects product j ∈ S t with probability given by the preference model and uses it for a random number of periods, t ˜ j , that is distributed i.i.d. according to some distribution that depends only on j generating a revenue r j ( t ˜ j ) for the seller. The goal of the seller is to find a policy that maximizes the expected cumulative revenue over a finite horizon T . Our main contribution is to show that a simple myopic policy (where we offer the myopically optimal assortment from the available products to each user) provides a good approximation for the problem. In particular, we show that the myopic policy is 1/2-competitive, that is, the expected cumulative revenue of the myopic policy is at least half the expected revenue of the optimal policy with full information about the sequence of user preference models and the distribution of random usage times of all the products. In contrast, the myopic policy does not require any information about future arrivals or the distribution of random usage times. The analysis is based on a coupling argument that allows us to bound the expected revenue of the optimal algorithm in terms of the expected revenue of the myopic policy. We also consider the setting where usage time distributions can depend on the type of each user and show that in this more general case there is no online algorithm with a nontrivial competitive ratio guarantee. Finally, we perform numerical experiments to compare the robustness and performance of myopic policy with other natural policies.

Keywords: assortment optimization online algorithms; reusable resources; coupling; competitive ratio (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2021.4134 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:68:y:2022:i:7:p:4772-4785

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().