Question 1,2,3,4,5

I upload 5 questions and two materials related to this questions, please take a look then decide whether you want to do them or not, the name of this course is ” Dynamic Pricing & Revenue Management “, please upload solution to me before deadline, also I need detailed explaination, thank you.

IEOR

Assignment 7

1. Static Pricing under the Linear Demand Model. Consider the linear demand model
d(p) = a−Bp with

a =


 100150


 ,

and

B =


 1 0 −.1−.1 2 −.15

0 .− 05 1.5




a) Find p(z) and r(z) for

z =


 5050


 .

b) Compare the prices and the profit in part a) with the prices and individual profits
if there are three competitors, with competitor i controlling the price for product
i = 1, 2,

2. Static Pricing under the Multinomial Logit model. Suppose that you have m different
variants of a product, say a line of laptops, and you want to optimally price them for a
market segment whose members make choices according to an MNL model. Let p be the
vector of prices for the m variants and let z be the vector of unit costs. Let πi(p) be the
probability that the customer selects variant i ∈{1, . . . ,m} and π0(p) = 1 −

∑m
i=1

πi(p)

be the probability that he selects the no purchase alternative. This exercise will show
that the optimal price vector is of the form p(z) = z + θe where e is a vector of ones in
m dimensions and θ ≥ 0 is a constant. In other words, the exercise will show that there
is a fixed markup quantity θ∗ that is optimal for all of the variants.

Let r(p,z) =
∑m

i=1(pi − zi)πi(p) be the expected profit per arriving customer when the
price vector is given by p and the unit cost vector is z, where

πi(p) =
exp(γ(µi −pi))

1 +
∑m

j=1 exp(γ(µj −pj))
.

a) Show that ∂πj(p)/∂pi = γπi(p)πj(p) for j 6= i and that ∂πi(p)/∂pi = γπi(p)(πi(p)−
1).

b) Use the results of part a) to show that the first order conditions can be written as

πi(p)


1 + n∑

(pj −zj)γπj(p) −γ(pi −zi)


 = 0.

c) Argue from part b) that the only solution to the first order conditions with all
prices finite is of the form pi = zi + θ for all i for some constant θ. In vector terms
this means that p(z) = z + θe where e is the vector of ones in m dimensions.

d) Use the results of part c) to show that θ∗ is the unique root of the equation θπ0(z +
θe) = 1/γ.

e) Show that for this solution the objective function is equal to r(z) = r(z + θ∗e,z) =
θ∗[1−π0(z + θ∗e)]. Note: It can be shown that there are a total of 2m solutions to
the first order conditions but only one with all prices finite. Moreover, it is possible
to show that all other solutions result in lower profits.

3. Consider a dynamic pricing problem where rt(p,z) = r(p,z) = λ(p)(p − z), so the
demand rate is time homogeneous. We will assume that r(p,z) is unimodal in p for
each z so there is a unique p(z) maximizing r(p,z) with r(z) = r(p(z),z). Let p∗ = p(0)
be the price that maximizes the revenue rate r(p, 0) = pλ(p), let λ∗ = λ(p∗) be the
corresponding demand rate, and r∗ = p∗λ∗ be the corresponding revenue rate. This
exercise is designed to justify that the static pricing policy p∗ is near optimal for states
(t,x) for x/t >> λ∗.

(a) Recall that the value function V (t,x) satisfies the HJB equation:

∂V (t,x)

∂t
= r(∆V (t,x)).

Use the fact that r(∆V (t,x)) ≤ r(0) = r∗ to show that V (t,x) ≤ r∗t for all states
(t,x).

(b) Let V ∗(t,x) be the expected revenue of using the static pricing policy p∗. Let N∗(t)
be Poisson λ∗t. Argue that demand under this policy is N∗(t) and that sales are
min(N∗(t),x). Use this to justify:

V ∗(t,x) = p∗E min(N∗(t),x) ≤ V (t,x) ≤ r∗t

show that

V ∗(t,x) =
∫ t
0
r∗ds−p∗

E(N∗(t) −x)+

V ∗(t,x)

V (t,x)
≥ 1 −

E(N∗(t) −x)+

λ∗t

V (t,x) −V ∗(t,x)
V (t,x)

≤
E(N∗(t) −x)+

λ∗t
.

(d) For any random variable Y , show that Y + = 0.5(Y + |Y |). Then take expectations
and use the Cauchy Schwartz inequality E|Y | ≤

√
E(Y 2) =

√
Var(Y ) + (EY )2 to

show that

E[(N∗(t) −x)+]

≤
1

(
λ∗t−x +

√
λ∗t + (λ∗t−x)2

)
. (1)

and to concluded that

V (t,x) −V ∗(t,x)
V (t,x)
≤
1
2

√
(x−λ∗t)2 + λ∗t− (x−λ∗t)

λ∗t
.

(e) Use the first order Taylor’s expansion of
√
y, and the fact that

√
y is a concave

function to show that √
y2 + z −y

z
≤

and use this result for y = x−λ∗t ≥ 0 and z = λ∗t to conclude that

V (t,x) −V ∗(t,x)
V (t,x)
≤
1

4(x−λ∗t)
. (2)

(f) Evaluate the right hand side of (2) at x(k) = λ∗t + k
√
λ∗t for values of k = 1, 2, 3.

What happens if t is fixed and k increases? What happens if k > 0 is fixed and
t increases? What is the largest relative loss of optimality you can make by using
the fixed price policy p∗ if λ∗t = 100 and x = 130?

4. Consider the same situation as in Problem 3, except that now x < λ∗t. Since capacity is scarce the market will clear at a relatively high price. Let po be the price such that λo = λ(po) = x/t (draw a picture to convince yourself that po > p∗). Let No(t) be a
Poisson random variable with mean λot = x.

(a) Let V o(t,x) be the expected revenue of using the fixed price policy po. Argue that
demand under this policy is No(t) and sales min(No(t),x) and justify the equation:

V o(t,x) = poE min(No(t),x) ≤ V (t,x) ≤ pox.

Hint: Don’t forget to justify the second inequality. To do this you may want
to consider the upper bound problem that arises from the approximate dynamic
program.

(b) Argue that E min(No(t),x) = x − E(x − No(t))+ = x − E(x − No(t))+ and use
this to justify the equations:

V o(t,x) = pox−po

E(x−No(t))+

V o(t,x)

V (t,x)
≥ 1 −
E(x−No(t))+

V (t,x) −V o(t,x)
V (t,x)

≤
E(x−No(t))+

x
.

V (t,x) −V o(t,x)
V (t,x)
≤
E(x−No(t))+

x
≤ 0.5

1
√
x
. (3)

This shows that the fixed price policy po is asymptotically optimal if x is large, but
x < λ∗t as the right hand side of (3) becomes small as (x,t) grow with x < λ∗t.

(d) What is the largest relative loss of optimality that may result from using price po

when x = 100 and λ∗t > 100? What if x = 400 and λ∗t > 400?

5. Let V f (t,x) be the expected revenue obtained from using the fixed price policy max(po,p∗).
Combine the results of the last two problems to argue that

V (bt,bx) −V f (bt,bx)
V (bt,bx)

→ 0 as b →∞.

Interpret this result.

An Introduction to Static and Quasi-Static Pricing
Policies c©

Guillermo Gallego

Spring

Abstract

We consider the static pricing problem that calls for maximizing profits in excess
of marginal costs that are driven by state dynamics. We establish conditions for the
existence and uniqueness of finite maximizers and show that optimal profits are decreas-
ing convex in the marginal cost. The convexity of optimal profits on the marginal cost,
together with randomness in marginal costs driven by state dynamics is what justifies
dynamic pricing. The results remain valid for the case of bounded capacity and when
lower bound are imposed on sales under the assumption that aggregate demand is com-
prised from many small customers or that large customers are willing to take partial
orders. We then consider the welfare problem and show that options on capacity elim-
inate the dead weight loss when booking and consumption are separated by time

and

consumers have ex-ante homogeneous willingness to pay. We then consider existence
and uniqueness issues when aggregate demand comes from several market segments. We
show that aggregate demand inherits existence properties from the individual market
segments but this is not true for uniqueness properties. The problem of using a limited
price menu to price multiple market segments is analyzed. Using a single price for all
the market segments and a different price for each market segment are two extreme
strategies that provide us with lower and upper bounds on profits. We next consider
bounds and heuristics to design a menu of J > 1 prices for M > J market segments
for a variety of demand functions including linear, log-linear demands and for demands
governed by the multinomial logit model (MNL). Existence and uniqueness results for
multiple products are provided for a variety of commonly used demand models

1 Introduction

We are concerned with the following static pricing problem:

r(z)

= sup
p∈X

(p−z)d(p) (1)

where z is the marginal cost of capacity, d(p) is the demand at price p and X is the set of
allowable prices. Economists are usually interested in the more general problem where costs

are non-linear. Our interest in the simpler problem with linear costs stems from dynamic
pricing where problem (1) arises with z equal to the marginal value of capacity. Readers not
interested in the connection to dynamic pricing can skip to Section 2.

To see the connection with dynamic pricing consider the problem of maximizing the ex-
pected revenue that can be obtained from finite, non-replenishable, capacity c over a finite
horizon [0,T] assuming zero salvage value. Gallego and van Ryzin [

] show that when demand
arrives as a Poisson process with intensity dt(p), then the value function V (t,x), representing
the maximum expected revenue when the time-to-go is t and the remaining inventory is x,
satisfies the Hamilton Jacobi Bellman (HJB) equation:

∂V (t,x)

∂t
= sup

p∈X
(p− ∆V (t,x))dt(p), (2)

where ∆V (t,x) = V (t,x)−V (t,x−1) is the marginal value of the xth unit of capacity, and the
conditions are V (t, 0) = V (0,x) = 0. Equation (2) requires continuity of dt(p) with respect
to t. If dt(p) is piecewise continuous then the HJB equation (2) holds over each subinterval
where dt(p) is continuous where the boundary condition is modified to be the value function
over the remaining time horizon.

Notice that the optimization in (2) is of the form (1) with z = ∆V (t,x). If a maximizer,
say pt(z), exists for each z ≥ 0 and each t ∈ [0,T], then an optimal solution to the dynamic
pricing problem (2) is to set price P(t,x) = pt(∆V (t,x)) at state (t,x). There are two sources
of price variation in dynamic pricing. The first source is variations due to state dynamics as
the marginal cost ∆V (t,x) changes with the state (t,x). Gallego and van Ryzin show that
∆V (t,x) is increasing in t, so the marginal value of the x unit is more valuable if we have more
time to sell it, and decreasing in x, so the marginal value decreases with capacity. We will later
show that pt(z) is increasing in z, so a sale at state (t,x) causes the price to instantaneously
increase to P(t,x− 1) > P(t,x). The second source of price variation is changes in pt(z) due
to changes of demand dt(p) over time t. If pt(z) = p(z) is time invariant and then P(t,x) is
increasing in the time-to-go t, since ∆V (t,x) is increasing in t. This means that prices decline
in the absence of sales to stimulate demand. If pt(z) changes with time then P(t,x) can either
increase or decrease over time as the forces of state dynamics may be in conflict with changes
in willingness to pay.

Quasi-static pricing policies are heuristic pricing policies of the form

Ph(t,x) = pt(z(T,c)) 0 ≤ t ≤ T

that react to changes in dt(p) in t but not to changes in the marginal value ∆V (t,x). Typically
z(T,c) is chosen to capture the marginal value of capacity by solving the following fluid
program:

V̄ (T,c) = min
z≥0

[cz +
∫ T

0
rt(z)dt]. (3)

Program (3) arises in at least three different ways: 1) By using Approximate Dynamic
Programming (ADP) with affine functions, 2) By using a fluid limit approximation and du-
alizing the capacity constraint and 3) By modifying the differential equation (2) by replacing

∆V (t,x) with the partial derivative Vx(t,x) of V (t,x) with respect to x. We will later show
that (3) is a convex minimization program. We refer the reader to Gallego and van Ryzin
[5] for a proof that V̄ (T,c) is an upper bound on V (T,c) and for a discussion of the asymp-
totic optimality properties of the quasi-static pricing policy for the case d(p) = dt(p) for all
t ∈ [0,T].

Quasi-static pricing policies are responsive to changes in willingness to pay but not re-
sponsive to changes in state dynamics. It can be shown that quasi-static pricing policies are
asymptotically optimal, see Gallego [

], and they are a natural extension of the fixed priced
policies in [5]. The fact that quasi-static pricing policies ignore state dynamics is materially
detrimental only when both capacity and aggregate demand are relatively small. On the posi-
tive side, quasi-static pricing policies do not suffer from the nervousness of full dynamic pricing
policies that react instantaneously to state dynamics, e.g., decreasing prices between sales and
increasing them after each sale. This is an important advantage in practice as quasi-static
policies are easier to implement. Limits are often are imposed on prices, so the optimization
is restricted to p ∈ Xt where Xt may be a finite price menu. The design of the price menu is
considered part of the problem. For example, if the cardinality of the set of different prices
utilized by the static pricing heuristic {pt(z(T,c)) : 0 ≤ t ≤ T} is M and M is considered too
large, then the task may be to select a pricing menu with at most J < M different prices, to prevent the pricing policy from being too nervous. We study a variant of this problem in Section

.1.

The quasi-static heuristic is often made more dynamic by frequently resolving (3), ob-
taining an updated value of the marginal value of capacity each time (3) is resolved. More
precisely, if the realization of demand deviates significantly from its deterministic path, then
the value of z can be updated at state (s,y) to z(s,y) where z(s,y) is the minimizer of
[yz +

∫s
0 rt(z)dt]. Prices are then updated to pt(z(s,y)) for t ∈ [0,s] or until the deterministic

problem (3) is solved again. If the system is updated continuously, we get a feedback policy
Ph(t,x) = pt(z(t,x)), which tends to perform better than the quasi-static policy but is al

requires more computations and results in more nervous prices. The reader is referred to
Maglaras and Meissner [

] who show that the feedback policy is also asymptotically optimal,
and to Cooper [2] who presents and example that shows that updating z when the inventory
and the time-to-go are small can hurt rather than help performance.

The near optimality of quasi-static pricing policies motivates the study of static optimiza-
tion problem (1). Although this is a special case of the basic pricing problem where marginal
costs are constant there are some subtle issues regarding existence and uniqueness. In addi-
tion, there are a number of variants of the problem that are of interest in their own right. Our
aim on this Chapter is to present the reader with a unified and comprehensive analysis of the
problem.

In Section 2 of this Chapter we present basic properties and existence of finite maximizers.
We first show that r(z) is decreasing convex in z and present conditions on d(p) that guarantee
the existence of a finite price p(z) increasing in z such that r(z) = (p(z)−z)d(p(z)). In Section
3 we present sufficient conditions for the uni-modality of r(p,z) in p and for the uniqueness
of p(z). We analyze the case of bounded capacity and lower bounds on sales in Section

.
Multiple market segments are treated in Section 6. We first look into the question of existence

and uniqueness when the demands of two or more market segments are aggregated. We show
that existence conditions for the individual market segments are inherited by the aggregate
demand. This is not so for uniqueness conditions. We then explore heuristics to price M
market segments with at most J < M different prices. This problem may arise either because only a few prices are allowed or because detailed demand information from the different market segments is not enough to support using more prices. We show that it is often possible to design near optimal price menus for values of J that are small relative to M. The welfare problem is discussed in Section 5 where call options on capacity are presented as a viable solution when booking and consumption are separated by time and customers learn their valuations between booking and the time of consumption.

2 Basic Properties and Existence of Finite Maximizers

Let d(p) : X ⊂ [0,∞) → [0,∞] be a function representing the demand for a product at
price p ∈ X. For any z ≥ 0 let r(p,z) = (p − z)d(p) be the profit function for any p ∈ X.
We treat z as an exogenous unit cost and r(p,z) as the profit function. For z ≥ 0, we define
r(z) = supp∈X r(p,z), the optimal profit as a function of the unit cost. We write sup instead of
max in the definition of r(z) because the maximum may not be attained. To see this consider
the demand function d(p) = 1 for p ∈ [0,

) and d(p) = 0 for p ≥ 10 then r(z) = (10−z)+ but
the maximum is not attained. As an example where a finite maximizer fails to exist, consider
the demand function d(p) = p−b,p ≥ 0 for b ∈ (0, 1). Then r(p, 0) = p1−b so r(0) = ∞ and
there is no finite maximizer. Later we will present sufficient conditions for the existence of a
finite maximizer p(z) < ∞ such that r(z) = r(p(z),z). However, even if the supremum is not attained we can show that r(z) is decreasing1 convex in z.

Theorem 1 r(z) is decreasing convex in z.

Proof: Notice that for any z < z′, r(p,z) = (z′ − z)d(p) + r(p,z′) ≥ r(p,z′). Therefore r(z) = supp∈X r(p,z) ≥ supp∈X r(p,z′) = r(z′). To verify convexity, let α ∈ (0, 1),

and let

z(α) = αz + (1 −α)z′. Then

r(z(α)) = sup
p∈X

r(p,z(α))

= sup
p∈X

[αr(p,z) + (1 −α)r(p,z′)]

≤ α sup
p∈X

r(p,z) + (1 −α) sup
p∈X

r(p,z′)

= αr(z) + (1 −α)r(z′).

Remark 1: The convexity of r(z) implies that cz +
∫T
0 rt(z)dt is a convex problem in z, so to

obtain z(T,c), the marginal cost to be used for quasi-static pricing, all we need to do is to

1We use the term increasing and decreasing in the weak sense unless stated otherwise.

find the unconstrained minimizer of the convex function cz +
∫T

0 rt(z)dt and take its positive
part.

Remark 2: Jensen’s inequality implies that Er(Z) ≥ r(EZ). This means that a retailer
prefers a random unit cost Z than unit cost EZ, provided that he can charge random prices
p(Z). This also explains why dynamic pricing reacts to state dynamics, ∆V (t,x), even when
demand dt(p) = d(p) is time invariant.

Remark 3: If r is twice differentiable then r(Z) ‘ r(E[Z]) + (Z − E[Z])r′(E[Z]) + 0.5(Z −
E[Z])2r′′(E[Z]). Taking expectations yields E[r(Z)] − r(E[Z]) ‘ 0.5Var[Z]r′′(E[Z]). Conse-
quently, the benefits of responding to cost changes is large when Z has a large variance and
r has large curvature at E[Z].

