1 Introduction

Dynamic pricing is mainly concerned with how a firm could maximize its revenue by charging the right prices over a given time horizon, during which demand arrives in a random and yet price-dependent fashion. We focus on one of the two irreversible pricing cases where the concerned firm is in the markup mode, so that it continuously charges a sequence of progressively increasing prices. Airlines and hotels often practice markup to sell tickets to exploit the difference in cost sensitivity between leisure and business travelers. Obviously, a firm may also exercise markdown, or when there is no predetermined direction in which prices can go, reversible pricing. Reversible and irreversible cases are known to require different treatments. Surprisingly, we find that the two seemingly symmetric irreversible cases of markup and markdown should be handled quite differently as well.

Our assumption of Poisson arrival reflects that the aggregate demand arises from independent purchase decisions made by a myriad of buyers. The influence of the firm’s pricing decisions over buyers’ behaviors is captured by the arrival rate’s dependence on the price charged by the firm. Demand arrival may also fluctuate over time. This time-variability may be caused by seasonality of the product being sold, the fact that the concerned product is newly introduced or is gradually phasing out of the market, or other factors such as predictable changes over time of competitive firms’ aggregate behavior.

In this study, we let demand arrival be governed by the following product form: there is an overarching time-dependent term that spells out the demand’s oscillation over time, and the actual demand arrival rate is proportional to both this term and another price-dependent factor. Under this demand pattern, we establish the optimality of a threshold policy for both markup and markdown cases, albeit with the first being our primary focus. The policy is representable by price-switching time points \(\tau ^k_n\) that depend on both current price choices k and inventory levels n, with higher inventory levels corresponding to earlier times.

To better understand our contribution, let us first briefly recount earlier research on dynamic pricing. Gallego and van Ryzin (1994) started treating dynamic pricing from the optimal control perspective. They examined the problem of dynamically pricing inventories with stationary, stochastic demands, and showed the optimality of a monotone pricing policy as well as the asymptotic optimality of fixed-price heuristics. Dealing with a similar model involving a finite number of price choices, Feng and Xiao (2000a) provided justifications to the earlier assumption that the revenue-generation rate be increasing and concave in the demand arrival rate. They derived the optimality of a comparable monotone pricing policy and offered a procedure for computing this policy.

When demand is time-varying, Zhao and Zheng (2000) identified the decline over time of customers’ willingness to pay premiums as a sufficient condition for the monotonicity of the optimal pricing policy. This result generalizes the claim made by Bitran and Mondschein (1997), that a monotone policy would be optimal when the ratio of arrival rates at any two given prices remains the same over time. For a multi-product/resource version of the problem, Gallego and van Ryzin (1997) gave asymptotically optimal heuristics that are based on the solution to the problem’s deterministic control counterpart.

Various attempts have been made to generalize dynamic pricing to the case involving ambiguity, where the demand-price relationship is initially unknown to the firm; see, e.g., Aviv and Pazgal (2005), Araman and Caldentey (2009), Besbes and Zeevi (2009), Farias and van Roy (2010), Broder and Rusmevichientong (2012) and Wang et al. (2014). Recently, Xia et al. (2019) also considered the case involving a randomly evolving economic indicator. To the best of our knowledge, most of the recent progresses were made on the reversible pricing case where the firm is free to revisit any previously used prices.

In comparison, the irreversible case relevant to certain pricing practices of airlines and hotels has not received as much attention. Feng and Gallego (1995) initiated irreversible pricing control with their study of a problem involving two price choices and an arrival pattern that is dependent on price only. For this problem, they showed the optimality of a threshold-like policy. Feng and Xiao (2000b) generalized the above result to a case with multiple price switches in the same direction. Feng and Gallego (2000) moved on to the more general problem where both paths of prices and arrival rates can be time-varying, and demand may be dependent on sales-to-date. For this case, however, optimal policies were not shown to necessarily come from the threshold-like family.

The current work remedies the markup portion of Feng and Xiao (2000b) and show that it is fundamentally different from the seemingly symmetric case of markdown. For both cases, Feng and Xiao (2000b) arrived to the same conclusion on the threshold-like policy shape when demand is stationary. Our derivation sheds more light on the distinction between the markup and markdown cases. As a property, complementarity between price flexibility and inventory is not possessed by the markdown case; yet, it is essential to the derivation for the markup case. The property expresses the increased value of an additional unit of inventory when the firm possesses yet more flexibility to raise its prices. Feng and Xiao’s (2000b) treatment of the markup case seems to have missed this point; see in Sect. 5 our counter example to the markup portion of their Lemma 1.

Methodologically, we let the solution of an ordinary differential equation (ODE) permeate through our derivation. Such extensive use of ODE in dynamic pricing has not been known to us. We also introduce a mixed use of mathematical induction and sample-path arguments to facilitate the derivation of the complementarity property. Besides, we show in general that \(\tau ^k_n\) is not decreasing in k for the two irreversible pricing cases, though for the reversible pricing case this trend known as time monotonicity is in existence (Zhao and Zheng 2000). Our development also leads to an efficient policy-computing algorithm.

The rest of the paper is organized as follows. In Sect. 2, we provide the markup problem’s formulation. A procedure for constructing value functions and threshold levels is proposed in Sect. 3, while the optimality of the thus constructed threshold policy is proved in Sect. 4. We introduce an algorithm for computing an optimal policy and discuss merits of our current approach in Sect. 5. Computational studies are presented in Sect. 6 and the paper is concluded in Sect. 7. We have relegated proofs to “Appendix A” and details about the markdown case to “Appendix B”, and minor algorithms to “Appendix C”.

