Dynamic bid prices in revenue management.

We formally derive the standard deterministic linear program (LP) for bid-price control by making an affine functional approximation to the optimal dynamic programming value function. This affine functional approximation gives rise to a new LP that yields tighter bounds than the standard LP. Whereas the standard LP computes static bid prices, our LP computes a time trajectory of bid prices. We show that there exist dynamic bid prices, optimal for the LP, that are individually monotone with respect to time. We provide a column generation procedure for solving the LP within a desired optimality tolerance, and present numerical results on computational and economic performance.

Subject classifications: revenue management, pricing: network; bid prices; dynamic programming/optimal control: applications, approximate.

Area of review: Manufacturing, Service, and Supply Chain Operations.

1. Introduction

The notion of "bid-price controls" (Talluri and van Ryzin 1998, Simpson 1989, Williamson 1992) has been a powerful and influential solution concept in revenue management for more than a decade. Major airlines, for instance, have used bid-price control policies for deciding when to open and close customer fare classes for sale. More generally, they can be used in revenue management settings where the supply of resources is fixed and customer requests arrive over a finite time horizon to consume various resource configurations. The arriving requests must either be accepted or rejected, with the objective of maximizing expected profit over the time horizon. The basic idea of bid-price control is simple: Accept the request if the revenue earned exceeds the value of the resources consumed as measured by bid prices. Typically, the bid prices are computed as optimal dual prices, i.e., marginal resource values, of a simple deterministic linear program.

While the system under control is dynamic, to date there only exist models for computing static bid prices, which do not change as a function of time. The effect of dynamically changing prices is created by re-solving the static bid-price model through time as the system evolves. One purpose of this paper is to derive and explore a tractable model for computing a time trajectory of bid prices all at once within a single model. In implementation this model may still be re-solved over time, and this turns out to be a good strategy, but hopefully the prices will be more accurate and effective due to the fact that system dynamics must somehow be taken into account in computing them.

The second purpose of this paper is to further formalize the connection between bid-price control in revenue management and dynamic programming, beyond Talluri and van Ryzin (1998). Given the standard bid-price linear program, Talluri and van Ryzin (1998) heuristically interpret the embedded pricing mechanism as making a linear functional approximation to the dynamic programming value function. However, the linear program itself has never been derived directly from the dynamic program. Rather, its prices are heuristically interpreted ex post in terms of a value function approximation.