Example 1 If d(p) = 1 − p over p ∈ [0, 1] then for z ∈ [0, 1], p(z) = (1 + z)/2 maximizes
r(p,z) = (p−z)(1−p) resulting in r(z) = (1−z)2/4. If z = 1/2 then r(1/2) = 1/

. Notice a
retailer with demand d(p) prefers a wholesaler with unit cost z1 = 1/3 with probability 1/2 and
unit cost z2 = 2/3 with probability 1/2 since this leads to more than a 10% increase in expected
profits from 1/16 to 5/72. However, this does not mean that the retailer prefers to randomize
prices if his true cost is z = 1/2 for any deviation from p(1/2) leads to lower profits.

The following Corollary pushes the idea a bit further. The proof is provided in the Ap-
pendix.

Corollary 1 If g(y) :

We can interpret z = g(y) as the unit cost where y is the vector of component costs. As an
example, g(y) = f ′y where f ∈

We have not assumed that d(p) is decreasing in p to allow for prestige goods whose demand
may increase in price over a certain range. We will now show that we can construct a decreasing
function d̄(p), based on d(p), such that under mild conditions we can find a maximizer p(z) of
r(p,z) by finding a maximizer, say p̄(z), of r̄(p,z) = (p−z)d̄(p). Indeed, let d̄(p) = supp′≥p d(p′)
for all p ≥ 0, and assume that d(p) is upper-semi-continuous (USC). Recall that a function
d(p) : X ⊂ [0,∞) → [0,∞] is USC at po ∈ X if lim supp→po d(p) ≤ d(po) and d(p) is USC
in p ∈ X if it is USC at every point p ∈ X. Clearly d(p) USC implies that d̄(p) is USC.
Moreover any decreasing USC function is left-continuous with right limits (LCRL), so d̄(p) is
LCRL. Let r̄(z) = supp∈X r̄(p,z). It is easy to construct examples where r̄(z) > r(z). The
next Lemma shows that this is not possible if d(p) is upper-semi-continuous (USC).

Lemma 1 If d(p) is USC and p̄(z) is a finite maximizer of r̄(p,z), then p(z) = p̄(z) is a
maximizer of r(p,z) and r(z) = r̄(z).

The proof of Lemma 1 can be found in the Appendix.

Our next task is to find conditions that guarantee the existence of a finite price that
attains the maximum of r(p,z) and for this we need a few definitions from convex analysis,
see Rockefeller [

]. A function d(p) is said to be proper if d(p) < ∞ for all p ∈ [0,∞). The product of two non-negative, proper USC functions is also USC. The product of two non-negative USC, proper or not, is also USC provided we treat 0 ×∞ = ∞, and we will agree to this convention to develop a unified theory for both proper and improper functions. Let s̄(z) =

∫∞
z d̄(y)dy be the area under the function d̄(y) to the right of z, and notice that

r̄(z) ≤ s̄(z) ≤ s̄(0) for all z ≥ 0.

The following result presents conditions that guarantees the existence of a finite maximizer.
The proof of the result is somewhat technical and can be found in the Appendix.

Theorem 2 If d(p) is USC and s̄(0) < ∞ then for every z ≥ 0 there exist a finite price p(z) ∈ [z,∞) such that r(z) = r(p(z),z). Moreover, p(z) can be selected so that it is increasing in z.

Remark 1: If we want to guarantee the existence of a finite price for a given z, rather than for
all z ≥ 0, then it is enough to require d to be USC on X ∩{p ≥ z} and to require s̄(z) < ∞.

Remark 2: Notice that the condition s̄(0) < ∞ is sufficient but not strictly necessary. To see this notice that d̄(p) = 1/p results in s̄(0) = ∞ yet r̄(p, 0) = 1 for all p > 0, so p̄(0) = 1 is
optimal. However, p̄(z) = ∞ for all z > 0 since r̄(p,z) = 1 −z/p is increasing in p.

Remark 3: In many cases d(p) is eventually decreasing, i.e., there is a p′ such that d(p) is
decreasing on p ≥ p′. However, Theorem 2 does not require this. For example, the demand
function d(p) = a exp(−bp) sin2(p) is not eventually decreasing yet d̄(p) ≤ a exp(−bp) so
s̄(0) ≤ a

b
.

The following result shows that if the demand comes from a maximum willingness to pay
function with finite mean then the conditions of Theorem 2 apply.

Corollary 2 If d(p) = λP(W ≥ p) for some random variable W with E[W] < ∞, then there exist a finite maximizer p(z) such that r(z) = r(p(z),z).

Under the first two conditions of Corollary 2, the actual demand, say D(p) is random with
d(p) = E[D(p)]. As an example, the potential demand may be Poisson with parameter λ and
demand at price p may be a thinned Poisson with parameter λH(p). Notice that by defining
H(p) = P(W ≥ p) instead of H(p) = P(W > p) we are able to claim that H(p) is LCRL.
This is an innocuous assumption if the distribution of W is continuous, or if W is discrete and
pricing is, as it is in practice, restricted to discrete values, e.g., dollars and cents. However, the
case where W is discrete and prices are allowed to be continuous leads to technical problems.
Thus, if a customer is willing to pay any price lower than $10, then there is no finite price
that maximizes the revenue that we can generate from such a customer, but things are fine if
he is willing to pay up to and including $10. For this reason it is convenient to think of W as
the maximum willingness to pay when H(p) is defined as P(W ≥ p).

As an example, if W is exponential with mean θ, then d(p) = λe−p/θ, p(z) = z + θ and
r(z) = θe−(z+θ)/θ = θe−1e−z. In this case the demand function d(p) has two parameters, λ
representing the expected market size and θ representing the mean willingness to pay. There
are, however, examples where d(p) = λH(p) with H(p) decreasing in p, where H(p) is not of
the form P(W ≥ p) for some random variable W. To see this consider the demand function
d(p) = λp−β for some β > 1. Then s(z) < ∞ and p(z) = βz/(β − 1) for all z > 0, yet
there is no random variable W such that λP(W ≥ p) = d(p), as p−β > 1 for p ∈ (0, 1).
Often d(p) = λH(p), with H decreasing can be written as d(p) = λf(αp + β ln p), where f is
a decreasing function and α and β are non-negative parameters. For example, f(x) = e−x,
α = 1/θ and β = 0 yields d(p) = λe−p/θ, while α = 0 and β > 1 yields d(p) = λp−β.

2.1 Demand Estimation

Suppose that time is rescaled into tiny intervals so that the demand Dt = D(pt) at price pt in
period t is a Bernoulli random variable with expected value d(pt) = λf(αpt + β ln(pt)) << 1, for some positive, decreasing function f, e.g., f(x) = e−x or f(x) = e−x/(1 + e−x). Then Dt = 1 with probability d(pt) and Dt = 0 with probability 1 −d(pt). Suppose we have data (ps,ds) : s = 1, . . . , t, where ds is the realized value of Ds in period s. The likelihood function up to time t is given by

Lt(λ,α,β) = Π
t
s=1d(ps)

d
s(1 −d(ps))

1−ds.

The log-likelihood function is given by

lt(λ,α,β) =
s∑
s=1

[ds ln(d(ps)/(1 −d(ps)) + ln(1 −d(ps))].

The score equations are obtain by setting the derivatives lt(λ,α,β) with respect to λ,α and
β equal to zero. The solution to the score equations are the maximum likelihood estimators
λ̂t, α̂t, β̂t. One important concern is whether the sequence of estimators λ̂t, α̂t, β̂t converges to
the true parameter values λ,α and β. An interesting finding is that to guarantee convergence
there needs to be enough variability in the prices. Without enough variability, it is possible
for the estimates to converge to incorrect values of the parameters.

3 Unimodality of r(p,z), uniqueness of p(z)

We now turn to conditions on the demand function d(p) that guarantee that r(p,z) does not
have local, non-global, maximizers or more succinctly that r(p,z) is uni-modal in p ≥ z. This
equivalent to r(p,z) being quasi-concave in p ≥ z and to r(p,z) having convex upper level
sets: {p ≥ z : r(p,z) ≥ α} for all α. If d(p) is continuous and differentiable, we define the
hazard rate at p to be h(p) = −d′(p)/d(p) where d′(p) is the derivative of d at p. The hazard
rate function h(p) is defined for all p < p∞ = sup{p : d(p) > 0}. Notice that p∞ may be ∞.
p∞ is the null price as d(p) > 0 for all p < p∞ and d(p) = 0 for all p ≥ p∞. We say that a function f(p) has a unique sign change from + to − over p ≥ z if the function starts positive,

becomes non-positive and stays non-positive once it becomes non-positive for the first time.
Notice that we are not requiring f(p) to be decreasing, nor for a root of f(p) = 0 to exist.
The following Theorem provides sufficient conditions for the existence of a finite maximizer.
The proof of the Theorem is in the Appendix.

Theorem 3 If d(p) is differentiable and

f(p) = 1 − (p−z)h(p) (4)

has a unique sign change from + to − on p ≥ z, then r(p,z) is unimodal and

p(z) = sup{p : 1 − (p−z)h(p) ≥ 0} (5)

is a global maximizer of r(p,z).

Proof: The derivative of r(p,z) with respect to p can be written as

∂r(p,z)

∂p
= d(p) + d′(p)(p−z)

= d(p) [1 − (p−z)h(p)] (6)

for all p < p∞. As a result r(p,z) is increasing in p for all p < p(z) and decreasing for all p ≥ p(z). Moreover, r(p,z) = 0 for all p ≥ p∞, proving that p(z) is a global maximizer.

Notice that we cannot guarantee the existence of a root to 1−(p−z)h(p). This is because
d′(p) and therefore f(p) need not be continuous. While Theorem 3 rules out the existence of
local, non-global, maximizers, there may be multiple global maximizers, i.e., multiple roots of
f(p) = 0, if there is an interval over which h(p) = 1/(p− z). The following corollary provide
stronger conditions for the existence and uniqueness of a finite maximizer and also provides
bound on p(z).

Proposition 1 a) If d̃(p) is a demand function with hazard rate h̃(p) such that h̃(p) ≥ h(p)
or ph̃(p) ≥ ph(p) for all p, then p̃(z) ≤ p(z) where p̃(z) is a maximizer of r̃(p,z) =
(p−z)d̃(p).

b) If h(p) is continuous and increasing in p and h(z) > 0, then there is a unique optimal
price satisfying z ≤ p(z) ≤ z + 1/h(z). Moreover, the upper bound is attained by the
exponential demand function d(p) = λe−p/θ.

c) If ph(p) is continuous and increasing in p and there exists a finite z′ ≥ z such that
1 < z′h(z′), then there is a unique optimal price satisfying z ≤ p(z) ≤ z/(1−1/z′h(z′)). Moreover, the upper bound is attained by the constant elasticity demand function d(p) = λp−b for any b > 1.

Proof:

a) Clearly f̃(p) ≤ f(p) so p̃(z) ≤ p(z).

b) If h(p) is continuous and increasing in p then f(p) is continuous and strictly decreasing
in p ≥ z. Now f(z) = 1 > 0 implies that p(z) > z, while f(z + 1/h(z)) = 1 − h(z +
1/h(z))/h(z) ≤ 0 on account of h(z + 1/h(z)) ≥ h(z) > 0 implies that p(z) ≤ z + 1/h(z).
Therefore there exist a unique p(z) satisfying (5) that is bounded below by z and above
by z + 1/h(z). For the exponential demand function d(p) = λe−p/θ, we have h(z) = 1/θ
and p(z) = z + θ = z + 1/h(z), so the upper bound is attained.

c) If ph(p) is increasing in p and z′h(′z) > 1 then f(p) is continuous in p > z and the
equation f(p) = 0 can be written as ph(p) = p/(p−z) with the left hand side increasing
in p and the right hand side decreasing to one for p > z. Since zh(z) < ∞ it follows that p(z) ≥ z. Notice that z/(1 − z′h(z′)) is the root of z′h(z′) = p/(p − z). Since ph(p) ≥ z′h(z′) ≥ p/(p−z) for all p ≥ z/(1 −z′h(z′)) it follows that p(z) is unique and bounded above by z/(1 − 1/z′h(z′)). For d(p) = λp−b, with b > 1, we have ph(p) = b,
and p(z) = bz/(b− 1) = z/(1 − 1/b) = z/(1 − 1/z′h(z′)), so the bound is attained.

The reader is directed to van den Berg [

] and references therein for earlier efforts to
characterize the existence or uniqueness of global maximizers. In particular van den Berg
assumes that H exist, is continuous and E[V ] < ∞ to show existence. He assumes that ph(p) is strictly increasing to show uniqueness. He calls this condition increasing proportional failure rate condition (IPFR) and gives a large list of distribution functions that satisfy the IPFR condition. Economists frequently write the first order condition f(p) = 0 as

p−z
p

=
1

ph(p

)
=

|e(p)|

where e(p) = −ph(p) = pd′(p)/d(p) is the elasticity of demand. Since ph(p) is the (absolute)
elasticity of demand at price p, the IPFR condition is equivalent to assuming an increasing
(absolute) demand elasticity. The reader is also referred to Lariviere and Porteus [10] for an
equivalent assumption where ph(p) is called the generalized hazard rate.

The problem of maximizing r(p,z) can sometimes be transformed so that demand rather
than price is the decision variable. This can be done if there is an inverse demand function,
say p(d), that yields demand d at price p(d). This results in the problem of maximizing
(p(d) −z)d over d. It is sometimes advantageous to use this formulation as there are demand
functions for which (p(d) −z)d is concave in d while r(p,z) is not concave in p. While we are
cognizant of this advantage, and have used it in some of our research, it is interesting to note
that there are also demand functions for which r(p,z) is concave in p without (p(d)−z)d being
concave in d. We refer the reader to Ziya et al. [1

] for an interesting analysis that shows
that non-equivalence of the following assumptions (i) concavity of pd(p) in p, (ii) concavity of
dp(d) in d and (iii) ph(p) increasing in p.

3.1 Behavior of p(z) and r(z) for Gamma willingness to pay

One family of demand functions that is frequently used because of its flexibility is d(p) =
λP(W ≥ p) and W has a gamma distribution with parameters α and β. This gives us great
flexibility since E[W] = αβ and Var[W] = αβ2. Then we can fit any mean µ and variance σ2

by setting the parameter β = σ2/µ and α = µ2/σ2. One may wonder how p(z) and r(z) behave
as a function of σ2 for fixed µ. Does more variance lead to higher or lower prices and/or profits?
The following tables present p(z) and r(z) for a range of values of the coefficient of variation
cv for fixed E[W] = 500. Table 1 shows that prices p(0) and p(400) first go down and then
up as the coefficient of variation goes up. In contrast, r(0) and r(400) exhibit very different
behavior, with r(0) going down and r(400) first going down and then up with the coefficient of
variation. This suggests that when the marginal cost z is large, more randomness can result
in higher prices and higher profits. This has implications for revenue management. When
capacity is tight, the marginal value of capacity is high, and then variance in the willingness
to pay helps because it increases the likelihood that someone will be willing to pay dearly for
capacity. In contrast, when the marginal value of capacity is low, higher variance leads to
higher prices and lower revenues, as we lose demand from customers with lower willingness to
pay. Surprisingly, for very large coefficient of variations, the revenues seem to be independent
of z. In this case the price is so high, and the probability of sale d(p(z)) is so low that zd(p(z))
becomes negligible. For the example in Table 1, as cv →∞, we see r(0) = r(z) = $

0.75.

cv p(0) r(0) p(400) r(400)
0.000 $500.00 $500.00 $500.00 $100.00
0.

5 $408.44 $382.35 $487.72 $49.

0 $372.90 $316.68 $5

$48.76
0.375 $362.

3.14 $578.95 $53.67
0.500 $368.15 $

2.80 $6

.87 $59.69
0.625 $386.62 $2

.02 $693.42 $65.83
0.750 $415.51 $

5.03 $757.56 $71.79
0.875 $453.56 $

3.06 $826.38 $77.41
1.000 $500.00 $183.94 $900.00 $82.65
1.125 $554.

$176.88 $978.56 $87.47
1.250 $616.26 $171.33 $1,062.19 $91.89
1.375 $685.54 $166.92 $1,151.03 $95.91
1.500 $762.03 $163.35 $1,245.21 $99.56

Table 1: p(0) and r(0) for E[W ] = 500

4 Bounded Capacity and Sales Constraints

Consider pricing a product where up to c units can be procured at marginal cost z. At
price p we can sell at most dc(p) = min(d(p),c) units. It is possible to sell up to dc(p)
units assuming that customers are willing to take partial orders or that demand comes from
many customers with small demands. In this case the pricing problem can be formulated as

rc(z) = supp∈X rc(p,z) where rc(p,z) = (p−z)dc(p).

Proposition 2 If d(p) satisfies the conditions of Theorem 2, then so does dc(p) = min(d(p),c),
and as a result there exists a finite maximizer pc(z), increasing in z, of rc(p,z) such that
rc(z) = rc(pc(z),z) is decreasing convex in z.

Proof: Since dc(p) ≤ d(p) it follows that x̄c(z) ≤ s̄(z) for all z and consequently x̄c(0) ≤
s̄(0) < ∞. If d(p) is USC then so is dc(p) because the minimum of USC functions is USC.

As an example, suppose that z = 0, d(p) = 3 for p ≤ 10 and d(p) = 0 for p > 10. If
c = 2 then d2(p) = 2 if p ≤ 10 and d2(p) = 0 for p > 10. Then r2(p, 0) is maximized at
p2(0) = 10 resulting in r2(0) = 20. Notice that at this price three units are demanded but
only two units are sold. If demand comes from three different customers each requesting one
unit this is not a problem, but if it comes from a single customer that wishes to fulfill all
of his demand or none at all then the formulation proposed here would be inappropriately
optimistic. Indeed, if customers are not willing to take partial orders we can use a more
conservative formulation: supp≥z r(p,z) subject to d(p) ≤ c. The set of feasible prices for
the current example is {p : p > 10} and over this range r(p, 0) = 0, so the profit under this
formulation is zero. This would be the correct profit if demand comes from a single customer
unwilling to take partial orders but the formulation would be excessively pessimistic if the
demand came from three different customers each demanding one unit at any price p ≤ 10.

We now turn to the questions of unimodality of rc(p,z) and uniqueness of pc(z).