2 Formulation

Over some time interval [0, T], we suppose the concerned firm is to sell some N items of a product; and, it is allowed to consecutively charge a sequence of some \(K+1\) prices \({\bar{p}}^0,\bar{p}^1,\ldots ,{\bar{p}}^K\), where \(0<{\bar{p}}^0<{\bar{p}}^1<\cdots <{\bar{p}}^K\). Demand comes to the firm as a time-varying Poisson process whose instantaneous rate \(\lambda ^k(t)\) depends on both the current price \({\bar{p}}^k\) charged by the firm and the overall market condition at time t. We also suppose that the demand rate function is of the product form. There are strictly positive constants \({{\bar{\alpha }}}^0,{\bar{\alpha }}^1,\ldots ,{\bar{\alpha }}^K\) and strictly positive and continuous function \(\beta (\cdot )\) on [0, T], so that

$$\begin{aligned} \lambda ^k(t)={\bar{\alpha }}^k\cdot \beta (t),\quad \forall k=0,1,\ldots ,K,\;t\in [0,T]. \end{aligned}$$

The time multiplier \(\beta (\cdot )\) may be a consequence of seasonality of the product being sold, the fact that the concerned product is newly introduced or is gradually phasing out of the market, or other factors such as predictable changes over time of competitive firms’ aggregate behavior. The price multiplier \({\bar{\alpha }}^k\) indicates the relative attractiveness of the product under price \({\bar{p}}^k\). We assume

(S1) for the revenue generation rates,

$$\begin{aligned} {\bar{p}}^0{\bar{\alpha }}^0>{\bar{p}}^1{\bar{\alpha }}^1>\cdots >{\bar{p}}^K{\bar{\alpha }}^K. \end{aligned}$$

(S1) is known as the “maximum increasing concave envelope” property. It lets lower prices be associated with higher revenue generation rates. A lower price would not need to be considered were it not to generate revenue faster than a higher price. With this assumption at hand, we no longer have to separately require

(S1’) for the demand arrival rates,

$$\begin{aligned} {\bar{\alpha }}^0>{\bar{\alpha }}^1>\cdots >{\bar{\alpha }}^K. \end{aligned}$$

Of course, (S1’) is universally true because demand is in general a decreasing function of price. For our current case, (S1) happens to be needed in the first place. We may take the view that potential buyers arrive at the rate of \({\bar{\alpha }}^0\cdot \beta (t)\) at time t, and among all those that arrive, only a \({\bar{\alpha }}^k/{\bar{\alpha }}^0\) portion will purchase the product when the price being charged is \({\bar{p}}^k\).

We denote a threshold policy by \(\tau \equiv (\tau ^k_n\mid k=1,2,\ldots ,K,\;n=1,2,\ldots ,N)\in (\Delta _N)^K\), where \(\Delta _N\subset [0,T]^N\) is defined through

$$\begin{aligned} \Delta _N\equiv \{(\tau _1,\tau _2,\ldots ,\tau _N)\mid 0\le \tau _N\le \tau _{N-1}\le \cdots \tau _1\le T\}. \end{aligned}$$
(1)

For the current markup case, adopting such a policy entails that, the firm should raise its price from \({\bar{p}}^{k-1}\) to \({\bar{p}}^k\) when its inventory level drops to n ahead of the threshold level \(\tau ^k_n\). \(\tau \in (\Delta _N)^K\) with \(\Delta _N\) defined through (1) means that \(0\le \tau ^k_N\le \tau ^k_{N-1}\le \cdots \le \tau ^k_1\le T\) for each \(k=1,2,\ldots ,K\). Such a policy indicates that the higher the firm’s inventory level is, the earlier it should exercise price switching. In Sects. 3 and 4 , we show such a policy is indeed optimal for the markup case and more than that, the extra k-monotonicity property that \(\tau ^k_n\) be decreasing in k could also be had.

We let all random elements be defined on a probability space with a filtration. Also, denote by \({{\mathcal {T}}}(t)\) the set of stopping times that is later than t. Each price choice k is associated with a point process \((N^k(t)\mid t\in [0,T])\) that is with intensity process \(({\bar{\alpha }}^k\cdot \beta (t)\mid t\in [0,T])\) and adapted to the given filtration. For any \(s<t\) and \(n=0,1,2,\ldots \),

$$\begin{aligned} {\mathbb {P}}\left[ N^k(t)-N^k(s)=n\right] =\exp \left( -{\bar{\alpha }}^k\cdot {{\hat{\beta }}}(s,t)\right) \cdot \frac{\left( {\bar{\alpha }}^k\cdot {{\hat{\beta }}}(s,t)\right) ^n}{n!}. \end{aligned}$$
(2)

In (2), we have taken the conventions \(0^0=1\) and \({{\hat{\beta }}}(s,t)\equiv \int _s^t\beta (u)\cdot du\).

Let \(v^k_n(t)\) be the maximum revenue the firm can make in time interval [t, T] when it starts the interval with price \({\bar{p}}^k\) and inventory level n. As the highest price \({\bar{p}}^K\) is the last price for the firm to charge, we have

$$\begin{aligned} v^K_n(t)={\bar{p}}^K\cdot {\mathbb {E}}\left[ (N^K(T)-N^K(t))\wedge n\right] . \end{aligned}$$
(3)

For \(k=K-1,K-2,\ldots ,0\), the firm still has the chance to increase its price to \({\bar{p}}^{k+1}\) when it is currently charging \({\bar{p}}^k\). Hence,

