{'fraction_non_alphanumeric': 0.04744638972340205, 'fraction_numerical': 0.01231050795952899, 'mean_word_length': 4.524513544448684, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dealing with the Dimensionality Curse in Dynamic Pricing Competition: Using Frequent Repricing to Compensate Imperfect Market Anticipations

Most sales applications are characterized by competition and limited demand information. For successful pricing strategies, frequent price adjustments as well as anticipation of market dynamics are crucial. Both effects are challenging as competitive markets are complex and computations of optimized pricing adjustments can be time-consuming. We analyze stochastic dynamic pricing models under oligopoly competition for the sale of perishable goods. To circumvent the curse of dimensionality, we propose a heuristic approach to efficiently compute price adjustments. To demonstrate our strategy's applicability even if the number of competitors is large and their strategies are unknown, we consider different competitive settings in which competitors frequently and strategically adjust their prices. For all settings, we verify that our heuristic strategy yields promising results. We compare the performance of our heuristic against upper bounds, which are obtained by optimal strategies that take advantage of perfect price anticipations. We find that price adjustment frequencies can have a larger impact on expected profits than price anticipations. Finally, our approach has been applied on Amazon for the sale of used books. We have used a seller's historical market data to calibrate our model. Sales results show that our data-driven strategy outperforms the rule-based strategy of an experienced seller by a profit increase of more than 20%.


Introduction
In most markets, sellers have to deal with competition. On modern e-commerce platforms, it has become easy to observe and to adjust prices. On such platforms, sales do not only depend on a sellers' prices but also on competitors' prices. Moreover, customers take further product features into account, e.g., product quality, ratings, shipping time, shipping costs, etc.

Motivation
Modern market platforms such as Amazon Marketplace or eBay are highly dynamic as sellers can observe the current market situation at any time and adjust their prices instantly. Sellers typically rival against Email addresses: rainer.schlosser@hpi.de (Rainer Schlosser), martin.boissier@hpi.de (Martin Boissier) dozens of competitors, decide on prices for thousands of products, and face steadily changing market situations, cf. Profitero (2014). As electronic markets are constantly growing and the costs of price changes are close to free, intelligent automated repricing systems become increasingly important for practitioners, see Popescu (2016). Since demand information is limited and market dynamics are uncertain, deriving intelligent pricing strategies is highly complex. Pricing strategies are required to take a multitude of dimensions for each competitor into account (e.g., price, quality, shipping time, shipping costs, ratings). Further, aspects such as discounting, cash-flows, and inventory holding costs also have to be included.
In this paper, we study oligopoly pricing models in a stochastic dynamic finite horizon framework. We consider single-product problems. We seek to deal with the following real-life aspects: (i) demand probabilities are unknown, (ii) products have multiple offer dimensions (price, quality, ratings, shipping time, etc.), (iii) products are offered by multiple competitors, (iv) competitors' sales, inventories, and strategies are not observable.
The setting of limited and asymmetric information, multiple offer dimensions and multiple competitors is highly challenging. To compute viable pricing strategies in competitive settings, we introduce a dynamic programming model that circumvents the curse of dimensionality. We show how to calibrate the model using data-driven demand estimations. To illustrate the applicability of our approach, we use reproducible numerical examples. Finally, we present the performance result of our strategy applied on Amazon.

Literature Review
The best way to sell products is employing a classical application of revenue management theory. The problem is closely related to the field of dynamic pricing, which is summarized in the books by Talluri, van Ryzin (2004), Phillips (2005), and Yeoman, McMahon-Beattie (2011). The surveys by Chen, Chen (2015) and Den Boer (2015a) provide an excellent overview of recent pricing models under competition.
In the article by Gallego, Wang (2014) the authors consider a continuous time multi-product oligopoly for differentiated perishable goods. They use optimality conditions to reduce the multi-dimensional dynamic pure pricing problem to a one-dimensional one. Gallego, Hu (2014) analyze structural properties of equilibrium strategies in more general oligopoly models for the sale of perishable products. The solution of their model is based on a deterministic version of the model. Martinez-de-Albeniz, Talluri (2011) consider duopoly and oligopoly pricing models for identical products. They use a general stochastic counting process to model customer's demand. Further related models are studied by Yang, Xia (2013), Wu, Wu (2015), and Schlosser (2017). Dynamic pricing models under competition that also include strategic customers are analyzed by Levin et al. (2009) and Liu, Zhang (2013).
In most existing models, the demand intensity is assumed to be known. Dynamic pricing competition models with limited demand information are analyzed by Tsai, Hung (2009), Adida, Perakis (2010), Chung et al. (2012, and Den Boer (2015b) using robust optimization and learning approaches. For a more comprehensive review, we refer to Chen, Chen (2015).
In contrast to the assumptions of most publications, in real-life applications, specific information is not observable, demand and price reactions are typically unknown, and customers as well as sellers might not act rational. Moreover, when dealing with dynamic pricing competition models, the most critical problem is their high complexity and the enormous number of potential market situations (cf. curse of dimensionality).
Thus, most solution approaches are only applicable if specific assumptions can be verified and the number of competitors is small.
In general, dynamic pricing competition problems with incomplete information are not tractable and cannot be optimally solved. Hence, in real-life applications, heuristic strategies have to be used. In practice, rule-based strategies as well as data-driven strategies are used, cf. Popescu (2016). As the evaluation of complex competing pricing strategies is also not analytically tractable, it is impossible to give performance guarantees of a specific strategy -even if the underlying customer behavior as well as the competing strategies are known. Hence, simulation studies have to be used to compare the performance of dynamic pricing strategies and to analyze their strategic interaction in different oligopoly settings, see, e.g., Kephart et al. (2000) or Serth et al. (2017).

Contribution
We tackle the problem of identifying efficient pricing strategies that are applicable in real-life scenarios.
In this paper, we present the following contributions: (i) We show how to compute dynamic price adjustments to be applied in practice (Sec. 3).
(ii) We demonstrate that our heuristic is applicable even if the number of competitors is large and the competitors' strategies are unknown (Sec. 4).
(iii) We verify the performance of our pricing strategy by comparing it to upper bounds, which are obtained by optimal strategies that take advantage of price anticipations (Sec. 5).
(iv) We find that higher price adjustment frequencies can easily overcompensate a loss in expected profits due to the lack of price anticipations.
(v) We successfully applied our strategy on the Amazon Marketplace (Sec. 6).
We present a dynamic programming model that allows for high dimensional market situations characterized by offers of several competitors with multiple features. We show how real-life market data consisting of competitors' offers, our offers, and our sales can be used to estimate sales probabilities for arbitrary market situations. This way, the impact of market dynamics and competitors' price reactions are implicitly taken into account without anticipating future market situations explicitly. Further, we use a decomposition approach to compute pricing decisions for single situations separately. This makes it possible to efficiently compute price adjustments that are based on current market situations. Finally, we compensate the lack of perfect price anticipations by frequent price adjustments, which in turn are possible as the model allows for rapid re-computations of optimized prices. Further, we present an extended model which takes price adjustment costs into account. This allows to combine fast reaction times and a limited use of price updates.
Our approach is successfully applied in practice. The model was calibrated using historical market data from the Amazon Marketplace. Results show that our strategy outperforms the established rule-based strategy of an experienced seller regarding profitability and speed of sales.

Model Description
We consider the situation where a firm wants to sell a finite number of perishable goods on a digital market platform (e.g., Amazon or eBay). For the products, there are several competitors. In our model, we allow that customers compare prices. They also might take additional product features, such as qualities or ratings of different competitors into account.
We assume that items cannot be reproduced or reordered. The initial number of items to sell is N , N ≤ ∞, and the time horizon is finite. If a sale takes place, shipping costs c have to be paid, c ≥ 0. A sale of one item at price a leads to a net revenue of a − c. Moreover, we consider inventory holding costs.
We assume that each unsold item leads to inventory costs of l per period (e.g., one hour or one day), l ≥ 0.
Furthermore, we use the discount factor δ, 0 < δ ≤ 1, for a period of length one.
In our discrete time model, we consider sales probabilities denoted by P . Due to customer choice, sales probabilities will particularly depend on our offer price a and the competitors' prices. Moreover, we allow sales probabilities to depend on time. In our model, P is a general function of our offer price a and a market situation denoted by s. The market situation s is a vector which includes all relevant observable quantities of interest, such as time t, the competitors' prices p, customer ratings v, product conditions, etc. (see, e.g., Kachani, Shmatov (2010)). The probability to sell exactly i items within the time span (t, t + 1) in a stable market situation s = (t, p, v, ...) is denoted by, t = 0, 1, 2, ..., T − 1, a ≥ 0, i = 0, 1, 2, ..., P t (i, a, s). (1) In real-life scenarios the sales probabilities P t (i, a, s) are typically not known and have to be estimated using data-driven approaches. In simulation models, the sales probabilities P t (i, a, s) can be specifically defined and allow to verify the quality of data-driven estimations as well as the performance of pricing strategies. For instance, assuming a given sales intensity λ = λ t (a, s) and a scaling factor d, we can define Poisson distributed sales probabilities for various intervals, t = 0, 1, 2, ..., T − 1, i = 0, 1, 2, ..., a ≥ 0, d > 0, P t (i, a, s) := P ois (d · λ t (a, s)) .
The random inventory level at time t -the beginning of period t -is denoted by X t , t = 0, 1, ..., T . The end of sale (for our firm) is either time T or the random time τ , when all N products are sold. For each period t, a new offer price a can be chosen. We call pricing strategies admissible if they are non-anticipating (Markov policies); pricing decisions a t ≥ 0 may depend on time t, the own inventory level X t , and the current market situation (denoted by S t ), which particularly contains the current prices of the competitors.
A list of variables and parameters is given in the Appendix, cf. Table A.7.
The firm's profits are defined by each period's realized sales (cf. X t − X t+1 ) and inventory holding costs (cf. l · X t ). For chosen prices a t , the random accumulated profit G t from time t on (discounted on time t) amounts to, t = 0, 1, ..., T , We look for a pricing policy that maximizes expected (discounted) future profits E(G t |X t = n, S t = s t ) for all times t, inventories n, and occurring market situations s t .
In the following sections, we will solve dynamic pricing problems that are related to (1) -(2). In the next section, we propose our heuristic pricing strategy for scenarios with many competitors and unknown strategies. The applicability of our strategy is demonstrated in Section 4. In Section 5, we measure the performance of our pricing strategy by studying various settings in which competitors frequently and strate-gically adjust their prices. In Section 6, our approach is used in a live production setting on Amazon.

Circumventing the Curse of Dimensionality: A Heuristic Approach
In this section, we derive viable pricing strategies for markets with many competitors. We use an efficient algorithm to circumvent the curse of dimensionality and propose an effective heuristic pricing strategy.
There are two major problems to derive applicable dynamic programming strategies in competitive markets: (i) as demand is affected by many parameters (e.g., dozens of competitors' prices) a model's state space explodes, and (ii) in general, competitors' strategies are not known, and competitors' price adjustments and other market evolutions cannot be fully anticipated.
Our approach deals with both problems. Most importantly, we subsequently compute prices for one period only based on the current market situations that occur during a sales process. To compute a price for the next time period, in general, the current market situation (current state) as well as potential evolutions of the market (future states) have to be taken into account. As price reactions of competitors occur with a certain delay, the short-term evolution of the market can be well approximated by the current market situation. The long-term evolution of the market, however, can hardly be predicted.
In our use-case, the optimal price for one period mostly depends on the current state and is less affected by possible market evolutions in the far future. Note, while the expected profit of the next period highly depends on the current price decision and the current market situation, the expected future profits are typically much less influenced by the current price decision. This is due to the following: First, future profits are determined by various upcoming decisions that account for future states. Second, our price update typically hardly affects the long-term evolution of the market (especially if many firms are involved).
Third, in markets in which price patterns are cyclic or fluctuate around certain reference prices, it can be assumed that the best expected long-term profits are similar for different market situations.
Hence, instead of trying to predict possible market evolutions in the future, in our approach, we compute price updates based on an accurate calculation of short-term profits and expected long-term profits that are approximated based on current market conditions.
For a current state, we manage problem (i) as follows: We roughly approximate future market situations by using sticky prices. While the degree of inaccuracy is acceptable, we gain a structure that makes it possible to circumvent the curse of dimensionality, cf. problem (i), as the states of our dynamic system (i.e., the market situation) are not coupled and can be easily decomposed. Thus, decisions for single market situation can be computed independently from others.
The second key idea is to compensate the "sticky" model's inaccuracy as well as the lack of correct price anticipations, cf. problem (i), by frequent price adjustments, which in turn, are possible as the model's simplicity allows for fast re-computations.
Due to price adjustments, the exit, or entry of firms, in general, market situations are not stable. In our model, we differentiate between sales probabilities P t (i, a, s) for stable market situations, cf. (1), and conditional sales probabilities, t = 0, 1, ..., T − 1, a ≥ 0, i = 0, 1, 2, ..., for selling i items within the time interval (t, t + 1) at price a under the condition that at time t the market situation is s (but may change within the period). Note, the probabilitiesP t (i, a| s), cf.
(3), can be estimated from real-life data where market situations are typically not stable.
As our approach to compute price adjustments is designed to be applied in unstable markets, it will be based on (estimated) conditional probabilitiesP t (i, a| s), cf.
(3). As described in the beginning of the section, we use a simplified dynamic programming approach in which expected future profits E(G t |X t = n, S t = s), cf.
(2), are described by the value function V t (n, s), t = 0, 1, ..., T , n = 0, 1, ..., N . If all items are sold or the time horizon is over, no future profits can be made, i.e., for any market situation s the natural boundary conditions of the value function are given by, n = 0, 1, ..., N , t = 0, 1, ..., T , The remaining values V t (n, s) are given by the Hamilton-Jacobi-Bellman (HJB) equation, n = 1, ..., N , and can be computed recursively. The set of admissible prices A can be continuous or discrete. Finally, the pricing strategy is determined by the arg max of (6), n = 1, ..., N , t = 0, 1, ..., T − 1, In case the prices determined by (7) are not unique, we choose the largest one.
Note, due to the size of the state space it is not possible to compute prices a t (n, s) for all states s in advance. The following algorithm, however, circumvents the curse of dimensionality by considering just single states and computing feedback strategies multiple times. This allows to derive viable heuristic pricing strategies in competitive markets with a large number of competitors.

Algorithm 3.1
We propose the following pricing heuristic: ( Step 1) For the current point in time t, observe the new state, i.e., the current inventory level X t and the current market situation S t . ( Step 2) Use T − t recursion steps and the probabilitiesP s (i, a| S t ), s = t, ..., T − 1, i = 0, 1, ..., X t , a ∈ A, to compute the specific value V t (X t , S t ), cf. (6). (Step 3) Choose price a t (X t , S t ), which is associated to the last step of the recursion, cf. (7).
At the point in time of the next price adjustment, i.e., t + 1, go to Step (1) and re-solve the system (6) -(7) based on the new inventory X t+1 and the new state S t+1 .
We just have to compute prices for single (current) market situations and to regularly refresh prices in response to changing market situations. Note, a single recomputation of (6) -(7) is very fast and does neither increase with the number of competitors nor increase with the number of dimensions of the market situation.

Sales Probabilities
In this section, we assume that market situations are only characterized by the point in time t and the prices of K competitors. The vector of prices p := (p 1 , ..., p K ) does not necessarily have to be ordered. To be able to demonstrate the applicability and the performance of pricing strategies, cf. next Section 5, we need to quantify realistic sales probabilities in competitive markets. Instead of using made-up or highly stylized demand probabilities (e.g., of linear, exponential, or isoelastic type), we seek to use a more general (data-driven) demand setting. As an example, we define such probabilities based on a logistic regression model using linear combinations of state-dependent features/regressors x = x(a, s) and given coefficients β; i.e., we consider binary probabilities of the form, t = 0, 1, ..., T , a ≥ 0, i ∈ {0, 1}, where the logit probabilityP (a, s) is given bŷ The dependent variable is the number of sales within a certain time frame. In the following definition, we give simple examples of explanatory variables. In this framework, further explanatory variables can be easily defined to capture the impact of various effects, such as customer ratings, product quality, shipping time, the type of product (categories/clusters), etc.
The demand coefficients defined in Example 4.1 are based on a large data set (>20 M observations/month) from the Amazon market for used books including 100 000 different products and up to K = 20 competitors, cf. Schlosser et al. (2016). The average length of a period is 2.4 hours.
Given the market situation p described in Example 4.1, Figure 1a illustrates sales probabilitiesP (a, p) for different potential offer prices a. As expected, we observe that the sales probability decreases with the price a, cf. Definition 4.1 (ii) and β 2 := −0.56 < 0. The jumps in Figure 1a occur whenever the price rank changes. Note, undercutting a competitor's price yields a better price rank, which can easily double the sales probability. The corresponding expected profits (a − c) ·P (a, p) for one period of time are shown in Figure 1b. Expected profits are positive as long as a exceeds the shipping costs c. The peaks in Figure 1b are caused by the price rank related jumps ofP (a, p). In this example, expected profits are maximized if one slightly undercuts the best competitors' price, i.e., p 1 = 5.18. Our approach to model sales probabilities is simple yet reasonable, especially for practitioners. Logistic regression is a well-understood method and allows to handle hundreds of features and millions of observations.
Regression results are robust and can be directly interpreted. Nevertheless, our model also allows to calibrate sales probabilities using other approaches (e.g., using decision trees, see Quinlan (1986), or gradient-boosted decision trees, see Chen, Guestrin (2016), etc.).

Numerical Examples
In the following, we demonstrate the applicability of our repricing approach in competitive markets, cf.
Algorithm 3.1. We illustrate the computation of the heuristic strategy using the sales probabilities defined in Section 4.1.
Example 4.2. We consider the setting of Example 4.1. We let T = 100, c = 3, δ = 0.9995, N = 25, l = 0.01, and assume the exemplary state s = p = (5. 18,5.96,6.31,8.28,9.48,9.88,10.33,10.98,11.67,13.52). We illustrate state-dependent prices of our heuristic, cf. The value function ( Figure 2) and the associated heuristic feedback prices ( Figure 3) are illustrated for the setting of Example 4.2. Figure 2a and 2b summarize (approximated) expected profits at a current time t in state n given the market situation s. As inventory holding costs are included in the model it is not advantageous to store too many items. In this example, we observe that at time 0 one should not store more than 15 items. If 20 periods of time are left (t = 80) the best expected profit can be gained by offering 5 items. Having more items in stock is unfavourable due to inventory holding costs. Figure 3 illustrates prices that are recommended by our heuristic at a current time t in state n given the market situation s = p. We observe that prices are higher the less items are left to sell and the more time is left. For instance, if more than 50 periods of time are left and there is only one item left to sell the price is 9.47 = p 5 − 0.01 (rank 5). If more than 60 periods of time are left and there are 2 or 3 items left to sell the price is 8.27 (rank 4). If more than 3 items are left to sell the price is either 5.95 (rank 2) or 5.17 (rank 1) depending on the time-to-go. If more than 7 items are left in stock the price a t (n, s) will occupy price rank 1 at every point in time. Note, price rank 3 (6.30) is not chosen at all since the difference between price rank 2 and 3 is too small. Next, we demonstrate the applicability of our approach in competitive markets with many active competitors and unknown strategies. We consider a numerical example that can be reproduced by the reader.
Example 4.3. We consider the setting of Example 4.2, i.e., we let T = 100, c = 3, δ = 0.9995, N = 10, d = 10, l = 0.01. We simulate competitors' price trajectories over time as follows. We let competitors adjust their prices using random reaction times and randomized price changes. The probability that a single firm The random amplitude of price jumps are normalized via h, T , and π such that average trends over time are the same even if the frequency of price jumps (cf. π) or the period length h are different. Initial prices p 0 are chosen as in Example 4.2. We simulate price trajectories using four scenarios of randomized price adjustments, cf.
iv) strategic competitor: Consider setting (i), in which the other competitors' price adjustments are mutual independent and have no trend. One single firm, however, plays a strategic price adjustment strategy by steadily undercutting our price by ε=0.2.
In this example, we also consider stock-outs of firms by simulating competitors to exit the market at random times. Similarly, we allow new competitors to enter the market with a random starting price. Our realized sales are simulated using sales probabilities for time intervals Our firm adjusts its price at t = 0, 1, ..., T − 1 according to Algorithm 3.1; for ease of simplicity, we useP t (i, a| s) := P ois(d ·P (a, p)).
For case (i) -(iv) of Example 4.3, the four subfigures of Figure 4 show price trajectories of the competing firms over time. The price trajectory of our firm can be identified by little blue bullet points indicating the price adjustments at times t, t = 0, 1, ..., T − 1, according to the strategy defined in Algorithm 3.1 for the observed states S t and remaining inventory levels X t . In this context, the black decreasing step function illustrates the remaining inventory level of our firm. The evaluation of each scenario takes less than a second.
In scenario (i)-(iii), we observe that the heuristic strategy slightly undercuts other competitors, cf., Figure   4a, 4b, and 4c. Furthermore, we observe two effects. First, if the prices of the competitors are high, then the strategy occupies leading price ranks, see Figure 4b; if competitors' prices are low, it is more profitable to use moderate price ranks, see Figure 4c. Second, at the end of the time horizon the strategy occupies leading price ranks. Scenario (iv) illustrates the case of an aggressive strategic competitor. We observe that the interplay of the strategic competitor's and the price adjustments of our heuristic lead to specific cyclical price patterns, cf. Figure 4d, which have similarities to Edgeworth-price cycles, see, e.g., Maskin, Tirole (1988) or Noel (2007. Whenever the price level is too low, our firm raises the price up to a certain level. Note, the heuristic strategy just responds to market situations, prices are not anticipated.  Note, the number of computation steps of Algorithm 3.1 does not increase with the number of competitors.
The approach remains also applicable if the competitors' price adjustments are mutually dependent. The repeating price adjustments of our firm allow to respond to any change of the market environment.
Moreover, the approach allows to take additional factors, such as ratings, product conditions, or shipping times into account. These extensions will only affect the sales probabilities of the model, e.g., by using additional explanatory variables, cf. Definition 4.1. The simple optimization of the model, however, is not affected, since the number of computation steps of Algorithm 3.1 does not increase. Our approach allows to directly include dozens of features and dozens of competitors without increasing the model's complexity.
The following remark summarizes important managerial recommendations.

Remark 4.2. (Managerial recommendations)
(i) If market conditions can be assumed to be overall stable, a reasonable initial inventory can be determined based on max n≥0 {V 0 (n, s)}, cf. economic order quantities.
(ii) It is mostly optimal to undercut one of the competitors' prices by the smallest unit (e.g., 1 cent).
(iii) As expected, discounting motivates short-term profits and leads to more aggressive, i.e., lower feedback prices. Hence, a lower (higher) discount factor δ can be used to increase (or decrease) the overall aggressiveness of the strategy. This "instrument" can also be used to actively manage the total inventory of a firm as well as its cash flow. If negative (or positive) price trends can be anticipated, cf. Fig. 4b (and 4c), the aggressiveness of the strategy can also be used to further improve the heuristic strategy.

Measuring the Performance of the Heuristic Strategy
In this section, we want to measure the performance of our strategy derived in Section 3. We consider the case of many active competitors, cf. Section 5.1, as well as the case of strategic competitors that strategically respond to our price adjustments, cf. Section 5.2. In Section 5.3, we analyze the case in which our strategy is played against itself.

Heuristic vs. Optimal Forward-Looking Strategies in Dynamic Oligopoly Competition
We measure the performance of our heuristic by comparing its expected profits to upper bounds determined by optimal expected profits for the case that the competitors' future prices are completely known in advance. In this subsection, we assume that the competitors' prices are not affected by our price decisions.
Let H denote the number of subperiods of one period, and let h := 1/H, e.g., H = 10 and h = 0.1. We assume a realization of competitors price trajectories over time via step functions p t , t = 0, h, 2h, ..., T − h.

Deriving Upper Bounds: Evaluation of Forward Looking Strategies
As we look for upper bounds, in this subsection, we consider the true probabilities P Next, we consider a second version of the anticipating strategy above, which adjusts prices less often.
Price updates are only allowed at t = 0, 1, ..., T − 1 instead of t = 0, h, ..., T − h. To still be able to use a recursive computation (backward induction), we use a − to store our most recent offer price in an extended state space. The optimal (forward-looking) pricing policy a Note, the action space in (10) is time-dependent and guarantees that price adjustments are only admissible at t = 0, 1, ..., T − 1 while at all other times the fixed previous price a − is used. In (10) also perfect price anticipations are used.
Further, using the property that it is advisable to undercut one of the competitors' prices by the smallest unit ε, cf. Remark 4.2 (ii), we can accelerate the computation of (10) significantly: (i) instead of A, we use the smaller action setÃ t := k=1,...,Kt (p

Evaluation of Non-Anticipating Heuristics
Next, we show how to analytically evaluate the non-anticipating policy described in Section 3, cf. Algorithm 3.1. First, we allow prices to be adjusted only at time t = 0, 1, ..., T − 1. The corresponding heuristic strategy, cf. Algorithm 3.1., is denoted by a H(1) . We consider given (conditional) probabilities P (1) t (i, a| p) for periods (t, t + 1), t = 0, 1, ..., T − 1. The prices a H(1) (n, p t ) are determined by the arg max of, t = 0, h, ..., T , n = 0, 1, ..., N , V The recursion (12)  Next, we also consider a second version of the heuristic above, which adjusts prices more often. Allowing the heuristic, cf. Algorithm 3.1., to adjust prices at all t = 0, h, ..., T − h, we define the corresponding policy which is a generalization of (11) using periods of length h instaed of 1 and usingP
Lemma 5.1. For any given scenario of price trajectories p t , t = 0, h, ..., T , for all n = 1, ..., Proof. The first inequality of (i) holds since in (9) prices can be adjusted at additional points in time compared to (10). The second inequality of (i) holds since in (10) the set of admissible prices includes those of (12). Assertion (ii) follows from similar arguments.
Finally, we quantify the performance of our heuristic strategies compared to the upper bounds derived.
We simulate price trajectories using three families of randomized price adjustments, k = 1, ..., K, K = 10, t = 0, h, ..., T − h, h = 0.1, and different adjustment probabilities π = 0.01, 0.03, 0.1, 0.3: In the three settings of Example 5.1, we apply the following five different strategies, cf.    The relaxed heuristic strategy (D) yields 63-96% of the optimal results; the frequent heuristic strategy (C) even obtains 93-99%. The performance of the strategies (B) and (C) is in between those of strategy (A) and (D), cf. Lemma 5.1. We observe that the more volatile the market, the more important become adjustment frequencies. Our example shows that the frequent heuristic strategy (C) can even beat the relaxed informed strategy (B). The best fix price strategy (E) only yields 35-84% of the optimal profits, although future prices are fully known. A boxplot of Table 1 is given in the Appendix, see Figure  In further simulations, we also varied other parameters, such as time horizon T , initial items N , number of competitors K, as well as the demand parameters β or the adjustment dynamics of the competitors.
Overall, the results were similar. We summarize the most important findings in the following remark.
Remark 5.1. (Impact of adjustment frequencies and price anticipations) (i) In general, adjustment frequencies as well as price anticipations significantly raise profits.
(iii) The performance of fix price strategies is low, even if they are optimally chosen and perfect price anticipations are taken into account. (iv) If market prices have a positive trend, cf. scenario (ii), then price anticipations are more important than frequent price adjustments.
(v) If market prices have a negative trend, cf. scenario (iii), then frequent price adjustments are more important than price anticipations.
(vi) If prices are adjusted frequently, then price anticipations are less important.
(vii) If market volatility is high, then it is important to adjust prices frequently.

Heuristic vs. Optimal Response Strategies in Strategic Duopoly Competition
In this subsection, we consider strategic competitors, who choose his/her prices in response to our current price. The goal is to compare our heuristic approach to optimal response strategies. Since optimal response strategies cannot be computed for complex competition settings (due to the curse of dimensionality), we consider a duopoly setting.

Optimal Response Strategies in a Duopoly
We want to compare the performance of our heuristic strategy derived in Section 3 to upper bounds, which are determined by optimal response strategies that make use of full information. We assume that the price reaction of the competitor as well as the reaction times can be fully anticipated. Note, our heuristic strategy does not use this additional information, which corresponds to real-life scenarios.
We assume that the market situation (state) is one-dimensional and simply characterized by the competitor's price p, i.e., we let s := p. We assume that the competitor adjusts its price p in response to our price a with a fixed delay of ∆ periods, 0 < ∆ < 1. Choosing a price a at time t is followed by the competitor's price reaction F , which can depend on p and a. I.e., after an interval of size ∆ the competitor adjusts its price from p to F (a, p). Consequently, our reaction time is 1 − ∆.
Following the examples of the previous sections, in period t the probability to sell exactly i items during the first interval of size ∆ (Phase 1) is P (∆) t (i, a, p) := P ois(∆ · d ·P (a, p)). For the rest of the period (Phase 2) the sales probability changes to P F (a, p))).

Heuristic Response Strategies in a Duopoly
In case neither the competitor's strategy nor his/her reaction time ∆ is known, our heuristic strategy, cf.

Comparison of Strategies in a Duopoly
Next, we want to measure the performance of the heuristic compared to the optimal (informed) strategy.
The following example studies one of the most common strategies which always slightly undercuts the competitor's price, cf. Example 4.3 (iv), Fig. 4d. We also study impact of the reaction time ∆ as well as the accuracy of the estimation ofP  (18). Figure 5 shows optimal response strategies for Example 5.2 (i) -(iii) at time t = 0 for different inventory levels n and competitor's prices p in case of ∆ = 0.5. Figure 5a illustrates the optimal policy; Figure 5b and 5c depict the heuristic policy in case (ii) and (iii), respectively. The optimal response strategy (i) is of similar shape for different inventory levels: If the competitor's price is very low, it is optimal to raise the price up to a certain price level. Almost the same price level has to be chosen if the competitor's price is very high. If the competitor's price is somewhere in between (intermediate range), it is best to undercut that price by one price unit ε. If n increases, then the upper price level decreases; the intermediate range is of the same size but at a lower level. Note, the policy of case (ii) is independent of ∆ as the reaction time is neither explicitly nor implicitly taken into account. We observe that the intermediate range of the optimal policy is increasing in ∆. Policy (i) and (iii) are quite similar for all ∆ values. If ∆ is large then policy (ii) is similar to the other two. If ∆ is small then policy (ii) differs significantly.
The application of the optimal and both heuristic strategies leads to cyclic price patterns over time, cf.
Edgeworth cycles, see, e.g., Maskin, Tirole (1988) or Noel (2007). The resulting price paths for the optimal response strategy and the heuristic strategies are shown in Figure 6. We observe that compared to heuristic (ii) the cycle length and the amplitude of the price patterns are smaller for the optimal policy (i) and the heuristic (iii). Finally, we obtain that heuristic (iii) is very similar to the optimal strategy (i).
The cyclic price patterns are basically independent of the initial price. Hence, if the time horizon and the discounting factor are not too "small" then the expected future long-term profits V (∆) * (n, p) andV (∆) 0 (n, p), respectively, are (almost) the same for different initial prices p (in our example the maximum deviation is 0.1). The number of items left to sell and particularly the reaction time ∆ plays a more prominent role.
Finally, we observe that the performance of our heuristic is quite promising. Although the heuristic does not anticipate the competitor's blue reaction, in case (ii), 94-98% of the theoretically optimal expected profits are obtained; in case (iii), we obtain even 98-99%.
If the competitor's reaction time ∆ is small, the results of heuristic (iii) outperform those of heuristic (ii) by up to 5%. The reason is the following: If ∆ is large then the market situation hardly changes during one period of time and, thus, P (1) andP (1) are almost identical. If ∆ is small then the market situation quickly changes, i.e., P (1) andP (1) differ significantly, and in turn, the performance of the heuristic suffers.

Comparison of Reaction Times in a Duopoly
Due to the significant impact of reaction times, firms will try to minimize their reaction times by anticipating their competitors' time of adjustment and to time their price adjustments optimally. In order not to act predictably, in turn, strategic firms might randomize their reaction times. Finally, the percentage of time a firm has the most recent price will be determined by the ratio of the firms' adjustment frequencies.
Refreshing the prices x times as often as the competitor can be compared to our model with ∆ := x/(1 + x), or x = ∆/(1 − ∆), x > 0. For instance, the ratio x = 2.33 corresponds to a value of ∆ = 0.7. Note, while some firms adjust their prices once a day, other firms adjust their prices every one or two hours.
In the following, we study to which extent expected profits of our strategies are affected by ∆. Following Example 5.2, we compare the expected profits V (∆) * of the optimal policy andV (∆) of the heuristic policy with the benchmark profit V (0.5) * (for the case ∆ = 0.5 or x = 1, respectively).    Table 3 illustrates the ratio V (∆) * /V (0.5) * as well as the ratioV (∆) /V (0.5) * for different n and ∆ in case (i) -(iii) of Example 5.2. We observe that the reaction time ∆ has a significant impact on expected profits. On the one hand, our example shows that small reaction frequencies can shrink expected profits by more than 20%, cf. ∆=0.1. On the other hand, heuristics using shorter reaction times or more frequent price adjustments, respectively, can easily overcompensate a lack of information, cf. ∆=0.55, and increase expected profits by more than 20%, cf. ∆=0.9. We conclude that the more volatile the market is, the more important is it to use an accurate estimation of conditional probabilitiesP , which are also characterized by the own adjustment frequency. Note, it is not necessary to know the competitors' reaction strategy -the information of the competitors' behavior and the market dynamics are implicitly contained inP . (ii) To circumvent the curse of dimensionality, we simplify the problem: While the reduced state space of "time and inventory level" allows for fast optimization, in our model the anticipation of market evolutions is transferred to the model's sales probabilities. The inaccuracy of our simplifying "stability assumption"which is the key for the decomposition -can be compensated as frequent observations of the current market situation and corresponding price adjustments keep the system up to date.
(iii) In real-life applications, the conditional sales probabilities of the model can be estimated from market data using state-of-the-art regression models (logistic regression, decision trees, neural networks, etc.).
Our examples verify that the performance of our heuristic compared to optimal policies (that use full information) is excellent even if strategic competitors are involved. While optimal solutions are limited to very few competitors, the heuristic strategy instead can easily be applied in the presence of even very large numbers of competitors. Since the state space of the heuristic approach just consists of two dimensions, the computation of prices is constantly fast. Hence, it is ensured that it is possible to compute prices for complex situations and to adjust prices with high frequencies.

Heuristic vs. Heuristic Response Strategies in Strategic Oligopoly Competition
In this subsection, we study the case in which our heuristic strategy is played by multiple firms against each other. In the next example, we consider such a scenario.   Figure 7a illustrates a scenario in which the heuristic strategy, cf. Algorithm 3.1, is played by multiple firms. We observe that firms undercut each other until a certain price level is obtained. Then firms -one after another -raise their prices up to a certain maximum. This evolution is similar to the price patterns of Figure 6, cf. Example 5.2. We observe, that the length of price cycles is longer if less firms are involved. The evolution of the inventory levels of all firms is shown in Figure 7b. Firms exits the market due to stock-outs (t = 88 and t = 96, cf. Figure 7b). Overall, we observe that the heuristic feedback strategy is "reasonably aggressive" but not "destructive" and effectively avoids a decline in price (race to the bottom). Note, this character has similarities to equilibrium strategies.
In case reaction times and inventory levels are observable and firms are rational, best response strategies could be derived using backward induction. This assumption, however, appears not to be a realistic one.
Pricing strategies of firms will depend on time and their inventory level, which, in general, is not observable for competitors. Hence, we have competition with asymmetric information. In this setting, equilibrium pricing strategies will be hard to determine. Mutual best response strategies might use observations of offer prices to estimate probability distributions for the competitors' remaining inventory (Hidden Markov Model), cf. Schlosser, Richly (2018). However, the applicability of such models is again limited due to the curse of dimensionality.
Finally, our heuristic is a viable and successful strategy to be applied in competitive real-life markets.
Moreover, our heuristic is also a suitable strategy to be played as a response against itself.

Price Adjustment Costs
In the previous sections, we have assumed that price changes are free. Hence, frequent updates can be used to compensate for the lack of market anticipation. However, in some markets the number of price updates are limited or may create even (hidden) costs as frequent price adjustments may confuse customers and reduce their trust. Hence, it can be reasonable to put penalties on price changes in order to implement only necessary price adjustments.
In this context, we present a model with a fixed penalty z for each price adjustment. To be able to include price adjustment costs in our dynamic programming framework, cf. (4) - (7), we extend the state space by one dimension -the offer price a − of the previous period, a − ∈ A. The costs z, z > 0, of a price change occur if the price update a differs from the previous price a − . To model the case in which no previous price exists, we let a − := 0.
For any market situation s the natural boundary condition for the value function is given by, cf. (4) - The remaining values V t (n, s, a − ) are defined by the HJB equation, n = 1, ..., N , t = 0, ..., T −1, a − ∈ A∪{0}, where the indicator function 1 {a =a − ∧a − >0} is 1 if a = a − and a − > 0, it is 0 if a = a − or a − = 0. The transition of the new state component is straightforward -the new price a becomes the old price a − of the next period. Again, the associated pricing strategy is determined by the arg max of (20), n = 1, ..., N , Algorithm 3.1 can still be used in the same way. The numerical complexity is slightly higher but tolerable. Due to adjustment costs, prices are only updated if opportunity costs (of not updating the price) are sufficiently large. The larger z is chosen, the less price updates will be made. Note, compared to our previous models, in general, larger delays between two price adjustments (i.e., lower adjustment frequencies) also lead to less price updates, but they sacrifice the advantage of fast reactions to changing markets. Hence, the model above allows for fast reactions and a reasonable limitation of the number of price updates.

Evaluation in Practice
To evaluate the real-life performance of the presented approach, we applied our heuristic strategy on Amazon Marketplace. Online market platforms such as Amazon or eBay are highly dynamic as sellers can observe the current market situation at any point in time and adjust their prices instantly. This dynamic is hard to manage as pricing decision requires handling a multitude of dimensions for each competitor (price, quality, seller ratings, etc.).
In this experiment, we have partnered with a German bookseller. The seller is among the top 10 sellers for used books on Amazon in Germany and has an inventory of over 100 000 distinct books (ISBN), each with multiple items (1-20). Our seller can decide -to some extent -on the replenishment of used books (by adjusting purchase prices). However, supply is limited and it is not possible to directly reorder specific (used) books. Hence, the challenge is to extract as much profit as possible from a given number of books (cf. inventory level) in a reasonable amount of time. The pricing strategy of our project partner is characterized by a rule-based system that has been developed over the past years by carefully adjusting rules to lessons learned from selling books on Amazon. As our project partner has more than ten years of experience in the market, we consider his strategy to be effective and accurate. However, market dynamics are increasingly sophisticated making rule-based strategies increasingly hard to handle and maintain.

Implementation and Architecture
As our approach is designed to be applied in practice, we needed to calibrate the model, i.e., holding costs, shipping costs, discount rate, and particularly the sales probabilities, which are based on multiple offer dimensions. Requested market situations for a certain product from Amazon Marketplace include product-specific features (e.g., Amazon sales rank) as well as merchant-specific features (price, quality, seller ratings, feedback count, etc.). The most important offer dimensions are summarized in Table 4.    Based on predicted sales probabilities for a product's market situation (Step 4), cf. Demand Learning, the Price Optimization determines a price and the price update is sent back to Amazon (Step 5).
As the rate with which sellers can request market situations and update prices is limited, products of higher importance are stored in the most frequently updated queue. On the other hand, products which do not face strong competition or are expected to be accessed less often by customers, are stored in the least frequently updated queue. The queuing mechanism updates products every 2-12 hours (i.e., 2-10 updates per book per day), which results in >20 M observed market situations per month. Considering on average seven competitors per market situation corresponds to >140 M single competitor observations per month.
The majority of requests also lead to a price update.
Another used service is the Push Notification Service, cf. Figure 9, which informs sellers of products sold on the Marketplace platform. Sellers can store both data streams (requested market situations and pushed sales) locally in a database. We join the market data with our partner's price updates, placed orders, and stock data to create the required observations and the corresponding features (cf. Definition 4.1). Working directly on the raw time-series data provides us with more flexibility, e.g., when regressing only a subset of comparable market situations. The components regularly train a regression model that allows to predict sales probabilities for any market situation.
Our estimations of sales probabilities for a specific book in a certain time interval are based on market situations, which are characterized by product-specific features as well as multiple competitor-specific offer dimensions for each present competitor, cf. Table 4. We defined 30 customized features (explanatory variables, cf. Section 4.1) to describe the relative competitiveness (i.e., sales probabilities) of a single offer in a particular market situation. We used features similar to those described in Definition 4.1 such as, e.g., the price rank of our offer price within the present competitors' prices, etc. Besides price also other offer  Figure 9: Illustration of the data-driven price update process of a merchant on Amazon Marketplace.
dimensions were taken into account. To reduce estimation biases, in an exploration phase, also a certain share of randomized prices updates were used by the seller.

Performance Results
We tested different demand learning techniques to quantify how sales probabilities of specific products are affected by our offer prices in specific market situations. We decided for a weighted logistic regression approach to estimate probabilities to sell a certain book within a certain time frame at potential offer prices given a particular market situation. We calibrated our dynamic programming model, cf. Section 3, based on the estimated (conditional) sales probabilities (P ). Using our heuristic approach, we computed price adjustments for exemplary product offers in specific market situations and checked their plausibility compared to the merchant's strategy and experience. The application of our dynamic pricing strategy works as described in the previous sections, cf. Algoritm 3.1. Note, as discussed earlier, the extension of the dimensionality of the market situation does not affect the algorithm's complexity.
Finally, we used the calibrated model to determine heuristic pricing strategies to be applied on the Amazon Marketplace. In our experiment, we used four different discount factors (δ (1) > δ (2) > δ (3) > δ (4) ) to vary the strategies' aggressiveness, cf. strategy S (1) -S (4) in Table 5. S (4) is the most aggressive strategy; S (1) is the most tame strategy, cf. Remark 4.2 (iii). Over two months, we compared our datadriven strategies with the seller's rule-based benchmark strategy. To each strategy, we randomly assigned a test group of around 3 300 books. To guarantee a fair comparison of the quality of a strategies' pricing decisions, the price adjustment frequencies were the same for the merchant's benchmark strategy and our four data-driven strategies.  tradeoff between profitability and speed of sales. Moreover, strategy S (4) reveals that our approach can sell faster (+3%) and at the same time more profitable (+12%) as the seller's benchmark strategy.

Strategy
Relative accumulated profit Benchmark 100% S (1) + 3% S (2) + 17% S (3) + 24% S (4) + 15% In Table 6, we compare the accumulated profits of all strategies. The relative accumulated profit denotes the quantity "profit per sale (EUR) × % of items sold" compared to the corresponding value of the benchmark strategy. Results show that with our strategy applied, profits can be increased by more than 20%, cf. S (3) . Moreover, the model's discount factor can be used as a management instrument to smoothly balance profits, revenues, and the speed of sales according to a seller's needs.
The individual price patterns of the merchant's benchmark strategy and our data-driven strategy highly depend on (i) the specific article involved, (ii) the number of competitors, (iii) the competitors' offers, (iv) the kind of competitors (commercial, private, strategic) involved, and (v) the price reaction frequencies of competitors. In general, it is advisable not to exclude higher price ranks in advance. Instead, multiple offer dimensions of competitors' offers have to be taken into account. Price adjustment frequencies and reaction times play a prominent role, particularly, when the customer arrival intensity is high. Further, a successful strategy has to balance two effects: a decline in price by undercutting competitors and moderate price decisions that retain/restore a profitable price level.

Conclusion
Dynamic pricing under strong competition and incomplete information is a major open problem in revenue management. Practical relevance is enormous, but the problem appears intrinsically hard due to the curse of dimensionality. The challenge is to derive viable heuristic approaches that (i) can be applied in various settings, (ii) allow for data-driven demand estimations, (iii) achieve near-optimal performance results, and (iv) have minimal computation times.
We have shown how to compute dynamic pricing strategies under competition. We have demonstrated that our heuristic approach is applicable even if the number of competitors is large and the competitors' strategies are unknown.
Due to the intractibility of the problem, in general, neither optimal policies nor performance guarantees can be derived. To measure the performance of our strategy, we computed upper bounds for expected profits, which are obtained by optimal strategies that take advantage of price anticipations. We observed that reaction times have a major effect on the performance of dynamic pricing strategies. Moreover, we found that higher adjustment frequencies can easily overcompensate a loss in expected profits due to the lack of price anticipations. Adjusting the price more frequently can be more advantageous than anticipating future market dynamics. Our heuristic approach allows for frequent price adjustments as the computation of prices is efficient and fast. Furthermore, in order to choose the number of price adjustments with care without sacrifizing a short reaction time, we present an extended version of the model which allows to take price adjustment costs into account.
Our approach is based on conditional sales probabilities that are estimated from observable market data.
Market situations are allowed to be high-dimensional and might also include multiple product features, such as quality, ratings, shipping time, etc. Estimated (conditional) sales probabilities make it possible to capture the essence of market dynamics as the impact of (even unobservable) market evolutions on sales probabilities is implicitly included. Thus, it is not necessary to know competitors' strategies explicitly or their reaction times, but we can still take their characteristic behaviour into account. Note, on average, this also includes the impact of exits or entries of new competitors. Finally, changes of market situations are captured within the framework of regular market observations and price adjustments.
Using numerical examples that are based on real-life data, we verified the performance of our heuristic pricing strategy. In a real-life experiment, we outperformed the rule-based strategy of an experienced seller by more than 20%.
Finally, our approach combines key features that are important for real-life applications. First, the approach is applicable if many competitors are involved and offers have multiple features. Second, market dynamics do not have to be explicitly known, but they can be indirectly taken into account using data-driven demand estimations. Third, the computation of prices is efficient, easy to implement, and allows for frequent price adjustments.  (n, p) (left window A.12a) and heuristic prices (iii)ã (∆) 0 (n, p) in case (iii) (right window A.12b) for n = 1, 2, 3, 5, T = 100, ∆ = 0.9; Example 5.2.