Abstract We study the dynamic pricing problem faced by a monopolistic retailer who sells a storable product to forward-looking consumers. In this framework, the two major pricing policies (or mechanisms) studied in the literature are the preannounced (commitment) pricing policy and the contingent (threat or history dependent) pricing policy. We analyse and compare these pricing policies in the setting where the good can be purchased along a finite time horizon in indivisible atomic quantities. First, we show that, given linear storage costs, the retailer can compute an optimal preannounced pricing policy in polynomial time by solving a dynamic program. Moreover, under such a policy, we show that consumers do not need to store units in order to anticipate price rises. Second, under the contingent pricing policy rather than the preannounced pricing mechanism, (i) prices could be lower, (ii) retailer revenues could be higher, and (iii) consumer surplus could be higher. This result is surprising, in that these three facts are in complete contrast to the case of a retailer selling divisible storable goods [Dudine et al., 2006 ]. Third, we quantify exactly how much more profitable a contingent policy could be with respect to a preannounced policy. Specifically, for a market with N consumers, a contingent policy can produce a multiplicative factor of Ω(log N ) more revenues than a preannounced policy, and this bound is tight. Abstract 1 A firm may wish to reduce the lifespan of a durable good to avoid a Coasian outcome, that is, one where the firm loses all monopoly power. Indeed, Amazon has recently been granted a US patent (8,364,595) for a second-hand market in digital goods that restricts the number of times a good can be resold, that is, limits the longevity of the goods. Apple has applied for a similar patent (US 20130060616 A1). Abstract 2 A durable good is a long-lasting good that can be "stored" and consumed repeatedly over time. Examples include digital goods, land and, to a large degree, housing, metals, electronic goods, etc. Introduction The problem of determining an optimal pricing policy for a monopolistic retailer has attracted the attention of many researchers from Economics and Operations Research. This interplay between a retailer that dynamically sets up prices and consumers who anticipate future price reductions and/or future prices increases may sometimes lead to surprising equilibria. Some relevant questions in this topic are: What does the price path look like in an equilibrium? How profitable can the retailer be, and what pricing policy should it use? Is it possible to compute the optimal pricing policy efficiently? In this paper we study the dynamic pricing problem faced by a retailer (a monopolist) who sells storable goods to forward-looking consumers along a finite time horizon. Storable goods are goods that can be stored for a long period but then loses all value after its first use. Prominent examples of storable goods include non-perishable grocery items and many natural commodities, for example, oil and natural gas. A less conspicuous example concerns digital goods. Digital goods are durable, but the technology often exists to make them perishable and, thus, convert them into storable goods. 1 Dynamic pricing, a practice which is very common in most industries, can be seen as a weak form of price discrimination. The retailer does not dictate how consumers are segmented, but rather consumers segment themselves by self-selecting the time (and corresponding price) at which they prefer to buy the item. A classic and well studied dynamic pricing problem occurs when a monopolist sells a durable good to strategic consumers. 2 In this setting, Ronald Coase [1972] conjectured that a durable good monopolist who lacks price commitment cannot sell the good above the competitive price. Stokey [1979] then showed that the optimal preannounced pricing policy consists of setting a fixed price. Introduction The Coase conjecture was first proven by Gul et al. [1986] under an infinite time horizon model with non-atomic consumers. However, the conjecture relied upon several assumptions, such as that the time between periods approaches zero and that there is an continuum of consumers. Since then, there have been several studies regarding the performance of different pricing policies for various economic models for durable goods, perishable goods, under different time horizons. Güth and Ritzberger [1998] studied a finite horizon model with a continuum of consumers (i.e. non-atomic demand) and showed that when consumer valuations follow a uniform distribution, there exists a subgame perfect equilibrium, as period lengths approach zero, in which the monopolist profits converge to the static monopoly profits discounted to the beginning of the game. Bagnoli et al. [1989] studied the durable good monopoly problem in which there are finite (atomic) consumers (i.e. discrete demand). When the time horizon is infinite, they proved a surprising result: the existence of a subgame perfect Nash equilibrium in which the duropolist extracts all the consumer surplus. This equilibrium refutes the Coase conjecture when there is a finite set of atomic buyers and an infinite time horizon. Indeed, it shows there exists a subgame perfect Nash equilibrium where duropoly profits exceed static monopoly profits by an unbounded factor. Berbeglia et al. [2014] studied the same model as Bagnoli et al. [1989] and proved that when there is a finite time horizon the monopolist profits cannot exceed twice the static monopoly profits. Dasu and Tong [2010] analyzed preannounced pricing policies for a retailer for the case in which consumers are finite and the number of items are limited (i.e. there is an availability constraint). The authors showed that dynamic pricing (through preannounced pricing) is beneficial for the retailer, but the benefit decreases as the market size increases. Su [2007] studied contingent (subgame perfect or threat) pricing policies in a finite time horizon model where consumers, who arrive continuously, are heterogeneous in their valuation and in their patience. The author characterized the structure of optimal pricing policies and showed that, depending on what population type dominates the market, prices are increasing or decreasing. Aviv and Pazgal [2008] studied contingent pricing and preannounced pricing equilibria for a related two-period model of a retailer selling a finite number of items to strategic consumers that arrive under a Poison process. The authors proved that a preannounced policy, with respect to contingent pricing, can increase monopoly profits by up to eight percent. Li [2001] consider optimal pricing policies for another model where items are also limited inspired by the revenue management problem faced by airlines. The potential benefit of strategic capacity rationing under preannounced pricing was analyzed by Liu and van Ryzin [2008] in a two period pricing model of a durable good. Their main result is that rationing can be beneficial for the retailer but only when consumers are risk-adverse. Recently, Correa et al. [2016] studied a new type of pricing mechanism so called contingent preannounced pricing in which the retailer commits to a price menu which states what would be the future price as a function of the number of available inventory. The authors showed that under this pricing policy, there exists a unique equilibrium when there is a single unit of inventory, but multiple equilibria may exist otherwise. Computational experiments showed that the contingent preannounced pricing outperforms previously proposed pricing mechanisms. Other models of durable good markets that incorporate multi-generation products and the effects of price sensitivity has been studied by Kuo and Huang [2012] and Liberali et al. [2011] respectively. Introduction A related setting in which there is a complex dynamic interaction between a retailer and the consumers is when the good is storable -a storable good is a good that can be stored prior to consumption but it is not durable as it perishes upon consumption. Consequently, as stated, such a good can be stored for a long period but then loses all value after its first use. Prominent examples of storable goods include non-perishable grocery items and many natural commodities, for example, oil and natural gas. A less conspicuous example concerns digital goods. As with durable good markets, the consumers in a storable good market can strategically time their purchases by taking into account current and expected future prices. In a storable good market, a consumer who observes a low price promotion sale, may increase her purchases not only to augment the current consumption level (the consumption effect) but also to stockpile the good for future consumption (the stockpiling effect). There is a large amount of evidence from empirical work showing that the stockpiling effect -also known as demand anticipation -is non-negligible in markets for storable goods. For example, Pesendorfer [2002] investigated supermarket price reductions for ketchup products in Springfield, Missouri. His main finding is that demand at low prices depends on past prices, which suggests the existence of a stockpiling effect. Similarly, Hendel and Nevo [2006] examined the price and demand dynamics of soft drinks, laundry detergents, and yogurt from nine supermarkets in the US. This analysis also showed that demand increases during price reductions are, in part, due the stockpiling effect. To capture the potential for stockpiling, the models of storable good markets assume that consumers have access to inventory space for an associated cost. 3 Dudine et al. [2006] studied a market where the retailer sells a storable good to consumers with time-dependent demand over an arbitrary (but finite) number of time periods. They proved that, under some mild assumptions on consumer demand, if the retailer uses a preannounced price mechanism then consumers will not stockpile any goods in equilibrium. They also showed that (i) prices are higher, (ii) profits are lower, and (iii) consumer surplus is lower if the retailer uses a contingent pricing mechanism rather than a preannounced price mechanism. These results also suggest, unlike the classical results that proved the Coase conjecture in durable good settings, that monopoly power in storable good markets leads to several inefficiencies. The results of Dudine et al. [2006] have later been extended to other settings of a storable good market, namely a two-level vertically integrated monopoly [Nie, 2009a] , and a duopoly market model [Nie, 2009b] . Other models for storable goods studied in the literature include a continuous time stochastic inventory model for a commodity traded in a spot market [Chiarolla et al., 2015] and a model where the storable good has a fixed shelf-life [Herbon, 2014] . Contributions A major assumption in the storable good market model of Dudine et al. [2006] is that the good is infinitesimally divisible. In addition, they consider that either there is a single consumer in the market who can always obtain some positive additional utility by consuming an additional fraction of the good (no matter how small that fraction is), or that there is a continuum of non-atomic buyers. In this paper we analyze the market of a retailer selling storable goods in which either (1) there is a finite (possibly very large) number of buyers with a unitary demand per period or (2) there is a single buyer with an arbitrary demand per period but who can only obtain an utility from an integral number of items. Equivalently, the items are indivisible. Contributions Our main contributions are as follows. We first characterize the optimal preannounced pricing strategy for the retailer. We then show that it can be computed efficiently and that, under this preannounced price mechanism, the consumers will not stockpile the good. We next show that it is possible for (i) prices to be lower, (ii) retailer's profits to be higher and (iii) the consumer surplus to be higher, if the retailer uses a contingent pricing mechanism rather than a preannounced price mechanism. These last three results are surprising, since they are in complete contrast to the case of a retailer for divisible storable goods [Dudine et al., 2006] . Contributions We then quantitatively compare the profitability of the preannounced price and contingent pricing mechanisms. Specifically, for a market with N consumers, a contingent pricing mechanism can generate Ω(log N) times more profits than an optimal preannounced price mechanism, and this bound is tight. This is notable because previous models with a finite number of periods have the property that the contingent pricing mechanism cannot significantly outperform the preannounced price mechanism. In particular, we explain how our result contrasts with related results for a durable good retailer. Finally, we examine the setting where inventory costs are concave. Interestingly, the consumers may now utilise storage when the retailer uses a preannounced price mechanism. The Model Consider a retailer facing consumers with demands for a consumable good over T time periods. The retailer can produce units of the good at a unitary cost u and wishes to select prices {p 1 , p 2 , . . . , p T } to produce sale quantities {x 1 , x 2 , . . . , x T } that maximize profits, T t=1 p t · q t . We assume, without loss of generality, that u = 0 and consequently, profit and revenue are interchangeable in this setting. For a perishable good with a short shelf-life, the corresponding optimization problem is straightforward as the firm can optimize in each time period independently. The problem, however, becomes more complex and interesting as the shelf-life grows. In particular, we examine the case of storable goods. Storability offers the consumers the opportunity to purchase the good before they actually wish to use it. Indeed, this option is desirable if the resultant price savings exceed storage costs. In accounting for this possibility, the retailer's optimization problem now becomes non-separable. The Model Following the literature, we consider two cases: the single-buyer and the multi-buyer settings. In the former, all the demand comes from a single buyer whose (time-depedent) utility depends on the quantity of indivisible items consumed. In the latter, there is a finite number of consumers, each of them having a single (indivisible) unitary demand per period. In previous studies, the results obtained from these two settings are essentially identical. However, for an indivisible good, these two settings are not equivalent and can produce very different outcomes; see Sections 4 and 5. The Model Our interest lies in analysing and comparing two standard pricing mechanisms: the preannounced price mechanism and the contingent pricing mechanism. In the preannounced price mechanism, the retailer publicly announces in advance (that is, at time t = 0) a price schedule {p 1 , p 2 , . . . , p T } where p t is the per unit price in period t. The consumers can then make their purchasing and storage decisions based upon these prices. In the contingent pricing mechanism, the retailer announces prices sequentially over time. Thus, the announced price p t = p(H, t) may depend not only on the current time period t, but also on past history H. Once the price at period p t is announced, the consumer (or consumers) must decide how many units to purchase and store without knowledge of future prices. For such a sequential game, the solutions we examine are pure subgame perfect Nash equilibria (SPNE). In particular, this restricts our attention to credible contingent pricing mechanisms. The Single-Buyer Case. We begin with case where the retailer faces a unique buyer (monopsonist) for its good. Let the utility the buyer receives from consuming x units of the good at period t be given by the function U(x, t). Units are assumed to be indivisible, and therefore the domain of the utility function U(x, t) is N × [T ]. Assume the buyer faces a set of prices {p 1 . . . , p T } and that the storage cost is c ≥ 0 dollars per unit per time period. The consumer problem then consists of choosing the consumption quantities {x 1 , x 2 , . . . , x T }, the number of units purchased per period {q 1 , . . . , q T }, and the storage levels {S 1 , S 2 , . . . , S T }. These are chosen to maximize her total utility The Single-Buyer Case. subject to the storage constraints that S t = S t−1 + q t − x t , for all t = 1, . . . , T where S 0 = 0. The Single-Buyer Case. The retailer selects the prices {p 1 . . . , p T } in order to maximise the resulting profits T t=1 p t ·q t . As stated, for the preannounced price mechanism the prices are chosen in advance and for the contingent pricing mechanism the prices are chosen sequentially. In analyzing these two mechanisms we make the following standard assumptions. First we assume the buyer's utility function U(x, t) is non-decreasing in x. Second, we assume the marginal utility function is non-increasing in x. Specifically, let V (x, t) = U(x, t) − U(x − 1, t) represent the marginal utility of consuming x units of the good at period t. Then we have that V (x, t) is nonincreasing in x. We also assume that there exists H ∈ N such that V (H, t) = 0 for all t ∈ T . No other restrictions are imposed on the consumer utilities. For notational purposes, we set The Single-Buyer Case. where L is a huge number. The Multi-Buyer Case. Next consider the set-up for the multi-buyer case. We now have a set of N consumers each seeking to maximize their own utility. Each consumer i has a demand of at most one unit per period and the value she obtains if she consumes the unit at period t is u i,t . A consumer i may, however, purchase multiple units q i,t of the indivisible good in any time period and store them for future consumption. Again, there is a storage cost of c per period and per unit stored. This time the retailer chooses prices {p 1 , . . . , p T } to maximize T t=1 p t · q t , where q t = i q i,t is the total number of items sold in period t. The Multi-Buyer Case. For the preannounced price mechanism, the consumers make their purchasing/storage decisions based upon the entire set of prices. For the contingent pricing mechanism, in each time period, the consumers decide (simultaneously) their purchasing/storage quantities for that period, given the current price. As we shall see, these decisions impose constraints on the retailer's optimization problem. In particular, for the contingent pricing mechanism these constraints force solutions to correspond to pure subgame perfect Nash equilibria (SPNE). The Multi-Buyer Case. To simplify notation, let σ t : [N] → [N] denote the permutation that ranks the N consumers in decreasing values of their utilities in period t and let An Example. We now present a small example to illustrate the model and the concepts involved. Consider a two-period game with a per unit storage cost of c = 1 and with consumer valuations given in Table 1 . Here we assume that we are in the multi-buyer case with N = 2; however, it is straightforward to check that our analysis also applies if there is a single-buyer whose marginal utilities for each extra unit are described by the same table. We first calculate the optimal preannounced pricing strategy for this game. Let p 1 and p 2 denote an optimal sequence of prices under the preannounced pricing policy for periods 1 and 2 respectively. We claim that no consumer will ever buy a unit at period 1 and then store it for consumption in period 2. If so, we must have p 2 > p 1 + 1 as it is beneficial to buy early and pay the storage cost. But this cannot be optimal for the retailer as it would then benefit from setting p 2 = p 1 + 1. It follows that the optimal choice for p 1 must either be p 1 = 17 in which case only consumer 1 buys, or be p 1 = 10 in which case both consumers buy. In the former case, the optimal choice for p 2 would be p 2 = 15 yielding a total profit of 17 · 1 + 15 · 1 = 32. In the latter case, the optimal period two price p 2 cannot be higher than 11, otherwise consumer 1 would use storage. Consequently, the optimal price is p 2 = 11, which yields the retailer a profit of 10 · 2 + 11 · 1 = 31. Therefore the optimal preannounced price strategy yields a profit of 32 and consists of setting prices p 1 = 17 and p 2 = 15. An Example. Next we calculate the optimal contingent pricing mechanism. Because prices and actions are chosen sequentially we can compute the optimal contingent pricing mechanism by reasoning backwards from the final time period. So consider time t = 2. In order to select p 2 the retailer will base its decision on the set of items currently stored. If consumer 1 has not stored an item from period 1 to 2 then the retailer will set p 2 = 15, regardless of the prior decisions made by consumer 2. Knowing this, consumer 1 will purchase two items in period 1 provided p 1 + c ≤ 15, that is p 1 ≤ 14. This observation leads to the following four possibilities. (i) The retailer sets p 1 = 17. Consumer 1 then purchases one item in each time period giving a profit of 17 · 1 + 15 · 1 = 32. (ii) The retailer sets p 1 = 14 and consumer 1 purchases two units. Given this, the retailer then charges p 2 = 4 and consumer 2 buys one unit in the last period. This gives a profit of 14 · 2 + 4 · 1 = 32. (iii) The retailer sets p 1 = 10 and consumer 1 purchases two units and consumer 2 purchases one unit. Again, the retailer then charges p 2 = 4 and consumer 2 buys one unit in the last period. This gives a profit of 10 · 3 + 4 · 1 = 34. An Example. (iv) In order to induce consumer 2 to purchase two units in period 1 the retailer will have to charge p 1 ≤ 3 giving profits of at most 3 · 4 = 12. Note that option (iii) is a credible threat. If consumer 1 refuses to buy two units in period 1 her utility will fall as the price would then rise to p 2 = 15. If consumer 2 refuses to buy one unit in period 1 then his utility will be unchanged. Thus, the optimal contingent pricing mechanism gives total profits of 34. An Example. We now point out some interesting observations. First, note that, in this example, the equilibrium under the contingent pricing mechanism involves storage whereas the preannounced pricing solution does not. We prove in Section 3 that this observation is universal. Regardless of the number of time periods, the valuation functions, or whether the game is single-buyer or multi-buyer, there is an optimal preannounced pricing strategy that induces no storage. Thus, in terms of storage costs, the preannounced pricing mechanism is more efficient that the contingent pricing mechanism. Second, note that, in this example, the prices under the preannounced pricing policy are higher than under the contingent pricing mechanism in each period. Third, the retailer profits are lower under preannounced pricing (32) than contingent pricing (34). Finally, the consumer surplus (the total utility obtained by consumers minus money transfers to the retailer and storage costs) is lower under the preannounced pricing policy (0) than with the contingent pricing mechanism (11). The last three observations are surprising as Dudine et al. [2006] prove that none of those three statements can be true if the retailer is selling a divisible storable good. Optimal Preannounced Pricing Mechanisms In this section we derive an efficient procedure to calculate an optimal sequence of prices {p 1 , . . . , p T } (price at period t is p t ) that the retailer could announce to maximize its revenue under preannounced pricing. Furthermore, the optimal price sequence is the same regardless of whether we are in the single-buyer or multi-buyer case. Optimal Preannounced Pricing Mechanisms We begin with the following simple observation that holds for the multi-buyer and the single buyer settings. Optimal Preannounced Pricing Mechanisms Observation 1. Let {p 1 , . . . , p T } be any sequence of preannounced prices. If sales at period t are positive then p t is finite and Optimal Preannounced Pricing Mechanisms This contradicts the rationality of the consumer (single-buyer case) or the consumers who buy at period t (multi-buyer case), as she/they can increase their utility by bringing forward the period t purchases to period t ′ and then storing the good. Optimal Preannounced Pricing Mechanisms The following theorem shows that under preannounced pricing there is no wasteful storage. This "storage-proof" property of the preannounced pricing mechanism extends the result of Dudine et al. [2006] to the case of indivisible demand. 4 Optimal Preannounced Pricing Mechanisms Theorem 3.1. There always exists a revenue maximising preannounced pricing strategy in which there is no storage. This pricing strategy is the same for the single-buyer and the multiple-buyer settings. Optimal Preannounced Pricing Mechanisms Proof. Take any optimal preannounced pricing strategy {p 1 , . . . , p T } in which the consumer (or consumers) use the storage option. We show that there is another optimal preannounced pricing strategy that requires less storage. The theorem will follow. Let t be the first time period where q t > x t . Thus a consumer stores at least one unit of the good between period t and period t + 1. We may assume in the case of a tie that the consumer(s) selects an option with the least storage. By the rationality of each consumer, we then have that p t+1 > p t +c. By Observation 1, we then have that q t+1 = 0. Now suppose the retailer modifies its preannounced policy by setting p t+1 = p t +c. Observe first that consumption in periods 1 to t will not change. Second, in the single-buyer case the consumer now prefers to purchase q t − x t units in period t + 1 rather than buying them earlier and storing them. In the multi-buyer case there are q t −x t consumers who previously bought a unit to store at period t and now prefer to purchase it in period t + 1. Thirdly, the purchases made from period t + 2 are unaffected by this price change; if it is now preferable to buy additional units in period t + 1 then each consumer would have originally benefited by making such purchases in period t. This modified strategy pricing cannot decrease the retailer profits (if c > 0 then profits strictly increase). Now recall that in the multiple-buyer setting, v i,t is the utility of the i th consumer (ranked in decreasing order of their utility values in time period t). In the single-buyer setting, in order to unify notation, we let v i,t = V (i, t) (that is the marginal utility of consuming x units of the good at period t) and let the value of H ∈ N such that V (H, t) = 0 for all t ∈ T be equal to N + 1. Optimal Preannounced Pricing Mechanisms Lemma 3.1 allows us to write the retailer's problem as follows. The formulation is valid for the single-buyer model as well as for the multiple-buyer setting. Optimal Preannounced Pricing Mechanisms Here q t is a non-negative integer representing the number of items sold at time t. For the consumer to desire this amount, the price at time t must be at most the corresponding marginal utility -this gives the first constraint. The second constraint states that if there are sales in period t then the price p t cannot be more than the total cost of purchasing a good in an earlier period and storing it until time t. Recall that we set v 0,t = L. Thus, if q t = 0 we may set p t = L; this cannot decrease the objective function as it can only weaken the restrictions imposed by the second set of constraints. Optimal Preannounced Pricing Mechanisms The following theorem is crucial for the construction of the polynomial-time algorithm to compute an optimal preannounced pricing strategy. Optimal Preannounced Pricing Mechanisms Theorem 3.2. There exists optimal preannounced pricing sequence p 1 , . . . , p T such that for each t, we have p t = v j,s + (t − s) · c for some s t and some 0 ≤ j ≤ N. Optimal Preannounced Pricing Mechanisms Proof. Take an optimal sequence of preannounced pricing sequence (p 1 , . . . , p T ) that do not require storage. If these do not satisfy the requirements of the theorem then take smallest time t such that p t = v j,s + (t − s) · c for any s t and for any j N. Now, if q t = 0 then setp t = v 0,t = L. It is easy to verify that the new prices {p 1 , . . . ,p t , . . . , p T } induce the same behaviour by the consumer or consumers and, thus, produce the same revenue. Moreover, the period t now satisfies the requirements of the theorem for s = t and j = 0. So suppose q t ≥ 1. We now set Optimal Preannounced Pricing Mechanisms We claim (p 1 , . . . ,p t , . . . , p T ) is a more profitable sequence of preannounced prices. To do this we again desire that the consumer (or consumers) behaviour does not change. If so, the price increase at time t will result in additional revenue. First, the price increase at time t will not affect consumption by the consumer(s) in any period t ′ < t. Second the price increase at time t will not alter consumption in periods t ′′ > t; making additional purchases at time t and storing them for future consumption is even less desirable than before. It remains to consider sales in period t. Recall there were originally q t sales in period t. Because there was no storage, it must, by consumer rationality, be the case that v q t+1 ,t < p t ≤ v qt,t . Optimal Preannounced Pricing Mechanisms Thus, p t < v qt,t , otherwise p t does satisfy the requirements of the theorem. It follows that v qt,t was a feasible option when selectingp t . Hence,p t ≤ v qt,t . Thus the price of the item at time t is still at most the marginal value the q th t unit (in the multi-buyer case,p t is at most the utility at period t of the consumer with the q th t highest utility in that period). But does the price increase from p t top t now induce the consumer or consumers to now purchase early and store for consumption at time t? This is not the case. Since q t > 0, we know by Observation 1 that p t p s + (t − s) · c for all s < t. Since by assumption p t = v j,s + (t − s) · c for any s t and for any j N, we have that p t < p s + (t − s) · c. Now, by the minimality of t we have that p s = v j ′ ,r + (s − r) · c for some r ≤ s and 0 ≤ j ′ ≤ N. Hence Optimal Preannounced Pricing Mechanisms It then follows, by the definition ofp t , thatp t p s +(t−s)·c. Consequently, it is not beneficial for the consumer or consumers to use storage and {p 1 , . . . ,p t , . . . , p T } is a more profitable solution for the retailer. Iterating the argument produces a sequence of preannounced prices that satisfy the requirements of the theorem for every period t. Optimal Preannounced Pricing Mechanisms The structure provided by Theorem 3.2 allows us to construct an optimal preannounced pricing strategy in polynomial time via a dynamic program. The key is that we search for prices of the form p t = v j,s + (t − s) · c, for some s t and some 0 ≤ j ≤ N. Intuitively, this means we are matching a price p t with a value v j,s . Of course, this correspondence has to satisfy numerous constraints in order to be rational and profit-maximizing. Optimal Preannounced Pricing Mechanisms To explain how to find the optimal correspondence, we begin with some definitions. For each demand utility v i,t we associate a 2D contour γ i,t to the demand of the ith item in period t. (Recall that demands are sorted by decreasing value in each period, that is, v i,t v i+1,t .) We then define a total ordering over all the contours. Specifically, we say γ i,t γ j,r if v i,t + c · (r − t) v j,r and t r. To motivate this, assume the consumer is debating whether to purchase and consume j items in period r or to purchase in period t < r and then store the goods until period r. The best choice is determined by the ordering of the contours γ i,t and γ j,r . Optimal Preannounced Pricing Mechanisms We denote by C t = {γ i,t : i ∈ [N]} the set of contours associated with demands in period t. Further, we set C 0 to contain a dummy contour, C 0 = {γ * } where γ γ * for all γ ∈ T t=1 C t . We will view the selection of the dummy contour in time t as the assignment p t = L for some huge L. Now suppose we select a contour γ j,s at time t. As described, this produces the price p t = v j,s + (t − s) · c. In addition, this choice constrains the price choices for all periods r > t. Specifically, such a price p r must correspond to a contour no higher than γ j,s . Hence, the choice of contours (excluding dummy contours) is non-increasing over time. To formalize this for the dynamic program we use the following notation. Optimal Preannounced Pricing Mechanisms is the feasible set of contours for period t, given that the lowest contour chosen so far is γ i,y . Given a contour γ i,s and a time period t s, we define p t (γ i,s ) = v i,s + c · (t − s). We then set q t (γ i,s ) = #{j ≥ 1 : v j,t ≥ p t (γ i,s )} to be the number of items in period t with value at least p t (γ i,s ). Note that if there is no storage then q t (γ i,s ) is exactly the number of sales in period t when prices are p t (γ i,s ). We are now ready to present a dynamic program that calculates the optimal sequence of preannounced prices in polynomial time. Optimal Preannounced Pricing Mechanisms ALGORITHM 1: Optimal preannounced pricing mechanism Optimal Preannounced Pricing Mechanisms Theorem 3.3. The dynamic program computes an optimal preannounce pricing strategy. Optimal Preannounced Pricing Mechanisms Proof. We want to show that R(t, γ i,s ) computes the optimal revenue obtainable in period t to T , given that the maximum price we may use in period t is induced by the contour γ i,s . That is, the maximum price p t is at most v i,s +(t−s)·c. We prove this by backwards induction from the last period. For t = T , we have that R(t, γ i,s ) maximises the quantity times price given the upper bound on price implied by γ i,s , as desired. Now consider R(t, γ i,s ), for t < T . Again, by Theorem 3.2 there exists an optimal pricing strategy in which the price at period t is equal to p t (γ i,r ) for some γ i,r ∈ t τ =1 C τ . To maximise profits we wish to select a contour in C t ; however, the corresponding price must not be above γ i,s . Thus, the optimal choice, S(t, γ i,s ), must either be γ i,s itself or a lower contour in C t . The objective is to maximise revenue in period t plus revenues from periods t + 1 to T . The correctness of the procedure follows as the latter has been calculated inductively. Optimal Preannounced Pricing Mechanisms Theorem 3.4. An optimal sequence (p 1 . . . , p T ) of preannounced pricing can be computed in time O(T · D 2 ), where T is the number of periods and D is the total number of items in demand (D N · T ). Optimal Preannounced Pricing Mechanisms Proof. The outer loop covers T periods. The inner loop takes examines at most D counters (one for each demand item). The two variable assignments require O(D) operations. Together this takes time O(T · D 2 ). Item 1 2 3 · · · i · · · N Marginal Utility in Period t = 1 0 0 0 · · · 0 · · · 0 Marginal Utility in Period t = 2 1+ǫ 1 2 1 3 A Relationship between Preannounced Pricing Profits and Contingent Pricing Profits Recall, in the divisible storable good [Dudine et al., 2006] , retailer profits under a preannounced pricing mechanism are always higher than or equal to those obtained under a contingent pricing mechanism. We saw an example in Section 2.3 showing this need not be the case for an indivisible good. In this section, we quantify exactly how much more profits a contingent pricing mechanism can generate than a preannounced pricing mechanism for an indivisible good. Specifically, let Π CP (G) and Π P A (G) denote the retailer revenue in the game G under contingent pricing and preannounced pricing respectively. Our main result is that, for the multi-buyer case with N(G) consumers, there exists an example for which Π CP (G) = Ω(log(N(G)) · Π P A (G)). Furthermore this result is tight, for any game G, we have Π CP (G) = O(log(N(G)) · Π P A (G)). Before presenting these results, we give a simple example to show that in the single-buyer case there are examples where the retailer can obtain arbitrarily higher profits using a contingent pricing mechanism rather than a preannounced pricing mechanism. The Single-Buyer Case. Here is a single-buyer example where profits for the contingent pricing mechanism are arbitrarily higher than for the preannounced pricing mechanism Theorem 4.1. For any k ∈ N, there exists a single-buyer storable good game G such that The Single-Buyer Case. Proof. We create a game G with T = 2 periods. The buyer receives zero utility from consumption in the first period. In the second period, the buyer has a marginal utility of 1 + ǫ for the first unit of consumption (for some small ǫ > 0), and a marginal utility of 1 i for the ith unit of consumption, for 2 ≤ i ≤ N. This is summarized in Table 2 . The storage costs are assumed to be negligible, that is, c = 0. The Single-Buyer Case. Using a preannounced pricing strategy the maximum profit obtainable by the retailer is clearly Π P A (G) = 1+ǫ. On the other hand, the retailer can do far better by using a contingent pricing mechanism. To see this, first consider what happens if the consumer refuses to buys any items in the first period. The price in the second period will be then be the static monopoly price of 1 + ǫ; the consumer surplus would then be zero. So suppose the retailer announces a price of The Single-Buyer Case. As discussed, the consumer generates no surplus if she refuses to buy in period 1. What happens if the consumer buys one unit at price p 1 and stores it for consumption in period 2? Then, in the second period, if the consumer buys k < N additional items, her marginal utility for that final unit of consumption is 1 k+1 . Therefore, given that the consumer bought exactly one unit in period 1, the optimal price for the retailer is p 2 = 1 N in the second period. Consumer surplus over the two periods is then The Single-Buyer Case. Hence the consumer is no worse off by purchasing one item in the first period at p 1 than if she waits and buys only in the second period. The consumer has negative utility if she purchases more than one unit in period one. Thus, we have an equilibrium where the consumer purchases exactly one unit in period one with retailer's profits of The Single-Buyer Case. It is well-known that H N > log N + 1 2 . Consequently, we have Π CP ≥ log N ·Π P A , as ǫ → 0. The Multi-Buyer Case. Is it also the case that retailer profits can be arbitrarily higher under contingent pricing mechanisms than under preannounced pricing mechanisms when there are a large number of consumers? We remark that the example used to prove Theorem 4.1 does not extend to the multi-buyer case. To see this, suppose we interpret Table 2 as a game with N buyers each with a unit demand. The optimal prices using the contingent pricing mechanism would then be p 1 = 1 + ǫ (one consumer buys) and p 2 = 1/N (and the remaining N − 1 consumers buy). But this only yields a total profit that is less than 2 · Π P A . Intuitively, the reason why higher profits cannot be extracted is because the N buyers do not cooperate. In contrast, in the single-buyer setting, the retailer is able to exploit the fact that the buyer is willing to buy at a "loss" in period 1 in order to obtain a surplus in period 2. The Multi-Buyer Case. Nonetheless, we now show, via a far more complex example, that the retailer in the multibuyer setting can generate a multiplicative factor log(N(G)) more profits by using a contingent The Multi-Buyer Case. pricing mechanism. This is interesting, and perhaps surprising, in light of the results of Berbeglia et al. [2014] who examined a model of a durable good monopoly problem with N atomic consumers and finite time horizon originally proposed by Bagnoli et al. [1989] . In that model, Berbeglia et al. [2014] proved that retailer profits under a contingent pricing mechanism are always within an additive constant (and within at most a multiplicative factor of two) of profits under a preannounced pricing strategy. The model proposed by Bagnoli et al. [1989] corresponds to a special case of the storable good problem studied here. Specifically, to capture their model we simply assume each consumer obtains a positive utility only in the final period, that is, v i,t = 0 for all 1 ≤ i ≤ N and for all 1 ≤ t ≤ T − 1. 5 This additive constant bound does not extend to the more general storable goods problem studied in this paper. Again, as in the single-buyer case, the ratio between the profits under a contingent pricing mechanism over the profits under a preannounced pricing strategy can be unbounded. The Multi-Buyer Case. Theorem 4.2. There exists an infinite sequence of games G 1 , G 2 , . . ., such that the number of consumers is strictly increasing and that Π CP (G i ) Π P A (G i ) = Ω(log(N(G i ))). The Multi-Buyer Case. Proof. Take any integer N > 2. We create a game with T = N i=1 2 N −i = 2 N − 1 periods. In each period t ∈ [T ], there is exactly one consumer with positive utility for the item; that is, v 1,t > 0 and v i,t = 0, for all 1 ≤ t ≤ T and all 2 ≤ i ≤ N. Furthermore, each consumer has a positive utility for the good in only one period. Specifically, we partition the time periods into N blocks, {B 1 , B 2 , . . . , B N }. Here block B k consists of 2 N −k consecutive time periods. Note that N k=1 |B k | = 2 N − 1 and so there are indeed T = 2 N − 1 time periods in total. It remains to assign, at each period t, a valuation to the only consumer who wishes to consume in that period. If consumer i is the unique buyer with positive utility in period t then we say that i is the consumer of period t, or that i belongs to period t. (Given a set S of time periods, we say that a consumer belongs to S if the consumer belongs to any period in S.) The consumer belonging to any period in block B k , for each 1 ≤ k ≤ N, is given a valuation of v k = 2 k−1 . Again, we assume that storage costs are negligible, that is c = 0. Table 4 .2 summarizes this construction. The Multi-Buyer Case. Let's first calculate the retailer profit, Π P A (G), under preannounced pricing. To do this, we claim that there is an optimal preannounced pricing strategy in which prices do not change over time. Let {p 1 , p 2 , . . . , p T } denote an optimal preannounced pricing strategy. Consider the largest t such that p t < p t+1 . Because there are no storage costs no consumer in any period s with s > t would buy at price p t+1 . Thus, setting a price p ′ t+1 = p t at period t + 1 will not cause the retailer's profits to decrease. On the other hand, take the largest t such that p t > p t+1 . If no consumer buys in period t then decreasing the price in period t down to p ′ t = p t+1 can only increase profits. If at least one consumer does buy in period t at price p t then that must be the consumer that belongs to period t; any other consumer will do better by waiting to purchase in period t + 1. This means that the consumer from period t has a valuation at least p t . By the construction of the game, this in turn implies that every consumer belonging to a period s, with s > t, also has a valuation at least p t . Therefore, even with a fixed price of p t between periods t + 1 to T all consumers in periods t + 1 to T would still buy the item. This increases monopoly profits. It follows that there is a fixed price strategy that yields optimal profits. Therefore, to compute Π P A (G) we can restrict attention to fixed price strategies. It is then easy to verify that the optimal fixed price is 1. Every consumer will then purchase the good giving the retailer a profit of 1 in each time period, and thus of T = N −1 i=0 2 i = 2 N − 1 in total. Hence Π P A (G) = 2 N − 1. The Multi-Buyer Case. Next consider contingent pricing mechanisms. We will show that there is a subgame perfect equilibrium in which the retailer extracts almost all the consumer surplus. This equilibrium is composed of the following pair of strategies. The strategy of the retailer is to announce a price equal to the value of the highest consumer yet to buy. The strategy of each consumer is to buy the item in the earliest period t where the price is at most her valuation, provided the consumer belongs to a period s ≥ t. Following Bagnoli et al. [1989] , who studied a similar strategy pairing in a different setting, we call the retailer's strategy pacman and the consumers strategies get-it-while-you-can. The Multi-Buyer Case. To analyse this we denote by G i,k a subgame in which the remaining consumers belong to the set of blocks {B i , B i+1 , . . . , B k }. That is, the
{'paper_id': '197473394', 'title': 'Pricing Policies for Selling Indivisible Storable Goods to Strategic Consumers', 's2_url': 'https://api.semanticscholar.org/CorpusID:197473394', 'source': 'S2ORC'}