Dynamic Resource Allocation: Theory and Practice
In "Seminars and talks"

Speakers

Akshit Kumar
Akshit Kumar

Columbia Business School

Akshit Kumar is a final year PhD candidate in the Decision, Risk, and Operations division at Columbia Business School. His research focuses on problems in dynamic resource allocation, online matching, and recommendation systems, with applications in online platforms and marketplaces. In the summer of 2023, he interned in the Supply Chain Optimization group at Amazon. Before his PhD, he earned a Master’s in Electrical Engineering from the University of Michigan and a Bachelor’s in Electrical Engineering from IIT Madras.


Date:
Tuesday, 26 November 2024
Time:
10:00 am - 11:30 am
Venue:
NUS Business School
Mochtar Riady Building BIZ1-0302
15 Kent Ridge Drive
Singapore 119245 (Map)

Abstract

We study a broad class of dynamic resource allocation problems inspired by applications in online matching markets, online advertising, order fulfillment, and network revenue management. Our 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. We first investigate these questions in the simplest instance of a resource allocation problem that captures the core challenges at play: the prototypical multi-secretary problem. We establish 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. We then address the algorithmic challenge of designing a practical and near-optimal solution. Starting with the widely used Certainty Equivalent policy, we identify its limitations and introduce a unifying algorithmic principle, Conservativeness with respect to Gaps (CwG), which ensures near-optimal performance across diverse environments. Building on this principle, we propose the Repeatedly Act using Multiple Simulations (RAMS) algorithm, an adaptive approach that leverages multiple forecasted scenarios to make dynamic allocation decisions. We establish 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.