Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks

Xinchang Xie (), Itai Gurvich () and Simge Küçükyavuz ()
Additional contact information
Xinchang Xie: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Itai Gurvich: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Simge Küçükyavuz: Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

Operations Research, 2025, vol. 73, issue 4, 2097-2124

Abstract: 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.

Keywords: Stochastic; Models; sequential resource allocation; regret; linear programming relaxation; loss networks; Lyapunov function; reusable resources (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0429 (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:73:y:2025:i:4:p:2097-2124

Access Statistics for this article

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