Description
Consider a firm that owns a fixed capacity of a resource that is consumed in the production or delivery of
multiple products. The firm strives to maximize its total expected revenues over a finite horizon, either
by choosing a dynamic pricing strategy for each product or, if prices are fixed, by selecting a dynamic rule
that controls the allocation of capacity to requests for the different products. This paper shows how these wellstudied
revenue management problems can be reduced to a common formulation in which the firm controls
the aggregate rate at which all products jointly consume resource capacity, highlighting their common structure,
and in some cases leading to algorithmic simplifications through the reduction in the control dimension of
the associated optimization problems. In the context of their associated deterministic (fluid) formulations, this
reduction leads to a closed-form characterization of the optimal controls, and suggests several natural static and
dynamic pricing heuristics. These are analyzed asymptotically and through an extensive numerical study. In the
context of the former, we show that “resolving” the fluid heuristic achieves asymptotically optimal performance
under fluid scaling.
MANUFACTURING & SERVICE
OPERATIONS MANAGEMENT
Vol. 8, No. 2, Spring 2006, pp. 136–148
issn1523-4614[ eissn1526-5498[ 06[ 0802[ 0136
informs
®
doi 10.1287/msom.1060.0105
©2006 INFORMS
Dynamic Pricing Strategies for Multiproduct
Revenue Management Problems
Constantinos Maglaras
Columbia Business School, Columbia University, 409 Uris Hall, 3022 Broadway,
New York, New York 10027, [email protected]
Joern Meissner
Lancaster University Management School, Lancaster University, Room A48,
Lancaster LA1 4XY, United Kingdom, [email protected]
C
onsider a ?rm that owns a ?xed capacity of a resource that is consumed in the production or delivery of
multiple products. The ?rm strives to maximize its total expected revenues over a ?nite horizon, either
by choosing a dynamic pricing strategy for each product or, if prices are ?xed, by selecting a dynamic rule
that controls the allocation of capacity to requests for the different products. This paper shows how these well-
studied revenue management problems can be reduced to a common formulation in which the ?rm controls
the aggregate rate at which all products jointly consume resource capacity, highlighting their common structure,
and in some cases leading to algorithmic simpli?cations through the reduction in the control dimension of
the associated optimization problems. In the context of their associated deterministic (?uid) formulations, this
reduction leads to a closed-form characterization of the optimal controls, and suggests several natural static and
dynamic pricing heuristics. These are analyzed asymptotically and through an extensive numerical study. In the
context of the former, we show that “resolving” the ?uid heuristic achieves asymptotically optimal performance
under ?uid scaling.
Key words: revenue management; dynamic pricing; capacity controls; ?uid approximations; ef?cient frontier
History: Received: July 21, 2003; accepted: November 11, 2005. This paper was with the authors 9 months for
3 revisions.
1. Introduction
Consider a ?rm that owns a ?xed capacity of a cer-
tain resource that is consumed in the process of pro-
ducing or offering multiple products or services, and
which must be consumed over a ?nite time horizon.
The ?rm’s problem is to maximize its total expected
revenues by selecting the appropriate dynamic con-
trols. We consider two well-studied variants of this
problem. In the ?rst, the ?rm is assumed to be a
monopolist or to operate in a market with imper-
fect competition, and thus to have power to in?u-
ence the demand for each product by varying its
price. In this setting, the ?rm’s problem is to choose
a dynamic pricing strategy for each of its products
to optimize expected revenues. In the second variant,
prices are assumed to be ?xed either by the competi-
tion or through a higher-order optimization problem,
and the ?rm’s problem is now to choose a dynamic
capacity allocation rule that controls when to accept
new requests for each of these products. In the sequel,
these two problems are referred to as the “dynamic
pricing” and “capacity control” formulations, respec-
tively. Revenue management problems of that sort
gained interest in the late 1970s in the context of
the airline industry, and have since been successfully
introduced in a variety of other areas such as hotels,
cruise lines, rental cars, retail, etc.
This paper illustrates how these two problems can
be reduced to a common formulation, thus connect-
ing prior results that have appeared in the literature
under a uni?ed framework, and explores some of
the consequences of this formulation. Speci?cally, we
show that the multiproduct dynamic pricing prob-
lem introduced by Gallego and van Ryzin (1997) and
the capacity control problem of Lee and Hersh (1993)
can be recast within this common framework, and
be treated as different instances of a single-product
pricing problem for appropriate concave revenue
136
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 137
functions (Propositions 1 and 2). Broadly speaking,
this is done by decoupling the revenue maximization
problems in two parts: First, at each point in time the
?rm selects an aggregate capacity consumption rate
from all products, and second, it computes the vector
of demand rates to maximize instantaneous revenues
subject to the constraint that all products jointly con-
sume capacity at the aforementioned rate. The latter is
akin to the basic microeconomics problem of resource
allocation subject to a budget constraint, and gives
rise to an appropriate aggregate revenue rate function
in each case. This common formulation recovers well-
known structural results regarding the monotonicity
properties of the value function and the associated
controls (see Proposition 3 and Corollary 2), which
were previously derived in the literature while study-
ing each of these problems in isolation; see, e.g.,
Gallego and van Ryzin (1994, 1997), Lee and Hersh
(1993), Lautenbacher and Stidham (1999), Zhao and
Zheng (2000), and the recent book by Talluri and van
Ryzin (2004b). It also facilitates the derivation of new
results, such as Corollary 1, that extend these proper-
ties to the setting of multiproduct pricing policies.
Extending this idea of demand aggregation in con-
sidering deterministic and continuous (?uid) approx-
imations of the underlying problems suggests a set
of simple pricing and capacity control heuristics for
the underlying problems. These stem from the fact
that this aggregated formulation leads to closed-
form solutions to the ?uid model revenue maxi-
mization problems (see Proposition 4). This extends
the analysis of Gallego and van Ryzin (1997), which
offered only an implicit characterization of these poli-
cies in the multiproduct setting; see also Bitran and
Caldentey (2003) for a discussion of deterministic
multiproduct pricing problems. Based on the solution
of the ?uid formulation, we propose three heuristics:
(i) a static pricing heuristic, (ii) a static pricing heuris-
tic applied in conjunction with an appropriate capac-
ity allocation policy, and (iii) a “resolving” heuristic
that reevaluates the ?uid policy as a function of the
current state and time-to-go (which is derived by
expressing the ?uid solution in feedback form). The
?rst of these heuristics was proposed by Gallego and
van Ryzin (1997), while policies that combine static
prices with capacity controls as in (ii) have been sug-
gested in other papers such as McGill and van Ryzin
(1999), Feng and Xiao (2004), and Lin et al. (2003).
Finally, the “resolving” heuristic (iii) is widely applied
in practice, but to the best of our knowledge has
not been analyzed theoretically thus far. The only
exception was the negative result of Cooper (2002),
which illustrated through an example that resolving
may in fact do worse than applying the static ?uid
policy. Propositions 5–7 in §4.2 establishes that all
three heuristics achieve asymptotically optimal per-
formance under ?uid scaling, i.e., in the spirit of Gal-
lego and van Ryzin (1997) and Cooper (2002). These
results show that the phenomenon demonstrated in
Cooper’s example does not persist in problems with
large capacity and demand, where, in fact, resolv-
ing achieves the asymptotically optimal performance.
Moreover, the numerical results of §5 illustrate that
the dynamic heuristics (ii) and (iii) tend to outperform
the static one.
In terms of qualitative insights, we ?nd that the
translation of the capacity consumption rate to a set
of product-level controls that jointly maximize the
instantaneous revenue rate de?nes an ef?cient frontier
for the ?rm’s optimal pricing and capacity control
strategies. This captures in a tractable way the interac-
tions between products due to cross-elasticity effects
and the joint capacity constraint. The idea of an ef?-
cient frontier has appeared in Talluri and van Ryzin
(2004a) in the context of a capacity control problem for
a model with customer choice among products, and
in Feng and Xiao (2000, 2004) while studying pricing
problems with a predetermined set of price points.
The remainder of the paper is structured as fol-
lows. This section concludes with some additional
bibliographic references. Section 2 describes the two
problem formulations. Section 3 demonstrates the
reduction of the dynamic programming formulations
to that of a single-product pricing problem, and
derives some of its structural properties. Section 4
studies the ?uid formulations of these problems and
analyzes the asymptotic performance of the associ-
ated heuristics mentioned earlier. Section 4.3 outlines
how the same approach can be extended to a network
setting. Section 5 provides some numerical illustration
of our results and offers some concluding remarks.
The idea of demand aggregation appeared in Tal-
luri and van Ryzin (2004a) while analyzing a capac-
ity control problem for a system where customer
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
138 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
behavior is captured through a discrete choice model,
while similar techniques have been exploited in
the past in the numerical solution of the dynamic
programs associated with revenue management prob-
lems. Similar ideas also arise in problems of rev-
enue management of multiproduct queueing sys-
tems; see Maglaras (2006) for a recent example.
The papers by Elmaghraby and Keskinocak (2003),
Bitran and Caldentey (2003), and McGill and van
Ryzin (1999), and the book by Talluri and van Ryzin
(2004b), provide comprehensive overviews of the
areas of dynamic pricing and revenue management.
The modelling framework adopted in this paper
closely matches that of Gallego and van Ryzin (1994,
1997). Additional references on the capacity con-
trol formulation are Brumelle and McGill (1993) and
Lautenbacher and Stidham (1999). Finally, a dynamic
pricing heuristic that is related to the one studied in
this paper was derived by Reiman (2002) as the solu-
tion to a “second-order” control problem that seeks
to minimize an appropriate measure of the devia-
tion from the inventory trajectory derived through
the deterministic model. Indeed, the single-product
policy proposed in Reiman (2002) is the same as the
one we derive here. The multiproduct formulation in
Reiman (2002) differs from ours, and therefore the
resulting pricing policies also differ.
2. Single Resource, Multiproduct
Model
This section formulates the multiproduct dynamic
pricing and capacity control problems studied by
Gallego and van Ryzin (1997) and Lee and Hersh
(1993), respectively, among others.
2.1.1. Dynamic Pricing Problem. Consider a ?rm
endowed with C units of capacity of a single resource
used in producing or offering multiple products or
services, indexed by i = 1, . . . , n. Each product i
request requires one unit of capacity. There is a ?nite
horizon T over which the resources must be used,
and capacity cannot be replenished up to that time.
The salvage value of remaining capacity at time T
is assumed to be zero. (A constant per-unit sal-
vage value would also result in formulations sim-
ilar to those developed below.) The ?rm is either
a monopolist or is assumed to operate in a mar-
ket with imperfect competition, and, therefore, has
power to in?uence the demand for each product by
varying its menu of prices. Let p(|) =|p
1
(|), . . . , p
n
(|)]
denote the vector of prices at time |. The demand
process is assumed to be n-dimensional nonhomoge-
neous Poisson process with rate vector \ determined
through a demand function \(p(|)), where \: ?,
?
n
is the set of feasible price vectors, and =
{x ? 0: x = \(p), p ? ] ?
n
÷
is the set of achievable
demand rate vectors. We assume that is a convex
set. For ease of exposition, the demand function \(·)
is assumed to be stationary; an extension to allow for
nonstationarities could follow Gallego and van Ryzin
(1994, 1997) and Zhao and Zheng (2000). This class of
demand functions incorporates product complemen-
tarity and substitution effects. Following Gallego and
van Ryzin (1994, 1997), we consider regular demand
functions that satisfy some additional conditions. In
the sequel, x
/
denotes the transpose of any matrix x,
for any real number j, j
÷
:=max(0, j), c is the vector
of ones of appropriate dimension, and “a.s.” stands
for almost surely.
De?nition 1. A demand function is said to be reg-
ular if it is a continuously differentiable, bounded
function, and: (a) for each product i, \
i
(p) is strictly
decreasing in p
i
, (b) lim
p
i
?~
\
i
(p) =0 (i.e., consumers
have bounded wealth), and (c) the revenue rate
p
/
\(p) =
n
i=1
p
i
\
i
(p) is bounded for all p ? and has
a ?nite maximizer ¨ p.
We assume that there exists a continuous inverse
demand function p(\), p: ? , that maps an
achievable vector of demand rates \ into a corre-
sponding vector of prices p(\). This allows us to view
the demand rate vector as the ?rm’s control, and infer
the appropriate prices using the inverse demand func-
tion. The expected revenue rate can be expressed as
a function of the vector of demand rates \ as í(\) :=
\
/
p(\), and is assumed to be continuous, bounded,
and strictly concave.
Example. Under a linear demand model, the de-
mand for product i is given by
\
i
(p) =A
i
?|
ii
p
i
?
_
¡,=i
|
i¡
p
¡
or
(in vector form) \(p) =A?8p,
where A
i
is the market potential for product i and |
ii
,
|
i¡
are the price and cross-price sensitivity parame-
ters. The inverse demand and revenue functions are
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 139
p(\) = 8
?1
(A ? \) and í(\) = \
/
8
?1
(A ? \), respec-
tively. Assumption 1 requires that |
ii
> 0 for all i.
To ensure that the inverse demand function is well
de?ned and the revenue function is concave, we
require that either |
ii
>
¡,=i
[|
¡i
[ or |
ii
>
¡,=i
[|
i¡
[ for
all i; both conditions guarantee that 8 is invertible and
that its eigenvalues have positive real parts (Horn and
Johnson 1994, Thm. 6.1.10).
The problem that we address is roughly described
as follows: Given an initial capacity C, a selling hori-
zon T , and a demand function that maps a vector of
prices to a vector of demand rates, the ?rm’s goal is to
choose a nonanticipating dynamic pricing strategy for
each product in order to maximize its total expected
revenues.
We adopt a discrete-time formulation, i.e., one
where time has been discretized in small intervals
of length o|, indexed by | = 1, . . . , T , such that
(product i arrival in |0, o|]) = \
i
o| ÷o(o|) for all i,
and (product i and ¡ arrivals in |0, o|]) =\
i
\
¡
(o|)
2
÷
o((o|)
2
), where o(x) implies that o(x),x ?0 as x ?0.
With slight abuse of notation, we write \
i
in place of
\
i
o|, and refer to \
i
either as the demand or the buy-
ing probability for product i. The random demand
vector in period |, denoted by ((|, \), is Bernoulli
with probabilities \(|) = \(p(|)), and ((
i
(|) = 1) =
\
i
(p(|)) and ((
i
(|) =0) =1?\
i
(p(|)) for all i. Treating
the demand rates \
i
as the control variables (prices
are inferred via the inverse demand relationship),
the discrete-time formulation of the dynamic pricing
problem of Gallego and van Ryzin (1997) is
max
{\(|), |=1,...,T ]
_
?
_
T
_
|=1
p(\(|))
/
((|, \)
_
:
T
_
|=1
c
/
((|,\) ?C a.s. and \(|) ? ?|
_
. (1)
2.1.2. Capacity Control Problem. The second
problem that we consider is the one studied by
Lee and Hersh (1993), where the price vector p and
the demand rate vector \ = \(p) are ?xed, and the
?rm optimizes over capacity allocation decisions. For
this problem and without any loss of generality, we
assume that products are labelled such that p
1
?
p
2
?· · · ?p
n
. The ?rm has discretion as to which prod-
uct requests to accept at any given time. This is mod-
elled through the control u
i
(|) that is equal to the
probability of accepting a product i request at time |.
It is customary to assume that the ?rm is “opening”
or “closing” products, thus considering controls u
i
(·)
that are zero or one, but this need not be imposed as
a restriction. The dynamic capacity control problem is
the following:
max
{u(|), |=1,...,T ]
_
?
_
T
_
|=1
p
/
((|, u\)
_
:
T
_
|=1
c
/
((|, u\) ?C
a.s. 1 and u
i
(|) ? |0, 1] ?|
_
, (2)
where u\ above denotes the vector with coordi-
nates u
i
\
i
.
3. Analysis of the Pricing and
Capacity Control Problems
This section describes how to reduce (1) and (2) into
dynamic optimization problems where the control is
the (one-dimensional) aggregate capacity consump-
tion rate. Subsequently, we derive some structural
properties for these two problems through a uni?ed
analysis.
3.1. A Common Formulation in Terms of
the Aggregate Capacity Consumption
3.1.1. Dynamic Pricing Problem. Let x denote the
number of remaining units of capacity at the begin-
ning of period |, and V(x, |) be the expected revenue-
to-go starting at time | with x units of capacity left.
Then, the Bellman equation associated with (1) is
V(x, |) =max
\?
_
n
_
i=1
\
i
|p
i
(\) ÷V(x ?1, | ÷1)]
÷(1 ?c
/
\)V(x, | ÷1)
_
, (3)
with the boundary conditions
V(x, T ÷1) =0 ?x and V(0, |) =0 ?|. (4)
Letting AV(x, |) =V(x, | ÷1) ?V(x ?1, | ÷1) denote
the marginal value of one unit of capacity as a func-
tion of the state (x, |), (3) can be rewritten as
V(x, |) = max
\?
_
í(\) ?
n
_
i=1
\
i
AV(x, |)
_
÷V(x, | ÷1)
= max
j?
{í
r
(j) ?jAV(x, |)] ÷V(x, | ÷1), (5)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
140 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
where j :=
n
i=1
\
i
is the aggregate rate of capacity con-
sumption, := {j:
n
i=1
\
i
= j, \ ? ] is the set of
achievable capacity consumption rates, and
í
r
(j) :=max
\
_
í(\):
n
_
i=1
\
i
=j, \ ?
_
(6)
is the maximum achievable revenue rate subject to the
constraint that all products jointly consume capacity
at a rate j. Note that (6) is a concave maximization
problem over a convex set, and its solution is read-
ily computable, often in closed form (examples are
given in §5). Moreover, í
r
(·) is a concave function and
satis?es the conditions of Assumption 1. The optimal
vector of demand rates, denoted by \
r
(j), is unique
and continuous in j.
Proposition 1. The dynamic pricing problem (1) can
be reduced to the dynamic program (5) and (4) expressed
in terms of the aggregate consumption rate. In particular, if
j
?
(x, |) denotes the associated optimal control and \
?
(x, |)
and p
?
(x, |) denote the optimal demand rate and price vec-
tors associated with (1), then \
?
(x, |) = \
r
(j
?
(x, |)) and
p
?
(x, |) =p(\
r
(j
?
(x, |))).
3.1.2. The Capacity Control Problem. Similarly,
the Bellman equation associated with (2) is
V(x, |) = max
u
i
?|0, 1]
_
n
_
i=1
\
i
u
i
|p
i
÷V(x ?1, | ÷1)]
÷(1 ?u
/
\) V(x, | ÷1)
_
, (7)
with the boundary condition (4), which, using the
marginal value of capacity AV becomes
V(x, |) = max
u
i
?|0, 1]
_
n
_
i=1
\
i
u
i
p
i
?u
/
\AV(x, |)
_
÷V(x, | ÷1) (8)
= max
0?j?
n
i=1
\
i
{í
u
(j)?jAV(x,|)]÷V(x,| ÷1), (9)
where j =u
/
\ and
í
u
(j) =max
u
_
n
_
i=1
u
i
\
i
p
i
: u
/
\ =j, u
i
? |0, 1]
_
is the maximum revenue rate when the capacity is
consumed at a rate equal to j, and u
u
(j) is the corre-
sponding control.
Proposition 2. The capacity control problem (2) can
be reduced to the dynamic program (9) and (4) expressed
in terms of the aggregate consumption rate j. In par-
ticular, if j
?
(x, |) denotes the optimal solution of (9)
and (4) and u
?
(x, |) denote the optimal policy for (2), then
u
?
(x, |) =u
u
(j
?
(x, |)).
A similar result was derived by Talluri and van
Ryzin (2004a) for a capacity control problem for a
model with customer choice.
3.2. A Uni?ed Analysis of the Pricing and
Capacity Control Problems
The preceding analysis illustrates that both problems
can be reduced to “appropriate” single-product pric-
ing problems, highlighting their common structure
and enabling a uni?ed treatment. As a starting obser-
vation, for both (5) and (9) the optimal control j
?
(x, |)
is computed from
j
?
(x, |) =argmax
j?
{í(j) ?jAV(x, |)],
where í(·) is a concave increasing revenue function.
Using the properties of í(·), one gets that j
?
(x, |)
is decreasing in AV(x, |), which using a backward
induction argument in | gives that AV(x, |) is decreas-
ing in x and |. These standard results for single-
product dynamic pricing problems are summarized
below; a proof can be found in Talluri and van Ryzin
(2004b, Prop. 5.2, Ch. 4).
Proposition 3 (Talluri and van Ryzin 2004b,
Prop. 5.2, Ch. 4). For both problems de?ned in (1) and (2),
we have that
1. j
?
(x, |) is decreasing in the marginal value of capac-
ity AV(x, |), and
2. AV(x, |) is decreasing in x and |.
Structural results for the pricing and capacity allo-
cation policies follow from the properties of í
r
, \
r
and í
u
, u
u
, respectively. For example, consider the
pricing problem for the case where the products are
nonsubstitutes, i.e., the demand for product i is only
a function of the price for that product p
i
. In that
case, the Lagrangian associated with (6) is |(\, x, j) =
í(\) ÷ x(j ?
n
i=1
\
i
) ? j
/
\, with ?rst-order condi-
tions given by oí(\),o\
i
= x ÷ j
i
, for some x ? 0
and j
i
?0 with j
i
= 0 if \
i
> 0. It is easy to show
that x is decreasing in j (i.e., the shadow price for
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 141
the capacity consumption constraint decreases as the
rate j increases), and that \
r
i
(j) is decreasing in x.
Corollary 1. Consider the problem speci?ed in (3)
and (4), and further assume that the products are non-
substitutes, i.e., \
i
(p) = \
i
(p
i
) for all i. Then, \
?
i
(x, |) is
nondecreasing in j
?
(x, |) (and nonincreasing in AV(x, |)).
A similar result can be obtained when products are
substitutable provided that the demand model satis-
?es certain conditions analogous to those of the sen-
sitivity matrix 8 of the linear model in §2.
For the capacity control problem, it is easy to
recover some well-known structural properties of the
optimal policy, see, e.g., Lee and Hersh (1993). Our
derivation based on the capacity consumption rate
offers new intuition as to why they hold. Speci?cally,
í
u
(·) is a knapsack solution for which
í
u
(j) =min
i
c
i
÷p
i
j and
u
u
|
(j) =min
_
(j?
i-|
\
i
)
÷
\
|
, 1
_
,
(10)
where c
1
= 0 and c
i
=
|-i
\
|
(p
|
? p
i
), and for
any x ? , x
÷
:= max(x, 0), and the optimal control
j
?
(x, |) reduces to the solution to max{min
i
c
i
÷(p
i
?
AV(x, |))j: 0 ? j ?
n
i=1
\
i
]. Let i
?
(x, |) = max{i ? 1:
p
i
? AV(x, |)]. Then, by inspecting the form of
the piecewise-linear objective function involved in
the calculation of j
?
(x, |), we get that j
?
(x, |) =
n
i?i
?
(x, |)
\
i
. That is, the solution is “bang-bang” in the
sense that the form of the optimal control is such that
u
?
i
(x, |) is zero if i > i
?
(x, |) and one if i ? i
?
(x, |).
In addition, from Proposition 3, Part 1, we see that
i
?
(x, |) is decreasing in the marginal value of capacity
AV(x, |).
Corollary 2. For the capacity control problem (2) or,
equivalently, (9) and (4), the optimal allocation policy is
nested in that u
?
i
(x, |) =1 if i ?i
?
(x, |), and u
?
i
(x, |) =0
otherwise, and i
?
(x, |) is decreasing in the marginal value
of capacity AV(x, |).
Remark. The subproblem of computing the opti-
mal revenue subject to a constraint on the aggregate
capacity consumption rate speci?ed in (6) and (10)
de?nes an ef?cient frontier (j, í
r
(j)) and (j, í
u
(j))
for the dynamic pricing and capacity allocation prob-
lems, respectively. As in the context of portfolio
optimization, the ef?cient frontier provides a system-
atic framework for comparing different policies and
highlights the structure of the respective optimal con-
trols. It may also lead to computational improve-
ments if this subproblem can be solved ef?ciently,
preferably in closed form. This is possible in some
common demand models such as the linear and the
multinomial logit. Such an ef?cient frontier has also
appeared and been discussed in more detail in Feng
and Xiao (2000, 2004) and Talluri and van Ryzin
(2004a). Finally, we note that the structure of the
dynamic programs studied in this section has been
observed in other papers, such as Lin et al. (2003) and
their study of single-resource capacity control prob-
lems where each arrival may request multiple units
of capacity; and Vulcano et al. (2002) and their anal-
ysis of optimal dynamic auctions. The latter involves
an analysis of a discrete-time, batch-demand analog
to the dynamic program studied here.
4. Analysis of the Pricing Problem
Using Its Fluid Approximation
This section studies deterministic (?uid model) for-
mulations of multiproduct revenue management
problems to provide some structural results (§4.1) and
suggest simple and implementable heuristics for the
pricing and capacity control problems (§4.2). The lat-
ter have desirable theoretical performance guaran-
tees and are shown to perform well in the numerical
experiments of the next section. Finally, §4.3 sketches
how to extend these ideas to the network setting. Fol-
lowing the results of §3.2 that relate the pricing and
capacity control formulations, hereafter we will focus
exclusively on the former.
4.1. Solution to the Deterministic Multiproduct
Pricing Problem
The “?uid” model has deterministic and continuous
dynamics, and is obtained by replacing the discrete
stochastic demand process by its rate, which now
evolves as a continuous process. It is rigorously jus-
ti?ed as a limit under a law-of-large-numbers type
of scaling as the potential demand and the capacity
grow proportionally large; see Gallego and van Ryzin
(1994, 1997) and §4.2. It is simplest to describe the
?uid model in continuous time (this is consistent with
Gallego and van Ryzin 1994, 1997). In more detail, the
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
142 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
realized instantaneous demand for product i at time |
in the ?uid model is deterministic and given by \
i
(|).
We allow product i requests to consume capacity at
a rate of u
i
>0 units per unit of demand, and denote
by u the vector |u
1
, . . . , u
n
]. This is a generalization of
the model considered thus far, which assumed uni-
form capacity requirements (all equal to 1). With a
general capacity requirement vector u, the capacity
consumption rate is de?ned by j =u
/
\, and the de?-
nitions of í
r
and \
r
can be appropriately adjusted to
re?ect that change. The system dynamics are given by
dx(|),d| = ?
n
i=1
u
i
\
i
(|), x(0) = C, together with the
boundary condition that x(T ) ? 0. The ?rm selects a
demand rate \
i
(|) (or a price) at each time |. The ?uid
formulation of the multiproduct pricing problem is
the following:
max
{\(|), |?|0, T ]]
_
_
T
0
í(\(|)) d|:
_
T
0
u
/
\(|) d| ?C and \(|) ? ?|
_
. (11)
Single-product problem. In this case, Gallego and van
Ryzin (1994) showed that a constant price (and thus
a constant demand rate) is optimal for (11). Specif-
ically, let
ˆ
\ = argmax{í(\): \ ? ] and ´ p = p(
ˆ
\) be
the demand rate and price, respectively, that maxi-
mize the revenue rate disregarding any capacity con-
siderations. Also, let \
0
= C,T be the run-out rate
that depletes capacity at time T , and p
0
=p(\
0
). Then,
Gallego and van Ryzin (1994) showed that the opti-
mal controls are constant over time and given by
¨
\ =
min(
ˆ
\, \
0
) and ¨ p =max( ´ p, p
0
). (The overbar notation
denotes the optimal ?uid solution.) Intuitively, the
?rm uses the revenue-maximizing price ´ p unless this
would deplete the capacity too soon, in which case it
increases its unit price to p
0
and sells its capacity by
time T , while accruing higher total revenues. Gallego
and van Ryzin (1997, §4.5) extended these results to
multiple products, but in that case without providing
such a succinct solution.
Multiproduct problem. Following the approach of §3,
we can reduce the multiproduct problem to an
appropriate single-product one, and thus solve it in
closed form. Speci?cally, recalling the de?nitions of
the aggregate revenue function í
r
(j) and optimal
demand rate vector \
r
(j) in (6), adjusted for the fact
that j =u
/
\, (11) can be rewritten as
max
{j(|), |?|0, T ]]
_
_
T
0
í
r
(j(|)) d|:
_
T
0
j(|) d| ?C, j(|) ? ?|
_
. (12)
Note that (12) is identical to a single-product problem
with revenue function í
r
, and thus is solvable using
the approach described above. Let j
0
:=C,T and ´ j =
argmax
j
í
r
(j). Then, the optimal solution to (12) is to
consume capacity at a constant rate ¨ j given by
¨ j(|) :=min( ´ j, j
0
) ?|, (13)
the corresponding vector of demand rates is \
r
( ¨ j),
while the price vector is p(\
r
( ¨ j)). A direct veri?cation
that this solution satis?es the optimality conditions
for (11) establishes the following:
Proposition 4. Let
¨
\(·) and ¨ p(·) denote the optimal
vectors of demand rates and prices for (11). Then,
¨
\, ¨ p
are constant over time and are given by
¨
\(|) =\
r
( ¨ j) and
¨ p(|) =p(\
r
( ¨ j)).
4.2. Asymptotically Optimal Heuristics Extracted
from the Deterministic Model
Based on the preceding analysis, we discuss three
heuristics for the underlying revenue management
problems, which we analyze in the asymptotic set-
ting introduced in Gallego and van Ryzin (1997) and
Cooper (2002). Among other things, it is shown that
the dynamic heuristic that “resolves” the ?uid policy
as | progresses is asymptotically optimal in an appro-
priate sense.
a. The Static Pricing Heuristic of Gallego and van Ryzin
(1997). This policy implements the static prices ¨ p spec-
i?ed in Proposition 4. (This is the “make-to-order”
heuristic in Gallego and van Ryzin 1997.)
4.2.1. Dynamic Heuristics. The static nature of
policy (a) is desirable for implementation purposes
(see Gallego and van Ryzin 1997), but also lacks the
capability of corrective action against stochastic ?uc-
tuations. This does not arise in the ?uid formulation,
where the capacity is drained along the optimal deter-
ministic trajectory, but it is relevant for the stochas-
tic problems of original interest. The next heuristics
provide two possible adjustments to this static policy
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 143
that add such control capability and seem of practical
interest. We start by observing that the solution of the
?uid pricing problem of §4.1 can also be described in
feedback form as
¨ j(x, |) =min
_
´ j,
x
T ?|
_
, (14)
where x is the remaining capacity at time |. The deter-
ministic trajectory of the ?uid model is, of course,
such that x,(T ? |) = C,T for all | if ´ j ? C,T , and
x,(T ?|) =(C ? ´ j|),(T ?|) ?C,T if ´ j - C,T . In both
cases, ¨ j(x, |) =min( ´ j, C,T ) for all x, | along the opti-
mal ?uid trajectory of the remaining capacity process,
and thus (14) is identical to the static control derived
in (13).
b. A List-Price Capacity Control (LPCC) Heuristic.
One way to implement (14) is by introducing capac-
ity control capability on top of the static prices given
in (a). Speci?cally, our second heuristic is de?ned as
follows:
1. price according to ¨ p and label products such that
¨ p
1
,u
1
? ¨ p
2
,u
2
?· · · ? ¨ p
n
,u
n
, and
2. compute ¨ j(x, |) and use the capacity controls
u
1
(x, |) =1 if x >0, u
1
(0, |) =0, and
u
i
(x, |) =
_
_
_
1 if ¨ j(x, |) ?
_
¡-i
u
¡
¨
\
¡
?0
0 otherwise
for i ?2. (15)
Note that this policy can only reduce the aggregate
capacity consumption rate from its nominal value of
n
i=1
u
i
¨
\
i
, but can never increase it. A product is made
available only if the ?uid solution starting from that
state would choose to sell this product in all future
time periods, and “closes” the product if the ?uid
solution would dictate only partial acceptance of the
associated demand.
This policy is a re?nement of the static pricing pol-
icy in (a) and the make-to-order heuristic of Gallego
and van Ryzin (1997). Other examples of joint pric-
ing and capacity controls can be found in the recent
papers by Vulcano et al. (2002), Lin et al. (2003), and
Feng and Xiao (2004).
c. A Dynamic Pricing Heuristic. The third policy
translates the aggregate control ¨ j(x, |) into product-
level rates (and prices) through
\(x, |) =\
r
( ¨ j(x, |)) and p(x, |) =p(\(x, |)), (16)
where the mapping \
r
(·) was the maximizer in (6)
and it is continuous in j. This corresponds to the idea
of “resolving” the ?uid problem as we step through
time, which is widely applied in practice, where, how-
ever, the resolving occurs at discrete points in time,
e.g., daily or weekly depending on the application set-
ting. Despite its practical appeal and use, to the best
of our knowledge policies that use this resolving idea
have not been analyzed theoretically, other than the
isolated example provided by Cooper (2002). Our pre-
ceding discussion illustrates that “resolving” is noth-
ing but implementing the ?uid policy in feedback
form. The analysis that follows provides a characteri-
zation of its asymptotic behavior, while the numerical
results of the next section demonstrate that it tends
to outperform the other two candidate policies. The
single-product version of this policy has also been
studied by Reiman (2002).
4.2.2. Asymptotic Performance Analysis of the
Pricing Heuristics. The remainder of this subsection
offers a brief asymptotic characterization of the per-
formance under these three heuristics that shows that
all three are (?uid-scale) asymptotically optimal in
a regime where the potential demand and capac-
ity grow proportionally large; this is the ?rst-order
asymptotic optimality criterion of Gallego and van
Ryzin (1997) and Cooper (2002). Speci?cally, using |
as an index, we consider a sequence of problems with
demand model \
|
(·) = |\(·) and capacity C
|
= |C,
and let | increase to in?nity; hereafter, a superscript |
will denote quantities that scale with |. Let N
i
for
i =1, . . . , n denote independent unit rate Poisson pro-
cesses, and recall that the functional strong-law-of-
large numbers for the Poisson process asserts that as
| ?~ and for all | ?0,
N
i
(||)
|
?| a.s. (17)
For all of the candidate policies, the capacity dy-
namics can be expressed as follows. The cumulative
demand for that product up to time | is equal to
N
i
(¹
|
i
(|)), where ¹
|
i
(|) =
_
|
0
\
|
i
(s) ds, and the remaining
capacity at time | is
X
|
(|) =C
|
?
n
_
i=1
u
i
N
i
(¹
|
i
(|)). (18)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
144 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
Our goal here is to analyze the “?uid-scale” behav-
ior of the capacity process de?ned as
¨
X
|
(|) :=X
|
(|),|
under the three candidate policies. The asymptotic
optimality of the static policy (a) was established
by Gallego and van Ryzin (1997). Nevertheless, we
include our analysis, which is different than theirs
and serves to introduce the ideas used in studying the
dynamic policies (b) and (c).
Analysis of the static heuristic (a). The ?rm uses the
constant price vector ¨ p, which induces the demand
rates \
|
( ¨ p) = |
¨
\. Under this policy, ¹
|
i
(|) =
¨
\
i
||, and
the capacity dynamics are X
|
u
(|) = (C
|
?
n
i=1
u
i
N
i
·
(¹
|
i
(|)))
÷
. (The subscript is used to identify the policy.)
As | ?~
N
i
(¹
|
i
(|))
|
?
¨
\
i
| a.s., uniformly in | ? |0, T ], (19)
from which it follows that as | ? ~ and for all
| ? |0, T ]
¨
X
|
u
(|) ?
_
C ?
n
_
i=1
u
i
¨
\
i
|
_
÷
=C ? ¨ j| a.s.
(The (·)
÷
was removed because from (13) ¨ j| ? C for
all | ? |0, T ].) Let í
|
u
denote the revenues extracted
under policy (a), and t
|
:= inf{s ? 0:
n
i=1
u
i
N
i
(
¨
\
i
|s)
? C
|
] be the random time where the aggregate
capacity requested reaches or exceeds the available
capacity C
|
. Then, í
|
u
:=
n
i=1
¨ p
i
N
i
(|
¨
\
i
min(T , t
|
)) ?o,
where o is a random variable that corrects revenues
for the case where t
|
-T , which is bounded above by
max
i
¨ p
i
. (We will not delve into an accurate descrip-
tion of o, because it is asymptotically negligible.)
Using (19) and arguing by contradiction, one can eas-
ily conclude that (T ?t
|
)
÷
?0 a.s., as | ?~. Using
the expression for í
|
u
we get the following:
Proposition 5. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the static pricing policy p
|
(x, |) = ¨ p for all x, | and
all |. Then, as | ?~,
¨
X
|
u
(|) ?C? ¨ j| a.s., uniformly in |,
and (1,|)í
|
u
?
n
i=1
¨ p
i
¨
\
i
T a.s.
Recall the fact established in Gallego and van
Ryzin (1997) that the solution of the deterministic
pricing problem serves as an upper bound for the
revenues extracted in the stochastic system, i.e., í
|
u
?
|
n
i=1
¨ p
i
¨
\
i
T . Applying the bounded convergence the-
orem gives that ?í
|
u
?
n
i=1
¨ p
i
¨
\
i
T , and establishes
the asymptotic optimality of the static pricing heuris-
tic (a).
Analysis of the dynamic heuristic (c). The dynamic
nature of this policy requires a more detailed study.
The cumulative demand for product i up to time | is
equal to N
i
(¹
|
i
(|)), where
¹
|
i
(|) =
_
|
0
|\
i
(s) ds where
\
i
(s) =\
r
i
_
min( ´ j, X
|
c
(s),(|(T ?s)))
_
(20)
for \
r
i
(·) de?ned in (6), and X
|
c
(|) denotes the remain-
ing capacity at time | under policy (c), de?ned in (18).
Now, note that ¹
|
(0) = 0, ¹
|
(|) is nondecreasing
and ¹
|
i
(|) ? ¹
|
i
(s) ? (| ? s) · |\
i, max
, where \
i, max
=
argmax{\
i
: \ ? ]. This implies that the family of pro-
cesses {(1,|)¹
|
(|)] is equicontinuous, and therefore
relatively compact. It follows that it has a converging
subsequence, say |
¡
, such that (1,|
¡
)¹
|
|
i
(|) ?
¨
¹
i
(|) for
all i. Along this subsequence we get that N
i
(¹
|
¡
i
(|)),|
¡
converges to
¨
¹
i
(|), and therefore that
¨
X
|
¡
c
(|) itself con-
verges to a limit ¨ x
c
(|); the last two results hold a.s.,
uniformly in |. Expression (22) will show that the
limit trajectories do not depend on the selection of
the converging subsequence itself. In the sequel we
denote the converging subsequence by | to simplify
notation. Using the continuity of \
r
i
(·) and Lemma 2.4
of Dai and Williams (1995), we get that
1
|
¹
|
i
(|) =
_
|
0
\
r
i
_
min
_
´ j,
¨
X
|
c
(s)
T ?s
__
ds
?
_
|
0
\
r
i
_
min
_
´ j,
¨ x
c
(s)
T ?s
__
ds (21)
as | ?~a.s., uniformly in |. Using (17), (18), and (21),
we get that as | ?~
¨
X
|
c
(|) = C ?
1
|
n
_
i=1
u
i
N
i
(¹
|
i
(|))
? C ?
_
|
0
min
_
´ j,
¨ x
c
(s)
T ?s
_
ds =C ? ¨ j|, (22)
a.s., uniformly in |. The revenues extracted under pol-
icy (c) are í
|
c
=
n
i=1
_
|
0
p
|
i
(|) dN
i
(¹
|
i
(|)), where p
|
(|) is
the price vector that corresponds to \
r
(min( ´ j,
¨
X
|
c
(|),
(T ? |))), the demand rate vector at time |, and
the integrals should be interpreted in the Riemann-
Stieltjes sense. From (21) and (22) we have that
\
r
i
(min( ´ j,
¨
X
|
c
(|),(T ?|))) ?
¨
\
i
a.s., uniformly in |. By
the continuity of the inverse demand function we
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 145
have that p
|
(|) ? ¨ p a.s., uniformly in |, and therefore,
again using Lemma 2.4 of Dai and Williams (1995),
we get the result summarized below.
Proposition 6. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the dynamic pricing heuristic de?ned through (20).
Then,
¨
X
|
c
(|) ? C ? ¨ j(|) a.s., uniformly in |0, T ], and
(1,|)í
|
c
?
n
i=1
¨ p
i
¨
\
i
T a.s.
Analysis of the LPCC heuristic (b). This policy is
de?ned through ¹
|
i
(|) = |
¨
\
i
·
_
|
0
u
|
i
(|) d|, where u
|
i
(|)
was de?ned in (15) and can be expressed as follows:
u
|
1
(|) =1{
¨
X
|
|
(|) >0] and
u
|
i
(|) =1
_
min
_
´ j
¨
X
|
|
(|)
T ?|
_
?
_
¡-i
u
¡
¨
\
¡
?u
i
¨
\
i
_
for i ?2,
(23)
where 1{·] is the indicator function. Similarly to the
analysis of policy (c), the family {
¨
X
|
|
(|), | ? |0, T ]] is
tight, and thus it has a converging subsequence {|
¡
]
on which
¨
X
|
¡
|
(|) ? ¨ x
|
(|) a.s., uniformly in |. Writing
down ¨ x
|
(|) and evaluating u
i
(|) reveals that in the
limit model u
i
(|) =1 for all products i. Let í
|
|
be the
corresponding revenue. Similar arguments to the ones
used above give the following result.
Proposition 7. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the LPCC heuristic de?ned through (23). Then,
¨
X
|
|
(|) ?C? ¨ j(|) a.s., uniformly in |0, T ], and (1,|)í
|
|
?
n
i=1
¨ p
i
¨
\
i
T a.s.
That is, resolving in the context of the dynamic
pricing or the LPCC heuristics is ?uid-scale asymp-
totically optimal, as is the static policy (a). This
shows that the suboptimal behavior demonstrated by
Cooper (2002) does not persist in systems with large
capacity and large demand. The same asymptotic per-
formance can be achieved while resolving at discrete
points in time, provided that this is done suf?ciently
frequently. If l
|
is the time between resolving epochs,
then the type of analysis used in studying discrete-
review policies (see Harrison 1996 and Maglaras 2000)
can be applied to show that it suf?ces that l
|
? 0.
This allows the number of demand requests between
resolving periods to be large in absolute terms, but
small compared to the capacity; e.g., a period l
|
=
log(|),| corresponds to order log(|) arrivals.
4.3. Dynamic Pricing Network Revenue
Management Problems
Suppose that the ?rm is operating a network of
resources, indexed by ¡ = 1, . . . , m, and that each
product i request consumes ¹
i¡
units of resource ¡
capacity. Let ¹ := |¹
i¡
] denote the associated capac-
ity consumption matrix, and assume that the initial
capacity for each resource ¡ is C
¡
. Then, the ?uid
model formulation of the network dynamic pricing
problem is
max
{\(|), |?|0, T ]]
_
_
T
0
í(\(|)) d|:
_
T
0
¹\(|) d| ?C and \(|) ? ?|
_
. (24)
As before, this problem can be expressed in terms
of j, which is de?ned by j :=¹\. Speci?cally, let
í
r
(j) :=max
\
{í(\): ¹\ =j, \ ? ] (25)
be the maximum achievable revenue rate when
resource capacity is consumed at a rate j, and let \
r
(j)
denote the corresponding vector of optimal demand
rates. Then, (24) can be reduced to
max
{j(|), |?|0, T ]]
_
_
T
0
í
r
(j(|)) d|:
_
T
0
j(|) d| ?C and j(|) ? ?|
_
. (26)
Let ¨ j denote the solution to (26). Then, \
r
( ¨ j) is the
vector of optimal demand rates for (24). This reduc-
tion could prove computationally bene?cial because,
as is often the case, the number of products (e.g.,
the number of fare-class and origin-destination pairs)
tends to be greater than the number of resources (e.g.,
number of ?ights in a hub-and-spoke network). We
refer the reader to Gallego and van Ryzin (1997) and
Kleywegt (2001) for ?uid formulations to multiprod-
uct network revenue management problems.
5. Numerical Examples
This section reports on a set of numerical examples
that contrast the performance of the heuristics pro-
posed in the previous section to that of the optimal
policy obtained from the dynamic program. Our base
model has two products, each consuming one unit of
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
146 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
capacity per request, and a linear demand relation-
ship of the form \(p) =A?8p with A=|0.3, 0.1] and
T = 200 time periods. The price set is = {p: A ?
8p ?0], the inverse demand is p(\) =8
?1
(A?\), and
the revenue function is í(\) =\
/
8
?1
(A?\). The poli-
cies that we consider are the following:
• “RevMax” corresponds to the monopoly price
vector ´ p that maximizes the aggregate instantaneous
revenue rate disregarding the capacity constraints,
given by ´ p = 8
?1
(A ?
ˆ
\), where
ˆ
\ = argmax{\
/
8
?1
·
(A?\): \ ?0] =(1,2)(8
?1
÷8
?1
/
)
?1
A.
• “Fluid” implemented the price vector ¨ p =p(\
r
( ¨ j))
as de?ned in Proposition 4.
• “LPCC” is the joint (list) pricing and capacity
control heuristic de?ned through (15).
• “DynPrice” is the dynamic implementation of the
?uid policy de?ned through (16).
• “DP” implemented the solution of the dynamic
program outlined in §3.
Remark (Comments onComplexity). The expected
revenues under the ?rst two static policies were com-
puted analytically using a binomial model that under
DP was simply V(C, T ), while for the remaining
policies we averaged out revenues over 1,000 sim-
ulated sample paths. The effort needed to compute
V(C, T ) in problems with uniform capacity require-
ments (Tables 1 to 3) is that of solving a single-
product pricing problem, which grows in proportion
to C T . If í
r
(j) and \
r
(j) cannot be expressed in
closed form and are not precomputed and stored,
the state space dimension of the dynamic program
stays the same, but its complexity increases by a con-
stant factor that depends on the number of products.
Table 4 looks at examples with nonuniform capac-
ity requirements, where the demand aggregation no
longer applies and the backward induction step of
the dynamic program needs to be changed, increasing
the overall complexity again by a constant factor. The
complexity of computing LPCC and DynPrice, the
performance of which is the emphasis of our study, is
negligible.
5.1.1. The Effect of the Joint Capacity Constraint.
Table 1 provides an illustration of the behavior of
these heuristics on a particular problem instance as
we varied the available capacity. Tables 2 and 3 will
provide summary statistics for many randomly gener-
ated test cases. The demand model had no cross-price
Table 1 Optimality Gaps Relative to Optimal Policy (DP)
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
25 31.4 3.0 2.6 0.4 417.63
30 22.2 4.4 3.3 1.0 440.53
35 12.6 5.1 1.9 1.3 451.63
40 5.4 5.4 0.7 0.7 457.00
45 1.8 1.8 0.2 0.2 459.50
50 0.7 0.7 0.3 0.3 460.39
Note. ß =diag(1, 6)
terms and was given by \
1
(p) =0.3 ?1p
1
and \
2
(p) =
0.1 ?6p
2
.
The Fluid pricing problem becomes unconstrained
for C ? 40 units, in which cases the RevMax and
Fluid prices coincide. We observe the following. First,
the relative performance under all heuristics improves
as the capacity C increases; this is consistent with
the results of Gallego and van Ryzin (1994, 1997) for
Fluid and RevMax. Second, while the Fluid heuris-
tic that incorporates the capacity constraint outper-
forms RevMax when capacity is scarce, its regret over
the DP policy can still be substantial (2%–5%). Third,
when the capacity is scarce, C ? 25, the ?uid prices
effectively switch off Product 2 and operate the sys-
tem as a single-product one. As the capacity increases,
it is optimal to offer both products, and the effect
of the capacity control of LPCC becomes more evi-
dent. Switching from an effectively single-product to
a two-product solution causes the optimality gaps to
be nonmonotone. Fourth, the dynamic pricing (resolv-
ing) heuristic is signi?cantly better than all others
when capacity is scarce.
5.1.2. The Cross-Price Elasticity Effects and Mul-
tiple Products. Table 2 summarizes results from 100
test cases for systems with ?xed capacity C =40, lin-
ear demand model with A=|0.3, 0.1], and randomly
Table 2 Average and Standard Deviations of % Optimality Gaps for
Two-Product Examples: 0 =40, '(p) =A?ßp, A =|0.3, 0.1],
and Random ß Matrices
´ p RevMax Fluid LPCC DynPrice
0.8–0.9 1.5 (0.3) 1.6 (0.3) 1.6 (0.3) 0.8 (0.2)
0.9–1.0 3.6 (0.6) 3.6 (0.5) 3.1 (1.6) 1.1 (0.2)
1.0–1.1 5.2 (1.1) 3.9 (0.3) 3.0 (1.5) 1.0 (0.2)
1.1–1.2 9.8 (1.3) 3.1 (0.4) 2.4 (0.3) 1.0 (0.2)
1.2–1.3 14.0 (1.5) 3.1 (0.4) 2.1 (0.2) 0.9 (0.2)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 147
Table 3 Average and Standard Deviations of % Optimality Gaps for
Three-Product Examples: 0 = 40, '(p) = A ? ßp, A =
|0.3, 0.05, 0.05], and Random ß Matrices
´ p RevMax Fluid LPCC DynPrice
0.8–0.9 1.5 (0.3) 1.6 (0.2) 1.5 (0.3) 0.8 (0.1)
0.9–1.0 3.3 (0.7) 3.3 (0.7) 3.3 (1.6) 1.0 (0.2)
1.0–1.1 6.4 (1.4) 3.7 (0.4) 3.6 (2.0) 1.1 (0.2)
1.1–1.2 9.4 (1.3) 3.1 (0.3) 3.0 (2.0) 0.9 (0.2)
1.2–1.3 14.0 (1.3) 3.0 (0.3) 2.1 (1.5) 0.8 (0.2)
generated 8 matrices; the elements of the main diago-
nal were drawn from a uniform distribution on |0, 1],
while the cross terms were drawn from a uniform dis-
tribution on |?1, 0]. We then tested that the dominant
diagonal condition given in §2 was satis?ed, which
also assured that an inverse exists. Results have been
grouped according to their nominal load factors ´ j :=
(
i
u
i
ˆ
\
i
),C, where
ˆ
\ is the RevMax demand vector
that would maximize instantaneous revenue in the
absence of the capacity constraint.
1
The table reports
the average and standard deviation of the % optimal-
ity gap for each candidate policy. The main obser-
vation is that DynPrice signi?cantly outperformed
all other heuristics not only in terms of the average
gap, but also in its standard deviation. In turn, LPCC
improved over Fluid in cases where the capacity con-
straint was binding and the ability to incorporate
the extra element of capacity control decisions was
bene?cial. Table 3 reports results for three-product
examples, and illustrates the consistently good perfor-
mance of the LPCC and DynPrice policies. The resolv-
ing structure of the latter is important in problems
with multiple products and substitution and/or com-
plementarity effects.
5.1.3. NonuniformCapacity Requirements. Table
4 summarizes results for two models with two prod-
ucts that have different capacity requirements. This
change complicates the associated dynamic program-
ming formulation (see comments in the beginning
of this section), but does not affect the ?uid analy-
sis of §4.1, and the heuristics extracted therein are
still valid. In the notation of §4, product i consumes
u
i
units of capacity and u
1
,=u
2
. Our ?ndings suggest
1
A ?le with the test parameters for Tables 2 and 3 is avail-
able athttp://www.meiss.com/ orhttp://www.gsb.columbia.edu/
faculty/cmaglaras/maglaras.htm.
Table 4 Optimality Gaps Relative to Optimal Policy (DP)
(i) ß =|1 ?0.4; ?0.6 6] and a =|1 2]
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
30 42.7 4.3 3.7 2.7 476.91
40 27.1 5.6 2.1 1.5 496.05
50 12.0 5.7 1.7 1.0 502.77
60 2.9 3.2 1.1 0.3 505.81
70 0.8 0.7 0.4 0.3 506.73
80 0.3 0.2 0.2 0.1 506.86
(ii) ß =|1 ?0.4; ?0.6 6] and a =|2 1]
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
30 39.5 4.4 4.0 3.9 340.95
40 32.2 3.3 3.0 1.7 406.89
50 23.4 3.0 2.9 0.6 451.85
60 14.2 3.7 3.4 1.2 479.64
70 6.0 4.4 3.6 0.8 495.78
80 1.7 2.0 1.7 0.7 503.60
that the ?uid model heuristics perform quite well in
cases where the capacity requirements are small com-
pared to the capacity itself. (Eventually, as C and \
grow large, these policies become asymptotically opti-
mal in the sense of Propositions 5 to 7.)
The last three tables illustrate that static pricing is
close to optimal in problem instances that are either
very under- or overloaded, and that the effect of
dynamic pricing, either through the optimal policy
(DP) or the DynPrice heuristic, is most pronounced
when ´ j is close to 1. This is intuitive: When ´ j _ 1,
the system’s capacity far exceeds the nominal require-
ment under the prices that maximize revenues per
unit time (implemented in RevMax), and thus one
would expect that the static pricing heuristics RevMax
and Fluid to be close to optimal. In contrast, if ´ j ¸1,
the system’s capacity is too low, and the static prices
implemented through the Fluid heuristic are close
to optimal. Finally, we did not observe any problem
instances where the performance under the DynPrice
heuristic was worse (in a statistically signi?cant man-
ner) than that under the LPCC or Fluid heuristics.
The narrowest gap between LPCC and DynPrice was
observed in the ?rst row of Table 4, which, due to
the nonuniform capacity requirements, corresponds
to the problems with the lowest overall capacity in
terms of the number of sales; this is the closest to the
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
148 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
setting in Cooper’s example (2002), which had low
capacity and a short selling horizon.
References
Bitran, G., R. Caldentey. 2003. An overview of pricing models for
revenue management. Manufacturing Service Oper. Management
5(3) 203–229.
Brumelle, S., J. McGill. 1993. Airline seat allocation with multiple
nested fare classes. Oper. Res. 41(1) 127–137.
Cooper, W. 2002. Asymptotic behavior of an allocation policy for
revenue management. Oper. Res. 50(4) 720–727.
Dai, J. G., R. J. Williams. 1995. Existence and uniqueness of semi-
martingale re?ecting Brownian motions in convex polyhe-
drons. Theory Probab. Appl. 40(1) 1–40.
Elmaghraby, W., P. Keskinocak. 2003. Dynamic pricing: Research
overview, current practices and future directions. Management
Sci. 49(10) 1287–1389.
Feng, Y., B. Xiao. 2000. A continuous-time yield management model
with multiple prices and reversible price changes. Management
Sci. 46(5) 644–657.
Feng, Y., B. Xiao. 2004. Integration of pricing and capacity allocation
for perishable products. Preprint, Chinese University of Hong
Kong.
Gallego, G., G. van Ryzin. 1994. Optimal dynamic pricing of inven-
tories with stochastic demand over ?nite horizons. Management
Sci. 40(8) 999–1020.
Gallego, G., G. van Ryzin. 1997. A multiproduct dynamic pricing
problem and its applications to network yield management.
Oper. Res. 45(1) 24–41.
Harrison, J. M. 1996. The BIGSTEP approach to ?ow manage-
ment in stochastic processing networks. F. Kelly, S. Zachary,
I. Ziedins, eds. Stochastic Networks: Theory and Applications.
Oxford University Press, Oxford, UK, 57–90.
Horn, R. A., C. R. Johnson. 1994. Matrix Analysis. Cambridge Uni-
versity Press, Cambridge, UK.
Kleywegt, A. J. 2001. An optimal control problem of dynamic pric-
ing. Working paper, Georgia Institute of Technology, Atlanta,
GA.
Lautenbacher, C., S. Stidham. 1999. The underlying Markov deci-
sion process in the single-leg airline yield-management prob-
lem. Transportation Sci. 33(2) 136–146.
Lee, T., M. Hersh. 1993. A model for dynamic airline seat inventory
control with multiple seat bookings. Transportation Sci. 27(3)
252–265.
Lin, G. Y., Y. Lu, D. D. Yao. 2003. The stochastic knapsack revisited:
Structure, switch-over policies, and dynamic pricing. Preprint,
Columbia University, New York.
Maglaras, C. 2000. Discrete-review policies for scheduling stochas-
tic networks: Trajectory tracking and ?uid-scale asymptotic
optimality. Ann. Appl. Probab. 10(3) 897–929.
Maglaras, C. 2006. Revenue management for a multi-class single-
server queue via a ?uid model analysis. Oper. Res. Forthcom-
ing.
McGill, J., G. van Ryzin. 1999. Revenue management: Research
overview and prospects. Transportation Sci. 33(2) 233–256.
Reiman, M. I. 2002. Asymptotically optimal dynamic pricing for
a wholesale/retail telecommunications service provider. 2nd
INFORMS Conf. Revenue Management, New York.
Talluri, K., G. van Ryzin. 2004a. Revenue management under a gen-
eral discrete choice model of consumer behavior. Management
Sci. 50(1) 15–33.
Talluri, K., G. van Ryzin. 2004b. The Theory and Prac-
tice of Revenue Management. Kluwer Academic Publishers,
Boston/Dordrecht/London.
Vulcano, G., G. van Ryzin, C. Maglaras. 2002. Optimal dynamic
auctions for revenue management. Management Sci. 48(11)
1388–1407.
Zhao, W., Y.-S. Zheng. 2000. Optimal dynamic pricing for perishable
assets with nonhomogeneous demand. Management Sci. 46(3)
375–388.
doc_767868489.pdf
Consider a firm that owns a fixed capacity of a resource that is consumed in the production or delivery of
multiple products. The firm strives to maximize its total expected revenues over a finite horizon, either
by choosing a dynamic pricing strategy for each product or, if prices are fixed, by selecting a dynamic rule
that controls the allocation of capacity to requests for the different products. This paper shows how these wellstudied
revenue management problems can be reduced to a common formulation in which the firm controls
the aggregate rate at which all products jointly consume resource capacity, highlighting their common structure,
and in some cases leading to algorithmic simplifications through the reduction in the control dimension of
the associated optimization problems. In the context of their associated deterministic (fluid) formulations, this
reduction leads to a closed-form characterization of the optimal controls, and suggests several natural static and
dynamic pricing heuristics. These are analyzed asymptotically and through an extensive numerical study. In the
context of the former, we show that “resolving” the fluid heuristic achieves asymptotically optimal performance
under fluid scaling.
MANUFACTURING & SERVICE
OPERATIONS MANAGEMENT
Vol. 8, No. 2, Spring 2006, pp. 136–148
issn1523-4614[ eissn1526-5498[ 06[ 0802[ 0136
informs
®
doi 10.1287/msom.1060.0105
©2006 INFORMS
Dynamic Pricing Strategies for Multiproduct
Revenue Management Problems
Constantinos Maglaras
Columbia Business School, Columbia University, 409 Uris Hall, 3022 Broadway,
New York, New York 10027, [email protected]
Joern Meissner
Lancaster University Management School, Lancaster University, Room A48,
Lancaster LA1 4XY, United Kingdom, [email protected]
C
onsider a ?rm that owns a ?xed capacity of a resource that is consumed in the production or delivery of
multiple products. The ?rm strives to maximize its total expected revenues over a ?nite horizon, either
by choosing a dynamic pricing strategy for each product or, if prices are ?xed, by selecting a dynamic rule
that controls the allocation of capacity to requests for the different products. This paper shows how these well-
studied revenue management problems can be reduced to a common formulation in which the ?rm controls
the aggregate rate at which all products jointly consume resource capacity, highlighting their common structure,
and in some cases leading to algorithmic simpli?cations through the reduction in the control dimension of
the associated optimization problems. In the context of their associated deterministic (?uid) formulations, this
reduction leads to a closed-form characterization of the optimal controls, and suggests several natural static and
dynamic pricing heuristics. These are analyzed asymptotically and through an extensive numerical study. In the
context of the former, we show that “resolving” the ?uid heuristic achieves asymptotically optimal performance
under ?uid scaling.
Key words: revenue management; dynamic pricing; capacity controls; ?uid approximations; ef?cient frontier
History: Received: July 21, 2003; accepted: November 11, 2005. This paper was with the authors 9 months for
3 revisions.
1. Introduction
Consider a ?rm that owns a ?xed capacity of a cer-
tain resource that is consumed in the process of pro-
ducing or offering multiple products or services, and
which must be consumed over a ?nite time horizon.
The ?rm’s problem is to maximize its total expected
revenues by selecting the appropriate dynamic con-
trols. We consider two well-studied variants of this
problem. In the ?rst, the ?rm is assumed to be a
monopolist or to operate in a market with imper-
fect competition, and thus to have power to in?u-
ence the demand for each product by varying its
price. In this setting, the ?rm’s problem is to choose
a dynamic pricing strategy for each of its products
to optimize expected revenues. In the second variant,
prices are assumed to be ?xed either by the competi-
tion or through a higher-order optimization problem,
and the ?rm’s problem is now to choose a dynamic
capacity allocation rule that controls when to accept
new requests for each of these products. In the sequel,
these two problems are referred to as the “dynamic
pricing” and “capacity control” formulations, respec-
tively. Revenue management problems of that sort
gained interest in the late 1970s in the context of
the airline industry, and have since been successfully
introduced in a variety of other areas such as hotels,
cruise lines, rental cars, retail, etc.
This paper illustrates how these two problems can
be reduced to a common formulation, thus connect-
ing prior results that have appeared in the literature
under a uni?ed framework, and explores some of
the consequences of this formulation. Speci?cally, we
show that the multiproduct dynamic pricing prob-
lem introduced by Gallego and van Ryzin (1997) and
the capacity control problem of Lee and Hersh (1993)
can be recast within this common framework, and
be treated as different instances of a single-product
pricing problem for appropriate concave revenue
136
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 137
functions (Propositions 1 and 2). Broadly speaking,
this is done by decoupling the revenue maximization
problems in two parts: First, at each point in time the
?rm selects an aggregate capacity consumption rate
from all products, and second, it computes the vector
of demand rates to maximize instantaneous revenues
subject to the constraint that all products jointly con-
sume capacity at the aforementioned rate. The latter is
akin to the basic microeconomics problem of resource
allocation subject to a budget constraint, and gives
rise to an appropriate aggregate revenue rate function
in each case. This common formulation recovers well-
known structural results regarding the monotonicity
properties of the value function and the associated
controls (see Proposition 3 and Corollary 2), which
were previously derived in the literature while study-
ing each of these problems in isolation; see, e.g.,
Gallego and van Ryzin (1994, 1997), Lee and Hersh
(1993), Lautenbacher and Stidham (1999), Zhao and
Zheng (2000), and the recent book by Talluri and van
Ryzin (2004b). It also facilitates the derivation of new
results, such as Corollary 1, that extend these proper-
ties to the setting of multiproduct pricing policies.
Extending this idea of demand aggregation in con-
sidering deterministic and continuous (?uid) approx-
imations of the underlying problems suggests a set
of simple pricing and capacity control heuristics for
the underlying problems. These stem from the fact
that this aggregated formulation leads to closed-
form solutions to the ?uid model revenue maxi-
mization problems (see Proposition 4). This extends
the analysis of Gallego and van Ryzin (1997), which
offered only an implicit characterization of these poli-
cies in the multiproduct setting; see also Bitran and
Caldentey (2003) for a discussion of deterministic
multiproduct pricing problems. Based on the solution
of the ?uid formulation, we propose three heuristics:
(i) a static pricing heuristic, (ii) a static pricing heuris-
tic applied in conjunction with an appropriate capac-
ity allocation policy, and (iii) a “resolving” heuristic
that reevaluates the ?uid policy as a function of the
current state and time-to-go (which is derived by
expressing the ?uid solution in feedback form). The
?rst of these heuristics was proposed by Gallego and
van Ryzin (1997), while policies that combine static
prices with capacity controls as in (ii) have been sug-
gested in other papers such as McGill and van Ryzin
(1999), Feng and Xiao (2004), and Lin et al. (2003).
Finally, the “resolving” heuristic (iii) is widely applied
in practice, but to the best of our knowledge has
not been analyzed theoretically thus far. The only
exception was the negative result of Cooper (2002),
which illustrated through an example that resolving
may in fact do worse than applying the static ?uid
policy. Propositions 5–7 in §4.2 establishes that all
three heuristics achieve asymptotically optimal per-
formance under ?uid scaling, i.e., in the spirit of Gal-
lego and van Ryzin (1997) and Cooper (2002). These
results show that the phenomenon demonstrated in
Cooper’s example does not persist in problems with
large capacity and demand, where, in fact, resolv-
ing achieves the asymptotically optimal performance.
Moreover, the numerical results of §5 illustrate that
the dynamic heuristics (ii) and (iii) tend to outperform
the static one.
In terms of qualitative insights, we ?nd that the
translation of the capacity consumption rate to a set
of product-level controls that jointly maximize the
instantaneous revenue rate de?nes an ef?cient frontier
for the ?rm’s optimal pricing and capacity control
strategies. This captures in a tractable way the interac-
tions between products due to cross-elasticity effects
and the joint capacity constraint. The idea of an ef?-
cient frontier has appeared in Talluri and van Ryzin
(2004a) in the context of a capacity control problem for
a model with customer choice among products, and
in Feng and Xiao (2000, 2004) while studying pricing
problems with a predetermined set of price points.
The remainder of the paper is structured as fol-
lows. This section concludes with some additional
bibliographic references. Section 2 describes the two
problem formulations. Section 3 demonstrates the
reduction of the dynamic programming formulations
to that of a single-product pricing problem, and
derives some of its structural properties. Section 4
studies the ?uid formulations of these problems and
analyzes the asymptotic performance of the associ-
ated heuristics mentioned earlier. Section 4.3 outlines
how the same approach can be extended to a network
setting. Section 5 provides some numerical illustration
of our results and offers some concluding remarks.
The idea of demand aggregation appeared in Tal-
luri and van Ryzin (2004a) while analyzing a capac-
ity control problem for a system where customer
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
138 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
behavior is captured through a discrete choice model,
while similar techniques have been exploited in
the past in the numerical solution of the dynamic
programs associated with revenue management prob-
lems. Similar ideas also arise in problems of rev-
enue management of multiproduct queueing sys-
tems; see Maglaras (2006) for a recent example.
The papers by Elmaghraby and Keskinocak (2003),
Bitran and Caldentey (2003), and McGill and van
Ryzin (1999), and the book by Talluri and van Ryzin
(2004b), provide comprehensive overviews of the
areas of dynamic pricing and revenue management.
The modelling framework adopted in this paper
closely matches that of Gallego and van Ryzin (1994,
1997). Additional references on the capacity con-
trol formulation are Brumelle and McGill (1993) and
Lautenbacher and Stidham (1999). Finally, a dynamic
pricing heuristic that is related to the one studied in
this paper was derived by Reiman (2002) as the solu-
tion to a “second-order” control problem that seeks
to minimize an appropriate measure of the devia-
tion from the inventory trajectory derived through
the deterministic model. Indeed, the single-product
policy proposed in Reiman (2002) is the same as the
one we derive here. The multiproduct formulation in
Reiman (2002) differs from ours, and therefore the
resulting pricing policies also differ.
2. Single Resource, Multiproduct
Model
This section formulates the multiproduct dynamic
pricing and capacity control problems studied by
Gallego and van Ryzin (1997) and Lee and Hersh
(1993), respectively, among others.
2.1.1. Dynamic Pricing Problem. Consider a ?rm
endowed with C units of capacity of a single resource
used in producing or offering multiple products or
services, indexed by i = 1, . . . , n. Each product i
request requires one unit of capacity. There is a ?nite
horizon T over which the resources must be used,
and capacity cannot be replenished up to that time.
The salvage value of remaining capacity at time T
is assumed to be zero. (A constant per-unit sal-
vage value would also result in formulations sim-
ilar to those developed below.) The ?rm is either
a monopolist or is assumed to operate in a mar-
ket with imperfect competition, and, therefore, has
power to in?uence the demand for each product by
varying its menu of prices. Let p(|) =|p
1
(|), . . . , p
n
(|)]
denote the vector of prices at time |. The demand
process is assumed to be n-dimensional nonhomoge-
neous Poisson process with rate vector \ determined
through a demand function \(p(|)), where \: ?,
?
n
is the set of feasible price vectors, and =
{x ? 0: x = \(p), p ? ] ?
n
÷
is the set of achievable
demand rate vectors. We assume that is a convex
set. For ease of exposition, the demand function \(·)
is assumed to be stationary; an extension to allow for
nonstationarities could follow Gallego and van Ryzin
(1994, 1997) and Zhao and Zheng (2000). This class of
demand functions incorporates product complemen-
tarity and substitution effects. Following Gallego and
van Ryzin (1994, 1997), we consider regular demand
functions that satisfy some additional conditions. In
the sequel, x
/
denotes the transpose of any matrix x,
for any real number j, j
÷
:=max(0, j), c is the vector
of ones of appropriate dimension, and “a.s.” stands
for almost surely.
De?nition 1. A demand function is said to be reg-
ular if it is a continuously differentiable, bounded
function, and: (a) for each product i, \
i
(p) is strictly
decreasing in p
i
, (b) lim
p
i
?~
\
i
(p) =0 (i.e., consumers
have bounded wealth), and (c) the revenue rate
p
/
\(p) =
n
i=1
p
i
\
i
(p) is bounded for all p ? and has
a ?nite maximizer ¨ p.
We assume that there exists a continuous inverse
demand function p(\), p: ? , that maps an
achievable vector of demand rates \ into a corre-
sponding vector of prices p(\). This allows us to view
the demand rate vector as the ?rm’s control, and infer
the appropriate prices using the inverse demand func-
tion. The expected revenue rate can be expressed as
a function of the vector of demand rates \ as í(\) :=
\
/
p(\), and is assumed to be continuous, bounded,
and strictly concave.
Example. Under a linear demand model, the de-
mand for product i is given by
\
i
(p) =A
i
?|
ii
p
i
?
_
¡,=i
|
i¡
p
¡
or
(in vector form) \(p) =A?8p,
where A
i
is the market potential for product i and |
ii
,
|
i¡
are the price and cross-price sensitivity parame-
ters. The inverse demand and revenue functions are
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 139
p(\) = 8
?1
(A ? \) and í(\) = \
/
8
?1
(A ? \), respec-
tively. Assumption 1 requires that |
ii
> 0 for all i.
To ensure that the inverse demand function is well
de?ned and the revenue function is concave, we
require that either |
ii
>
¡,=i
[|
¡i
[ or |
ii
>
¡,=i
[|
i¡
[ for
all i; both conditions guarantee that 8 is invertible and
that its eigenvalues have positive real parts (Horn and
Johnson 1994, Thm. 6.1.10).
The problem that we address is roughly described
as follows: Given an initial capacity C, a selling hori-
zon T , and a demand function that maps a vector of
prices to a vector of demand rates, the ?rm’s goal is to
choose a nonanticipating dynamic pricing strategy for
each product in order to maximize its total expected
revenues.
We adopt a discrete-time formulation, i.e., one
where time has been discretized in small intervals
of length o|, indexed by | = 1, . . . , T , such that
(product i arrival in |0, o|]) = \
i
o| ÷o(o|) for all i,
and (product i and ¡ arrivals in |0, o|]) =\
i
\
¡
(o|)
2
÷
o((o|)
2
), where o(x) implies that o(x),x ?0 as x ?0.
With slight abuse of notation, we write \
i
in place of
\
i
o|, and refer to \
i
either as the demand or the buy-
ing probability for product i. The random demand
vector in period |, denoted by ((|, \), is Bernoulli
with probabilities \(|) = \(p(|)), and ((
i
(|) = 1) =
\
i
(p(|)) and ((
i
(|) =0) =1?\
i
(p(|)) for all i. Treating
the demand rates \
i
as the control variables (prices
are inferred via the inverse demand relationship),
the discrete-time formulation of the dynamic pricing
problem of Gallego and van Ryzin (1997) is
max
{\(|), |=1,...,T ]
_
?
_
T
_
|=1
p(\(|))
/
((|, \)
_
:
T
_
|=1
c
/
((|,\) ?C a.s. and \(|) ? ?|
_
. (1)
2.1.2. Capacity Control Problem. The second
problem that we consider is the one studied by
Lee and Hersh (1993), where the price vector p and
the demand rate vector \ = \(p) are ?xed, and the
?rm optimizes over capacity allocation decisions. For
this problem and without any loss of generality, we
assume that products are labelled such that p
1
?
p
2
?· · · ?p
n
. The ?rm has discretion as to which prod-
uct requests to accept at any given time. This is mod-
elled through the control u
i
(|) that is equal to the
probability of accepting a product i request at time |.
It is customary to assume that the ?rm is “opening”
or “closing” products, thus considering controls u
i
(·)
that are zero or one, but this need not be imposed as
a restriction. The dynamic capacity control problem is
the following:
max
{u(|), |=1,...,T ]
_
?
_
T
_
|=1
p
/
((|, u\)
_
:
T
_
|=1
c
/
((|, u\) ?C
a.s. 1 and u
i
(|) ? |0, 1] ?|
_
, (2)
where u\ above denotes the vector with coordi-
nates u
i
\
i
.
3. Analysis of the Pricing and
Capacity Control Problems
This section describes how to reduce (1) and (2) into
dynamic optimization problems where the control is
the (one-dimensional) aggregate capacity consump-
tion rate. Subsequently, we derive some structural
properties for these two problems through a uni?ed
analysis.
3.1. A Common Formulation in Terms of
the Aggregate Capacity Consumption
3.1.1. Dynamic Pricing Problem. Let x denote the
number of remaining units of capacity at the begin-
ning of period |, and V(x, |) be the expected revenue-
to-go starting at time | with x units of capacity left.
Then, the Bellman equation associated with (1) is
V(x, |) =max
\?
_
n
_
i=1
\
i
|p
i
(\) ÷V(x ?1, | ÷1)]
÷(1 ?c
/
\)V(x, | ÷1)
_
, (3)
with the boundary conditions
V(x, T ÷1) =0 ?x and V(0, |) =0 ?|. (4)
Letting AV(x, |) =V(x, | ÷1) ?V(x ?1, | ÷1) denote
the marginal value of one unit of capacity as a func-
tion of the state (x, |), (3) can be rewritten as
V(x, |) = max
\?
_
í(\) ?
n
_
i=1
\
i
AV(x, |)
_
÷V(x, | ÷1)
= max
j?
{í
r
(j) ?jAV(x, |)] ÷V(x, | ÷1), (5)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
140 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
where j :=
n
i=1
\
i
is the aggregate rate of capacity con-
sumption, := {j:
n
i=1
\
i
= j, \ ? ] is the set of
achievable capacity consumption rates, and
í
r
(j) :=max
\
_
í(\):
n
_
i=1
\
i
=j, \ ?
_
(6)
is the maximum achievable revenue rate subject to the
constraint that all products jointly consume capacity
at a rate j. Note that (6) is a concave maximization
problem over a convex set, and its solution is read-
ily computable, often in closed form (examples are
given in §5). Moreover, í
r
(·) is a concave function and
satis?es the conditions of Assumption 1. The optimal
vector of demand rates, denoted by \
r
(j), is unique
and continuous in j.
Proposition 1. The dynamic pricing problem (1) can
be reduced to the dynamic program (5) and (4) expressed
in terms of the aggregate consumption rate. In particular, if
j
?
(x, |) denotes the associated optimal control and \
?
(x, |)
and p
?
(x, |) denote the optimal demand rate and price vec-
tors associated with (1), then \
?
(x, |) = \
r
(j
?
(x, |)) and
p
?
(x, |) =p(\
r
(j
?
(x, |))).
3.1.2. The Capacity Control Problem. Similarly,
the Bellman equation associated with (2) is
V(x, |) = max
u
i
?|0, 1]
_
n
_
i=1
\
i
u
i
|p
i
÷V(x ?1, | ÷1)]
÷(1 ?u
/
\) V(x, | ÷1)
_
, (7)
with the boundary condition (4), which, using the
marginal value of capacity AV becomes
V(x, |) = max
u
i
?|0, 1]
_
n
_
i=1
\
i
u
i
p
i
?u
/
\AV(x, |)
_
÷V(x, | ÷1) (8)
= max
0?j?
n
i=1
\
i
{í
u
(j)?jAV(x,|)]÷V(x,| ÷1), (9)
where j =u
/
\ and
í
u
(j) =max
u
_
n
_
i=1
u
i
\
i
p
i
: u
/
\ =j, u
i
? |0, 1]
_
is the maximum revenue rate when the capacity is
consumed at a rate equal to j, and u
u
(j) is the corre-
sponding control.
Proposition 2. The capacity control problem (2) can
be reduced to the dynamic program (9) and (4) expressed
in terms of the aggregate consumption rate j. In par-
ticular, if j
?
(x, |) denotes the optimal solution of (9)
and (4) and u
?
(x, |) denote the optimal policy for (2), then
u
?
(x, |) =u
u
(j
?
(x, |)).
A similar result was derived by Talluri and van
Ryzin (2004a) for a capacity control problem for a
model with customer choice.
3.2. A Uni?ed Analysis of the Pricing and
Capacity Control Problems
The preceding analysis illustrates that both problems
can be reduced to “appropriate” single-product pric-
ing problems, highlighting their common structure
and enabling a uni?ed treatment. As a starting obser-
vation, for both (5) and (9) the optimal control j
?
(x, |)
is computed from
j
?
(x, |) =argmax
j?
{í(j) ?jAV(x, |)],
where í(·) is a concave increasing revenue function.
Using the properties of í(·), one gets that j
?
(x, |)
is decreasing in AV(x, |), which using a backward
induction argument in | gives that AV(x, |) is decreas-
ing in x and |. These standard results for single-
product dynamic pricing problems are summarized
below; a proof can be found in Talluri and van Ryzin
(2004b, Prop. 5.2, Ch. 4).
Proposition 3 (Talluri and van Ryzin 2004b,
Prop. 5.2, Ch. 4). For both problems de?ned in (1) and (2),
we have that
1. j
?
(x, |) is decreasing in the marginal value of capac-
ity AV(x, |), and
2. AV(x, |) is decreasing in x and |.
Structural results for the pricing and capacity allo-
cation policies follow from the properties of í
r
, \
r
and í
u
, u
u
, respectively. For example, consider the
pricing problem for the case where the products are
nonsubstitutes, i.e., the demand for product i is only
a function of the price for that product p
i
. In that
case, the Lagrangian associated with (6) is |(\, x, j) =
í(\) ÷ x(j ?
n
i=1
\
i
) ? j
/
\, with ?rst-order condi-
tions given by oí(\),o\
i
= x ÷ j
i
, for some x ? 0
and j
i
?0 with j
i
= 0 if \
i
> 0. It is easy to show
that x is decreasing in j (i.e., the shadow price for
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 141
the capacity consumption constraint decreases as the
rate j increases), and that \
r
i
(j) is decreasing in x.
Corollary 1. Consider the problem speci?ed in (3)
and (4), and further assume that the products are non-
substitutes, i.e., \
i
(p) = \
i
(p
i
) for all i. Then, \
?
i
(x, |) is
nondecreasing in j
?
(x, |) (and nonincreasing in AV(x, |)).
A similar result can be obtained when products are
substitutable provided that the demand model satis-
?es certain conditions analogous to those of the sen-
sitivity matrix 8 of the linear model in §2.
For the capacity control problem, it is easy to
recover some well-known structural properties of the
optimal policy, see, e.g., Lee and Hersh (1993). Our
derivation based on the capacity consumption rate
offers new intuition as to why they hold. Speci?cally,
í
u
(·) is a knapsack solution for which
í
u
(j) =min
i
c
i
÷p
i
j and
u
u
|
(j) =min
_
(j?
i-|
\
i
)
÷
\
|
, 1
_
,
(10)
where c
1
= 0 and c
i
=
|-i
\
|
(p
|
? p
i
), and for
any x ? , x
÷
:= max(x, 0), and the optimal control
j
?
(x, |) reduces to the solution to max{min
i
c
i
÷(p
i
?
AV(x, |))j: 0 ? j ?
n
i=1
\
i
]. Let i
?
(x, |) = max{i ? 1:
p
i
? AV(x, |)]. Then, by inspecting the form of
the piecewise-linear objective function involved in
the calculation of j
?
(x, |), we get that j
?
(x, |) =
n
i?i
?
(x, |)
\
i
. That is, the solution is “bang-bang” in the
sense that the form of the optimal control is such that
u
?
i
(x, |) is zero if i > i
?
(x, |) and one if i ? i
?
(x, |).
In addition, from Proposition 3, Part 1, we see that
i
?
(x, |) is decreasing in the marginal value of capacity
AV(x, |).
Corollary 2. For the capacity control problem (2) or,
equivalently, (9) and (4), the optimal allocation policy is
nested in that u
?
i
(x, |) =1 if i ?i
?
(x, |), and u
?
i
(x, |) =0
otherwise, and i
?
(x, |) is decreasing in the marginal value
of capacity AV(x, |).
Remark. The subproblem of computing the opti-
mal revenue subject to a constraint on the aggregate
capacity consumption rate speci?ed in (6) and (10)
de?nes an ef?cient frontier (j, í
r
(j)) and (j, í
u
(j))
for the dynamic pricing and capacity allocation prob-
lems, respectively. As in the context of portfolio
optimization, the ef?cient frontier provides a system-
atic framework for comparing different policies and
highlights the structure of the respective optimal con-
trols. It may also lead to computational improve-
ments if this subproblem can be solved ef?ciently,
preferably in closed form. This is possible in some
common demand models such as the linear and the
multinomial logit. Such an ef?cient frontier has also
appeared and been discussed in more detail in Feng
and Xiao (2000, 2004) and Talluri and van Ryzin
(2004a). Finally, we note that the structure of the
dynamic programs studied in this section has been
observed in other papers, such as Lin et al. (2003) and
their study of single-resource capacity control prob-
lems where each arrival may request multiple units
of capacity; and Vulcano et al. (2002) and their anal-
ysis of optimal dynamic auctions. The latter involves
an analysis of a discrete-time, batch-demand analog
to the dynamic program studied here.
4. Analysis of the Pricing Problem
Using Its Fluid Approximation
This section studies deterministic (?uid model) for-
mulations of multiproduct revenue management
problems to provide some structural results (§4.1) and
suggest simple and implementable heuristics for the
pricing and capacity control problems (§4.2). The lat-
ter have desirable theoretical performance guaran-
tees and are shown to perform well in the numerical
experiments of the next section. Finally, §4.3 sketches
how to extend these ideas to the network setting. Fol-
lowing the results of §3.2 that relate the pricing and
capacity control formulations, hereafter we will focus
exclusively on the former.
4.1. Solution to the Deterministic Multiproduct
Pricing Problem
The “?uid” model has deterministic and continuous
dynamics, and is obtained by replacing the discrete
stochastic demand process by its rate, which now
evolves as a continuous process. It is rigorously jus-
ti?ed as a limit under a law-of-large-numbers type
of scaling as the potential demand and the capacity
grow proportionally large; see Gallego and van Ryzin
(1994, 1997) and §4.2. It is simplest to describe the
?uid model in continuous time (this is consistent with
Gallego and van Ryzin 1994, 1997). In more detail, the
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
142 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
realized instantaneous demand for product i at time |
in the ?uid model is deterministic and given by \
i
(|).
We allow product i requests to consume capacity at
a rate of u
i
>0 units per unit of demand, and denote
by u the vector |u
1
, . . . , u
n
]. This is a generalization of
the model considered thus far, which assumed uni-
form capacity requirements (all equal to 1). With a
general capacity requirement vector u, the capacity
consumption rate is de?ned by j =u
/
\, and the de?-
nitions of í
r
and \
r
can be appropriately adjusted to
re?ect that change. The system dynamics are given by
dx(|),d| = ?
n
i=1
u
i
\
i
(|), x(0) = C, together with the
boundary condition that x(T ) ? 0. The ?rm selects a
demand rate \
i
(|) (or a price) at each time |. The ?uid
formulation of the multiproduct pricing problem is
the following:
max
{\(|), |?|0, T ]]
_
_
T
0
í(\(|)) d|:
_
T
0
u
/
\(|) d| ?C and \(|) ? ?|
_
. (11)
Single-product problem. In this case, Gallego and van
Ryzin (1994) showed that a constant price (and thus
a constant demand rate) is optimal for (11). Specif-
ically, let
ˆ
\ = argmax{í(\): \ ? ] and ´ p = p(
ˆ
\) be
the demand rate and price, respectively, that maxi-
mize the revenue rate disregarding any capacity con-
siderations. Also, let \
0
= C,T be the run-out rate
that depletes capacity at time T , and p
0
=p(\
0
). Then,
Gallego and van Ryzin (1994) showed that the opti-
mal controls are constant over time and given by
¨
\ =
min(
ˆ
\, \
0
) and ¨ p =max( ´ p, p
0
). (The overbar notation
denotes the optimal ?uid solution.) Intuitively, the
?rm uses the revenue-maximizing price ´ p unless this
would deplete the capacity too soon, in which case it
increases its unit price to p
0
and sells its capacity by
time T , while accruing higher total revenues. Gallego
and van Ryzin (1997, §4.5) extended these results to
multiple products, but in that case without providing
such a succinct solution.
Multiproduct problem. Following the approach of §3,
we can reduce the multiproduct problem to an
appropriate single-product one, and thus solve it in
closed form. Speci?cally, recalling the de?nitions of
the aggregate revenue function í
r
(j) and optimal
demand rate vector \
r
(j) in (6), adjusted for the fact
that j =u
/
\, (11) can be rewritten as
max
{j(|), |?|0, T ]]
_
_
T
0
í
r
(j(|)) d|:
_
T
0
j(|) d| ?C, j(|) ? ?|
_
. (12)
Note that (12) is identical to a single-product problem
with revenue function í
r
, and thus is solvable using
the approach described above. Let j
0
:=C,T and ´ j =
argmax
j
í
r
(j). Then, the optimal solution to (12) is to
consume capacity at a constant rate ¨ j given by
¨ j(|) :=min( ´ j, j
0
) ?|, (13)
the corresponding vector of demand rates is \
r
( ¨ j),
while the price vector is p(\
r
( ¨ j)). A direct veri?cation
that this solution satis?es the optimality conditions
for (11) establishes the following:
Proposition 4. Let
¨
\(·) and ¨ p(·) denote the optimal
vectors of demand rates and prices for (11). Then,
¨
\, ¨ p
are constant over time and are given by
¨
\(|) =\
r
( ¨ j) and
¨ p(|) =p(\
r
( ¨ j)).
4.2. Asymptotically Optimal Heuristics Extracted
from the Deterministic Model
Based on the preceding analysis, we discuss three
heuristics for the underlying revenue management
problems, which we analyze in the asymptotic set-
ting introduced in Gallego and van Ryzin (1997) and
Cooper (2002). Among other things, it is shown that
the dynamic heuristic that “resolves” the ?uid policy
as | progresses is asymptotically optimal in an appro-
priate sense.
a. The Static Pricing Heuristic of Gallego and van Ryzin
(1997). This policy implements the static prices ¨ p spec-
i?ed in Proposition 4. (This is the “make-to-order”
heuristic in Gallego and van Ryzin 1997.)
4.2.1. Dynamic Heuristics. The static nature of
policy (a) is desirable for implementation purposes
(see Gallego and van Ryzin 1997), but also lacks the
capability of corrective action against stochastic ?uc-
tuations. This does not arise in the ?uid formulation,
where the capacity is drained along the optimal deter-
ministic trajectory, but it is relevant for the stochas-
tic problems of original interest. The next heuristics
provide two possible adjustments to this static policy
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 143
that add such control capability and seem of practical
interest. We start by observing that the solution of the
?uid pricing problem of §4.1 can also be described in
feedback form as
¨ j(x, |) =min
_
´ j,
x
T ?|
_
, (14)
where x is the remaining capacity at time |. The deter-
ministic trajectory of the ?uid model is, of course,
such that x,(T ? |) = C,T for all | if ´ j ? C,T , and
x,(T ?|) =(C ? ´ j|),(T ?|) ?C,T if ´ j - C,T . In both
cases, ¨ j(x, |) =min( ´ j, C,T ) for all x, | along the opti-
mal ?uid trajectory of the remaining capacity process,
and thus (14) is identical to the static control derived
in (13).
b. A List-Price Capacity Control (LPCC) Heuristic.
One way to implement (14) is by introducing capac-
ity control capability on top of the static prices given
in (a). Speci?cally, our second heuristic is de?ned as
follows:
1. price according to ¨ p and label products such that
¨ p
1
,u
1
? ¨ p
2
,u
2
?· · · ? ¨ p
n
,u
n
, and
2. compute ¨ j(x, |) and use the capacity controls
u
1
(x, |) =1 if x >0, u
1
(0, |) =0, and
u
i
(x, |) =
_
_
_
1 if ¨ j(x, |) ?
_
¡-i
u
¡
¨
\
¡
?0
0 otherwise
for i ?2. (15)
Note that this policy can only reduce the aggregate
capacity consumption rate from its nominal value of
n
i=1
u
i
¨
\
i
, but can never increase it. A product is made
available only if the ?uid solution starting from that
state would choose to sell this product in all future
time periods, and “closes” the product if the ?uid
solution would dictate only partial acceptance of the
associated demand.
This policy is a re?nement of the static pricing pol-
icy in (a) and the make-to-order heuristic of Gallego
and van Ryzin (1997). Other examples of joint pric-
ing and capacity controls can be found in the recent
papers by Vulcano et al. (2002), Lin et al. (2003), and
Feng and Xiao (2004).
c. A Dynamic Pricing Heuristic. The third policy
translates the aggregate control ¨ j(x, |) into product-
level rates (and prices) through
\(x, |) =\
r
( ¨ j(x, |)) and p(x, |) =p(\(x, |)), (16)
where the mapping \
r
(·) was the maximizer in (6)
and it is continuous in j. This corresponds to the idea
of “resolving” the ?uid problem as we step through
time, which is widely applied in practice, where, how-
ever, the resolving occurs at discrete points in time,
e.g., daily or weekly depending on the application set-
ting. Despite its practical appeal and use, to the best
of our knowledge policies that use this resolving idea
have not been analyzed theoretically, other than the
isolated example provided by Cooper (2002). Our pre-
ceding discussion illustrates that “resolving” is noth-
ing but implementing the ?uid policy in feedback
form. The analysis that follows provides a characteri-
zation of its asymptotic behavior, while the numerical
results of the next section demonstrate that it tends
to outperform the other two candidate policies. The
single-product version of this policy has also been
studied by Reiman (2002).
4.2.2. Asymptotic Performance Analysis of the
Pricing Heuristics. The remainder of this subsection
offers a brief asymptotic characterization of the per-
formance under these three heuristics that shows that
all three are (?uid-scale) asymptotically optimal in
a regime where the potential demand and capac-
ity grow proportionally large; this is the ?rst-order
asymptotic optimality criterion of Gallego and van
Ryzin (1997) and Cooper (2002). Speci?cally, using |
as an index, we consider a sequence of problems with
demand model \
|
(·) = |\(·) and capacity C
|
= |C,
and let | increase to in?nity; hereafter, a superscript |
will denote quantities that scale with |. Let N
i
for
i =1, . . . , n denote independent unit rate Poisson pro-
cesses, and recall that the functional strong-law-of-
large numbers for the Poisson process asserts that as
| ?~ and for all | ?0,
N
i
(||)
|
?| a.s. (17)
For all of the candidate policies, the capacity dy-
namics can be expressed as follows. The cumulative
demand for that product up to time | is equal to
N
i
(¹
|
i
(|)), where ¹
|
i
(|) =
_
|
0
\
|
i
(s) ds, and the remaining
capacity at time | is
X
|
(|) =C
|
?
n
_
i=1
u
i
N
i
(¹
|
i
(|)). (18)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
144 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
Our goal here is to analyze the “?uid-scale” behav-
ior of the capacity process de?ned as
¨
X
|
(|) :=X
|
(|),|
under the three candidate policies. The asymptotic
optimality of the static policy (a) was established
by Gallego and van Ryzin (1997). Nevertheless, we
include our analysis, which is different than theirs
and serves to introduce the ideas used in studying the
dynamic policies (b) and (c).
Analysis of the static heuristic (a). The ?rm uses the
constant price vector ¨ p, which induces the demand
rates \
|
( ¨ p) = |
¨
\. Under this policy, ¹
|
i
(|) =
¨
\
i
||, and
the capacity dynamics are X
|
u
(|) = (C
|
?
n
i=1
u
i
N
i
·
(¹
|
i
(|)))
÷
. (The subscript is used to identify the policy.)
As | ?~
N
i
(¹
|
i
(|))
|
?
¨
\
i
| a.s., uniformly in | ? |0, T ], (19)
from which it follows that as | ? ~ and for all
| ? |0, T ]
¨
X
|
u
(|) ?
_
C ?
n
_
i=1
u
i
¨
\
i
|
_
÷
=C ? ¨ j| a.s.
(The (·)
÷
was removed because from (13) ¨ j| ? C for
all | ? |0, T ].) Let í
|
u
denote the revenues extracted
under policy (a), and t
|
:= inf{s ? 0:
n
i=1
u
i
N
i
(
¨
\
i
|s)
? C
|
] be the random time where the aggregate
capacity requested reaches or exceeds the available
capacity C
|
. Then, í
|
u
:=
n
i=1
¨ p
i
N
i
(|
¨
\
i
min(T , t
|
)) ?o,
where o is a random variable that corrects revenues
for the case where t
|
-T , which is bounded above by
max
i
¨ p
i
. (We will not delve into an accurate descrip-
tion of o, because it is asymptotically negligible.)
Using (19) and arguing by contradiction, one can eas-
ily conclude that (T ?t
|
)
÷
?0 a.s., as | ?~. Using
the expression for í
|
u
we get the following:
Proposition 5. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the static pricing policy p
|
(x, |) = ¨ p for all x, | and
all |. Then, as | ?~,
¨
X
|
u
(|) ?C? ¨ j| a.s., uniformly in |,
and (1,|)í
|
u
?
n
i=1
¨ p
i
¨
\
i
T a.s.
Recall the fact established in Gallego and van
Ryzin (1997) that the solution of the deterministic
pricing problem serves as an upper bound for the
revenues extracted in the stochastic system, i.e., í
|
u
?
|
n
i=1
¨ p
i
¨
\
i
T . Applying the bounded convergence the-
orem gives that ?í
|
u
?
n
i=1
¨ p
i
¨
\
i
T , and establishes
the asymptotic optimality of the static pricing heuris-
tic (a).
Analysis of the dynamic heuristic (c). The dynamic
nature of this policy requires a more detailed study.
The cumulative demand for product i up to time | is
equal to N
i
(¹
|
i
(|)), where
¹
|
i
(|) =
_
|
0
|\
i
(s) ds where
\
i
(s) =\
r
i
_
min( ´ j, X
|
c
(s),(|(T ?s)))
_
(20)
for \
r
i
(·) de?ned in (6), and X
|
c
(|) denotes the remain-
ing capacity at time | under policy (c), de?ned in (18).
Now, note that ¹
|
(0) = 0, ¹
|
(|) is nondecreasing
and ¹
|
i
(|) ? ¹
|
i
(s) ? (| ? s) · |\
i, max
, where \
i, max
=
argmax{\
i
: \ ? ]. This implies that the family of pro-
cesses {(1,|)¹
|
(|)] is equicontinuous, and therefore
relatively compact. It follows that it has a converging
subsequence, say |
¡
, such that (1,|
¡
)¹
|
|
i
(|) ?
¨
¹
i
(|) for
all i. Along this subsequence we get that N
i
(¹
|
¡
i
(|)),|
¡
converges to
¨
¹
i
(|), and therefore that
¨
X
|
¡
c
(|) itself con-
verges to a limit ¨ x
c
(|); the last two results hold a.s.,
uniformly in |. Expression (22) will show that the
limit trajectories do not depend on the selection of
the converging subsequence itself. In the sequel we
denote the converging subsequence by | to simplify
notation. Using the continuity of \
r
i
(·) and Lemma 2.4
of Dai and Williams (1995), we get that
1
|
¹
|
i
(|) =
_
|
0
\
r
i
_
min
_
´ j,
¨
X
|
c
(s)
T ?s
__
ds
?
_
|
0
\
r
i
_
min
_
´ j,
¨ x
c
(s)
T ?s
__
ds (21)
as | ?~a.s., uniformly in |. Using (17), (18), and (21),
we get that as | ?~
¨
X
|
c
(|) = C ?
1
|
n
_
i=1
u
i
N
i
(¹
|
i
(|))
? C ?
_
|
0
min
_
´ j,
¨ x
c
(s)
T ?s
_
ds =C ? ¨ j|, (22)
a.s., uniformly in |. The revenues extracted under pol-
icy (c) are í
|
c
=
n
i=1
_
|
0
p
|
i
(|) dN
i
(¹
|
i
(|)), where p
|
(|) is
the price vector that corresponds to \
r
(min( ´ j,
¨
X
|
c
(|),
(T ? |))), the demand rate vector at time |, and
the integrals should be interpreted in the Riemann-
Stieltjes sense. From (21) and (22) we have that
\
r
i
(min( ´ j,
¨
X
|
c
(|),(T ?|))) ?
¨
\
i
a.s., uniformly in |. By
the continuity of the inverse demand function we
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 145
have that p
|
(|) ? ¨ p a.s., uniformly in |, and therefore,
again using Lemma 2.4 of Dai and Williams (1995),
we get the result summarized below.
Proposition 6. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the dynamic pricing heuristic de?ned through (20).
Then,
¨
X
|
c
(|) ? C ? ¨ j(|) a.s., uniformly in |0, T ], and
(1,|)í
|
c
?
n
i=1
¨ p
i
¨
\
i
T a.s.
Analysis of the LPCC heuristic (b). This policy is
de?ned through ¹
|
i
(|) = |
¨
\
i
·
_
|
0
u
|
i
(|) d|, where u
|
i
(|)
was de?ned in (15) and can be expressed as follows:
u
|
1
(|) =1{
¨
X
|
|
(|) >0] and
u
|
i
(|) =1
_
min
_
´ j
¨
X
|
|
(|)
T ?|
_
?
_
¡-i
u
¡
¨
\
¡
?u
i
¨
\
i
_
for i ?2,
(23)
where 1{·] is the indicator function. Similarly to the
analysis of policy (c), the family {
¨
X
|
|
(|), | ? |0, T ]] is
tight, and thus it has a converging subsequence {|
¡
]
on which
¨
X
|
¡
|
(|) ? ¨ x
|
(|) a.s., uniformly in |. Writing
down ¨ x
|
(|) and evaluating u
i
(|) reveals that in the
limit model u
i
(|) =1 for all products i. Let í
|
|
be the
corresponding revenue. Similar arguments to the ones
used above give the following result.
Proposition 7. Suppose that demand and capacity are
scaled according to \
|
(·) = |\(·) and C
|
= |C, and con-
sider the LPCC heuristic de?ned through (23). Then,
¨
X
|
|
(|) ?C? ¨ j(|) a.s., uniformly in |0, T ], and (1,|)í
|
|
?
n
i=1
¨ p
i
¨
\
i
T a.s.
That is, resolving in the context of the dynamic
pricing or the LPCC heuristics is ?uid-scale asymp-
totically optimal, as is the static policy (a). This
shows that the suboptimal behavior demonstrated by
Cooper (2002) does not persist in systems with large
capacity and large demand. The same asymptotic per-
formance can be achieved while resolving at discrete
points in time, provided that this is done suf?ciently
frequently. If l
|
is the time between resolving epochs,
then the type of analysis used in studying discrete-
review policies (see Harrison 1996 and Maglaras 2000)
can be applied to show that it suf?ces that l
|
? 0.
This allows the number of demand requests between
resolving periods to be large in absolute terms, but
small compared to the capacity; e.g., a period l
|
=
log(|),| corresponds to order log(|) arrivals.
4.3. Dynamic Pricing Network Revenue
Management Problems
Suppose that the ?rm is operating a network of
resources, indexed by ¡ = 1, . . . , m, and that each
product i request consumes ¹
i¡
units of resource ¡
capacity. Let ¹ := |¹
i¡
] denote the associated capac-
ity consumption matrix, and assume that the initial
capacity for each resource ¡ is C
¡
. Then, the ?uid
model formulation of the network dynamic pricing
problem is
max
{\(|), |?|0, T ]]
_
_
T
0
í(\(|)) d|:
_
T
0
¹\(|) d| ?C and \(|) ? ?|
_
. (24)
As before, this problem can be expressed in terms
of j, which is de?ned by j :=¹\. Speci?cally, let
í
r
(j) :=max
\
{í(\): ¹\ =j, \ ? ] (25)
be the maximum achievable revenue rate when
resource capacity is consumed at a rate j, and let \
r
(j)
denote the corresponding vector of optimal demand
rates. Then, (24) can be reduced to
max
{j(|), |?|0, T ]]
_
_
T
0
í
r
(j(|)) d|:
_
T
0
j(|) d| ?C and j(|) ? ?|
_
. (26)
Let ¨ j denote the solution to (26). Then, \
r
( ¨ j) is the
vector of optimal demand rates for (24). This reduc-
tion could prove computationally bene?cial because,
as is often the case, the number of products (e.g.,
the number of fare-class and origin-destination pairs)
tends to be greater than the number of resources (e.g.,
number of ?ights in a hub-and-spoke network). We
refer the reader to Gallego and van Ryzin (1997) and
Kleywegt (2001) for ?uid formulations to multiprod-
uct network revenue management problems.
5. Numerical Examples
This section reports on a set of numerical examples
that contrast the performance of the heuristics pro-
posed in the previous section to that of the optimal
policy obtained from the dynamic program. Our base
model has two products, each consuming one unit of
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
146 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
capacity per request, and a linear demand relation-
ship of the form \(p) =A?8p with A=|0.3, 0.1] and
T = 200 time periods. The price set is = {p: A ?
8p ?0], the inverse demand is p(\) =8
?1
(A?\), and
the revenue function is í(\) =\
/
8
?1
(A?\). The poli-
cies that we consider are the following:
• “RevMax” corresponds to the monopoly price
vector ´ p that maximizes the aggregate instantaneous
revenue rate disregarding the capacity constraints,
given by ´ p = 8
?1
(A ?
ˆ
\), where
ˆ
\ = argmax{\
/
8
?1
·
(A?\): \ ?0] =(1,2)(8
?1
÷8
?1
/
)
?1
A.
• “Fluid” implemented the price vector ¨ p =p(\
r
( ¨ j))
as de?ned in Proposition 4.
• “LPCC” is the joint (list) pricing and capacity
control heuristic de?ned through (15).
• “DynPrice” is the dynamic implementation of the
?uid policy de?ned through (16).
• “DP” implemented the solution of the dynamic
program outlined in §3.
Remark (Comments onComplexity). The expected
revenues under the ?rst two static policies were com-
puted analytically using a binomial model that under
DP was simply V(C, T ), while for the remaining
policies we averaged out revenues over 1,000 sim-
ulated sample paths. The effort needed to compute
V(C, T ) in problems with uniform capacity require-
ments (Tables 1 to 3) is that of solving a single-
product pricing problem, which grows in proportion
to C T . If í
r
(j) and \
r
(j) cannot be expressed in
closed form and are not precomputed and stored,
the state space dimension of the dynamic program
stays the same, but its complexity increases by a con-
stant factor that depends on the number of products.
Table 4 looks at examples with nonuniform capac-
ity requirements, where the demand aggregation no
longer applies and the backward induction step of
the dynamic program needs to be changed, increasing
the overall complexity again by a constant factor. The
complexity of computing LPCC and DynPrice, the
performance of which is the emphasis of our study, is
negligible.
5.1.1. The Effect of the Joint Capacity Constraint.
Table 1 provides an illustration of the behavior of
these heuristics on a particular problem instance as
we varied the available capacity. Tables 2 and 3 will
provide summary statistics for many randomly gener-
ated test cases. The demand model had no cross-price
Table 1 Optimality Gaps Relative to Optimal Policy (DP)
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
25 31.4 3.0 2.6 0.4 417.63
30 22.2 4.4 3.3 1.0 440.53
35 12.6 5.1 1.9 1.3 451.63
40 5.4 5.4 0.7 0.7 457.00
45 1.8 1.8 0.2 0.2 459.50
50 0.7 0.7 0.3 0.3 460.39
Note. ß =diag(1, 6)
terms and was given by \
1
(p) =0.3 ?1p
1
and \
2
(p) =
0.1 ?6p
2
.
The Fluid pricing problem becomes unconstrained
for C ? 40 units, in which cases the RevMax and
Fluid prices coincide. We observe the following. First,
the relative performance under all heuristics improves
as the capacity C increases; this is consistent with
the results of Gallego and van Ryzin (1994, 1997) for
Fluid and RevMax. Second, while the Fluid heuris-
tic that incorporates the capacity constraint outper-
forms RevMax when capacity is scarce, its regret over
the DP policy can still be substantial (2%–5%). Third,
when the capacity is scarce, C ? 25, the ?uid prices
effectively switch off Product 2 and operate the sys-
tem as a single-product one. As the capacity increases,
it is optimal to offer both products, and the effect
of the capacity control of LPCC becomes more evi-
dent. Switching from an effectively single-product to
a two-product solution causes the optimality gaps to
be nonmonotone. Fourth, the dynamic pricing (resolv-
ing) heuristic is signi?cantly better than all others
when capacity is scarce.
5.1.2. The Cross-Price Elasticity Effects and Mul-
tiple Products. Table 2 summarizes results from 100
test cases for systems with ?xed capacity C =40, lin-
ear demand model with A=|0.3, 0.1], and randomly
Table 2 Average and Standard Deviations of % Optimality Gaps for
Two-Product Examples: 0 =40, '(p) =A?ßp, A =|0.3, 0.1],
and Random ß Matrices
´ p RevMax Fluid LPCC DynPrice
0.8–0.9 1.5 (0.3) 1.6 (0.3) 1.6 (0.3) 0.8 (0.2)
0.9–1.0 3.6 (0.6) 3.6 (0.5) 3.1 (1.6) 1.1 (0.2)
1.0–1.1 5.2 (1.1) 3.9 (0.3) 3.0 (1.5) 1.0 (0.2)
1.1–1.2 9.8 (1.3) 3.1 (0.4) 2.4 (0.3) 1.0 (0.2)
1.2–1.3 14.0 (1.5) 3.1 (0.4) 2.1 (0.2) 0.9 (0.2)
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS 147
Table 3 Average and Standard Deviations of % Optimality Gaps for
Three-Product Examples: 0 = 40, '(p) = A ? ßp, A =
|0.3, 0.05, 0.05], and Random ß Matrices
´ p RevMax Fluid LPCC DynPrice
0.8–0.9 1.5 (0.3) 1.6 (0.2) 1.5 (0.3) 0.8 (0.1)
0.9–1.0 3.3 (0.7) 3.3 (0.7) 3.3 (1.6) 1.0 (0.2)
1.0–1.1 6.4 (1.4) 3.7 (0.4) 3.6 (2.0) 1.1 (0.2)
1.1–1.2 9.4 (1.3) 3.1 (0.3) 3.0 (2.0) 0.9 (0.2)
1.2–1.3 14.0 (1.3) 3.0 (0.3) 2.1 (1.5) 0.8 (0.2)
generated 8 matrices; the elements of the main diago-
nal were drawn from a uniform distribution on |0, 1],
while the cross terms were drawn from a uniform dis-
tribution on |?1, 0]. We then tested that the dominant
diagonal condition given in §2 was satis?ed, which
also assured that an inverse exists. Results have been
grouped according to their nominal load factors ´ j :=
(
i
u
i
ˆ
\
i
),C, where
ˆ
\ is the RevMax demand vector
that would maximize instantaneous revenue in the
absence of the capacity constraint.
1
The table reports
the average and standard deviation of the % optimal-
ity gap for each candidate policy. The main obser-
vation is that DynPrice signi?cantly outperformed
all other heuristics not only in terms of the average
gap, but also in its standard deviation. In turn, LPCC
improved over Fluid in cases where the capacity con-
straint was binding and the ability to incorporate
the extra element of capacity control decisions was
bene?cial. Table 3 reports results for three-product
examples, and illustrates the consistently good perfor-
mance of the LPCC and DynPrice policies. The resolv-
ing structure of the latter is important in problems
with multiple products and substitution and/or com-
plementarity effects.
5.1.3. NonuniformCapacity Requirements. Table
4 summarizes results for two models with two prod-
ucts that have different capacity requirements. This
change complicates the associated dynamic program-
ming formulation (see comments in the beginning
of this section), but does not affect the ?uid analy-
sis of §4.1, and the heuristics extracted therein are
still valid. In the notation of §4, product i consumes
u
i
units of capacity and u
1
,=u
2
. Our ?ndings suggest
1
A ?le with the test parameters for Tables 2 and 3 is avail-
able athttp://www.meiss.com/ orhttp://www.gsb.columbia.edu/
faculty/cmaglaras/maglaras.htm.
Table 4 Optimality Gaps Relative to Optimal Policy (DP)
(i) ß =|1 ?0.4; ?0.6 6] and a =|1 2]
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
30 42.7 4.3 3.7 2.7 476.91
40 27.1 5.6 2.1 1.5 496.05
50 12.0 5.7 1.7 1.0 502.77
60 2.9 3.2 1.1 0.3 505.81
70 0.8 0.7 0.4 0.3 506.73
80 0.3 0.2 0.2 0.1 506.86
(ii) ß =|1 ?0.4; ?0.6 6] and a =|2 1]
0 RevMax (%) Fluid (%) LPCC (%) DynPrice (%) DP
30 39.5 4.4 4.0 3.9 340.95
40 32.2 3.3 3.0 1.7 406.89
50 23.4 3.0 2.9 0.6 451.85
60 14.2 3.7 3.4 1.2 479.64
70 6.0 4.4 3.6 0.8 495.78
80 1.7 2.0 1.7 0.7 503.60
that the ?uid model heuristics perform quite well in
cases where the capacity requirements are small com-
pared to the capacity itself. (Eventually, as C and \
grow large, these policies become asymptotically opti-
mal in the sense of Propositions 5 to 7.)
The last three tables illustrate that static pricing is
close to optimal in problem instances that are either
very under- or overloaded, and that the effect of
dynamic pricing, either through the optimal policy
(DP) or the DynPrice heuristic, is most pronounced
when ´ j is close to 1. This is intuitive: When ´ j _ 1,
the system’s capacity far exceeds the nominal require-
ment under the prices that maximize revenues per
unit time (implemented in RevMax), and thus one
would expect that the static pricing heuristics RevMax
and Fluid to be close to optimal. In contrast, if ´ j ¸1,
the system’s capacity is too low, and the static prices
implemented through the Fluid heuristic are close
to optimal. Finally, we did not observe any problem
instances where the performance under the DynPrice
heuristic was worse (in a statistically signi?cant man-
ner) than that under the LPCC or Fluid heuristics.
The narrowest gap between LPCC and DynPrice was
observed in the ?rst row of Table 4, which, due to
the nonuniform capacity requirements, corresponds
to the problems with the lowest overall capacity in
terms of the number of sales; this is the closest to the
Maglaras and Meissner: Dynamic Pricing Strategies for Multiproduct Revenue Management Problems
148 Manufacturing & Service Operations Management 8(2), pp. 136–148, ©2006 INFORMS
setting in Cooper’s example (2002), which had low
capacity and a short selling horizon.
References
Bitran, G., R. Caldentey. 2003. An overview of pricing models for
revenue management. Manufacturing Service Oper. Management
5(3) 203–229.
Brumelle, S., J. McGill. 1993. Airline seat allocation with multiple
nested fare classes. Oper. Res. 41(1) 127–137.
Cooper, W. 2002. Asymptotic behavior of an allocation policy for
revenue management. Oper. Res. 50(4) 720–727.
Dai, J. G., R. J. Williams. 1995. Existence and uniqueness of semi-
martingale re?ecting Brownian motions in convex polyhe-
drons. Theory Probab. Appl. 40(1) 1–40.
Elmaghraby, W., P. Keskinocak. 2003. Dynamic pricing: Research
overview, current practices and future directions. Management
Sci. 49(10) 1287–1389.
Feng, Y., B. Xiao. 2000. A continuous-time yield management model
with multiple prices and reversible price changes. Management
Sci. 46(5) 644–657.
Feng, Y., B. Xiao. 2004. Integration of pricing and capacity allocation
for perishable products. Preprint, Chinese University of Hong
Kong.
Gallego, G., G. van Ryzin. 1994. Optimal dynamic pricing of inven-
tories with stochastic demand over ?nite horizons. Management
Sci. 40(8) 999–1020.
Gallego, G., G. van Ryzin. 1997. A multiproduct dynamic pricing
problem and its applications to network yield management.
Oper. Res. 45(1) 24–41.
Harrison, J. M. 1996. The BIGSTEP approach to ?ow manage-
ment in stochastic processing networks. F. Kelly, S. Zachary,
I. Ziedins, eds. Stochastic Networks: Theory and Applications.
Oxford University Press, Oxford, UK, 57–90.
Horn, R. A., C. R. Johnson. 1994. Matrix Analysis. Cambridge Uni-
versity Press, Cambridge, UK.
Kleywegt, A. J. 2001. An optimal control problem of dynamic pric-
ing. Working paper, Georgia Institute of Technology, Atlanta,
GA.
Lautenbacher, C., S. Stidham. 1999. The underlying Markov deci-
sion process in the single-leg airline yield-management prob-
lem. Transportation Sci. 33(2) 136–146.
Lee, T., M. Hersh. 1993. A model for dynamic airline seat inventory
control with multiple seat bookings. Transportation Sci. 27(3)
252–265.
Lin, G. Y., Y. Lu, D. D. Yao. 2003. The stochastic knapsack revisited:
Structure, switch-over policies, and dynamic pricing. Preprint,
Columbia University, New York.
Maglaras, C. 2000. Discrete-review policies for scheduling stochas-
tic networks: Trajectory tracking and ?uid-scale asymptotic
optimality. Ann. Appl. Probab. 10(3) 897–929.
Maglaras, C. 2006. Revenue management for a multi-class single-
server queue via a ?uid model analysis. Oper. Res. Forthcom-
ing.
McGill, J., G. van Ryzin. 1999. Revenue management: Research
overview and prospects. Transportation Sci. 33(2) 233–256.
Reiman, M. I. 2002. Asymptotically optimal dynamic pricing for
a wholesale/retail telecommunications service provider. 2nd
INFORMS Conf. Revenue Management, New York.
Talluri, K., G. van Ryzin. 2004a. Revenue management under a gen-
eral discrete choice model of consumer behavior. Management
Sci. 50(1) 15–33.
Talluri, K., G. van Ryzin. 2004b. The Theory and Prac-
tice of Revenue Management. Kluwer Academic Publishers,
Boston/Dordrecht/London.
Vulcano, G., G. van Ryzin, C. Maglaras. 2002. Optimal dynamic
auctions for revenue management. Management Sci. 48(11)
1388–1407.
Zhao, W., Y.-S. Zheng. 2000. Optimal dynamic pricing for perishable
assets with nonhomogeneous demand. Management Sci. 46(3)
375–388.
doc_767868489.pdf