Proposition 3 If the hazard rate h(p) of d(p) satisfies the conditions of Theorem 3 for a fixed
z then so does the hazard rate hc(p) of dc(p) and as a result rc(p,z) is unimodal in p.

Proof: Suppose that 1 − (p− z)h(p) has a unique sign change from + to −. Let dc(p) =
min(d(p),c). If d(0) < c then dc(p) = d(p) for all p ≥ 0 and there is nothing to show. Otherwise the hazard rate, say hc(p), of dc(p) is zero when d(p) > c and is equal to h(p)
otherwise. Thus, if 1 − (p − z)h(p) has a unique sign change then so does 1 − (p − z)hc(p),
showing that rc(p,z) is unimodal in p.

Let pmin(c) = sup{p ≥ 0 : d(p) ≥ c}. It is useful to think of pmin(c) as the market
clearing price as demand exceeds supply for all p < pmin(c) and supply exceeds demand for all p > pmin(c). The following result links pc(z) to p(z) via the market clearing price pmin(c).

Corollary 3 The price

pc(z) = sup{p ≥ pmin(c) : 1 − (p−z)h(p) ≥ 0} = max(p(z),pmin(c))

is a global maximizer of rc(p,z). Moreover, if either hc(p) or phc(p) are strictly increasing or
the equation 1 − (p−z)hc(p) has a unique root, then pc(z) is unique.

If d(p) is continuous then the formulation maxp≥z rc(p,z) is equivalent to the formulation
maxp≥z r(p,z) subject to d(p) ≤ c and we can bring in the machinery of Lagrangian Relaxation.

The idea is to impose a penalty γ(d(p) − c) for violations of the capacity constraint where γ
is a non-negative Lagrange multiplier. Subtracting the penalty results in the Lagrangian:

L(p,γ) = r(p,z) −γ(d(p) − c) = r(p,z + γ) + γc.

The agenda is to find minγ≥0 maxp≥z L(p,γ). The inner optimization is solved by p(z + γ)
and the outer optimization is equivalent to minγ≥0[r(z + γ) + γc] which is a convex program
in γ. Notice that γ ≥ 0 increases the marginal cost of capacity. Let γc be any unconstrained
minimizer of r(z + γ) + γc. Then the outer optimization is solved by γ∗c = max(γc, 0). If
d(p(z)) ≤ c, then γc ≤ 0 and consequently γ∗c = 0. In other words, p(z) is an optimal solution
if capacity is ample.2 On the other hand, if d(p(z)) > c, then capacity is scarce and γc is the
root of d(p(z + γ)) = c. This corresponds to using the market clearing price pmin(c) discussed
before. In summary, an optimal price is given by max(p(z),pmin(c) and if pmin(c) > p(z) then
there exists a γ∗c > 0 such that pmin(c) = p(z + γ

∗
c ). As an example, consider the problem with

d(p) = λe−p/µ then p(z) = µ+z and pmin(c) = µ ln(c/λ) so pc(z) = max(µ+z,µ ln(c/λ)) solves
the pricing problem and the problem is capacity constrained whenever c < d(p(z)) = e−1d(z). Also, γ∗c = max(0,µ[ln(c/λ) − 1] −z).

4.1 Sales Constraints

Management may be interested in achieving a certain sales volume and impose the constraint
d(p) ≥ c on sales. This is the opposite of a capacity constraint and if d(p) is continuous the
constraint can be handled by imposing a penalty γ(c−d(p)) on violations of the constraint.
Subtracting the penalty results in the Lagrangian L(p,γ) = r(p,z) − γ(c − d(p)) = r(p,z −
γ) −γc. The program is to maximize r(z −γ) −γc over γ ≥ 0. Notice that now γ ≥ 0 acts
as a subsidy to the unit cost z. This is a convex program in γ. Let γc be the unconstrained
optimizer of r(z−γ)−γc. Then γ∗c = max(γc, 0). If d(p(z)) ≥ c then γc ≤ 0 and consequently
p(z) is an optimal solution. In this case, the target sales c is overshot. On the other hand,
if d(p(z)) < c, then γc is the root of d(p(z − γ)) = c. This corresponds to using the market clearing price pmin(c) discussed before. In summary, the optimal price is given by pc(z) = min(p(z),pmin(c)).

5 Call Options and Social Welfare

Assume that demand is d(p) = λH(p) where H(p) = P(W ≥ p). While the seller is naturally
interested in maximizing r(p,z) = (p − z)d(p), a social planner may be more interested
in maximizing the sum of the seller’s profit r(p,z) plus the consumer’s surplus s(p) where
s(p) =

∫∞
p d(y)dy = λE[(W −p)

+] =. The social welfare problem is to maximize

w(p,z) = s(p) + r(p,z) = λ[E[(W −p)+] + (p−z)H(p)].
2In this case c−d(p(z)) units will go unsold. Any attempt to reduce the price to sell these additional units

will result in lower profits.

Let w(z) = maxp≥z w(p,z). It is easy to see, by just drawing a graph of E[(W − p)+] +
(p − z)H(p), that an optimal solution to the welfare problem is to set p = z, so w(z) =
s(z) + r(z,z) = s(z). Unfortunately, this solution reduces the profit of the seller to zero, as
r(z,z) = 0, while giving all of the surplus s(z) to the customers.

Welfare planners call dead-weight loss the difference w(z)−w(p(z),z) between the opti-
mal social welfare and the social welfare that results when the seller maximizes his profits. We
now explore a situation where the dead-weight loss can be eliminated. The situation requires
the use of call options on capacity when booking and consumption are separated by time and
customers have homogeneous ex-ante valuations at the time of booking. Examples include a
group of homogeneous customers booking air transportation a month in advance of traveling
or a single customer buying a service contract for services over a certain period of time.

Suppose there is a time separation between booking and consuming a service and that each
customer has random valuation, say W, for the service at the time of consumption. We assume
that customers know the distribution of W at the time of booking and learn the realization
of W at the time of consumption. We assume that the distribution H(p) = P(W ≥ p) is
known by the seller. Under these conditions, the seller can benefit from offering call options
to consumers. A call option requires an upfront non-refundable payment x that gives the
customer the non-transferable right to buy one unit of the service at price p at the time of
consumption; see Gallego and Sahin [6], Png [14], Shugan and Xie [16], Xie and Shugan [18].
The special case where p = 0, is called advanced selling.

Customers evaluate call options by the surplus they provide. A customer who buys an (x,p)
option will exercise his right to purchase one unit of the service at the time of consumption if
and only if W ≥ p. By doing this, an individual customer obtains expected surplus E[(W −
p)+]. Since the consumer needs to pay x for this right, the consumer receives surplus E[(W −
p)+]−x. We will impose a participation constraint λ[E(W −p)+ −x] = s(p)−λx ≥ s̃, where
s̃ ≥ 0 is a lower bound on the aggregate consumer surplus.

If all customers buy the call option then the seller’s profit is given by

λ[x + (p−z)H(p)]. (7)

This consists of the revenue from the non-refundable deposit x plus the profit p−z from those
customers who exercise their options.

Consider now the problem of maximizing the expression in equation (7) with respect to
(x,p) subject to the surplus constraint s(p) −λx ≥ s̃. Notice that the seller may set s̃ = 0 to
extract as much surplus from consumers. Here we will analyze the problem for other values
of s̃ to show that it is possible to eliminate the dead-weight loss and use s̃ as a mechanism to
distribute profits and surplus between the seller and the consumers.

Since the objective function (7) is increasing in x, it is optimal to set λx = s(p) − s̃, so
the problem reduces to that of maximizing s(p) + r(p,z) − s̃ = w(z,p) − s̃ with repect to p.
We already know that w(p,z) is maximized at p = z. Thus, the solution to the provider’s
problem is to set p = z and x = [s(z)− s̃]/λ, so the provider obtains profits equal to s(z)− s̃,
while consumers receive surplus s̃. We now explore the range of values of s̃ that guarantees

that both the seller and the consumers are at least as well off as the solution (x,p) = (0,p(z)),
where price p(z) is offered to consumers after they know their valuations. At price p(z), the
provider makes profit r(z), while purchasing customers obtain aggregate surplus s(p(z)). As
a result, consumers are better off whenever s̃ ≥ s(p(z)), while the seller is better off whenever
s(z)−s̃ ≥ r(z), so a win-win is achieved for any value of s̃ such that s(p(z)) ≤ s̃ ≤ s(z)−r(z).
Since the solution eliminates dead-weight loss, s(z) ≥ r(z) + s(p(z)), and consequently the
win-win interval is non-empty. Absent competition or an external regulator, the provider may
simply select s̃ = 0, to improve his profits from r(z) to w(z) extracting all consumer surplus
while also capturing the dead-weight loss.

The idea of using call options can be extended to the case where the variable cost Z
of providing the service at the time of consumption is random. In this case, the option be
designed by setting λx = Es(Z) − s̃ and p = Z, so that by paying x in advance the option
bearer has the right to purchase one unit of the service at the random marginal cost Z.
It is interesting to measure the benefits to the provider of offering call options on capacity
instead of selling at p(Z) when customers already know their valuations. In essence we want
to compare Es(Z) − s̃ to Er(Z). To make this a fair comparison we will set s̃ = Es(p(Z)),
so that both (x,p) with λx = Es(Z) −Es(p(Z)) and p = Z, and (x,p) = (0,p(Z)) result in
the same consumer surplus. However, the benefits of offering call options may be larger as
a monopolist need not compete against himself and can in fact extract all surplus by setting
s̃ = 0. Our next result is for exponentially distributed W with mean θ. For convenience, we
will let θ∗ = θ/e.

Proposition 4 If W is exponentially distributed with mean θ and the moment generating
function MZ(−1/θ) = E[e−Z/θ] < ∞, then the lift in expected profits from offering call option (Es(Z) −Es(p(Z)),Z) relative to offering call option (0,p(Z)) is 72%. Moreover, the lift in profits for a monopolist who sets s̃ = 0 is 172%.

Proof: If W is exponential with mean θ. Then p(Z) = Z + θ and r(Z) = λθ∗e−Z/θ.
Consequently, the expected profit from (0,p(Z)) is E[r(Z)] = λθ∗MZ(−1/θ). Since s(Z) =
λθe−Z/θ and s(p(Z)) = r(Z)/, it follows that the expected profits from the call option is given
by λ(θ−θ∗)MZ(−1/θ), and the relative lift in profits is equal to (θ−2θ∗)/θ∗ = (e−2) = 72%.
If the seller extracts all the surplus then the relative lift in profits is (e− 1) = 172%.

The lift in expected profits from the exponential distribution is quite large and one may
wonder whether large lifts are also possible for other distributions. It is possible to show
that if d(p) = λp−b, then for z > 0 and b > 1, the lift in profits is at least as large as that
for the exponential demand model, with the benefits converging to those of the exponential
distribution as b → ∞. Consequently, the benefits are at least as large under the constant
price elasticity model than under the exponential demand model. Here we show that if W
has a uniform distribution, then the lift in expected profits can be up to 50%. Readers not
interested in the details of the analysis can skip to the next section.

Example 2 : If W is uniformly distributed over the interval [a,b] then s(p) = E[W] −p for
p < a, s(p) = 0.5(b−p)2/(b−a) for p ∈ [a,b] and s(p) = 0 for p > b. The revenue maximizing
price is p(z) = max(a, (b+z)/2) for 0 < z ≤ b. For z > b there is no demand so we will confine

our analysis for z < b. Then r(z) = a−z for 0 ≤ z < (2a−b)+ and r(z) = 0.25(b−z)2/(b−a) for (2a − b)+ ≤ z ≤ b. The expected surplus from offering price p(z) is s(p(z)) = s(a) = E[W ]−a = 0.5(b−a) = 2r(a) for 0 ≤ z < (2a−b)+, s(p(z)) = 0.125(b−z)2/(b−a) = 0.5r(z) for 2a − b ≤ z ≤ b. An (x,p) option with p = z results in surplus −x + s(z) and for this to be more attractive we need x ≤ s(z) − s(p(z)). The contract (s(z) − s(p(z)),z) results in profits s(z) − s(p(z)) = E[W] − z − E[W] + a = a − z = r(z) for z < (2a − b)+ so there is no benefit in offering contracts when z < (2a − b)+. For (2a − b)+ ≤ z ≤ a we have s(z) −s(p(z)) = E[W] −z − 0.5r(z) > r(z) on account of θ(z) = E[W] −z − 1.5r(z) ≥ 0 on
(2a− b)+ ≤ z ≤ a. This can be verified by checking that θ(2a− b) = 0 and θ′(z) > 0 on the
interval (2a − b)+ ≤ z ≤ a. In fact at z = a we have θ(a) = E[W] − a − 1.5r(a) = 0.5r(a)
so the lift from contracts is between (0, 0.5] over the interval ((2a− b)+,a). Finally, over the
interval a ≤ z ≤ b we have s(z) −s(p(z)) = 2r(z) − 0.5r(z) = 1.5r(z) so there is a 50% lift.

5.1 Call Options and Service Contracts

As mentioned earlier, the idea of a call option may also apply to an individual customer
buying a service contract for services over a certain period of time. The contract allows the
customer to pay x in advance for the right to pay the marginal cost z each time the service
need arises over a certain pre-specified horizon. If the expected number of services during this
period of time is λ, and each service need has random value W, then a contract of the form
(x,p) = (λ(s(z) − s̃),z) may be designed, by selecting s̃, to be as attractive as offering á la
carte services at p(z). In this case, obtaining the surplus from á la carte services is a bit trickier
because the decision of whether or not to buy a service at price p(z) for a current service of
value W may influence the need for future services. As an example, consider the problem of
repair services for a certain product. If the customer declines the service at price p(z) because
W < p(z), then the customer forgoes the future utility associated with this product while the service provider forgoes the opportunity to continue servicing the product. This situation forces the customer to think carefully about whether or not to pay for the service at p(z) and forces the service provider to carefully design the contracts so they are win-win.

5.2 Call Options with Bounded Capacity

Assume there is a bounded capacity c. We will assume that each will buy at most one call
option. We will formulate the problem with the unconstrained demand function and impose
a condition on the number of customers that exercise the (x,p) option at the exercise price
p. Under this formulation the seller’s profit is [s(p) − s̃] + r(p,z) subject to the constraint
d(p) = λH(p) ≤ c. The constraint is equivalent to p ≥ pmin(c) so an optimal solution is to set
the exercise price at max(z,pmin(c)) and the option price at s(max(z,pmin(c)))− s̃. This leads
to profit [s(max(z,pmin(c))) − s̃] + r(max(z,pmin(c)),z) for the seller and aggregate consumer
surplus s̃. It is instructive to compare the two cases: pmin(c) ≤ z and pmin(c) > z. In the
first case the capacity constraint is not relevant as d(z) = λH(z) ≤ c, so the optimal option is
p = z and λx = s(z)−s̃, the profit to the seller is s(z)−s̃, and the aggregate consumer surplus
is s̃. On the other hand, if pmin(c) > z then λx = s(pmin(c)) − s̃ and p = pmin(c) resulting in
seller’s profit equal to s(pmin(c))− s̃ + r(pmin(c),z) = s(pmin(c))− s̃ + c(pmin(c)−z). It is also

possible to work directly with the truncated demand function dc(p). This leads to essentially
the same result but it is a bit more subtle to interpret.

6 Multiple Market Segments

Suppose we have multiple market segments with demands dm(p),m ∈ M = {1, . . . ,M}.
For any subset S ⊂ M, let dS(p) =

∑
m∈S dm(p) denote the aggregate demand over market

segments in S and let rS(p,z) = (p−z)dS(p) denote the profit function for market segments in
S when the variable cost is z, and a common price p is offered to all market segments in S. We
will first deal with questions related to the existence and uniqueness of finite maximizers of
rS(p,z) before exploring using a finite price menu of J different prices to price the M market
segments.

The following result shows that dS(p) inherits some desirable properties from the individual
market demand functions dm(p),m ∈ S.

Proposition 5 If dm(p) satisfies the conditions of Theorem 2 for every m ∈ S ⊂ M, then
so does dS(p). Moreover, there exists a finite price pS(z), increasing in z, such that rS(z) =
rS(pS(z),z) is decreasing convex in z.

Proof: Since the sum of USC is USC it follows that dS(p) is USC. Moreover x̄m(0) < ∞ for all m ∈ M implies that x̄S(0) =

∑
m∈S x̄m(0) < ∞. As a result dS(p) satisfies the conditions

of Theorem 2 so there exists a finite price pS(z), increasing in z, such that rS(z) = rS(pS(z),z)
is decreasing convex in z.

It may be tempting to conclude that under the conditions of Proposition 5 pS(z) would
lie in the convex hull of {pm(z),m ∈ S}, i.e., in the interval [minm∈S pm(z), maxm∈S pm(z)].
However, Example 3 shows that this is not true.

Example 3 Suppose that d1(p) = 1 for p ≤ 10 and d1(p) = 0 for p > 10. Then r1(p, 0) is
maximized at p1(0) = 10 and r1(0) = 10. Suppose that d2(p) = 1 for p ≤ 9, d2(p) = .1 for
9 < p ≤ 99 and d2(p) = 0 for p > 99. Then r2(p, 0) is maximized at p2(0) = 99 resulting
in r2(0) = 9.9 and total profit equal to 19.9 if each is allowed to be priced separately. Let
S = {1, 2}, then rS(p, 0) = r1(p, 0) + r2(p, 0) is maximized at pS(0) = 9 < mini∈S pi(0) resulting in rS(0) = 18.

Since the sum of quasi-concave functions is not, in general, quasi-concave, it should not
be surprising that properties of dm(p) that imply quasi-concavity of rm(p,z), for each m ∈M
are not, in general, inherited by dS(p) =

∑
m∈S dm(p). Example 4 illustrates this.

Example 4 a) Suppose that dm(p) = exp(−p/bm) for m = 1, 2 with b1 < b2. Then the hazard rate hm(p) = 1/bm, is constant, and there is a unique price pm(z) = z + bm that maximizes rm(p,z). Let S = {1, 2} and notice that the hazard rate hS(p) of dS(p) is decreasing in p.

b) Suppose that dm(p) = 1/p
bm for some bm > 1, then phm(p) = bm and there is a unique

price pm(z) = bmz/(bm − 1) that maximizes rm(p,z). However, the proportional hazard
rate phS(p) of dS(p) is decreasing in p.

