Conference Agenda

Session
TB8 - RM5: Online algorithms in revenue management
Time:
Tuesday, 28/June/2022:
TB 10:30-12:00

Session Chair: Will Ma
Location: Forum 12


Presentations

Online resource allocation for reusable resources

Wang Chi Cheung, Xilin Zhang

National University of Singapore, Singapore

We study a general model of reusable resource allocation problems. Customers of different types arrive according to a stationary stochastic process. The firm's goal is to maximize multiple kinds of rewards generated by customers. We develop an online policy for deciding on actions to take without knowing the distribution of customer types and show that when the usage duration is small compared with the length of the planning horizon, our policy achieves a near optimal performance.



The multi-secretary problem with many types

Omar Besbes, Yash Kanoria, Akshit Kumar

Columbia Business School, United States of America

We study the multisecretary problem with a capacity to hire up to B out of T candidates with their values drawn i.i.d from a distribution F on [0,1]. We investigate the achievable regret performance where our benchmark is the offline optimal policy. We establish the insufficiency of the common certainty equivalent heuristic for distributions with many types and gaps. We devise a new algorithmic principle called "Conservatism wrt Gaps" and use this to derive near-optimal regret scaling.



Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack

Jiashuo Jiang1, Will Ma2, Jiawei Zhang1

1New York University, United States of America; 2Columbia University, United States of America

Prophet inequalities are a useful tool for designing online allocation procedures and comparing their performance to the optimal offline allocation. In this paper we derive the best-known guarantee for $k$-unit prophet inequalities for all $k>1$. We also provide a tight resolution to the related Magician's problem. Finally, we improve the guarantee from 0.2 to 0.319 for online knapsack, and from 0.321 to 0.3557 for unit-density online knapsack.