Technical Note—Near-Optimal Bayesian Online Assortment of Reusable Resources

Yiding Feng (), Rad Niazadeh () and Amin Saberi ()
Additional contact information
Yiding Feng: University of Chicago Booth School of Business, Chicago, Illinois 60637
Rad Niazadeh: University of Chicago Booth School of Business, Chicago, Illinois 60637
Amin Saberi: Management Science and Engineering, Stanford University, Stanford, California 94305

Operations Research, 2024, vol. 72, issue 5, 1861-1873

Abstract: Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories c min is large, our main result is a near-optimal 1 − min ( 1 2 , log ( c min ) / c min ) competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies— one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce postprocessing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1 − 1 / c min + 3 competitive algorithm for the special case of nonreusable resources. We finally evaluate the performance of our algorithms using the numerical simulations on the synthetic data. Funding: R. Niazadeh’s research is partially supported by an Asness Junior Faculty Fellowship from the University of Chicago Booth School of Business. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2020.0687 .

Keywords: Market Analytics and Revenue Management; analysis of algorithms; analysis of algorithms; suboptimal algorithms; inventory/production; approximations/heuristics (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.0687 (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:oropre:v:72:y:2024:i:5:p:1861-1873

Access Statistics for this article

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