Near-Optimal Bayesian Online Assortment of Reusable Resources

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,\sqrt{log(c_min)/c_min}) competitive algorithm for the general case of reusable resources. For the special case of non-reusable resources, we further show an improved near-optimal 1-1/\sqrt{c_min+3} competitive algorithm. Our algorithms rely on an expected LP benchmark for the problem, solve this LP, and simulate the solution through an independent randomized rounding. To obtain point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms, 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. We also introduce post-processing assortment procedures that help with designing and analyzing our discarding policies, which might be of independent interest. We finally evaluate the performance of our algorithms using the simulation on synthetic data.