Transcript No Slide Title

Expanding the Scope of Dynamic Pricing
Yuri Levin, Tanya Levin, Jeff McGill, Mikhail Nediak
Queen’s University, School of Business
Kingston, Ontario, Canada
Sixth Annual INFORMS Revenue Management
and Pricing Section Conference
Columbia University
June 6, 2006
Introduction

traditional RM and Dynamic Pricing
– risk neutral
– service sector focus
– business-to-consumer

expanded scope
–
–
–
–
–
retail sector
risk-sensitive managers
strategic customers
business-to-business
volatile customer behavior
2
Outline
retail sector
price guarantees
risk-sensitive
managers
incorporation of lossprobability in dynamic pricing
strategic
customers
strategic customers in
monopoly and oligopoly
volatile
customer
behavior
online learning of
customer attributes
3
Price Guarantees

very common in retail sector
– internal or external
– forced by ‘free returns’ policies
– typically free of charge

potential benefits
– customer: reduced risk of opportunity loss
– company: encourage immediate purchase,
improve customer satisfaction

surprisingly little prior analytical work
4
Price Guarantees



Model Elements
finite time horizon: [0, T]
policy variables
– dynamic prices:
p(t)
– guarantee strike price: k(t)
– fee for guarantee:
f(t)
demand processes
– Poisson inquiry process: N(t), rate 
– probability of item purchase: u[p(t), k(t), f(t), t]
– item purchase process: Np(t), rate u[·]
– probability buy guarantee: v[p(t), k(t), f(t), t]
– guarantee purchase process: Nf(t)
5
Price Guarantees
Objective Function
Maximize expected revenues due to item sales
plus revenue due to sales of price guarantees
minus losses due to compensation payments
6
Price Guarantees
Approach

motivated by continuous time formulation

discrete-time analogue

nonlinear programming approach to solution

structural properties of the model

lower bound heuristic

numerical experiments with discrete model
– exact for small problems – NLP
– lower bound heuristic for larger problems via
dynamic programming
7
Price Guarantees
Main Results

existence of optimal policy

necessary optimality conditions via NLP
formulation

intuitive monotonicity results for value function

sufficient conditions for fixed policy with price
guarantees to dominate dynamic policy without
price guarantees

in case of free price guarantee the demand is more
sensitive to changes in price than in strike price

useful lower bound heuristic
8
Example - Heuristic
Price Guarantees
Policies vs. Time Before First Sale
1.4
Price
1.2
Strike price
Fee
Policy variables
1
0.8
0.6
0.4
0.2
0
0
1
2
3
4
5
6
7
8
Time
9
10
11
12
13
14
9
Price Guarantees
Example - Heuristic (2)
States with Nontrivial Expected Guarantee Payments
2
Remaining inventory
4
6
8
10
12
14
16
18
20
0
5
10
15
20
25
30
35
40
45
Time - t
10
Risk in Dynamic Pricing

traditional RM models are risk-neutral
– objective to maximize expected revenues at end
of disposal period
– appropriate for transportation and
accommodation services
– pricing strategies are implemented over
hundreds or thousands of problem instances

not the case for other applications
– major event management
– ‘big-ticket’ item clearance seasons
11
Risk
Model Elements

finite time horizon: [T, 0]

initial inventory:
YT

dynamic prices:
p(t)

demand processes
– nonhomogeneous Poisson demand process:
• N′(t), rate (t, p)
– sales process:
• N(t) = min{ N′(t), YT }
12
Risk
Model Elements (2)

revenue process

risk-neutral objective

loss-probability risk
constraint

z is desired minimum level of revenues and 0
is the minimum acceptable probability with
which we want this level
13
Risk
Model Elements (3)

If 0 is varied, problem has different optimal
solutions -- efficient frontier in the plane of optimal

Alternative way: solve
for range of values of

penalty parameter C -- cost of not meeting the
revenue target z
14
Risk
Approach

state variable (vector): [ Y(t), R(t) ]

discrete state space

[ Y(t), R(t) ] intensity-controlled, nonhomogeneous,
finite-state, continuous-time Markov Chain

introduce randomized policies to convert to form of
deterministic optimal control problem

particularly convenient form: bilinear control
problem

feasible for problems of realistic size
– e.g. 250 items, 25,000 time periods
15
Risk
Main Results

existence of optimal policy

necessary optimality conditions via optimal control

intuitive monotonicity results for value function

interesting phenomena: the price can drop
following a sale

highly efficient computation produces solution for
all values of initial inventory and desired level of
revenue simultaneously

generalizations include:
– salvage and disposal costs
– extended risk-neutral horizon
– moving revenue target
16
Risk
Example: Risk/Return Frontiers
z = target revenue
17
Strategic Consumers

traditional dynamic pricing models
– consumer behavior myopic

strategic consumers can increase utility by timing
their purchase decisions to periods with lower
price

consumers aided by third party brokers

company may increase its revenues by modelling
the strategic nature of consumers explicitly
18
Strategic Consumers
Consumer Population

most dynamic pricing models assume infinite
customers or customers sampled with replacement

modeling strategic customers requires considering
customers individually