$$\begin{aligned} v^k_n(t)=\sup _{\tau \in {{\mathcal {T}}}(t)}{\mathbb {E}}\left[ {\bar{p}}^k\cdot \left\{ (N^k(\tau )-N^k(t))\wedge n\right\} +v^{k+1}_{(n-N^k(\tau )+N^k(t))^+}(\tau )\right] . \end{aligned}$$
(4)

Basically, the firm is to choose the time \(\tau \), dependent on all historical observations, to switch to the next higher price \({\bar{p}}^{k+1}\) from its current \({\bar{p}}^k\). Inside the bracket on the right-hand side of (4), the first term is the firm’s gain from time t to \(\tau \) under the price \({\bar{p}}^k\) and the second term is its gain from \(\tau \) to T while starting at \(\tau \) with price \({\bar{p}}^{k+1}\).

3 A constructive procedure

Our analysis relies on an ordinary differential equation (ODE) and its known solution. Given continuous functions \(a(\cdot )\) and \(b(\cdot )\) defined on the interval [0, t], consider the following:

$$\begin{aligned} d_s f(s)=b(s)-a(s)\cdot f(s),{\quad }\forall s\in (0,t). \end{aligned}$$
(5)

This ODE has a unique solution \(f(\cdot )\), such that for any \(s\in [0,t]\),

$$\begin{aligned} \begin{array}{ll} f(s)&{}=f(0)\cdot \exp \left( -\int _0^s a(u)du\right) +\int _0^s b(u)\cdot \exp \left( -\int _u^s a(v)dv\right) \cdot du\\ &{}=f(t)\cdot \exp \left( \int _s^t a(u)du\right) -\int _s^t b(u)\cdot \exp \left( \int _s^u a(v)dv\right) \cdot du. \end{array} \end{aligned}$$
(6)

Coming back to the markup pricing problem, let us define the infinitesimal generator \({{\mathcal {G}}}^k_n(t)\) corresponding to price \({\bar{p}}^k\), inventory level n, and time t, so that when it is applied to a well-defined function vector \(u\equiv (u_n(t)\mid n=0,1,\ldots ,N,\;t\in [0,T])\),

$$\begin{aligned} {{\mathcal {G}}}^k_n(t)\circ u=d_t u_n(t)+{\bar{\alpha }}^k\cdot \beta (t)\cdot (u_{n-1}(t)-u_n(t)). \end{aligned}$$
(7)

Note that it would be an abuse of notation to call the left-hand side \({{\mathcal {G}}}^k u_n(t)\), as knowing \(u_n(t)\) at the particular n and t alone will not help one get to the right-hand side.

For the case where the time multiplier \(\beta (\cdot )\) is stationary, Theorem 1 of Feng and Xiao (2000b) offers sufficient conditions for a vector of functions to be the value functions \(v^k_n(t)\). But this result can be easily generalized to the case where \(\beta (\cdot )\) is time-variant. In the same spirit of this theorem, we have the following.

Proposition 1

For any \(k=K-1,K-2,\ldots ,0\), a function vector \(u\equiv (u_n(t)\mid n=0,1,\ldots ,N,\;t\in [0,T])\) that is uniformly bounded and absolutely continuous in t for every n will be \(v^k\equiv (v^k_n(t)\mid n=0,1,\ldots ,N,\;t\in [0,T])\) that satisfies (3) and (4), if it satisfies:

  1. (i)

    \(u_n(t)\ge v^{k+1}_n(t)\) for every \(n=0,1\ldots ,N\) and \(t\in [0,T]\),

  2. (ii)

    \(u_n(T)=0\) for every \(n=0,1,\ldots ,N\) and \(u_0(t)=0\) for every \(t\in [0,T]\),

  3. (iii)

    for \(n=1,2,\ldots ,N\) and \(t\in [0,T]\), \(u_n(t)=v^{k+1}_n(t)\) implies \({{\mathcal {G}}}^k_n(t)\circ u+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)\le 0\),

  4. (iv)

    for \(n=1,2,\ldots ,N\) and \(t\in [0,T]\), \(u_n(t)>v^{k+1}_n(t)\) implies \({{\mathcal {G}}}^k_n(t)\circ u+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)=0\).

Proposition 1 offers a hint as to how the value functions \(v^k_n(t)\) and threshold levels \(\tau ^k_n\) can be constructed. First, due to (3), \(v^K_n(t)\) can be shown to satisfy a differential equation involving \(v^K_{n-1}(t)\) but still in the spirit of (5). Hence, using (6) and the fact that \(v^K_0(t)=0\), we can establish all the \(v^K_n(t)\) values in an n-loop.

Then, for any \(k=K-1,K-2,\ldots ,0\), suppose \(v^{k+1}_n(t)\) is known for all n and t. We can then go through an n-loop to find all the \(v^k_n(t)\)’s. First, we can let \(v^k_0(t)=0\) as suggested by (ii) of the proposition. Second, suppose \(v^k_{n-1}(t)\) is known for all t and some \(n=1,2,\ldots ,N\). Then, we have \(v^k_n(T)=0\) by (ii) of the proposition. Next, we may “weave” \(v^k_n(t)\) for ever smaller t values by solving the differential equation \({{\mathcal {G}}}^k_n(t)\circ v^k+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)=0\) as indicated by (iv) of the proposition. We stop at the t when \(v^k_n(t)\) is to sink below \(v^{k+1}_n(t)\)—according to (i) of the proposition, \(v^k_n(t')\ge v^{k+1}_n(t')\) for every \(t'\). For time \(t'\) earlier than this t, which we mark as \(\tau ^{k+1}_n\), we let \(v^k_n(t')\) be \(v^{k+1}_n(t')\).

