Events

Dynamic Resource Allocation: Theory and Practice

Kumar studies a broad class of dynamic resource allocation problems inspired by applications in online matching markets, online advertising, order fulfillment, and network revenue management. Kumar’s objective is to understand the limits of achievable performance and develop algorithms that meet three key desiderata: 1) practicality, 2) strong provable performance, and 3) broad applicability. Extensive prior literature often establishes strong performance guarantees but typically relies on strong assumptions about the environment and finely tuned algorithms to these. Kumar first investigates these questions in the simplest instance of a resource allocation problem that captures the core challenges at play: the prototypical multi-secretary problem. Kumar establishes that if one requires broad applicability, then a spectrum of performances will emerge, as opposed to those typically appearing in the literature – highlighting how different environment characteristics fundamentally impact algorithmic performance. Kumar then addresses the algorithmic challenge of designing a practical and near-optimal solution. Starting with the widely used Certainty Equivalent policy, Kumar identifies its limitations and introduces a unifying algorithmic principle, Conservativeness with respect to Gaps (CwG), which ensures near-optimal performance across diverse environments. Building on this principle, Kumar proposes the Repeatedly Act using Multiple Simulations (RAMS) algorithm, an adaptive approach that leverages multiple forecasted scenarios to make dynamic allocation decisions. Kumar establishes that RAMS, which does not require fine-tuning, achieves near-optimal performance across environments, not only for the multi-secretary problem but also across a wide range of dynamic resource allocation problems.