in reality:
– populations are finite
– durable items or ticket sales, customers
sampled without replacement

possible competition between customers when
product supplies limited
19
Strategic Consumers
Model Elements

company(s) offer a perishable product in a finite
number of consecutive time periods

customer population is stochastically
homogeneous
– random valuations exchangeable

valuation distribution known to company(s) and all
customers but realizations are not

price may change with time, inventory level, and
customers’ presence in the market
20
Strategic Consumers
Model Elements (2)

customers fully rational - can anticipate pricing
policies of company(s)

customer utility increasing in (valuation – price)
surplus

utility of acquiring product in future discounted by
a factor β per time step
0  β  1 is strategicity parameter
β = 0 – myopic customers
β = 1 – fully strategic customers
21
Strategic Consumers
Model Elements (3)

in each time period
– company(s) announce price
– customers observe individual budgets
– customers express eagerness to purchase

successful purchases resolved probabilistically
– one purchase per time period
– probability proportional to eagerness

each customer maximizes expected present value
of utility of acquiring product

company(s) choose pricing policy to maximize
expected future revenues in each planning period
22
Strategic Consumers
Oligopoly Elements

competition among companies

consumer choice behavior: choosing between
different brands
– two possible choice rules
– specific choice
customers have to allocate eagerness towards a
specific product
– multiple choice
customers can be equally eager to purchase
several of the available products
• i.e. any with positive surplus
23
Strategic Consumers
Approach

stochastic dynamic games

seek Markov-perfect equilibria

dynamic programming formulation for both
customers and company(s)
24
Strategic Consumers

Oligopoly Case
stochastic dynamic game with asymmetric
information and hierarchical equilibrium
structure
25
Strategic Consumers
Results: Monopoly

unique equilibrium solution

optimality condition for consumers -- probability of
purchase:

monotonicity results: full supply case
– initial number of customers  initial inventory
– β general
• expected future revenues linear in remaining
inventory
• price constant in remaining inventory
– β=1 – price is decreasing in time
26
Strategic Consumers
Results: Monopoly (2)

general supply case, with β = 0
– revenues concave in remaining inventory
– price decreasing in time
– price decreasing in remaining inventory

β = 0 (myopic) case interesting since finite
population dynamic pricing model not previously
reported

computational procedure is tractable and efficient
for realistic-size problems
27
Strategic Consumers
Results: Oligopoly

existence of unique Markov-perfect equilibrium
– ‘multiple choice’ consumer case
– logconcave valuation distribution

similar optimal decision rule for customers

fewer provable structural results relative to
monopoly case

also computationally feasible for realistic problem
sizes
28
Strategic Consumers
Example (Monopoly)
Price vs. Time
Before First Sale
29
Strategic Consumers
Example (Oligopoly)
each company has supply of 20 units
30
Online Learning for Dynamic Pricing

dynamic pricing requires model of consumer
behavior (usually parametric)
– cycles of parameter estimation and optimization

desirable to have a learning method
– integrates periodic updates of parameter values
into pricing policy selection procedure
– should be independent of particular functional
form of demand model

two lines of research
– demand learning with strategic customers
– myopic consumers with general valuation
distribution
31
Strategic Online Learning
Model Elements

consumer game: similar to set up of monopoly
strategic consumer model except…

customers cannot compute company’s price policy
– ‘anticipated price’ Markov process

customer attributes to be estimated
– general valuation distribution
– expected (valuation – price) ‘surplus’
•
proxy for β and future purchase behavior
32
Strategic Online Learning
Approach

based on ‘aggregating algorithm’ of Vovk(1999)
– very general game-theoretic methodology for
‘machine learning’
– players: nature, advisor pool, decision-maker

in present setting, resembles Bayesian estimation
– start with a prior distribution for all parameters
– observe sales and price histories
– use posterior parameter distribution to estimate
the expected customer response, probabilities of
sample paths, and expected revenues

learning unfolds over several selling horizons
33
Strategic Online Learning
Approach (2)

periodic updates during each horizon

approximate valuation distribution by discrete
sample update
– accept-reject method with bootstrap resampling
– similar to selection of the fittest in genetic
algorithms with likelihood as a fitness function

avoid degeneration to a few discrete values with
perturbation by random walk (random mutation of
solutions)
34
Strategic Online Learning
Approach (3)

restrict to reasonable policy class, e.g.
– piecewise-constant in time
– or, threshold-based in inventory, linear in time

derivative-free simulation-based numerical method
for optimizing a policy in its class up to the end of
the horizon

simulation by sampling parameter vectors from the
posterior followed by simulation of sales paths
35
Strategic Online Learning
Main Results

existence and uniqueness of customer game
equilibrium

monotonicity results for equilibrium customer
surplus

customer response model

strategicity cannot be ignored in online learning

online learning feasible for
– strategic customers
– myopic customers with general valuation
distribution
36
Strategic Online Learning
Example
37
Conclusions

controlled price guarantees can protect consumer
goodwill and increase revenues
– special cases particularly accessible
– numerical approximations required

risk in dynamic pricing can be incorporated in
loss-probability form

possible to account for strategicity in both
monopoly and oligopoly settings

online learning is feasible

more work required!
38