According to (iii) of the proposition, we still need \({{\mathcal {G}}}^k_n(t')\circ v^k+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t')\le 0\) for \(t'<\tau ^{k+1}_n\) for the thus constructed \(v^k_n(\cdot )\) to be the true value function. Nevertheless, let us go ahead with the construction procedure thus outlined. Not knowing whether what shall be constructed are the true value functions, we call them u’s instead of v’s. Formally, here is the iterative procedure for constructing the function vector \(u\equiv (u^k_n(t)\mid k=0,1,\ldots ,K,\;n=0,1,\ldots ,N,\;t\in [0,T])\) and time point vector \(\tau \equiv (\tau ^k_n\mid k=1,2,\ldots ,K,\;n=1,2,\ldots ,N)\).

First, let

$$\begin{aligned} u^k_0(t)=0,{\quad }\forall k=K,K-1,\ldots ,0,\;t\in [0,T]. \end{aligned}$$
(8)

Then, for \(n=1,2,\ldots ,N\) and \(t\in [0,T]\), let

$$\begin{aligned} u^K_n(t)={\bar{\alpha }}^K\cdot \int _t^T \beta (s)\cdot \left( {\bar{p}}^K+u^K_{n-1}(s)\right) \cdot \exp \left( -{\bar{\alpha }}^K\cdot {{\hat{\beta }}}(t,s)\right) \cdot ds. \end{aligned}$$
(9)

Next, we go over an outer loop on \(k=K-1,K-2,\ldots ,0\) and an inner loop on \(n=1,2,\ldots ,N\). At each k and n, first let

$$\begin{aligned} u^k_n(t)={\bar{\alpha }}^k\cdot \int _t^T \beta (s)\cdot \left( {\bar{p}}^k+u^k_{n-1}(s)\right) \cdot \exp \left( -{\bar{\alpha }}^k\cdot {{\hat{\beta }}}(t,s)\right) \cdot ds,{\quad }\forall t\in [0,T]. \end{aligned}$$
(10)

Then, let

$$\begin{aligned} \tau ^{k+1}_n=\inf \left\{ t\in [0,T]\mid u^k_n(t)>u^{k+1}_n(t)\right\} , \end{aligned}$$
(11)

with the understanding that \(\tau ^k_n=0\) when the concerned inequality is always true and \(\tau ^k_n=T\) when it is never true. Finally, let

$$\begin{aligned} u^k_n(t)=u^{k+1}_n(t),{\quad }\forall t\in [0,\tau ^{k+1}_n]. \end{aligned}$$
(12)

In obtaining (9) and (10), we have resorted to (5) and (6) for solving \({{\mathcal {G}}}^k_n(t)\circ u^k+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)=0\) for \(k=K,K-1,\ldots ,0\). According to (7), the ODE boils down to

$$\begin{aligned} d_t u^k_n(t)=-\bar{\alpha }^k\cdot \beta (t)\cdot ({\bar{p}}^k+u^k_{n-1}(t))-\bar{\alpha }^k\cdot \beta (t)\cdot u^k_n(t). \end{aligned}$$
(13)

This is in the form of (5) with \(a(t)=\bar{\alpha }^k\cdot \beta (t)\) and \(b(t)=-\bar{\alpha }^k\cdot \beta (t)\cdot ({\bar{p}}^k+u^k_{n-1}(t))\). With the terminal condition \(u^k_n(T)=0\) and the second half of (6), we will have (9) for \(k=K\) and (10) for \(k=K-1,K-2,\ldots ,0\).

When properly discretized, the recursive procedure can be translated into an efficient algorithm for computing threshold policies. In implementation, we discretize the time axis [0, T] by a grid \(\{0,\Delta T,2\Delta T,\ldots ,Q\cdot \Delta T\}\), where Q is a strictly positive integer and \(\Delta T=T/Q\). For \(k=0,1,\ldots ,K\) and \(q=0,1,\ldots ,Q\), we use \(\lambda ^k_q\) to denote \({\bar{\alpha }}^k\beta (q\cdot \Delta T)\).

In spelling out the algorithm, we use the fact that (9) and (10) would lead to

$$\begin{aligned} u^k_n(t)=u^k_n(t+\Delta t)+{\bar{\alpha }}^k\beta (t)\cdot \Delta t\cdot ({\bar{p}}^k+u^k_{n-1}(t)-u^k_n(t+\Delta t))+o(\Delta t). \end{aligned}$$
(14)

Now, we can adapt the procedure from (8) to (12) to the following algorithm Markup.

figure a

In Markup, each \(v^k_{nq}\) corresponds to \(v^k_n(q\cdot \Delta T)\) in the continuous-time model. The algorithm’s time complexity is apparently O(KNQ).

4 Optimality and k-monotonicity

We now show that the above procedure indeed leads to the true value functions and an optimal pricing policy. First, through a sample-path argument that is reminiscent of Zhao and Zheng’s (2000) treatment of the same property for reversible dynamic pricing, we can show that the marginal value of any additional item is diminished at a higher inventory level.

Proposition 2

For any fixed \(k=0,1,\ldots ,K\) and \(t\in [0,T]\), the value function \(v^k_n(t)\) is concave in n: \(v^k_{n+1}(t)-v^k_n(t)\le v^k_n(t)-v^k_{n-1}(t)\).

We can use this result and more involved sample-path analysis to show the added benefit that more flexibility in pricing can bring to the firm when there are more items.

Proposition 3

For any fixed \(t\in [0,T]\), the value function \(v^k_n(t)\) has decreasing differences between k and n: \(v^{k+1}_{n+1}(t)-v^{k+1}_n(t)\le v^k_{n+1}(t)-v^k_n(t)\).

