TITLE: Online Resource Allocation under Arbitrary Arrivals: Optimal Algorithms and Tight Competitive Ratios

ABSTRACT:

We consider the problem of allocating fixed resources to heterogeneous customers arriving sequentially.  We study this problem under the framework of competitive analysis, which does not assume any predictability in the sequence of customer arrivals.  Previous work has culminated in optimal algorithms under two scenarios: (i) there are multiple resources, each of which yields reward at a constant rate when allocated; or (ii) there is a single resource, which yields reward at different rates when allocated to different customers.

In this paper, we derive optimal allocation algorithms when there are multiple resources, each with multiple reward rates.  Our algorithms are simple, intuitive, and robust against forecast error.  Their tight competitive ratio cannot be achieved by combining existing algorithms, which consider the tradeoffs between multiple resources and multiple reward rates separately.

By showing how to integrate these tradeoffs while making allocation decisions, we expand the applicability of competitive analysis in many areas, such as online advertising, matching markets, and personalized e-commerce.  We test our methodological contribution on the hotel data set of Bodea et al. (2009), where there are multiple resources (hotel rooms), each with multiple reward rates (fares at which the room could be sold).  We find that applying our algorithms, in conjunction with algorithms which attempt to forecast and learn the future transactions, results in the best performance.

BIO: Will Ma is a Ph.D. student in the MIT Operations Research Center, advised by David Simchi-Levi. Broadly speaking, he is interested in data-driven revenue management, helping firms dynamically optimize their operational decisions based on real-time data. More specifically, he has been working on online matching and recommendation problems, stochastic knapsack and Markovian multi-armed bandit problems, and the usage of product bundling as a tool for demand learning.

He spent 2013-2015 as a co-founder of Lunarch Studios, the start-up that designed the strategy game Prismata. During those years, he had also been a research intern with the Ad Exchange team in Google New York, and a trading intern at Jane Street Capital.

He completed his undergraduate degree in 2010 from the University of Waterloo, majoring in Pure Mathematics and Combinatorics/Optimization. During that time, he competed in many international poker tournaments. He also teaches the poker class at MIT, which has recently been archived onto MIT OpenCourseWare.