Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks

We study the problem of dynamically allocating reusable resources to customers of n types. There are d pools of resources and a finite number of units from each resource. If a customer request is accepted, the decision maker collects a type-dependent reward, and the customer occupies, for a random service time, one unit from each resource in a set of these. Upon service completion, these resource units become available for future allocation. This is a loss network: requests that are not accepted leave immediately. The decision maker’s objective is to maximize the long-run average reward subject to the resource capacity constraint. A natural linear programming (LP) relaxation of the problem serves as an upper bound on the performance of any policy. We identify a condition that generalizes the notion of overload in single-resource networks (i.e., when $d=1$). The LP guides our construction of a threshold policy. In this policy, the number of thresholds equals the number of resource types (hence, does not depend on the number of customer types). These thresholds are applied to a “corrected” headcount process. In the case of a single resource, the corrected head count is the number of resource units that are occupied. We prove that, in overloaded networks, the additive loss (or regret) of this policy benchmarked against the LP upper bound is logarithmic in the total arrival volume in the high-customer-volume, many-resource-units, asymptotic regime. No policy can achieve sublogarithmic regret. Simulations showcase the performance of the proposed policy.

Funding: X. Xie and I. Gurvich were supported by an Amazon Research Award and DRAGONS – Dynamic Resource Allocation Gains for Operational Networked Sharing, Department of Defense (Army) [Grant STTR A18B-T007]. S. Küçükyavuz was supported by an Office of Naval Research [Grant N00014-22-1-2602].

Supplemental Material: Data and code files are available at https://doi.org/10.1287/opre.2022.0429.