Proposition 3 will play a critical role in the proof of the next key result. We believe this property is previously unknown; for instance, it has no counterpart in Feng and Xiao (2000b). In the proof of it, an important step is made on the premise that more sales will be made for pools of items starting with more flexible prices, to the effect that the concavity property Proposition 2 can be used. For the markup case, lower prices are the more flexible ones because they allow more room to be raised further. Proposition 3 thus conveys the message that an additional unit of inventory would be more valuable when there is more potential to further raise the price. At the same time, lower prices tend to attract more sales. However, the opposite is true for the markdown case. There, higher prices allow more room to be lowered further; yet, it is still the lower prices that hold more attractions for demands. Because of this asymmetry, a similar property as that exhibited in Proposition 3 is not to be expected of the markdown case. Indeed, one of our computational studies has shown that the case does not have complementarity between price flexibility and inventory.

We now demonstrate the optimality of a threshold policy for the markup case. For convenience, we have let the yet undefined \(\tau ^{K+1}_n=0\) for \(n=1,2,\ldots ,N\) and \(v^{K+1}_n(t)=u^K_n(t)\) for \(n=0,1,\ldots ,N\) and \(t\in [0,T]\).

Theorem 1

The u and \(\tau \) as constructed from (8) to (12) satisfy the following for \(k=K,K-1,\ldots ,0\):

(a[k]):

for any \(n=1,2,\ldots ,N\), \(({{\mathcal {G}}}^k_n)^+(\tau ^{k+1}_n)\circ v^{k+1}+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (\tau ^{k+1}_n)\le 0\);

(b[k]):

\({{\mathcal {G}}}^k_n(t)\circ v^{k+1}/\beta (t)\) is increasing in t for \(n=1,2,\ldots ,N\) and \(t\in (0,T)\);

(c[k]):

\(u^k_n(t)=v^k_n(t)\) for any \(n=0,1,\ldots ,N\) and \(t\in [0,T]\);

(d[k]):

for any \(n=1,2,\ldots ,N\), we have \(v^k_n(t)=v^{k+1}_n(t)\) and \({{\mathcal {G}}}^k_n(t)\circ v^k+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)\le 0\) for \(t\in (0,\tau ^{k+1}_n)\), and \({{\mathcal {G}}}^k_n(t)\circ v^k+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)=0\) for \(t\in (\tau ^{k+1}_n,T)\);

(e[k]):

\(\tau ^{k+1}_n\) is decreasing in n;

(f[k]):

on top of \(v^k_n(t)\) having decreasing differences between n and t, it is further true that \(d_t v^k_n(t)/\beta (t)\) is decreasing in t for \(n=1,2,\ldots ,N\) and \(t\in (0,T)\).

As a consequence, \(\tau \) provides an optimal policy for the firm; under this policy, the firm should switch to price \({\bar{p}}^{k+1}\) when its inventory level drops to n before time \(\tau ^{k+1}_n\) while its price level is \({\bar{p}}^k\).

In (a[k]) of Theorem 1, the operator \(({{\mathcal {G}}}^k_n)^+(t)\) is merely \({{\mathcal {G}}}^k_n(t)\) defined in (7) with \(d_t\) replaced by the right derivative \(d^+_t\). The successful proof of Theorem 1 depends very much on the complementarity property provided by Proposition 3. It suggests the firm to raise its price from the current \({\bar{p}}^k\) to the next higher level \({\bar{p}}^{k+1}\) if still possible when a demand arrival has prompted an inventory level drop to the level n at a time before the threshold level \(\tau ^{k+1}_n\). Finally, regarding the k-monotonicity of the optimal policy, we have the following result directly from the definition (11) and Theorem 1.

Proposition 4

Suppose \(\tau ^k_n<T\) for some \(k=1,2,\ldots ,K-1\) and \(n=1,2,\ldots ,N\). Then, we have \(\tau ^{k+1}_n\le \tau ^k_n\) if and only if \(v^{k-1}_n(t)-v^k_n(t)>0\) will lead to \(v^k_n(t)-v^{k+1}_n(t)>0\).

As confirmed by one of our computational studies, the threshold level \(\tau ^k_n\) for the markup case is not necessarily decreasing in k. Hence, this case may have its “leapfrog” phenomenon: When it is time to switch to the price level \({\bar{p}}^{k+1}\), it may also be the time to switch to the next higher price \({\bar{p}}^{k+2}\), and so on and so forth. Therefore, when it is time to make the price swith from \({\bar{p}}^k\), the ultimate target should be some \({\bar{p}}^{{\tilde{k}}^+(k,n)}\), where \({\tilde{k}}^+(k,n)\) is not necessarily \(k+1\). For each \(n=1,2,\ldots ,N\), we can use the following iterative procedure to find \(({\tilde{k}}^+(k,n)\mid k=0,1,\ldots ,K-1)\):

figure b

5 Discussion

For the markdown case, we can again use a constructive procedure to attain an optimal threshold policy, which is not necessarily k-monotone; see “Appendix B”. Under such a policy \(\tau \equiv (\tau ^k_n\mid k=1,2,\ldots ,K,\;n=1,2,\ldots ,N)\in (\Delta _N)^K\), the firm in the markdown case is supposed to lower its price from \({\bar{p}}^k\) to \({\bar{p}}^{k-1}\) if still possible when no demand arrival has prompted an inventory level drop from its current level n by the threshold time \(\tau ^k_n\).

