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_0$ is large, our main result is a near-optimal $1-\min\left(\frac{1}{2},\sqrt{\log(c_0)/c_0}\right)$ 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 $\textit{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 $\textit{post-processing}$ 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/\sqrt{c_0+3}$ competitive algorithm for the special case of non-reusable resources. We finally evaluate the performance of our algorithms using the numerical simulations on the synthetic data.

翻译：受电子商务中租赁服务的应用启发，我们研究针对具有不同类别的连续到达消费者，进行可复用资源在线组合以实现收益最大化的问题。我们在贝叶斯设定下设计了相对于最优在线策略具有竞争力的在线算法，其中消费者类别随时间从已知的异质分布中独立抽取。在初始库存最小值$c_0$较大的情况下，我们的主要成果是针对可复用资源一般情形提出一个近最优的$1-\\min\\left(\\frac{1}{2},\\sqrt{\\log(c_0)/c_0}\\right)$竞争比算法。该算法基于问题的期望线性规划基准，通过求解该线性规划并采用独立随机舍入对解进行模拟实现。核心挑战在于从这类基于模拟的算法中以计算高效的方式获得逐点库存可行性。为此，我们采用多种技术要素设计了针对每种资源的$\textit{丢弃策略}$。这些策略在可复用性下的库存可行性与各资源收益损失之间进行权衡。然而，丢弃一个资源单元会改变其他资源的未来消耗。为应对这一新挑战，我们还引入了$\textit{后处理}$组合程序，这些程序有助于在并行运行时设计和分析丢弃策略，其本身可能具有独立研究价值。作为附加成果，通过结合先知不等式文献中的技术，我们进一步针对不可复用资源的特殊情形提出了改进的近最优$1-1/\\sqrt{c_0+3}$竞争比算法。最后，我们通过合成数据的数值模拟评估了所提算法的性能。