Online Resource Allocation with Cancellations

We initiate the study of two-sided online resource allocation with costly cancellations within the buyback model. Our focus is on edge-weighted online matching and several of its extensions. In our base matching model, nodes arrive online on one side and request offline resources on the other side. In contrast to the classic literature, in our model the decision maker can reclaim any fraction of an offline resource that was preallocated to an earlier online node. However, reclaiming a resource not only results in the loss of the previously allocated edge-weight but also incurs an additional penalty equal to a non-negative constant factor f times the edge-weight. Parameterizing the problem by the buyback factor f, our main result is the development of optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms in the fractional (or equivalently, large capacity) setting. We establish the optimality of our results by deriving separate lower bounds for both the small and large buyback factor regimes and showing that our primal-dual algorithm exactly matches these lower bounds by appropriately tuning a parameter as a function of f. Interestingly, our result shows a phase transition: for small buyback regime, i.e., f<(e-2)/2, the optimal competitive ratio is e/(e-1-f), and for large buyback regime, i.e., f>(e-2)/2, the competitive ratio is W(-1/(e(1+f))), when W is the non-principal branch of the Lambert W function.

We also study the lower and upper bounds on the competitive ratio in variants of this model, such as matching with deterministic integral allocations or single-resource environments with varying demand sizes. For deterministic integral matching, our results again show a phase transition: for the small buyback regime (f<1/3), the optimal competitive ratio is 2/(1-f), while for the large buyback regime (f >=1/3 ), the competitive ratio is 1 + 2f + 2(f(1+f))^0.5. We further extend our model to settings with combinatorial configuration allocations, buyer-arriving submodular welfare maximization, and assortment planning. We also consider an extension with negative values of f, which models scenarios with secondary supply channels or overflow capacities available at discounted rates. Our unifying family of primal-dual algorithms achieves the exact optimal competitive ratio across all these variants, demonstrating the power of our algorithmic framework for online resource allocations with cancellations. We further complement our theoretical analysis by numerically evaluating the performance of our algorithms and validating our theoretical results in more realistic scenarios.