It has long been known by Zhao and Zheng (2000) that an ostensibly similar-looking threshold policy \(\tau \in (\Delta _N)^K\) is optimal for the reversible-pricing case, where price changes can be in either direction. Our product-form demand pattern also satisfies the sufficient condition specified in Zhao and Zheng (2000) for the k-monotonicity (time-monotonicity in that context) of the threshold policy: \(0\equiv \tau ^{K+1}_n\le \tau ^K_n\le \tau ^{K-1}_n\le \cdots \le \tau ^1_n\le \tau ^0_n\equiv T\). At the inventory level n, the firm following such a policy should charge price \({\bar{p}}^k\) when the time is between \(\tau ^{k+1}_n\) and \(\tau ^k_n\). The irreversible- and reversible-pricing cases clearly differ on whether optimal policies possess the k-monotone property.

Within the irreversible-pricing category, we have something more important to stress. While the threshold point \(\tau ^k_n\) is a zero-crossing point for \(v^{k-1}_n(t)-v^k_n(t)\) for the markup case, it is not necessarily one for \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k+{\bar{p}}^{k-1}{\bar{\alpha }}^{k-1}\cdot \beta (t)\): Though the term is below 0 when \(t\in (0,\tau ^k_n)\), we can verify through computation that the term is not necessarily above 0 when \(t\in (\tau ^k_n,T)\) is not too much above \(\tau ^k_n\). This marks a huge contrast with the markdown case, for which the threshold point \(\tau ^k_n\) is the zero-crossing point for both \({{\mathcal {G}}}^k_n(t)\circ v^{k-1}+{\bar{p}}^k{\bar{\alpha }}^k\cdot \beta (t)\) and \(v^k_n(t)-v^{k-1}_n(t)\); see Figs. 1 and 2 for a demonstration of this discrepancy. This previously unnoticed point determines that, in order to obtain the n-monotone pattern of the \(\tau ^k_n\) points for the markup case, we have to deal with the dependence of \(v^{k-1}_n(t)-v^k_n(t)\) on n.

Fig. 1
figure 1

Illustration for the markup case

Full size image

Feng and Xiao’s (2000b) treatment of the markup case relied on properties of \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k\) rather than those of \(v^{k-1}_n(t)-v^k_n(t)\). Temporarily, let us consider the stationary-demand case where \(\beta (t)=1\) for all \(t\in [0,T]\). Their Lemma 1 claimed that the increase of \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k\) in t and n alone, without other benefits that might come from the \(v^k_n(\cdot )\)’s being truly value functions of a markup problem, would lead to optimal threshold levels \(\tau ^k_n\) that necessarily satisfy \(0\le \tau ^k_N\le \tau ^k_{N-1}\le \cdots \tau ^k_1\le T\). While its counterpart for the markdown case is correct, we have a counter example to the current claim.

Fig. 2
figure 2

Illustration for the markdown case

Full size image

Consider the case with \(T=1\), \(K=1\), \(N=2\), and \({\bar{\alpha }}^0=2\). Let \(v^1_0(t)=0\), \(v^1_1(t)=-2t+2\), and \(v^1_2(t)=t^2-4t+3\). We can check that \(d_t v^1_1(t)=-2\) and \(d_t v^1_2(t)=2t-4\). These lead to \({{\mathcal {G}}}^0_1(t)\circ v^1=4t-6\) and \({{\mathcal {G}}}^0_2(t)\circ v^1=-2t^2+6t-6\). Hence, \({{\mathcal {G}}}^0_1(t)\circ v^1\) and \({{\mathcal {G}}}^0_2(t)\circ v^1\) are both increasing in \(t\in [0,1]\). In addition, \({{\mathcal {G}}}^0_2(t)\circ v^1-{{\mathcal {G}}}^0_1(t)\circ v^1=-2t^2+2t\), which is positive for \(t\in [0,1]\). That is, \({{\mathcal {G}}}^0_n(t)\circ v^1\) is increasing in n too. On the other hand, we may let \(v^0_1(t)=-t^2-t+2\) and \(v^0_2(t)=v^1_2(t)=t^2-4t+3\). Now, \(v^0_1(t)-v^1_1(t)=-t^2+t\), which is strictly positive for \(t\in (0,1)\), and \(v^0_2(t)-v^1_2(t)=0\). Thus, it is not true that \(v^0_1(t)-v^1_1(t)\le v^0_2(t)-v^1_2(t)\) on \(t\in [0,1]\). Among other violations, the last point consists of a violation of Proposition 3. So the possibility that these \(v^k_n(\cdot )\)’s form actual value functions for a markup problem has been ruled out.

When we pretend that these \(v^k_n(t)\)’s form value functions for a markup problem, however, we should have \(\tau ^1_1\) as the smallest t such that \(v^0_1(t)-v^1_1(t)>0\) and \(\tau ^1_2\) the smallest t such that \(v^0_2(t)-v^1_2(t)>0\); also, each threshold level should be set at 0 when the corresponding strict positivity is always true and set at \(T=1\) when the corresponding strict positivity is never true. Therefore, we should have \(\tau ^1_1=0\) and \(\tau ^1_2=1\) for this example. It is therefore not true that \(\tau ^1_1\ge \tau ^1_2\). But the latter is required for a threshold policy.

In our approach for the markup case, Proposition 3 has been set aside for the sole purpose of illustrating the complementarity between price flexibility and inventory, a property that is both previously unknown and not possessed by the seemingly symmetric markdown case. In addition, property (a[k]) in Theorem 1, concerning right derivatives of the value functions, has no counterpart in earlier literature. Moreover, Feng and Xiao (2000b) erroneously used the increase of \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k_n\) in n (their Lemmas 1 and 2) that we have no use of. Our computational test confirmed that this is not necessarily true.

6 Computational studies