This state of affairs is very unsatisfying because in both cases in Example 4 the profit
function rS(p,z) is actually quasi-concave, even if the aggregate demand function dS(p) has
decreasing hazard rate (part a) or decreasing proportional hazard rate (part b). Some level of
satisfaction may be restored if sufficient conditions can be founds so that rS(p,z) has a finite
bounded maximizer. Here we present such conditions.

Theorem 4 Assume that the hazard rate hm(p) is continuous in p and there is a finite root
pm(z) of fm(p) = 1 − (p − z)hm(p) = 0 for each m ∈ S. Assume further that phm(p)
is increasing for each m ∈ S. Then rS(p,z) has a finite maximizer in the convex-hull of
{pm(z),m ∈ S}.

Proof: It is easy to see that pm(z) > z is the root of
p
p−z = phm(p). Since the left hand

side is decreasing in p and phm(p) is increasing in p, it follows that there is a unique root
p > z. This implies that fm(p) > 0 on p < pm(z) and fm(p) < 0 on p > pm(z). Let
fS(p) = 1 − (p − z)hS(p) where hS(p) is the hazard rate of dS(p). Since fS(p) is a convex
combination of fm(p) = 1 − (p − z)hm(p) with weights θm(p) = dm(p)/dS(p), it follows that
fS(p) > 0 for all p < minm∈S pm(z) because over that interval fm(p) > 0 for all m ∈ S. Also
fS(p) < 0 for all p > maxm∈S pm(z) because over that interval fm(p) < 0 for all m ∈ S. Since the derivative of rS(p,z) is proportional to fS(p) it follows that rS(p,z) is increasing over p < minm∈S pm(z) and decreasing over p > maxm∈S pm(z). Moreover, since rS(p,z) is
continuous over the closed and bounded interval [minm∈S pm(z), maxm∈S pm(z)] and appeal to
the EVT yields the existence of a global maximizer pS(z) of rS(p,z).

Corollary 4 Theorem 4 holds if hm(p) is increasing in p for all m ∈ S

The Corollary follows since then phm(p) is increasing in p for all m ∈ S.

6.1 Pricing with Finite Price Menus

Consider now the situation where it is possible to use third degree price discrimination so
that a different price can be used for each market segment m ∈ M without worrying about
incentive compatibility. This situation arises when it is possible to vary price by time, location
or customer attributes without cannibalizing demand from other market segments. We will
embed this problem as part of a more general problem where we are allowed a price menu that
consist of at most J ≤ M different prices. The use of a finite price menu J < M may result from constraints in pricing flexibility or because the demand functions of some of the market segments is not know with sufficient accuracy. We will assume that the demand functions

dm(p),m ∈ M belong to the same family. By this we mean that dm(p) = λmHm(p),m ∈ M
and the tail distributions Hm(p) = P(Vm ≥ p),m ∈ M differ only on their parameters.
Examples of families of demand functions include linear, log-linear, CES, Logit, among others.
We will assume that the profit function rm(p,z) = (p−z)dm(p) is quasi-concave for each m and
that there is a unique finite maximizer pm(z) for each m ∈M. We will assume that the market
segments are ordered so that p1(z) ≤ . . . ≤ pM (z). Finally, we will assume that for any S ⊂M,
the profit function rS(p,z) has a finite maximizer in the interval [minm∈S pm(z), maxm∈S pm(z)],
as guaranteed under the conditions of Theorem 4.

The extreme cases are J = 1 where a single price is used for all market segments and
J = M where each market segment can be individually priced. In practice, one seldom has
the freedom or sufficiently detailed knowledge to use J = M prices, particularly if M is large.
In this section we solve to optimality the case J = M assuming detailed knowledge of the
demand functions. In addition, we develop heuristics for J ∈ {1, . . . ,M − 1} that are robust
to possible misspecification of demand functions dm(p),m ∈M. If J = M the problem is to
separately select prices pm,m ∈M to maximize

∑
m∈M rm(pm,z). This problem has a trivial

solution, namely to price market segment at pm(z),m ∈M, so the optimal profit is given by

RM (z)

=
∑
m∈M

rm(z).

Since each rm(z) is decreasing convex in z it follows that RM (z) is decreasing convex in z.
RM (z) will serve as a benchmark upper bound against which we will measure heuristics when
the price menu allows only J < M prices.

Since we will be using heuristic prices, it is convenient to have a measure of how efficient it
is to use price p instead of pm(z) for market segment m. This motivates defining the relative
efficiency of price p instead of pm(z) for market segment m when the unit cost is z as

em(p,pm(z),z) =

rm(p,z)

rm(z)

(8)

Notice that em(p,pm(z),z) ≤ 1, em(p,pm(z),z) reaches maximum efficiency at p = pm(z),
and decays on both directions as a result of our quasi-concavity assumption. It is possible to
find closed form formulas for em(p,pm(z),z) for many families of demand functions including
linear, log-linear and CES. However, there are distributions that do not admit closed form
expressions for em(p,pm(z),z) but the results that we will derive here can also be applied,
numerically, for distributions that do not admit closed form expressions. The relative efficien-
cies of prices will help us deal with situations where we may not know the exact parameters
of some of the market segments.

We will be particularly interested in families of demands for which em(p,pm(z),z) is inde-
pendent of m, i.e, that the functional form of e does not depend on the market segment. The
following result confirms that em is independent of m for the linear, for the log-linear and for
the logit demand functions.

Lemma 2 For the linear demand function dm(p) = am − bmp

e(p,pm(z),z) =
p−z

pm(z) −z

(
2 −

p−z
pm(z) −z

)
, (9)

for the log-linear demand function dm(p) = am exp(−p/bm)

e(p,pm(z),z) =
p−z

pm(z) −z
exp

(
1 −

p−z
pm(z) −z

)
, (10)

and for the logit demand function dm(p) = λme
am−p/(1 + eam−p),

e(p,pm(z),z) =
p−z

pm(z) −z + (ep−pm(z) − 1)
. (11)

Proof: For the linear demand function d(p) = a − bp, p(z) − z = (a − bz)/2b. Since
a− bp(z) = b(p(z) −z) it follows that r(z) = b(p(z) −z)2. Therefore

e(p,p(z),z) =
(a− bp)(p−z)
b(p(z) −z)2

Then (9) follows from (a− bp) = 2b(p(z) −z) − b(p−z) since 2b(p(z) −z) = a− bz.

For the log-linear demand function d(p) = ae−p/b, p(z) = z + b, so d(p(z)) = e−1d(z) and
r(z) = be−1d(z). On the other hand, r(p,z) = (p−z)e(p−z)/bd(z). As a result,

e(p,p(z),z) =
p−z
p(z) −z

exp{(p(z) −z)/b− (p−z)/b}.

The result (10) follows since b = p(z) −z.

For the logit demand function ea−p/(1 + ea−p), p(z) is the root of the equation p − z =
1 + ea−p, so r(z) = ea−p(z) = p(z) −z − 1. Consequently, the ratio r(p,z)/r(z) can be written
as (p−z)/[(p(z)−z−1)/d(p)] and the result follows if we can show that (p(z)−z−1)/d(p) =
p(z) − z − 1 + ep−p(z). But this is equivalent to showing that (p(z) − z − 1)/ea−p = ep−p(z)
or equivalently p(z) − z − 1 = ea−p(z). But we know this to be true since r(z) = ea−p(z) =
p(z) −z − 1.

Notice that in the first two cases what is important is the markup ratio (p−z)/(p(z)−z).
On occasions we will write e(p,q,z) and this should be interpreted as the efficiency of using
price p when q is optimal, so for example, e(p,q,z) = (p−z)/(q −z)[2 − (p−z)/(q −z)] for
the linear demand model.

The following result will be helpful in establishing our results.

Lemma 3 Suppose q1 < q2 and q ∈ (q1,q2) is selected so that e(q,q1,z) = e(q,q2,z), then e(q,p,z) ≥ e(q,q1,z) = e(q,q2,z) for all p ∈ (q1,q2).

Proof: Recall that e(q,p,z) deteriorates as q gets further from p in either direction. If p ∈
(q1,q) then e(q,p,z) > e(q,q1,z) as q is closer to p than to q1. On the other hand, if p ∈ (q,q2)
then e(q,p,z) > e(q,q2,z) as q is closer to p than to q2.

We will now provide a bound when only one price is allowed for all of the market segments.
We will make use of Lemma 6.1 to lower bound the ratio R1(z)/RM (z) where for J = 1 we
write R1(z) = rM(z) as the maximum profit when all market segments are priced at pM(z).

Theorem 5 Assume that the functions rm(p,z) are quasi-concave and each has a unique finite
maximizer pm(z). Suppose that the market segments are indexed so that pm(z) is increasing in
m ∈M. Assume that em(αpm(z),pm(z),z),m ∈M is independent of m ∈M for all α > 0.
Let q1 be the root of

e(q,p1(z),z) = e(q,pM (z),z) (12)

and let γ1(z) = e(q1,p1(z),z) = e(q1,pM (z),z) be the loss of efficiency of using q1 for market
segments 1 and M. Then

R1(z)

RM (z)

≥

rM(q1,z)

RM (z)
≥ γ1(z),

Proof: Assume p1(z) and pM (z) are respectively the smallest and the largest optimal prices
for the M market segments. Let q1 be the root of e(q,p1(z),z) = e(q,pM (z),z). Then, by
Lemma 6.1 we know that e(q1,pm(z),z) ≥ γ1(z) for all m = 2, . . . ,M−1. From this it follows
that

R1(z)

RM (z)
≥

rM(q1,z)
RM (z)
=
∑
m∈M

e(q1,pm(z),z)
rm(z)

RM (z)

≥
∑
m∈M

γ1(z)
rm(z)

RM (z)

= γ1(z).

Notice that Theorem 5 does not require precise knowledge of the demand functions dm(p)
other than knowing that pm(z) ∈ [p1(z),pM (z)]. Without detail knowledge of the demand
functions dm(p),m ∈{2, . . . ,M −1} it is not possible to find RM (z) or even R1(z). However,
it is possible to find q1, the root of equation (12). Theorem 5 guarantees that pricing all
segments at q1 is not too far from optimal when p1(z) and pM (z) are not too far apart.
Moreover, the actual performance R1(q1,z)/RM (z) can be significantly better than the lower
bound γ1(z). Closed form expressions for γ1(z) will be presented shortly for the linear and
log-linear demand functions after we generalize Theorem 5 to J > 1.

We will now define RJ(z) the maximum expected revenue that we can obtain if we are
allowed to use up to J different prices for J ∈ {2, . . . ,M − 1}. Fix 1 < J < M and consider

any partition S1, . . . ,SJ of M such that ∪Jj=1Sj = M and Si ∩Sj = ∅ for i 6= j. Let

rSj (z) = sup
p≥z

∑
m∈Sj

rm(p,z)
and let

RJ(z|S1, . . . ,SJ)

=
J∑
j=1

rSj (z).

Optimizing over the partitions we obtain

RJ(z) = max
S1,…,SJ

RJ(z|S1, . . . ,SJ)

where the maximum is taken over all mutually exclusive and collectively exhaustive partitions
of M into J subsets. Notice that finding RJ(z) can be a difficult as there are a combinatorial
number of possible partitions of M. Moreover, solving for RJ(z) requires precise knowledge
of all of the demand functions dm(p),m ∈M.

To extend the heuristic for J > 1 we proceed as follows: Select break-points p1(z) = s0 < s1 < s2 . . . < sJ−1 < sJ = pM (z) and prices qj ∈ (sj−1,sj) such that e(qj,sj−1,z) = e(qj,sj,z) for each j and the efficiencies e(qj,sj,z) are independent of j. More precisely, the sjs and qjs are selected so that

e(qj,sj−1,z) = e(qj,sj,z) for all j = 1, . . . ,J (13)

and
e(q1,s1,z) = e(q2,s2,z) = . . . = e(qJ,sJ,z). (14)

Let γJ(z) = e(q1,s1,z) and define the sets Mj = {m : pm(z) ∈ [sj−1,sj)} for j = 1, . . . ,J − 1
and MJ = {m : pm(z) ∈ [sJ−1,sJ]}. Notice that the qjs and sjs are independent of the
precise specification of dm(p),m = 2, . . . ,M −1 and consequently γJ(z) is also independent of
the intermediate demands. However, identifying the sets Mj,j = 1, . . . ,J does require some
knowledge of the intermediate demand functions in the sense that we need to identify the
subset Mj to which each pm(z) belongs.

Theorem 6 Under the assumptions of Theorem 5, offering price qj to all segment in Sj for
j = 1, . . . ,J results in

RJ(z)

RM (z)
≥ γJ(z).

Proof: Clearly

RJ(z)
RM (z)
≥

∑J
j=1

∑
m∈Mj rm(qj,z)

RM (z)
=
J∑
j=1

∑
m∈Mj

e(qj,pm(z),z)
rm(z)

RM (z)
21

≥
J∑
j=1

∑
m∈Mj

γJ(z)
rm(z)

RM (z)

= γJ(z)
J∑
j=1

∑
m∈Mj
rm(z)
RM (z)

= γJ(z).

We now illustrate the lower bounds for a variety of demand functions.

6.2 Linear Demand Functions

Consider linear demand functions dm(p) = (am − bmp),m = 1, . . . ,M. Then pm(z) = (am +
bmz)/2bm and e(p,pm(z),z) =

p−z

∆m(z)

(
2 − p−z

∆m(z)

)
where ∆m(z) = pm(z) −z.

Let
sj = z + ∆

1−j/J
1 (z)∆

j/J
M (z) j = 0, 1, . . . ,J (15)

and prices

qj = z + 2
∆

1−(j−1)/J
1 (z)∆

j/J
M (z)

∆
1/J
1 (z) + ∆

1/J
M (z)

j = 1, . . . ,J. (16)

Proposition 6 Equations (15,16) are roots of equations (13, 14). Moreover,

γJ(z) =
4∆

1/J
1 (z)∆

1/J
M (z)

(∆
1/J
1 (z) + ∆

1/J
M (z))

2
. (17)

Proof: To show that e(qj,sj,z) =
qj−z

sj−z

(
2 − qj−z

sj−z

)
= γJ(z) for each j = 1, . . . ,J, first notice

that

qj −z
sj −z

= 2
∆

1/J
1 (z)

∆
1/J
1 (z) + ∆
1/J
M (z)

j = 1, . . . ,J

and that

2 −
qj −z
sj −z

= 2
∆
1/J
M (z)
∆
1/J
1 (z) + ∆
1/J
M (z)

j = 1, . . . ,J,

e(qj,sj,z) =
qj −z
sj −z

(
2 −
qj −z
sj −z
)
=

4∆
1/J
1 (z)∆

1/J
M (z)
(∆
1/J
1 (z) + ∆
1/J
M (z))

2
.

To show that e(qj,sj−1,z) = γJ(z) for all j notice that

qj −z
sj−1 −z

= 2
∆
1/J
M (z)
∆
1/J
1 (z) + ∆
1/J
M (z)
j = 1, . . . ,J

and that

2 −
qj −z
sj−1 −z

= 2
∆
1/J
1 (z)
∆
1/J
1 (z) + ∆
1/J
M (z)
j = 1, . . . ,J,
so

e(qj,sj−1,z) =
qj −z
sj−1 −z

(
2 −
qj −z
sj−1 −z
)
=
4∆
1/J
1 (z)∆
1/J
M (z)
(∆
1/J
1 (z) + ∆
1/J
M (z))
2
.

The results for the linear demand function for z = 0 and J = 1 first appeared in Gallego
and Queyranne [4].

One may wonder how large J needs to be to achieve γJ(z) ≥ 1−α for some pre-specified α
and given ∆1(z), ∆M (z). The following corollary answers this question and Table 2 illustrates
the results for a range of values of α and of the ratio ∆M (z)/∆1(z).

Corollary 5 Let a(z) = ∆M (z)/∆1(z) and w(α) = (1 +
√
α)2/(1 − α). If J is an integer

greater or equal to ln(a(z))/ ln(w(α)), then γJ(z) ≥ 1 −α.

Proof: Let aJ(z) = a(z)
1/J. Then γJ(z) = 4aJ(z)/(1 + aJ(z))

2. Notice that w(α) is a
solution to the equation 4w/(1 + w)2 = 1 −α. Thus γJ(z) ≤ 1 −α whenever aJ(z) ≤ w(α),
or equivalently whenever a(z) ≤ w(α)J. Solving for J gives the result.

∆M (z)/∆1(z)
1 −α w(α) 2 5 10 25
90% 1.92 2 3 4 5
93% 1.75 2 3 5 6
95% 1.58 2 4 6 8
98% 1.38 3 6 8 11
99% 1.22 4 9 12 17

Table 2: Smallest J such that γJ(z) ≥ 1 −α

From Table 2 we see that if the markup ratio ∆M (z)/∆1(z) = (pM (z) −z)/p1(z) −z) = 2
we need only J = 2 to achieve an effectiveness of 95% regardless of the number of products
M. If the markup ratio is 5 then J = 6 is enough to guarantee an effectiveness of 98%. The
following example illustrates the lower bounds for a set of 10 products with linear demands
as well as the actual performance of the heuristic for J = 1.

Example 5 Suppose that M = 10 with market sizes 100, 200,

0, 400, 500, 500, 400, 300,
200, 100, each with uniform willingness to pay functions U[Am,Am + 100] with Am = 100 +
5(m−1),m = 1, . . . , 10. Table 3 reports q1, γ1(z) and the actual performance rM(q1,z)/RM (z)
of the heuristic. Table 4 reports the improvements on the efficiency lower bound as we enlarge
the menu J. Recall that the results from the table are lower bounds on performance whereas the
actual realization from a limited price menu can be significantly higher than the lower bound.

z q1(z) γ1(z) rM(q1,z)/RM (z)
0 $110.11 99% 100%
50 $134.78 98% 100%
100 $159.18 97% 99%
120 $168.78 95% 99%
140 $178.18 93% 98%
160 $187.20 87% 95%
180 $195.29 72% 86%

Table 3: Prices, Lower Bounds and Actual Performance for Example 5.

z γ1(z) γ2(z) γ3(z) γ4(z) γ5(z)
0 98% 100% 100% 100% 100%
50 99% 100% 100% 100% 100%
100 97% 99% 100% 100% 100%
120 95% 99% 99% 100% 100%
140 93% 98% 99% 100% 100%
160 87% 97% 98% 99% 99%
180 72% 92% 96% 98% 99%

