Paccar Hall, Room 293

Seminar Speaker: Will Ma
Affiliation: MIT
Area: Operations Management

Name of Presentation:
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.