Without the analysis done in Sect. 3 and “Appendix B”, or without knowing the shape of the optimal pricing policy, one can already come up with brute-force algorithms Markup2 and Markdown2 for the two cases. These and other algorithms that are useful in our computational studies are presented in “Appendix C”.

Throughout our computational studies, we take the horizon length \(T=1\), \(K=4\) so that there are five different price levels, the number of initial stock level \(N=20\), the price-level vector \((\bar{p}^k\mid k=0,1,\ldots ,K)=(1,2,3,4,5)\), the time-multiplier vector \(({\bar{\alpha }}^k\mid k=0,1,\ldots ,K)=(4N,1.7N,1.0N,0.7N,\) 0.54N) unless otherwise specified, and the number of discrete time intervals \(Q=1,000,000\). Unless otherwise specified, we define the time multiplier \(\beta (\cdot )\) to be used in the product form by

$$\begin{aligned} \beta (t)=\frac{W}{1-e^{-W}}\cdot e^{W\cdot (t-T)/T},{\quad }\forall t\in [0,T], \end{aligned}$$
(15)

where parameter \(W\in \{1,2,\cdots ,10\}\). It is easy to check that the time average \(\int _0^T \beta (t)\cdot dt/T=1\) at all W values, and that W reflects the degree of time-variability of the arrival pattern \(\beta (\cdot )\). We set the default value of W at 5.

The bulk of our computational studies are devoted to probes of the following questions:

  1. (a)

    whether the markdown case does not have complementarity between price flexibility and inventory, a property that is essential for the markup case;

  2. (b)

    whether earlier treatment of the markup case needs minor corrections;

  3. (c)

    whether k-monotonicity is in general not true for the threshold policies of the irreversible-pricing cases;

  4. (d)

    whether heeding the time-variability of \(\beta (t)\) helps reap huge benefits; and,

  5. (e)

    whether optimal policies for arrival patterns more general than the current product form are not necessarily threshold-like.

    All these questions will be answered in the affirmative.

In test (a), we use \(v^{-k}_{nq}\) to denote the values achieved by Markdown on the markdown problem. Let us define the ratio \(\mu ^-\):

$$\begin{aligned} \mu ^-=\frac{\sum _{q=0}^Q\sum _{n=0}^{N-1}\sum _{k=0}^{K-1}\left( v^{-k}_{n+1,q}+v^{-,k+1}_{nq}-v^{-k}_{nq}-v^{-,k+1}_{n+1,q}\right) ^+}{\sum _{q=0}^Q\sum _{n=0}^{N-1}\sum _{k=0}^{K-1}\mid v^{-k}_{n+1,q}+v^{-,k+1}_{nq}-v^{-k}_{nq}-v^{-,k+1}_{n+1,q}\mid }. \end{aligned}$$
(16)

Note that \(\mu ^-\) is always between 0 and 1; it will be 0 if and only if \(v^{-k}_{nq}+v^{-,k+1}_{n+1,q}\ge v^{-k}_{n+1,q}+v^{-,k+1}_{nq}\) at every possible (k, n, q), that is, if and only if \(v^{-k}_{nq}\) has increasing differences between k and n. For the markdown case, a higher k means more price choices in the future. Thus, \(\mu ^-\) measures the degree to which complementarity between price flexibility and inventory is violated for the markdown case. When \(W=5\), we find \(\mu ^-\approx 25.0\%\). Figure 3 further shows varying \(\mu ^-\) values at different W levels. From all these, we can see that the markdown case does not enjoy complementarity between price flexibility and inventory. This contrasts with what Proposition 3 has said about the markup case.

Fig. 3
figure 3

Violations of complementarity between price-flexibility and inventory at different W’s

Full size image

In test (b), we use Markup for the markup case. For the arrival pattern, \(\beta (t)=1\) for all t’s suffices for our study. Concerning the sign of \({{\mathcal {G}}} ^{k-1}_n(t)\circ v^k+{\bar{p}}^{k-1}{\bar{\alpha }}^{k-1}\cdot \beta (t)\) within \((\tau ^k_n,T)\), we find that \({{\mathcal {G}}} ^3_6(t)\circ v^4+{\bar{p}}^3{\bar{\alpha }}^3\cdot 1<-1.7\) when \(t\in [0.6065,0.6165]\), where \(\tau ^4_6\simeq 0.6065\) is the threshold level for \(k=4\) and \(n=6\). Here, any \(d_t u(t)\) is approximated by \([u(t+\Delta t)-u(t)]/\Delta t\). Therefore, \({{\mathcal {G}}} ^{k-1}_n(t)\circ v^k+{\bar{p}}^{k-1}{\bar{\alpha }}^{k-1}\cdot \beta (t)\) may be negative when \(t>\tau ^k_n\). Concerning the monotonicity of \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k\) in n, we find that \({{\mathcal {G}}}^0_{17}(t)\circ v^1-{{\mathcal {G}}}^0_{16}(t)\circ v^1\simeq -0.340\) when \(t\simeq 0.2622\). That is, we do not necessarily have the increase of \({{\mathcal {G}}}^{k-1}_n(t)\circ v^k\) in n. However, this has been erroneously used in Feng and Xiao (2000b).

In test (c), we use \(\tau ^{\pm k}_n\) to denote threshold levels found by applying Markup(down)1 to the markup(down) problem. Let us define the \(\delta ^{\pm }\) ratios:

$$\begin{aligned} \delta ^{\pm }=\frac{\sum _{n=1}^N\sum _{k=0}^{K-1}\left( \tau ^{\pm ,k+1}_n-\tau ^{\pm k}_n\right) ^+}{\sum _{n=1}^N\sum _{k=0}^{K-1}\mid \tau ^{\pm ,k+1}_n-\tau ^{\pm k}_n\mid }. \end{aligned}$$
(17)