Table 4: Efficiency Lower Bounds: J ∈{1, . . . , 5}, Example 5

Notice that the lower-bound γJ(z) deteriorates as z increases and improves as J increases,
and even for fairly high values of z, it is possible to obtain reasonably high lower bounds with
J = 3 or J = 4. For most demand models the contribution margins (pm(z) − z)/pm(z) go
down as the unit cost z increases. The behavior of the lower bound indicates that as margins
become thinner it becomes more important to have more pricing flexibility. In other words,
higher marginal costs require a higher J to achieve near optimality. In the context of Revenue
Management this suggest that a rich fare menu is more important when capacity is scarce
than when it is ample.

Remark: Sometimes it is possible to improve on the performance of a limited price menu by
giving up on the lower market segments. For example, for J = 1 and z = 180 the profit from
market segment 1 is less than 1% of the total. This suggest we can do better by dropping the
effort to keep the relative efficiency of market segment 1 high. If we use the single price

q′1(z) = z + 2
∆2(z)∆M (z)

∆2(z) + ∆M (z)
= $198.06

to control the efficiency of markets 2 through 10, the performance for J = 1 improves from
86% to 91.5% even though the efficiency of market segment 1 drops significantly.

6.3 Log-Linear Demand Functions

The family of log-linear, or exponential, demand functions is of the form dm(p) = am exp(−p/bm).
The maximizer of rm(p,z) is given by pm(z) = z + bm and the efficiency function is given by

e(p,pm(z),z) =
p−z
pm(z) −z
exp

{
1 −

p−z
pm(z) −z

}
.

Let
sj = z + b1u

j/J, j = 0, 1, . . . ,J (18)

and prices
qj = z + b1u

j/JUJ j = 1, . . . ,J. (19)

where u = bM/b1 and UJ =
ln(u)

J(u1/J−1) .

Proposition 7 Equations (18,19) are roots of equations (13, 14). Moreover,

γJ = UJe
1−UJ. (20)

Proof:

To show that e(qj,sj,z) =
qj−z
sj−z

exp(1 − qj−z
sj−z

) = γJ(z) for each j = 1, . . . ,J, first notice

that
qj −z
sj −z

= UJ,

so e(qj,sj,z) = UJe
1−UJ = γJ(z).

Notice that
qj −z
sj−1 −z

= u1/JUJ,

so to show e(qj,sj−1,z) = e(qj,sj,z) it is enough to show that u
1/JUJe

1−u1/JUJ = UJe
1−UJ but

this is equivalent to showing that ln(u1/J) = UJ(u
1/J−1) but this is true because UJ(u1/J−1) =

ln(u)/J = ln(u1/J).

Notice that unlike the linear demand function, for log-linear demand functions γJ is inde-
pendent of z. However, just like the linear demand function the lower bound improves with
J. On the other hand, γJ(z) deteriorates as u = bM/b1 increases.

One may wonder how large J needs to be to achieve γJ ≥ 1 −α for some pre-specified α
and given ∆1(z), ∆M (z). The following corollary answers this question and Table 5 illustrates
the results for a range of values of α and of the ratio ∆M (z)/∆1(z).

Corollary 6 Let w(α) be the root of ln(a)/(a − 1) = 1 − α and let u = bm/b1. If J is an
integer greater or equal to ln(u)/ ln(w(α)), then γJ ≥ 1 −α.

Proof: Let bJ = b
1/J. Then γJ = ln(bJ)/(bJ − 1), so setting bJ = b1/J = w(α), solving for

J and rounding up achieves γJ ≥ α.

∆M (z)/∆1(z)
1 −α w(α) 2 5 10 25
90% 1.92 2 4 6 8
93% 1.75 2 5 7 9
95% 1.58 2 6 8 11
98% 1.38 4 9 12 17
99% 1.22 6 12 17 24

Table 5: Smallest J such that γJ(z) ≥ 1 −α

Example 6 Suppose that M = 10 with log-linear demand functions with parameters a1, . . . ,am
given by 100, 200, 300,400, 500,500, 400,300,200,100, respectively and with parameters bm =
50+10(m−1),m = 1, . . . , 10. Table 6 reports q1, γ1(z) and the actual performance R(q1,z)/R(z)
of a common pricing policy for a range of values of z. Notice that in this case γ1(z) is inde-
pendent of z and that the actual performance is significantly better than the lower bound but
does deteriorate slowly with z.

Table 7 reports the improvements on the efficiency lower bound as we enlarge the menu J
for different values of u. The key observation is that for log-linear demand functions pricing
flexibility is important when u is large, but just a little flexibility can result in a fairly high
lower bound on efficiency, with the true performance of the system likely to be significantly
better.

z q1(z) γ1 rM(q1,z)/RM (z)
$0.00 $80.08 88% 96%
$50.00 $130.08 88% 96%
$100.00 $180.08 88% 96%
$150.00 $230.08 88% 95%
$200.00 $

0.08 88% 95%
$250.00 $330.08 88% 95%

Table 6: Efficiency Lower Bounds and Actual Performance J = 1

u γ1 γ2 γ3 γ4 γ5
1 100% 100% 100% 100% 100%
2 94% 99% 99% 100% 100%
3 86% 96% 98% 99% 99%
4 79% 94% 97% 99% 99%
5 73% 92% 96% 98% 99%

Table 7: Efficiency Lower Bounds: J ∈{1, . . . , 5}

6.4 Logit Demand Model

Consider the logit demand functions dm(p) = λmHm(z) where Hm(z) = e
αm−p/(1 + eαm−p)

denotes the probability that a customer will select a product of quality αm at price p over

a no purchase alternative under the logit model. This model arises when the utlity of the
product is αm−p+� and the the no purchase alternative has utility �′ where � and �′ are both
standard Gumbel random variables. It is easy to see that pm(z), the maximizer of rm(p,z) is
the unique root of p = z + 1 + eαm−p and the efficiency function is given by

e(p,pm(z),z) =
p−z

pm(z) −z + (ep−pm(z) − 1)
.

The key to showing the form of e(p,pm(z),z) is that rm(z) = pm(z) − z − 1 = eαm−pm(z) =
Hm(pm(z))/(1−Hm(pm(z)), so the optimal profit per customer is the purchase to no-purchase
odds ratio. The highest efficiency common markup, say ∆ = p− z, for two market segments
with optimal markups ∆i(z) = pi(z) −z,i = 1, 2 is given by

∆ = ln
(

∆2 − ∆1
e−∆1 −e−∆2

)
where ∆ is the root of the equation e(z + ∆,p1(z),z) = e(z + ∆,p2(z),z). This result in the
lower bound

R1(z)

R2(z)
≥ γ1(z) = e(z + ∆,p1(z),z) =

∆(e−∆1 −e−∆2 )
(∆2 − 1)e−∆1 − (∆1 − 1)e−∆2

Finding a closed form solution to γJ(z) is quite involved, but γJ(z) can be computed
numerically by finding breakpoints p1(z) − s0 < s1 < .. . < SJ = pM (z) and prices qj ∈ (sj−1,sj) such that e(qj,sj−1,z) = e(qj,sj,z) and e(qi,si,z) = e(q1,s1,z) for all j = 1, . . . ,J. The following example illustrates the behavior of the heuristic q1 for the case of J = 1 and the performance of γJ(z) for several values of J and z.

Example 7 Suppose that M = 10 with market sizes λm = 220−20m and quality parameters
am = m,m = 1, . . . , 10. Table 8 reports q1, γ1(z) and the actual performance rM(q1,z)/RM (z)
of the heuristic that prices all market segments at q1 where q1 is the root of the equation
e(q1,p1(z),z) = e(q1,pM (z),z). Table 9 provides values of γJ(z) for J = 1, . . . , 5 and z =
2k,k = 0, . . . , 5. In sharp contrast to the linear demand function, where γj(z) decreases with
z, here γj(z) increases with z. The reason for this is that for the logit function the difference
pM (z) − p1(z) is decreasing in z, implying that restricting the price menu works better as z
increases.

z q1(z) γ1(z) rM(q1,z)/RM (z)
$0.00 $3.44 49% 77%
$2.00 $4.78 52% 82%
$4.00 $6.35 62% 85%
$6.00 $7.91 77% 89%
$8.00 $9.46 92% 95%
$10.00 $11.14 99% 99%

Table 8: Prices, Lower Bounds and Actual Performance for Example 7.

z γ1(z) γ2(z) γ3(z) γ4(z) γ5(z)
$0.00 49% 77% 88% 93% 95%
$2.00 52% 80% 90% 94% 96%
$4.00 62% 86% 93% 96% 97%
$6.00 77% 93% 97% 98% 99%
$8.00 92% 98% 99% 99% 100%
$10.00 99% 100% 100% 100% 100%

Table 9: Efficiency Lower Bounds: J ∈{1, . . . , 5}, Example 7

7 Multiple Products

So far we have explored how to price a single product in one or more markets. In this section
we explore the problem of maximizing r(p,z) = (p − z)′d(p) where z ∈

7.1 Linear Demand Function

Let d(p) = a − Bp where a and p are n-dimensional vectors and B is an n × n matrix. We
are interested in finding conditions on a and B that guarantee the existence of a unique,
non-negative, profit maximizing price vector p(z) such that r(z) = r(p(z),z) for all z ≥ 0 such
that d(z) ≥ 0.

Theorem 7 If B is positive definitive, Bij + Bji ≤ 0 for all i 6= j, and a ≥ 0, then

p(z) = S−1(a + B′z) ≥ 0, (21)

where S = B + B′, for all z such that Bz ≤ a. Moreover,

r(z) = (p(z) −z)′d(p(z)) = d(z)′Nd(z) (22)

where N = S−1BS−1.

Proof: Maximizing r(p,z) with respect to p is equivalent to minimizing 1
2
p′(B +B′)p−(a+

B′z)′p + a′z which is quadratic function. A sufficient condition for this function to be convex
is that S = B + B′ is positive definitive. It is known that S is positive definitive, if and only
if B is, see [9]. If S is positive definitive then S is invertible and since S is symmetric, so is
its inverse S−1. Consequently, if B is positive definitive then the maximizer of r(p,z) is given
by (21) as p(z) satisfies the first order necessary and sufficient conditions. We will now argue
that S is a Stieltjes or s-matrix. An s-matrix is a real symmetric, positive definitive matrix

with non-positve off-diagonal elements. We have already argued that S is positive definitive,
and the assumption on B ensures that Sij ≤ 0 for all i 6= j. An important consequence is that
an s-matrix has a non-negative inverse. By adding and subtracting Bz to the expression in
parenthesis on the righthand side of (21) we can write p(z) = z + S−1d(z), where d(z) is the
demand at p = z. This shows that p(z) ≥ 0 whenever z ≥ 0 and d(z) = a−Bz ≥ 0, on account
of S−1 being non-negative. It is also possible to write d(p(z)) = a−Bp(z) = a−B(p(z)±z) =
a−Bz−B(p(z)−z) = (I−BS−1)d(z) and then use the fact that I−BS−1 = B′S−1 to obtain
d(p(z)) = B′S−1d(z). This allow us to write r(z) = (p(z)−z)′d(p(z)) = d(z)′S−1B′S−1d(z) =
d(z)′Nd(z), where N = S−1BS−1.

7.1.1 Random Potential Demand

A natural extension to the linear demand model A − Bp, where the potential demand A is
random with E[A] = a. Are we better off if A is random? The answer is yes if we can observe A
before deciding the price p(z|A) = S−1(A+B′z) to offer. From equation (22) we can write the
optimal profit function as r(z) = (A−Bz)′N(A−Bz) which is a convex function of A given that
N is positive-definitive. By Jensen’s inequality EA(A−Bz)′N(A−Bz) ≥ (a−Bz)′N(a−Bz),
which is the revenue if we price at p(z) = S−1(a + B′z). The implication here is that dynamic
pricing can also be driven by randomness in the potential demand even if the marginal value
of capacity is unchanged.

7.1.2 Competitive Pricing under the Linear Demand Function

Our analysis above assumes a single decision maker trying to maximize (p−z)′d(p). Suppose
now that the there are n competitors, each selecting the price of a single product. Here we
will find the equilibrium price vector p̃(z) such that pi(z) maximizes ri(p,z) = (pi − zi)di(p)
with respect to pi for every i. More precisely, firm i tries to maximize (pi −ci)di(p) assuming
all other prices are fixed. This results in the best response price for firm i as a function of the
other firm’s prices. The first order conditions can be written in matrix form as

a + diag(B)z − (B + diag(B))p = 0.

We will assume that M = B + diag(B) is an m-matrix, so that the inverse of M exists and is
non-negative. In this case we can write the vector of equilibrium prices as

p̃(z) = M−1(a + diag(B)z) = z + M−1d(z). (23)

A little algebra yields
d(p̃(z)) = diag(B)M−1d(z) (24)

and
n∑
i=1

ri(p̃(z),z) = d(z)
′M

′−1diag(B)M−1d(z) = (p̃(z) −z)′diag(B)(p̃(z) −z)), (25)

The monopolist formulas (21) and (22) coincide with the competition formulas (23) and
(25) if diag(B) = B, so there are no cross elasticities. Otherwise, we expect competitive prices
to be lower, demand to be higher and aggregate profits to be lower under competition, with
more surplus going to the customers.

7.2 Log-Linear Demand

The log-linear demand function for multiple products can be written as d(p) = exp(a−Bp).
Unfortunately this demand function is not very amenable to analysis as attempts to maximize
r(p,z) = (p−z)′d(p) leads to unbounded solutions whenever the non-diagonal elements of B
are negative. Indeed, if bij < 0 for some i then there is an incentive to make pj very large which has the negative effect of bringing demand and revenues from product j to near zero, but also the positive effect of artificially increasing demand and revenue for product i. If bij > 0 then
increasing the price of product j decreases the demand of product i which is what we would
expect if the products are complements (e.g., a shirt and a tie) instead of substitutes. This
leaves the case bii = 0 which reduces to independent demands. This analysis shows that the
log-linear demand function has limited applications to independent demands and the pricing
of complementary products.

7.3 The Nested Logit Model

In this section we consider pricing under the Nested Logit (NL) model, which is a popular
generalization of the standard MNL model. Under the NL model, customers make product
selection decisions sequentially: at the upper level, they first select a branch, called a “nest”
that includes multiple similar products; at the lower level, their subsequent selection is within
that chosen nest (see McFadden [12], Carrasco and Ortuzar [1] and Green [3]). Suppose
that the substitutable products constitute n nests and nest i has mi products. Let pi =
(pi1,pi2, . . . ,pimi) be the price vector corresponding to nest i = 1, . . . ,n, and let (p1, . . . ,pn)
be the price vector for all the products in all the nests. Let Qi(p1, . . . ,pn) be the probability
that a customer selects nest i at the upper level; and let qk|i(pi) denote the probability that
product k of nest i is selected at the lower level, given that the customer selects nest i where
pi is the price vector for all the products in nest i. Qi(p1, . . . ,pn) and qk|i(pi) are defined as
follows:

Qi(p1, . . . ,pn) =
eγiIi

1 +
∑n
l=1 e

γlIl
, (26)

qj|i(pi) =
eαij−βijpij∑mi
s=1 e

αis−βispis
, (27)

where αis can be interpreted as the “quality” of product s in nest i, βis ≥ 0 is the product-
specified price sensitivity for that product, Il = log

∑ml
s=1 e

αls−βlspls represents the attractiveness
of nest l, which is the expected value of the maximum of the utilities of all the products in
nest l, and nest coefficient γi can be viewed as the degree of inter-nest heterogeneity. When
0 < γi < 1, products are more similar within nest i than across nests; when γi = 1, products

in nest i have the same degree of similarity as products in other nests, and the NL model
reduces to the standard MNL model; when γi > 1, products are more similar to the ones in
other nests.

The probability that a customer will select product k of nest i, which can also be considered
the market share of that product, is

πij(p1, . . . ,pn) = Qi(p1, . . . ,pn)qj|i(pi). (28)

The monopolist’s problem is to determine the price vectors (p1, . . . ,pn) to maximize the total
expected profit

R(p1, . . . ,pn) =
n∑
i=1

mi∑
j=1

(pij −zij)πij(p1, . . . ,pn), (29)

where zij is the unit cost of product j in nest i. The objective function R(p1, . . . ,pn) fails
to be quasi-concave in prices. When the objective function is rewritten with market shares
as decision variables then the objective function can be shown to be concave if the price
sensitivity parameters βij = βi are product independent in each nest and γi ≤ 1 for all i as
shown in Li and Huh [11]. However, the objective function fails to be concave in the market
shares in the more general case where the price sensitivities are product dependent.

Let pij(z) denote the optimal price for product j in nest i as a function of the vector of unit
costs z. Gallego and Wang [8], show that the optimal price pij(z) adds to the unit cost zij two
components. The first component is the reciprocal of the price sensitivity βij and the second
one is a nest dependent constant θi, so that pij(z) = zij + 1/βij + θi. They also show that the
nest dependent constants θi, i = 1, . . . ,n are linked as explained in the following Theorem.

Theorem 8 If γi ≥ 1 or maxs βismins βis ≤
1

1−γi
, then there exist a unique constant φ such that

θi + (1 −
1

γi
)wi(θi) = φ,

and

pij(zij) = zij +
1

βij
+ θ∗i ,

where wi(θ) =
∑mi
k=1

1
βik
· qk|i(θi) and qk|i(θi) = e

α̃ik−βikθi∑mi
s=1

eα̃is−βisθi
.

Theorem 8 is interesting because a non-concave optimization problem over
∑n
i=1 mi vari-

ables can be reduced, under mild conditions, to a root finding problem over a single variable.
Even in the mild condition γi ≥ 1 or maxs βismins βis ≤

1
1−γi

fails to hold, Gallego and Wang [8] show
that the problem reduces to a single variable maximization problem of a continuous function
over a bounded interval, so the problem can be easily solved numerically. Gallego and Wang
[8] also show that if different firms control different nests the pricing problem under com-
petition is strictly log-supermodular in the nest markup constants, so the equilibrium set is
nonempty with the largest equilibrium preferred by all the firms.

8 Acknowledgments

