Online Allocation of Reusable Resources: Achieving Optimal Competitive Ratio
share
We study the problem of allocating a given set of resources to sequentially arriving demand when the resources are reusable i.e., any allocated resource is used for a stochastic duration after which it is available for re-allocation. More concretely, we are given resources with fixed reusable inventory. Customers arrive sequentially and upon arrival reveal their type in the form of a set of resources they are willing to be matched to or more generally, a choice model. We must make an irrevocable decision to allocate from the set of available resources (in the form of a matching or by offering an assortment). The customer may then select at most one resource and use some of its inventory for a randomly drawn duration that is distributed i.i.d. according to a resource dependent usage distribution. The duration of usage is revealed to us only up on return. Successful allocations generate a resource and usage duration dependent reward. Our goal is to design online policies to maximize total expected reward without any knowledge of future customer types (adversarial demand model). Previously, Gong et al. (2019) showed that the Greedy algorithm is 1/2 competitive for this problem when compared against the clairvoyant algorithm that knows the entire customer type sequence in advance but sees the outcomes of usage durations in real-time. We propose a simple and novel algorithm for this problem that addresses reusability despite being oblivious to usage distributions. For large starting inventory, we show that our algorithm beats Greedy and achieves the best possible competitive ratio of (1-1/e) for a broad family of usage distributions.In addition, our method of analysis introduces a new general framework for certifying competitiveness w.r.t. clairvoyant algorithms that may be useful more broadly in other online allocation settings that have post-allocation stochasticity.
READ FULL TEXT