Note that \(\delta ^{\pm }\) is always between 0 and 1; it will be 0 if and only if \(\tau ^{\pm k+1}_n\le \tau ^{\pm k}_n\) at every possible (k, n). Thus, it measures the degree to which k-monotonicity has been violated. For \(W=5\) and time-multiplier vector \(({\bar{\alpha }}^k\mid k=0,1,\ldots ,K)=(2.0N,0.76N,0.5N,0.25N,0.1N)\), we have \(\delta ^+\approx 11.2\%\) for the markup case. For the markdown case, we have to use a different time-multiplier vector \(({\bar{\alpha }}^k\mid k=0,1,\ldots ,K)=(3N,N,0.5N,0.35N,0.27N)\) to achieve unequivocal results. Under this and \(W=5\), we find \(\delta ^-\approx 13.9\%\). We can also plot the \(\delta ^\pm \) values when W changes in Fig. 4. All results point to the violation of k-monotonicity in general for both irreversible-pricing cases. This is in stark contrast with reversible-pricing.

Fig. 4
figure 4

Violations of k-monotonicity at different W’s

Full size image

In test (d), we suppose that, when not aware of the time-variability of \(\beta (\cdot )\), the firm will take the flat \(\beta '(t)=1\) as \(\beta (t)\) in its policy derivation. Let us use \(v^{+k}_{nq}\) and \(\tau ^{+k}_n\) to denote, respectively, the values and threshold levels resulting from applying Markup to the markup problem defined by \(\beta (\cdot )\), and use \(\tau ^{+\prime k}_n\) to denote the threshold levels resulting from applying Markup to the corresponding flat-rate problem defined by \(\beta '(\cdot )\). To find the values \(v^{+\prime k}_{nq}\) from applying the sub-optimal policy defined by the \(\tau ^{+\prime k}_n\)’s to the actual situation defined by \(\beta (\cdot )\), we shall use algorithm Markup3.

Corresponding to Markup3, we have algorithms Markdown3 and Reversible3 for the markdown and reversible-pricing cases, respectively. All these are described in “Appendix C”. For the markdown case, the relevant values will be denoted by \(v^{-k}_{nq}\) and \(v^{-\prime k}_{nq}\), while for the reversible-pricing case, these values will be denoted by \(v^0_{nq}\) and \(v^{0\prime }_{nq}\).

To measure the losses due to neglecting the time-variability of \(\beta (\cdot )\), we may define \(\eta ^{\pm (0)}\) for the markup(down) and reversible-pricing cases:

$$\begin{aligned} \eta ^{\pm }=\frac{\sum _{k=0}^K (v^{\pm k}_{N0}-v^{\pm \prime k}_{N0})}{\sum _{k=0}^K v^{\pm k}_{N0}},{\quad }\eta ^0=\frac{v^0_{N0}-v^{0\prime }_{N0}}{v^0_{N0}}. \end{aligned}$$
(18)

When \(W=5\), we have \(\eta ^+\approx 2.0\%\), \(\eta ^-\approx 18.9\%\), and \(\eta ^0\approx 15.8\%\). Hence, the benefit of heeding demand’s time-variability in each of the three cases is substantial. When W varies, we show the \(\eta ^{\pm (0)}\) values in Fig. 5. It is quite clear from the figure that the benefit increases with the degree of the fluctuation.

Fig. 5
figure 5

Benefits of heeding demand’s time-variability at different W’s

Full size image

In test (e), we abandon the product-form arrival pattern \(\lambda ^k(t)={\bar{\alpha }}^k\cdot \beta (t)\). In its stead,

$$\begin{aligned} \lambda ^k(t)={\bar{\alpha }}^k\cdot \left[ 1+0.8\cdot \sin \left( 2\pi \cdot \left( \frac{k}{0.3}+t\right) \right) \right] . \end{aligned}$$
(19)

Note that (19) is not defined by one single \(\beta (\cdot )\) across different k values. As algorithms Markup, Markdown, and Reversible are designed for cases where the arrival pattern is of the product form, they are not guaranteed to arrive to correct answers any more. Indeed, discrepancies appear for the current arrival pattern between results produced by these algorithms and those by the brute-force algorithms. In Fig. 6, we demonstrate the pricing decisions reached by Markup2 and Markdown2, as well as \(p_n(t)\) reached by Reversible2 at particular (k and) n values.

Fig. 6
figure 6

Non-threshold pricing decisions when arrival is not of product form

Full size image

Since none of the above pricing decisions is decreasing in t, we simply can not define \(\tau ^k_n\) for any of these cases. Therefore, predictions made in the paper stop at the product-form case for the time being. Note that \(\lambda ^{k+1}(t)/\lambda ^k(t)\) under (19) is not decreasing in t. Therefore, Zhao and Zheng’s (2000) Assumption 1 is violated, and our counter example for the reversible-pricing case is not in contradiction with Zhao and Zheng’s prediction for time-monotone policies when arrival patterns are well behaved.

7 Concluding remarks

We hve considered the markup case of dynamic pricing, where a firm has to charge an increasing sequence of predetermined prices. A threshold policy has been found to be optimal when the demand arrival rate is of the product form. Our derivation corrects errors made in the earlier work Feng and Xiao (2000b) on almost the same subject. Our derivation relies on a complementarity property between price flexibility and inventory, an erstwhile-unknown property that sets the markup case apart from the markdown case. Our development also leads to an efficient algorithm and certain methodological advances.