I acknowledge the feedback from my students and collaborators. In particular, I would like to
recognize the contributions and feedback from Anran Li and Richard Ratliff.

9 Appendix

Proof of Corollary 1 Proof: Clearly y′ ≥ y implies g(y′) ≥ g(y) and r decreasing implies that
r(g(y′)) ≤ r(g(y)), showing that r(g(y)) is decreasing in y. Tho show that r(g(y)) is convex,
notice that from the concavity of h it follows that g(αy + (1−α)y′) ≥ αg(y) + (1−α)g(y′) for
all α ∈ [0, 1]. Then, since r is decreasing, it follows that r(g(αy + (1−α)y′) ≤ r(αg(y) + (1−
α)g(y′)). Finally, from the convexity of r we see that r(αg(y) + (1 − α)g(y′)) ≤ αr(g(y)) +
(1−α)r(g(y′)). Consequently, r(g(αy + (1−α)y′) ≤ αr(g(y)) + (1−α)r(g(y′)), showing that
r(g(y)) is convex.

Since r is convex, by Jensen’s inequality Er(Z) ≥ r(EZ), In particular, Er(g(Y )) ≥
r(Eg(Y )), By the concavity of g and Jensen’s inequality we have Eg(Y ) ≤ g(EY ). Since r is
decreasing, it follows that r(Eg(Y )) ≥ r(g(EY )).

Proof of Lemma 1 Proof: If d(p̄(z)) = d̄(p̄(z)) then r(z) ≤ r̄(z) = r̄(p̄(z),z) = r(p̄(z),z) ≤
r(z) implying that r(z) = r̄(z) and that p(z) = p̄(z) is a finite maximizer of r(p,z). Next,
we will show that d(p̄(z)) < d̄(p̄(z)) leads to a contradiction. To see this, first notice that d(p) ≤ d̄(p) < d̄(p̄(z)) for all p > p̄(z),p ∈ X for otherwise there is a p ∈ X, p > p̄(z)
such that r̄(p,z) > r̄(z) contradicting the optimality of p̄(z). But then, d(p(z)) < d̄(p(z)) = supp≥p(z) d(p) together with d(p) < d̄(p) < d̄(p(z)) for all p > p(z) contradicts the fact that d
is upper-semicontinuous at p(z) since

d(p̄(z)) < d̄(p̄(z)) = lim �↓0

sup
p̄(z)≤p≤p̄(z)+�

d(p) ≤ lim sup
p→p̄(z)

d(p) ≤ d(p̄(z)),

where the last inequality follows from the USC of d(p) at p̄(z).

Proof of Theorem 2. Proof: Since d(p) is USC and the product of non-negative USC
functions is also USC, it follows that r(p,z) and r̄(p,z) are USC in p ∈ [z,∞). If d(p) = 0
for all p ≥ z, then p(z) = z and r(z) = r(z,z) = 0 and there is nothing to prove. Otherwise
there exists a p′ > z such that 0 < d(p′) < ∞ for if not then s̄(z) = ∞. We will show that there is a q > p′ such that r̄(p,z) ≤ r(p′,z) for all p > q. This will allow us to restrict the
optimization of r̄(p,z) to p ∈ [z,q]. Since r̄(p,z) is USC and the supremum is now taken over
a closed and bounded set, the Extreme Value Theorem (EVT) guarantees the existence of a
finite price, say p̄(z) ∈ [z,q] such that r̄(z) = r̄(p̄(z),z) = maxp≥z r̄(p,z). Then, by Lemma 1,
p(z) = p̄(z) is a finite maximizer of r(p,z).

Let � > 0. We claim there exists a p1 > p
′ such that s̄(p) < � for all p > p1. This follows

because s̄(0) − s̄(p) is increasing and converges to s̄(0) as p → ∞. Consequently, there exist
a p1 > p

′ such that s̄(0) − s̄(p) > s̄(0) − � for all p > p1, or equivalently s̄(p) < � for all p > p1. We claim there exist a price q ≥ p1 such that r̄(q,z) < �. If q does not exist, then

r̄(p,z) > � for all p > p1, implying that d̄(p) > �/(p − z) for all p > p1 and consequently
s̄(0) ≥ s̄(p1) = ∞, contradicting the finiteness of s̄(0).

Therefore for all p > q,

r̄(p,z) = (q −z)d̄(p) + (p− q)d̄(p)
≤ (q −z)d̄(q) + s̄(q)
= r̄(q,z) + s̄(q)

≤ 2�.

By taking � ∈ (0, 0.5r(p′,z)) we guarantee that r̄(p,z) ≤ r̄(p′,z) for all p ≥ q, so we can
limit the optimization to the closed and bounded set [0,q], enabling us to call on the EVT to
show the existence of p̄(z) ≤ q such that r̄(z) = r̄(p̄(z),z).

We now turn to the monotonicity of the largest maximizer, say p(z), of r(p,z). Suppose
that z ≤ z′. If p(z) ≤ z′ then there is nothing to show as then p(z) ≤ z′ ≤ p(z′). On the
other hand, if z′ < p(z) we will show that r(p′,z′) < r(p(z),z′) for all prices p′ ∈ [z′,p(z)] so then r(z′) = maxp≥p(z) r(p,z

′) and therefore p(z′) ≥ p(z). To see this notice that r(p′,z) =
(p′ − z)d(p′) ≤ (p(z) − z)d(p(z)), so (p(z) − p′)d(p(z)) ≥ (p′ − z)(d(p′) − d(p(z)) > (p′ −
z′)(d(p′) −d(p(z)), and this implies that r(p′,z′) < r(p(z),z′), showing p(z′) ≥ p(z).

Proof of Corollary 2 Proof: If d(p) is proper and decreasing, and λ = d(0) < ∞, then H(p) = d(p)/λ ∈ [0, 1] is also decreasing and therefore it is the complement of the cumulative distribution function (CCDF) of a non-negative random variable, say W. If H(p) = P(W ≥ p), then H(p) is left continuous with right limits (LCRL). Since a decreasing LCRL function is USC it follows that H(p) and therefore d̄(p) = d(p) is USC. In addition, E[W] < ∞ implies that s̄(0) = s(0) = λE[W] < ∞. As a result the conditions of Theorem 2 are satisfied.

References

[1] Carrasco, J., J. de D. Ortuzar. 2002. Review and assessment of the nested logit model.
Transport Reviews 22(2) 197-218.

[2] Cooper, W. 2002. Asymptotic behavior of an allocation policy forrevenue management.
Oper. Res. 50(4) 720-727.

[3] Greene, W. H. 2007. Econometric Analysis. Pearson Education.

[4] Gallego, G. and M. Queyranne. 1995. Inventory Coordination and Pricing Decisions: Anal-
ysis of a Simple Class of Heuristics. Chapter 6 in Optimization in Industry 3, Mathema-
tical Programming and Modeling Techniques in Practice, Anna Sciomachen, Ed. Wiley.

[5] Gallego, G., G. van Ryzin. 1994. Optimal dynamic pricing of inventories with stochastic
demand over finite horizons. Management Science 40 999–1020.

[6] Gallego, G. and Sahin, O. 2010. Revenue Management with Partially Refundable Fares.
Operations Research 58, 817-833.

[7] Gallego, G. 2010. Dynamic Pricing Chapter. Working paper, Columbia University.

[8] Gallego, G. and R. Wang. 2011. Multi-Product Price Optimization and Competition un-
der the Nested Logit Model withProduct-Differentiated Price Sensitivities. Working paper.
Columbia University.

[9] Johnson, C. R. ”Positive Definite Matrices.” Amer. Math. Monthly 77, 259-264 1970.

[10] Lariviere, M. A., E. L. Porteus. 2001. Selling to the newsvendor: An analysis of price-only
contracts. Manufacturing Service Oper. Management, 3 293-305

[11] Li, H., W. T. Huh. 2011. Pricing multiple products with the multinomial logit and nested
logit models: Concavity and implications. To appear in Manufacturing Service Oper. Man-
agement.

[12] McFadden, D. 1974. Conditional logit analysis of qualitative choice behavior. P. Zarem-
bka, ed., Frontiers inEconometrics. Academic Press, New York, 105142

[13] Maglaras, C. and J. Meissner. 2006. Dynamic Pricing Strategies for Multiproduct Revenue
Management Problems. Manufacturing Service Oper. Management, 8, 2, 135-148.

[14] Png, I. P. L. 1989. Reservations: Customer insurance in the marketing of capacity. Mar-
keting Sci., 8, 248-264.

[15] R. T. Rockafellar, Convex Analysis. Princeton University Press, 1970.

[16] Shugan, S., J. Xie. 2000. Advance pricing of services and other implications of separating
purchase and consumption. J. Service Research. 2, 227239

[17] van den Berg, G. 2007. On the uniquenes of optimal prices set by monopolistic sellers.
Journal of Econometrics, 14, 482-491.

[18] Xie, J., S. Shugan. 2001. Electronic tickets, smart cards, and online prepayments: When
and how to advance sell. Marketing Sci., 20, 219243.

[19] S. Ziya , H. Ayhan, and R. D. Foley, Relationships Among Three Assumptions in Revenue
Management, Operations Research 52, (2004) 804-809.

Dynamic Pricing over Finite Horizons:
Single Resource Case

Guillermo Gallego

Spring

Abstract

In this chapter we consider the problem of dynamically pricing one or more products
that consume a single resource to maximize the expected revenue over a finite horizon.
We assume that there is a sunk investment in capacity that is not-replenishable over
the sales horizon. We formulate continuous and discrete optimal control problems for
price sensitive, Poisson and compound Poisson, demands. We discuss the advantages
and disadvantages of dynamic pricing versus fixed pricing and versus quasi-static pricing
policies. We use Approximate Dynamic Programming with affine functions to obtain
an upper bound on the value function and to develop heuristics that are asymptotically
optimal as the size of the system scales. We then consider pricing with finite price menus
and semi-dynamic pricing strategies.

1 Single Product Dynamic Pricing

In this Chapter we consider the problem of dynamically pricing one or more products that
consume a single resource over a finite horizon with the objective of maximizing the expected
revenue that can be obtained from c units of capacity over a given selling horizon. We will
measure time backwards so that t is the time-to-go until the end of the horizon. At the start
of the selling season the time-to-go is T . We assume that the salvage value at the end of the
horizon is zero to reflect the fact that in many applications the product is perishable. If there
is a positive salvage value then the objective is to maximize the expected revenue in excess
of salvage value, so the zero salvage value can be made without loss of optimality. We will
assume that the capacity provider cannot replenish inventory during the sales horizon. This
assumption holds for hotels and seasonal merchandise including fashion retailing, and to a
large extent to airlines who allocate planes to routes but may, in some cases, swap planes of
different capacities to better align capacity with demand.

We will assume that customers arrive as a time heterogeneous Poisson or compound Poisson
process. Expositionally, it helps to introduce the basic formulation for the Poisson case and
later take care of the changes needed to deal with the compound Poisson case. It is also

helpful to initially work with a single product and then show how that under mild conditions
the same formulation works for multiple products consuming a single resource. The pricing
problem for multiple resources will be dealt in a different Chapter.

Let dt(p) be the Poisson arrival rate of customers willing to buy at price p ∈ <+ at time t. We assume that customers unwilling to buy at price p leave the system. Let rt(p,z) = (p−z)dt(p). We know from the Static Pricing Chapter that if dt(p) is upper semi-continuous, and

∫∞
0 d̄t(p)dp < ∞, where d̄t(p) = supq≥p d(q), then there exist a finite price pt(z), increasing

in z, such that rt(z) = supp≥0 rt(p,z) = maxp≥0 rt(p,z) = rt(pt(z),z). As an example, if
dt(0) < ∞ and dt(p) is decreasing in p, we can write d̄t(p) = dt(p) = λtHt(p) where Ht(p) = dt(p)/dt(0) = P(Wt ≥ p) for some random variable Wt. In this case, the existence of a finite maximizer pt(z) is guaranteed if Ht(p) is left continuous and E[Wt] < ∞.

Let V (t,x) be the maximum expected revenue when the time-to-go is t, and the remaining
inventory is x ≥ 1. We will refer to (t,x) as the state of the system, with (T,c) being the
initial state. Our goal is to find V (T,c) and an optimal dynamic pricing policy that results
in expected revenue V (T,c). Consider a time increment δt small enough to approximate the
probability of a request for one unit at price p by dt(p)δt. Then,

V (t,x) = sup
p
{dt(p)δt[p + V (t− δt,x− 1)] + (1 −dt(p)δt)V (t− δt,x)} + o(δt) (1)

where o(t) is function that goes to zero faster than t. Researchers and practitioners who
prefer to keep the formulation in discrete time typically drop the o(δt) term and work with
the resulting discrete time dynamic program, usually after rescaling time so that δt = 1. If
dt(p) = λtHt(p) is continuous in t then we can rearrange terms and taking the limit as δt goes
to zero we obtain the Hamilton Jacobi Bellman (HJB) partial differential equation:

∂V (t,x)

∂t

= sup

p
rt(p, ∆V (t,x)) = rt(∆V (t,x)), (

)

where ∆V (t,x) = V (t,x) − V (t,x − 1) is the marginal value of the xth unit of capacity for
integer x ≥ 1. The boundary conditions are V (t, 0) = V (0, t) = 0. If dt(p) is piecewise
continuous then the HJB equation (2) holds over each subinterval where dt(p) is continuous
where the boundary condition is modified to be the value function over the remaining time
horizon. If dt(p) satisfies the conditions of Theorem 2 in the Static Pricing Chapter, then an
optimal policy at state (t,x) is given by P(t,x) = pt(∆V (t,x)) where pt(z) is the price that
maximizes rt(p,z).

1.1 Examples with Closed Form Solution

We now present a couple of examples for which we can directly solve the HJB without resorting
to numerically solutions.

Example 1 Suppose that dt(p) = λ exp(−p/θ) for all t ∈ [0,T]. This corresponds to a
time homogeneous arrival rate λ and an a time homogenous exponential willingness to pay

H(p) = P(W ≥ p) = exp(−p/θ) with mean θ. Gallego and van Ryzin [

] have shown that

V (t,x) = θλ∗t + θ ln(Pr(N∗(t) ≤ x)) (3)

= θ ln


 x∑
j=0

(λ∗t)j




where N∗(t) is the time homogeneous Poisson process with rate λ∗ = λ/e. One can verify
that (3) satisfies the HJB equation (2) by taking the partial derivative with respect to t.The
corresponding optimal price policy is given by

P(t,x) = θ + ∆V (t,x) (

)

= θ

(
1 + ln

(
Pr(N∗(t) ≤ x)

Pr(N∗(t) ≤ x− 1)

))
.

To illustrate the solution, suppose that the arrival rate is λ = 2, T =

0 and the willingness
to pay is exponentially distributed with mean θ = 500. If c = 50, then V (50, 50) = $1

, 386.31.
Figure 1 shows the price paths P(t,x),x ∈ {1, . . . , 5} for t ∈ {5,

, . . . , 50}. The figures
confirm that P(t,x) increases with t and decreases with x. Since t is the time-to-go, prices
decrease as time elapses and there is a price increase P(t,x− 1) −P(t,x) when a sale occurs
at state (t,x). Notice also that the price paths are neither convex nor concave in t for fixed x.

Example 2 Suppose that dt(p) = λtp
−b for some b > 1. Then pht(p) = b for all t where

h(p) = −d′t(p)/dt(p) is the hazard rate. Since pht(p) is the absolute elasticity of demand, this
demand function has a constant elasticity of demand. Let Λt =

∫ t
0 λsds be the expected number

of sales at price p = 1, and let kx be a sequence defined by k0 = 0 and for integer x ≥ 1,
kx =

(
b−1
b

)b−1
(kx −kx−1)1−b.

McAfee, and te Velde [8] have shown that

V (t,x) = Λ
1/b
t kx (5)

P(t,x) = Λ
1/b
t k

−1/(b−1)
x . (6)

They also show that for large x, V (t,x) ‘ (Λt)1/bx1−1/b and P(t,x) ‘ (Λt/x)1/b.

To illustrate the solution suppose that λ = 2 and T = 50 and b = 1.5. For c = 30,
V (50, 30) = 65.44. The price paths P(t,x),x ∈ {1, . . . , 5} for t ∈ {5, 10, . . . , 50} are given in
Figure 2.

1.2 Discrete Time Formulation and Numerical Solutions

Except for a few selected cases it is virtually impossible to solve the HJB equation (2) in
closed form. One can, of course, resort to numerical computations. One approach is to use
numerical techniques to locally solve the partial differential equations (2) and to use smooth

Optim al Price Paths

$500

$1,000

$1,500

$2,000

$2,500

0 10

30 40 50

T ime-to-go

P
ri

p(t,1)
p(t,2)
p(t,3)
p(t,4)
p(t,5)

Figure 1: P(t,x) for x = 1, . . . , 5 for Example 1

$-‐

$10

$20

$25

$30

$35

$40

$45

$50

0
5
10
15
20
25
30
35
40
45
50

P(t,1)

P(t,2)

P(t,3)

P(t,4)

P(t,5)

Figure 2: P(t,x) for x = 1, . . . , 5 for Example 2

pasting techniques to put together an approximate solution to (2). A more common approach,
however, is to discretize the dynamic program and then solve it numerically. This is typically
done by rescaling time and setting δt = 1. To see how this works, select a real number a > 1,
so that T ← aT is a large integer and rescale demand so that dt(p) ← 1adt/a(p) < �, for all p and all t ∈ [0,aT]. Now set δt = 1 in equation (1) and drop the term o(δt). Reorganizing terms leads to

V (t,x) = V (t− 1,x) + rt(∆V (t− 1,x)) (

)

with the same boundary conditions. The value of � governs the accuracy of the discrete time
dynamic program (7, and the smaller the � the better the accuracy. We suggest using values
� ≤ 0.1. One can then compute V (t,x) and the corresponding optimal price P(t,x) for all
(t,x) ∈ S = {(t,x) : t ∈ {0, 1, . . . ,T},x ∈ {0, 1, . . . ,c}}. The resulting policy is optimal
up to the small error introduced by the discrete time formulation. Both of these numerical
approaches yield approximate value functions and approximately optimal pricing policies. For
a given time increment δt, the level of accuracy that can be obtained by using smooth pasting
techniques is typically higher than using discrete time dynamic programming as pointed out
in Feng and Gallego [4].

2 Extensions of Basic Model

In this section we present extensions to multiple market segments, to discounted cash flows,
to compound Poisson demands and to situations where multiple products use the same scarce
resource.

2.1 Multiple Market Segments

Suppose there is a single product or resource but there is demand from different market seg-
ments. We will assume that markets are segmented by customer attributes such as age, gender,
occupation, time-of-purchase, geography, or club membership. If markets are segmented by
verifiable customer attributes, then the capacity provider can dynamically change the price
charged to each market. Let dmt(p) be the Poisson arrival rate of customers of market segment
m ∈ M = {1, . . . ,M} willing to purchase at price p. The value function V (t,x) is governed
by the HJB equation:

∂V (t,x)

∂t
=

M∑
m=1

rmt(∆V (t,x)) (8)

with boundary conditions V (t, 0) = V (0,x) = 0, where rmt(z) = supp≥z rmt(p,z), rmt(p,z) =
dmt(p)(p− z). If rm(p,z) admits a unique maximizer pm(z) then the optimal prices at state
(t,x) are Pm(t,x) = pmt(∆V (t,x)),m ∈ M, thus all markets use the same marginal value of
capacity to set prices.

Example 3 Suppose there are M = 4 market clusters with exponential willingness to pay
distributions with respective means $100, $150, $250, $300 and time homogeneous arrival rates
0.25, 0.5, 0.5, 0.25 and T = 100. Solving (8) numerically for c = 50 results in V (100, 50) =

$10, 801.65, ∆V (100, 50) = $31.

3 and initial price vector $

1.93, $

1.93, $281.93, $331.93.
Recall that the marginal value of capacity ∆V (t,x) is increasing in t and decreasing with x so
prices change continuously (going down between sales and up after each sale).

2.2 Discounted Cash Flows

Suppose that cash flows are discounted continuously at rate α, to the beginning of the sales
horizon T. Thus, a dollar received at time to go t ∈ [0,T] is worth e−α(T−t). Following
the same logic used to find the differential equation (2) we obtained for the case without
discounting, we obtain the following HJB differential equation for the value function V (t,x)
with discounting:

∂V (t,x)

∂t
= rt(∆V (t,x)) −αV (t,x). (9)

Not surprisingly, it is difficult to find closed form solutions to this problem and people
often resort to the discrete time approximations of the HJB. We will later look at heuristics
for (9) using Approximate Dynamic Programming (ADP).

2.3 Compound Poisson Demands

The dynamic program (2) is written under the implicit assumption that requests arrive for a
single unit. Suppose instead, that each arrival is for a random number of units, say Z. To
write a formulation we need to make an assumption of what happens if a customer arrives
and requests more units than available, and we also need to make assumptions about how
many units to fulfill at a the posted price just as we did in Chapters 1 and 2. More precisely,
if the posted price is p then it is optimal to accept a request for k ≤ x units at price p if and
only if kp ≥ ∆kV (t,x), where ∆Jk(t,x) = V (t,x) −V (t,x−k). This leads to the following
formulation for the compound Poisson case.

∂V (t,x)

∂t
= max

p≥0
dt(p)

∞∑
k=1

Pr(Z = k)(kp− ∆kV (t,x))+, (10)

with the same boundary conditions where we now set ∆kV (t,x) = ∞ for k > x. Under this
formulation a customer denied a request for k units may be willing to take the largest number
j(k) = max{j < k : jp ≥ ∆Vj(t,x)} thereby changing the distribution of Z. In practice, vendors observe group sales (accepted requests) rather than raw requests for capacity (which may or may not be fulfilled), so it is possible that a group sale for k units results from partially fulfilling a larger request that was denied at the posted price. In essence this means that raw requests may be censored and care must then be taken in estimating the distribution of Z.

2.4 Multiple-Products

Market segmentation is also possible by creating different variants of the product by either
adding restrictions or ancillary services, although care is needed as customers may not nec-
essarily buy the product designed for them. Here we consider the case where the capacity
provider sells multiple products (variants) that consume the same scarce resource. As an
example, in revenue management often the same basic product, e.g., transportation or lodg-
ing, is offered at different prices with different restrictions or amenities. Let dit(p) be the
demand rate for product i at price p = (p1, . . . ,pn) at time t and let dt(p) = (dit(p))

n
i=1 be

the vector of demand rates at p. Notice that the dt(p) allows for price dependencies among
the products. Such is the case, for example, when dt(p) = at − Btp where Bt has non-zero
off diagonal elements and when dt(p) is governed by a logit or a nested logit model. The
Chapter on Static Pricing discusses multi-product demand functions, including the linear and
the nested logit demand functions, for which there is a unique price vector p(z) maximizing
r(p,z) = (p−z)′d(p) where z = (zi)ni=1 is the vector of marginal costs and r(z) = r(p(z),z).

Let e be the vector of ones in

∂V (t,x)
∂t
= sup

p
rt(p, ∆V (t,x)e) = rt(∆V (t,x)e), (

)

with boundary conditions V (0,x) = 0 and V (t, 0) = 0 for x ≥ 0 and t ≥ 0.

3 Factors Affecting Dynamic Pricing

Recall that if dt(p) satisfies the conditions of Theorem 2 of the Static Pricing Chapter then
an solution to the dynamic pricing problem (2) is to price at

P(t,x) = pt(∆V (t,x)). (

)

There are two factors that cause price variations in dynamic pricing:

I Changes in the marginal value of capacity ∆V (t,x) as time elapse and inventory is
depleted.

II Changes in willingness to pay Wt, that lead to changes in the optimal price function
pt(z), 0 ≤ t ≤ T .

Consider first the case where there are no inter-temporal changes in the willingness to pay,
so there is a time invariant optimizer, p(z) = pt(z) for all t ∈ [0,T] and all z ∈N = {0, 1, . . . ,}.
In this case, P(t,x) = p(∆V (t,x)) and all price changes are due only to changes in state
dynamics. We know from the chapter in Static Pricing that p(z) is increasing in z. Gallego
and van Ryzin [6] investigated how ∆V (t,x) changes with the state (t,x). They found that

∆V (t,x) is increasing in t and decreasing in x. This implies that P(t,x) = p(∆V (t,x)) is
increasing in t and decreasing in t. As time elapses in the absence of sales, ∆V (t,x) decreases
causing P(t,x) = p(∆V (t,x)) to decrease, so prices drop between sales. A sale at state (t,x)
causes the state to change to (t,x− 1) and the price to rise from P(t+,x) = p(∆V (t+,x)) to
P(t,x− 1) = p(∆V (t,x− 1)).

The second factor that can cause prices changes is changes in the willingness to pay, i.e.,
when pt(z) varies with t. In this case P(t,x) = pt(∆V (t,x)) is still decreasing in x but it
may be either increasing or decreasing in t. A sufficient condition for P(t,x) to increase in
t is that pt(z) is increasing in t and a sufficient condition for this is that the hazard rate
ht(p) = −d′t(p)/dt(p) is decreasing in t as observed by Zhao and Zheng [10].

3.1 Fixed versus Dynamic Pricing Policies

Fixed prices make sense only if pt(z) is independent of t, as a fixed pricing policy can do
poorly if rt(p,z) has significantly different optimizers, pt(z), over t ∈ [0,T]. So, let us assume
that pt(z) is time invariant. This leaves only Factor I as a source of price variation in dynamic
pricing. Is dynamic pricing still a good idea in this case? As we shall see, there are cases
where dynamic pricing can result in a significant lift in profits relative to a fixed price policy,
but there are also cases where we expected a fixed price policy to be very close to optimal.
Let Nt(p) be a Poisson random variable with parameter Λt(p) =

∫ t
0 λs(p)ds. Notice that Λt(p)

is the expected number of customers that purchase at price p over the sales horizon [0, t]. Let
V1(t,x) = maxp pE min(x,Nt(p)) be the maximum expected profit that can be obtained by
using a fixed pricing policy over the horizon [0, t] starting with x units of inventory. Under mild
conditions there is a finite fixed price maximizer, say p1(t,x), of pE min(x,Nt(p)). Clearly
V1(t,x) ≤ V (t,x) as we can make at least as much money using dynamic pricing. Yet, it is
important to understand when the difference V (t,x) −V1(t,x) is significant enough, relative
to V (t,x), to warrant using a dynamic pricing policy over a fixed pricing policy. The following
examples indicate the performance of fixed pricing policies for the exponential and constant
elasticity demand functions.

Example 4 Consider again the exponential demand function of Example 1. V (50, 50) =
$18, 386.31 is only 0.06% larger than V1(50, 50) = $18, 374.49. In contrast, V (50, 5) =
$10, 625.94 is 5.

% larger than V1(50, 5) = $10, 101, 51. To see the effect of scaling the
state by one order of magnitude consider two systems: One with (t,x) = (200, 1) and the
other with (t,x) = (200, 20). For the first system, dynamic pricing provides a 7.19% lift in
revenues relative to fixed pricing. For the second system the advantage is less than 2%.

Example 5 Consider again the constant elasticity demand model dt(p) = λtp
−b with λt = 2

and b = 1.5 of Example 2. V (50, 30) = $65.44 is 4.8% higher than V1(50, 30) = $62.44. For
c = 10, V (50, 10) = $43.82 is 6.5% larger than V1(50, 10) = 40.98, while V (10, 1) = $5.11 is
7.8% higher than V1(10, 1) = 4.70.

These examples give us some indications of when the benefits of dynamic pricing are or
are not significant relative to a fixed pricing policy in the case that pt(z) is time invariant.

Consider first the situation with ample capacity. Since the revenue rate rt(0) ≥ rt(z) for all
z > 0. Integrating (2), we find it follows that V (t,x) ≤

∫ t
0 rs(0)ds for all x and all t. Now

pricing at p(0) over [0, t] results in expected demand Λt(p(0)). If x >> Λt(p(0)), then we
can price at p(0) over the entire horizon [0, t], with little risk of running of out inventory.
As a result, the revenues V1(t,x) will be close to

∫ t
0 rs(0)ds and dynamic pricing is of little

benefit. You can see this phenomena at work in some of the examples above. For instance, in
Example 4, the demand over the horizon [0, 50] at price p(0) = 500 is 100/e = 36.78 << 50, and the advantage of dynamic of static pricing is only 0.06%. At the other extreme state (t,x) is of severe shortage if x << Λt(p(0)), and here we expect the benefits of dynamic pricing to be significant. This is illustrated by the state (T,c) = (50, 5) and more extremely by the state (T,c) = (200, 1) for the exponential demand in Example 4. On the other hand, we expect the benefits to be small when the system is scaled, e.g., for the state (T,c) = (2000, 50) for the exponential demand distribution. Similar observations hold for the constant elasticity of substation demand model, except that in this case the the benefits of dynamic pricing tend to be more significant than in the case of the exponential demand function.

If one is determine to use a fixed pricing policy, here is how this can be done without
having to numerically find the maximizer of pE min(NT (p),c). Let pc be the market clearing
price, so that ENT (p) = ΛT (p) = c and let pr = p(0) be the price that maximizes the profit
r(p, 0) = pΛT (p). Consider now the fixed price policy:

pf = max(pc,pr). (13)

It turns out that using the fixed pricing policy (13) over the entire selling horizon [0,T] has
good asymptotic properties, so we expect the fixed pricing policy to do well for large systems.
To be more precise, let V b(T,c) be the optimal expected revenue for a system, indexed by
b ≥ 1, with capacity bc and demands bdt(p) 0 ≤ t ≤ T. Also, let V bf (T,c) be the expected
revenue from using price pf . Notice that pc, pr, and consequently pf are all independent of b.

Theorem 1 If NbT (p) is Poisson, then

lim
b→∞

V bf (T,c)

V b(T,c)
= 1.

Theorem 1, is due to Gallego and van Ryzin [6], and actually holds more generally as we
will see in the next section. The Theorem exploits the fact that the coefficient of variation of

NbT (p) is
√
bΛT (p)/bΛT (p) = 1/

√
bΛT (p) → 0 as b →∞. This means that the system behaves

as a deterministic system when b is large. It is easy to verify that pf is the optimal price for
the deterministic system and this essentially explains the asymptotic optimality of the fixed
pricing policy (13). In practice, it does not take a very large b for the asymptotic results to
kick in.

4 Quasi-static Pricing Heuristics

The main disadvantage of fixed price policies is that they do not react to changes in pt(z) over
time. In this section we present a quasi-static pricing heuristic which reacts to changes in pt(z)
over time, but ignores changes in the marginal value of capacity due to random changes in the
state space. More specifically, the quasi-static pricing policies are heuristic pricing policies of
the form Ph(t,x) = pt(z(T,c)), 0 ≤ t ≤ T , that react to changes in pt(z(T,c)) in t but not to
changes in the marginal value ∆V (t,x). As a result, changes in prices only occur when there
are changes in the willingness to pay that result in changes in the optimal price function pt(z).
Typically z(T,c) is chosen to capture the average marginal value of capacity over the horizon,
rather than the instantaneous marginal value of capacity at each state (t,x). For the basic
problem (2), z(T,c) can be obtained by solving the following one-dimensional program, that
arises, as we will see shortly, from approximate dynamic programming.

V̄ (T,c)

= min
z≥0

[
cz +

∫ T
0
rt(z)dt

]

. (

)

From the Static Pricing Chapter, we know that rt(z) is convex in z, so the minimization
problem in (14) is a convex program in a single variable, so if zc is the unconstrained minimizer
of (14), then z(T,c) = max(zc, 0) is an optimal solution to the constrained problem.

The quasi-static heuristic can be made more dynamic by resolving (14) more frequently,
thereby obtaining an updated value of the marginal value of capacity. More precisely, if the
realization of demand deviates significantly from its expected path, then the value of z can be
updated at state (s,y) to z(s,y) where z(s,y) is the minimizer of [yz +

∫s
0 rt(z)dt] subject to

z ≥ 0. Prices are then updated to Ph(t,x) = pt(z(s,y)) for t ∈ [0,s] or until the deterministic
problem (14) is solved again. If the system is updated continuously, we get a feedback policy
Pf (t,x) = pt(z(t,x)), which tends to perform better than the quasi-static policy but also
requires more computations and results in more nervous prices. The reader is referred to
Maglaras and Meissner [9] who show that the feedback policy is asymptotically optimal for
situations where the demand is time invariant over the selling horizon, and to Cooper [3] who
points out that updating z when the inventory and the time-to-go are small can hurt rather
than help performance. That the feedback policy Pf (t,x) is asymptotically optimal and at
the same time it can hurt performance when the state space is small may sound paradoxical
but it is easy to explain. Starting from a large state (T,c), the feedback policy makes many
good decisions along the way, taking advantage of the fact that for large state spaces the
coefficient of variation of the demand to come is very small. However, towards the end of the
horizon, there is a significant variance in demand and it is easy to be in a state where the
feedback policy selects prices that are suboptimal and cause revenue deteriorations that are
small in the aggregate. The warning in [3], however, is valid for systems where the coefficient
of variation of the demand to come is small.

We will justify program (14) and variants to account for compound Poisson and multiple
market segments using approximate dynamic programming in Section 4.1. We will then
show that the quasi-static heuristic is asymptotically optimal, in the sense of Theorem 1, in
Section 4.2.

4.1 Approximate Dynamic Programming

In this section we use approximate dynamic programming (ADP) with affine value functions
to justify program (14) and the bound V̄ (T,c) ≥ V (T,c). We will do this in the context
of a formulation that combines multiple market segments, as in (8) and compound Poisson
demands as in (10) to capture a more general formulation. The HJB with multiple market
segments and compound Poisson demands is given by

∂V (t,x)
∂t
=

∑
m∈M

max
pm≥0

dmt(pm)
∞∑
k=1

Pr(Zm = k)(kpm − ∆kV (t,x))+,

with boundary conditions V (t, 0) = V (0,x) = 0 for t ≥ 0 and x ≥ 0.

It is well known that a discrete time and state dynamic program can be solved using linear
programming by introducing a variable, say F(t,x) for each (t,x) ∈ S. The program for (10)
is given by

V (T,c) = min F(T,c)

s.t.
∂F (t,x)

∂t
≥

∑
m∈M
max
pm≥0
dmt(pm)
∞∑
k=1

Pr(Zm = k)(kpm − ∆kF(t,x))+ ∀ 0 ≤ t ≤ T

F(t,x) ≥ 0 ∀ 0 ≤ t ≤ T, x ∈Zm+ ,

with boundary conditions F(t, 0) = F(0,x) = 0, and where all functions F(t,x) that are
differentiable in t are allowed. At optimality, F(t,x) = V (t,x).

Because we are working with continuous time the resulting linear program has an uncount-
able number of variables and constraints. This may be daunting at first, but once we restrict
the allowable functional forms to be affine functions the formulation will greatly simplify. In
fact, it will simplify to a convex program in a single variable! The class of affine function is
of the form

F(t,x) =
∫ t
0
β(u,x)du + ztx, (15)

where we further restrict β(u,x) = βu for x > 1, β(u, 0) = 0, zt = z for t > 0 and
z0 = 0. These additional restrictions are imposed to satisfy the boundary conditions. Because
we are restricting the class of functions F(t,x), and we are minimizing, the resulting value
function will be an upper bound, say V̄ (T,c), of V (T,c). Since ∂F (t,x)/∂t = βt for x > 0,
and ∆kF(t,x) = kz, for k ≤ x, the program over this class reduces to

V̄ (T,c) = min{
∫ T
0
βtdt + zc} (

)

s.t. βt ≥
∑
m∈M

E[Zm]rmt(z) ∀ 0 ≤ t ≤ T

z,βt ≥ 0 ∀ 0 ≤ t ≤ T

(

)

where rmt(z) = maxpm≥0 rmt(pm,z). Since this is a minimization problem, it follows that
βt =

∑
m∈M E[Zm]rmt(z) ≥ 0.

Substituting βt for all t and integrating, the problem reduces to

V̄ (T,c) = min
z≥0
[
cz +
∑
m∈M

E[Zm]
∫ T
0
rmt(z)dt

]
, (18)

which reduces to (14), when restricted to a single market and Poisson demands. Notice that
the objective function is convex in z as cz is linear and each rmt(z) is convex in z. Let zc be
the unconstrained maximizer of cz +

∑
m∈M E[Zm]

∫T
0 rmt(z)dt. Then z(T,c) = max(zc, 0).

The quasi-static pricing policy uses the prices that solve the approximate dynamic program:

Phm(t,x) = pmt(z(T,c)), m = 1, . . . ,M, ∀ (t,x). (19)

Notice that (19) prescribes a quasi-static pricing policy with a price path pmt(z(T,c)) that
varies with t only if the willingness to pay of market segment m varies with t. The pricing
policy depends on the state (t,x) only through t, as pricing dynamics that adjusts for inventory
fluctuations are suppressed. We will now explore problem (18) further, to gain insights about
the marginal value z(T,c). If rmt(z) is differential with respect to z for all t and all m ∈M,
then the derivative of the optimal revenue function is just the demand at z. More precisely,
r′mt(z) = −dmt(pmt(z)), so the derivative of the objective function is given by

c−
∑
m∈M

E[Zm]
∫ T
0
dmt(pmt(z))dt, (20)

which is increasing in z, since pmt(z) is increasing in p and dmt(p) is decreasing in p. If

c ≥
∑
m∈M

E[Zm]
∫ T
0
dmt(pmt(0))dt

then z(T,c) = 0 as the objective function, being convex, is increasing for all z ≥ 0. This means
that if the capacity is large enough to sustain demand at pmt(0) for al markets over the entire
horizon, then z(T,c) = 0 and the quasi-static pricing heuristic reduces to Phm(t,x) = pmt(0)
for all m = 1, . . . ,M and all t ∈ [0,T]. This solution aims to maximize the revenue rate over
the entire horizon, and will result in revenues near the upper bound

∑
m∈M E[Zm]

∫T
0 rmt(0)dt,

when capacity is ample.

If capacity is scarce, z(T,c) is given by

z(T,c) = sup{z ≥ 0 : c−
∑
m∈M

E[Zm]
∫ T
0
dmt(pmt(z))dt ≤ 0}. (21)

If (20) is continuous then z(T,c) is simply the root of (20), and the market will clear, in
expectation by pricing at pmt(z(T,c)),m ∈M, t ∈ [0,T].

Example 6 Consider the multiple market segment case where we are free to price each market
segment separately. Suppose that dmt(p) = λmte

−p/EWm with time varying arrival rate λmt but
time invariant willingness to pay with mean Wm. Then z(T,c) = 0 is an optimal to (18) if
c ≥

∑
m∈M Λ

∗
mTE[Zm], where Λ

∗
mT =

∫T
0 λmte

−1dt. In this case Phm(t,x) = pmt(0) = EWm,m ∈
M, t ∈ [0,T]. Otherwise, Phm(t,x) = pmt(z) = EWm + z,m ∈ M, t ∈ [0,T], where z is the
root of the equation ∑

m∈M
Λ∗mTE[Zm]e

−z/EWm = c. (22)

The interpretation is that if there is enough capacity to sustain demand at the revenue
rate maximizing prices pmt(0) = EWm,m ∈ M, t ∈ [0,T], then these prices are optimal.
Otherwise, if c is scarce, the prices are all higher by z(T,c), the root of (22), that clears the
market in expectation. Solving the approximate dynamic program for the data of Example 3 we
obtain z(100, 50) = $17.20, and corresponding prices p1(t) = $117.20,p2(t) = $167.20,p3(t) =
$267.20,p4(t) = $317.20 for t ∈ [0, 1]. The upper bound is given by V̄ (100, 50) = $10, 992.66 >
$10, 801.65 = V (100, 50). One can estimate via simulation the expected revenue that results
from using these prices until the end of the sales horizon or until capacity is exhausted. A
simulation with 5,000 repetitions resulted in expected revenues $10,640.55 with a standard
error of $42. Thus using fixed prices results in a loss of approximately 1.5% relative to using
dynamic pricing as in Example 3.

If dt(p) is discontinuous in p there may be no root and the solution is given by (21) and
it is possible to have c <

∑M
m=1 E[Zm]

∫T
0 dmt(pmt(z(T,c)))dt indicating that we are expected

to run out of stock before the end of the horizon. To illustrate this situation consider a single
market segment problem with P(Z1 = 1) = 1 with horizon T = 1 and demand rate dt(p) = 3
if p ≤ 10 and dt(p) = 0 if p > 10. If c ∈{1, 2} then z(T,c) = 10 resulting in c−3T = c−3 < 0. For c ∈{1, 2, 3}, V̄ (1,c) = 10(c− 3) + 30 with the first term representing the loss due to lack of capacity when c < 3.

4.2 Asymptotic Optimality of Quasi-Static Pricing Policies

Just as the fixed pricing policy pf is asymptotically optimal for the case of a single market with
time invariant optimal price functions pt(z), the quasi-static pricing heuristic is asymptotically
optimal for multiple market segments with compound Poisson demands. To make this state-
ment more precise, we let Phm(t,x) = pmt(z(T,c)) be the quasi-static pricing policy for market
segment m ∈ M = {1, . . . ,M}, t ∈ [0,T], and let VQS(T,c) be the total expected revenue
of using these quasi-static prices until the end of the horizon or until capacity is exhausted.
Clearly VQS(T,c) ≤ V (T,c). Consider a sequence of dynamic pricing problems indexed by
b > 1 where the demand rates dbmt(p) = bdmt(p) and capacity c

b = bc. Let V bQS(T,c) and
V b(T,c) denote, respectively, the performance of the quasi-static heuristic and the optimal
dynamic pricing policy for any b ≥ 0.

Theorem 2 Suppose that for every market segment m ∈M, there is an optimal price func-
tion pmt(z) for all t ∈ [0,T], that the demand sizes Zm have finite first and second moments,
and that the market clears, in expectation, at prices Phm(t,x) = pmt(z(T,c)), m ∈M, t ∈ [0,T].
Then,

lim
b→∞

V bQS(T,c)

V b(T,c)
= 1

The proof of this result can be found in the Appendix.

Theorem 2 tells us that for large systems the quasi-static pricing heuristic is almost as good
as the optimal dynamic pricing policy, in the sense that it captures almost all the revenue
relative to the optimal solution. This suggest that ADP can be used effectively for moderately
large systems, but even large systems can benefit from refinements, i.e., by resolving the ADP
with forecast updates at reading periods. More precisely, the idea is to resolve the ADP at
specific reading dates tk taking into account the remaining inventory, say xk at that time,
obtaining new price paths based on the solution z(tk,xk). In fact, z(tk,xk) may be very
close to the the original solution z(T,c) if sales at pmt(z(T,c)) do not vary much from their
expectations over the interval [tk,T]. Resolving at reading dates, however, may be quite useful
if sales differ significantly from their expectations and if there are new forecast updates for
the demand to come. The fact that quasi-static pricing policies ignore state dynamics is
materially detrimental only when capacity or aggregate demand are relatively small. On the
positive side, quasi-static pricing policies do not suffer from the nervousness of full dynamic
pricing policies that react instantaneously to state dynamics, e.g., decreasing prices between
sales and increasing them after each sale. This is an important advantage in practice as quasi-
static policies are easier to implement. In practice, limits are often imposed on allowable
prices, so the optimization is restricted to p ∈ Xt where Xt may be a finite price menu. The
design of the price menu, may be itself considered part of the problem. For example, one
may want to restrict the offered prices to be a subset of size J of all the prices used by the
quasi-static pricing heuristic {pt(z(T,c)) : 0 ≤ t ≤ T}. If J is large enough then most of the
revenue from the quasi-static pricing heuristic can be preserved without introducing too much
nervousness into the price dynamics.

4.3 Fluid Model and Discounted Cash Flows

As mentioned earlier, ADP, is but one of several avenues to obtain (18). Consider the fluid
model where the arrival process is replaced by its expectation. The problem is then to maxi-
mize revenues subject to the capacity constraint. This yields the following formulation.

R(T,c) =

max
p

∑
m∈M

E[Zm]
∫ T
0
pmtdmt(pmt)dt

s.t.
∑
m∈M

E[Zm]
∫ T
0
dmt(pmt)dt ≤ c

pmt ≥ 0.

Dualizing the capacity constraint with a Lagrange multiplier z ≥ 0, results in the problem

R(T,c) = min
z≥0

max
p

[cz +
∑
m∈M

E[Zm]
∫ T
0
rmt(pmt,z)dt]

= min
z≥0
[cz +
∑
m∈M

E[Zm]
∫ T
0
rmt(z)dt]

= V̄ (T,c),

showing that R(T,c) = V̄ (T,c) ≥ V (T,c).

We can adapt the fluid model R(T,c) to the dynamic pricing problem where cash flows
are discounted at rate α ≥ 0 (9), resulting in

R(T,c,α) = max
p

∑
m∈M

E[Zm]
∫ T
0
e−α(T−t)pmtdmt(pmt)dt

s.t.
∑
m∈M
E[Zm]
∫ T
0
dmt(pmt)dt ≤ c
pmt ≥ 0.

Dualizing the capacity constraint at rate z, results in the program

R(T,c,α) = min
z≥0

max
p
[
cz +
∑
m∈M

E[Zm]
∫ T
0
e−α(T−t)rmt(pmt,e

α(T−t)z)dt

]
= min
z≥0
[cz +
∑
m∈M

E[Zm]
∫ T
0
e−α(T−t)rmt(e

α(T−t)z)dt].

If
∑
m∈M E[Zm]

∫T
0 dmt(pmt(0))dt < c, then z = 0 and the optimal price path is pmt(0),m ∈

M and t ∈ [0,T]. Otherwise, z(T,c,α) > 0 is the root of the equation

∑
m∈M

E[Zm]
∫ T
0
dmt(pmt(e

α(T−t)z))dt = c.

Clearly z(T,c,α) < Z(T,c, 0) since without the term eα(T−t) we would overshoot capacity at z(T,c,α). The quasi-static prices are given by

Pm(t,x) = pmt(e
α(T−t)z(T,c,α)) ∀m ∈M, t ∈ [0,T].

Since z(T,c,α) < z(T,c), the prices are lower with discounting for t close to T and higher for

t close to zero. This is done to stimulate demand and improve the present value of the cash
flow.

4.4 Infinitesimal Demands

A second alternative to ADP is to scale the problem so that arrival rates are multiplied by a
constant b >> 0 but requests are only for a fraction 1/b th of a unit. In the limit, as b →∞,
after some algebra, we obtain the following differential equation for the corresponding value
function G(t,x):

G(t,x)

∂t
=
M∑
m=1

E[Zm]rmt

(
∂G(t,x)

∂t

)
. (23)

with boundary G(0,x) = G(t, 0) = 0 for all x ≥ 0 and t ≥ 0. It can be shown that Ḡ(T,c) =
cz(T,c) +

∑M
m=1 E[Zm]

∫T
0 rmt(z(T,c)) satisfies the differential equation (23) at state (T,c), so

Ḡ(T,c) = V̄ (T,c).

5 Other Pricing Heuristic and Restrictions

So far we have allowed prices to vary continuously over time and have presented the fixed
price and the quasi-static heuristics. In this section we explore solving exactly formulations of
the dynamic pricing problem that explicitly limit the price menu or the points in time when
price changes are allowed.

5.1 Finite Price Menus

Consider formulation (2) with the maximization restricted to p ∈ P = {p0,p1, . . . ,pn} with
p0 > p1 > .. . > pn and p0, possibly infinity, such that dt(p

0) = 0 for all t. The restriction
to a finite price menu can be used whether or not pt(z) is time invariant, but in the time
invariant case, the optimal policy has a clear structure, because P(t,x) = p(∆V (t,x)) is
increasing in t and decreasing in x. This implies that there exist non-negative thresholds,
0 = τn(x) ≤ τn−1(x) ≤ . . . ≤ τ1(x) ≤ τ0(x) = ∞ such that it is optimal to offer price pj
at state (t,x) whenever t ∈ [τj(x),τj−1(x)). As we run out of time without a sale, prices
decrease as the time-to-go reaches the thresholds. Moreover, since P(t,x) is decreasing in x,
the thresholds τj(x) must be increasing in x for each j.

5.2 Semi-Dynamic Pricing

The capacity provider may decide to use a policy that lies between the two extremes of
dynamic and fixed pricing. To be more precise, suppose that prices are allowed to be changed
only at reading dates 0 = t0 < t1 < .. . < tm = T . One can then write a discrete time dynamic program where Vj(x) = V (tj,x) is the optimal expected revenue from reading day j until the

end of the horizon when the remaining inventory is x. Let Nj(p) be a Poisson random variable

with mean Dj(p) =
∫ tj
tj−1 ds(p)ds, which is the expected demand at price p between reading

dates tj and tj−1. The dynamic program is

Vj(x) = max
p∈Pt
{pE min(Nj(p),x) + Vj−1((x−Nj(p))+}, (24)

with boundary conditions V0(x) = Vj(0) = 0. Here Pt can be a time varying finite or infinite
price menu. Clearly Vm(c) ≤ V (T,c), but if m is even modestly large and the price menu
is rich enough we should expect Vm(c) to be fairly close to V (T,c), and of course at least as
close as using the best fixed pricing policy which would correspond to m = 1, i.e., a single
reading date at time t1 = T. In practice, one can use static pricing (m = 1) whenever
the benefits of dynamic pricing are small and model (24) with a few reading dates when the
benefits of dynamic pricing are large. This has the advantage of capturing most of the benefits
of dynamic pricing without its excessive nervousness. To do this, is important to select the
reading dates tj to coincide with significant changes in the willingness to pay. In other words,
the reading dates should be selected so that pt(z) is more or less constant over t ∈ (tj−1, tj].
Notice that this dynamic pricing model with a finite price menu closely resembles capacity
allocation models with finite fares, a topic covered Chapter 1.

5.3 Restriction to Monotone Pricing

All of the formulations so far allow prices to vary dynamically and this pricing flexibility helps
maximize expected revenues as long as customers are not strategic. If prices exhibit strong
fluctuations then some customers may decide to wait for better prices and if a significant
number of them act this way the strategy of allowing price flexibility may backfire resulting
in losses rather than gains. To avoid this, capacity providers may limit price flexibility. An
extreme case would be to insist on monotone prices. Such formulations are a little more
difficult to solve because the solution must implicitly price the cost of making irreversible
decisions, i.e, price increases. See Feng and Gallego [5] for such formulations within a limited
price menu. We can generalize the formulation (10) by expanding the state space to (t,x,pt)
where pt is the current price vector and by imposing lower bound pricing constraints, say
p ≥ g(pt) or p ≤ g(pt) for some reasonable function g, e.g., g(p) = (1 + d)p to ensure that
price paths are (nearly) monotone.

6 Appendix

Proof of Theorem 2. For ease of exposition we will write the proof of Theorem 2 for the case
of a single market with Poisson, rather than compound Poisson demands. However, the proof
holds as stated.

Proof: Clearly V bQS(T,c) ≤ V b(T,c) ≤ V
b
(T,c) = cz(T,c)+

∫T
0 rt(z(T,c))dt. The idea of the

proof is to show that the difference V
b
(T,c)−V bQS(T,c) becomes negligible relative to V bQS(T,c).

First notice that scaling arrival rates and demands does not change z(T,c) or the quasi-static

pricing policy P(t,x) = pt(Z(T,c)). To evaluate V
b
QS(T,c) let t = T − s be the time-to-go

for each s ∈ [0,T]. The quasi-static pricing policy at time s is qs = PT−s(z(T,c)). The
demand intensity at s is γs = dT−s(PT−s(z(T,c)). Let Ns be a Poisson process with intensity
Γs =

∫s
0 γsds and let τc be the first time the process reaches c, i.e., τc = inf{s ≥ 0 : Ns = c}.

The quasi-static policy earns revenues at rate qsdNs until time min(T,τc), so

VSQ(T,c) = E[
∫ min(T,τc)
0

qsdNs] = E[
∫ min(T,τc)
0

qsγsds]

where the equality follows from Watanabe’s characterization of Poisson processes, see Bremaud
[2]. Let Θs =

∫s
0 θudu, where θu = quγu, also let θ̄ = max0≤u≤T θu. The maximum exists as

θu = rT−u(z(T,c)) + γuz(T,c) < ∞ is bounded and continuous in u and bounded continuous functions have a bounded maximum over compact sets. It follows that

VSQ(T,c) = ΘT −E[ΘT − Θmin(T,τc)] ≥ ΘT − θ̄E(T − τc)
+.

On the other hand, we can write

V̄ (T,c) = ΘT − (ΓT − c)z(T,c).

The result follows since the gap between θ̄E(T −τc)+−(ΓT −c)z(T,c) grows as the square
root of b while the lower bound grows linearly with b.

References

[1] Besbes, O. and Zeevi, A. 2009. Dynamic Pricing without Knowing the Demand Function:
Risk Bounds and Near Optimal Algorithms. Operations Research, forthcoming.

[2] Bremaud, P. 1980. Point Processes and Queues. Martingale Dynamics. Springer Verlag,
New York Heidelberg Berlin.

[3] Cooper, W. 2002. Asymptotic behavior of an allocation policy forrevenue management.
Oper. Res. 50(4) 720-727.

[4] Feng Y. and G. Gallego (1995) Optimal Starting Times for End-of-Season Sales and Op-
timal Stopping Times for Promotional Fares. Management Science, 1371-1391.

[5] Feng Y. and G. Gallego (2000) Perishable Asset Revenue Management with Markovian
Time Dependent Demand Intensities. Management Science, 941-956.

[6] Gallego, G., G. van Ryzin. 1994. Optimal dynamic pricing of inventories with stochastic
demand over finite horizons. Management Science 40 999–1020.

[7] Lim, A. and G. Shanthikumar. 2006. Relative entropy, exponential utility, and robust
dynamic pricing. Operations Research, forthcoming.

[8] McAffee, P. R., V t. Velde. 2008. Dynamic Pricing with Constant Demand Elasticity.
Working paper, Caltech.

[9] Maglaras, C. and J. Meissner. 2006. Dynamic Pricing Strategies for Multiproduct Revenue
Management Problems. Manufacturing Service Oper. Management, 8, 2, 135-148.

[10] Zhao, W. and Zheng, Y-S. Dynamic Pricing for Perishable Assets with Nonhomogeneous
Demand. Management Science, 46, 375-388.

Turn in your highest-quality paper
Get a qualified writer to help you with

“ Question 1,2,3,4,5 ”

Get high-quality paper

NEW! AI matching with writer

Still stressed with your coursework?

Get quality coursework help from an expert!

Order now