Online Resource Allocation with Cancellations

Abstract

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 \emph{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 results reveal a phase transition: for the small buyback regime ($f<\frac{e-2}{2}$), the optimal competitive ratio is $\frac{e}{e-(1+f)}$, and for the large buyback regime ($f\ge \frac{e-2}{2}$), the competitive ratio is $-W_{-1}\left(\frac{-1}{e(1+f)}\right)$, where $W_{-1}$ is the non-principal branch of the Lambert $W$ function.

arXiv commentA preliminary conference version of this work has appeared in the ACM Economics and Computations(EC) 2023 conference under the title "Online Resource Allocation with Buyback: Optimal Algorithms via Primal-Dual." ; An earlier version of this paper was distributed under the title "Online Matching with Cancellation Costs."