Dynamic problems in revenue management: structure and approximation

Abstract

Although the origins of Revenue Management date back to its use by airlines in the post-deregulation era in the U.S., nowadays is heavily used by a variety of industries such as hotels, car rental companies and retailers. Since then, research in this area grew and became one of the most successful branches of operation research. How much, at what price and when to sell are the key questions that Revenue Management aims to answer in order to maximize the expected revenue of a seller. Different assumptions carry to different models and consequently, new theoretical and algorithmic challenges arise. In this thesis, we address some of them, going from a theoretical approach of a dynamic pricing problem to the study of the optimality gap for some online decision problems and the relation between some of them. In the first chapter, we study the problem faced by a seller endowed with a single unit for sale over an infinite time horizon in order to maximize her expected revenue. The firm pre-commits to the price function and the buyer is strategic and has a private value for the item. Our goal is to study the importance, in terms of seller's expected revenue, of the observability of the buyer's time arrival. Our main result states that, in a very general setting, the expected revenue when the seller observes the buyer's arrival is at most roughly 4.91 times the expected revenue when the seller does not know the time when the buyer arrives. In the second chapter, we show that if we have a posted price mechanism with a certain approximation guarantee, this can be turned into a prophet inequality (in the same setting) with the same approximation guarantee. This result, together with the work by Chawla et al. (2010), imply that the problem of designing posted price mechanisms is actually equivalent to that of finding stopping rules for a prophet. Finally, in the third chapter we introduce a general class of online decision problems, namely Dynamic Resource Constrained Reward Collection (DRCRC) that comprises several problems studied separately in the literature. In particular, the class of DRCRC admits as special cases the classes of network revenue management problems, dynamic pricing problems, online matching problems, to name a few. Due to the difficulty of solving the decision-maker problem optimally, it is usual to develop heuristics to approximate the optimal expected revenue. Thus, we study the revenue loss under a well studied certainty equivalent heuristic, providing a unifying proof for the revenue loss for DRCRC, recovering some existing results for some problems and obtaining new ones for others.