THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics Technical Note AN INVENTORY PRICING PROBLEM W. M. Kincaid D. A. Darling ORA Project O4597 under contract witho DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO, Nonr 1224(41) TASK NR 042-227 WASHINGTON, D. C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR July 1962

TABLE OF CONTENTS Page 1. STATEMENT OF THE PROBLEM 2 2. SOME USEFUL LEMMAS:3 3. SALE OF A SINGLE ITEM, SELLING PRICE NOT ANNOUNCED 4 4. SALE OF A SINGLE ITEM, SELLING PRICE ANNOUNCED 16 5. MULTIPLE ITEMS 23 6. FURTHER PROPERTIES OF THE OPTIMAL STRATEGIES 28 7. CONCLUDING REMARKS 36

AN INVENTORY PRICING PROBLEM W. M. Kincaid and D. A. Darling In this paper we analyze the optimum behaviour of a person who is forced to make a decision, or a set of decisions, before a specified deadline. We attempt to treat in considerable detail a very simple, yet perhaps not unrealistic, situation as an illustration, but the reader should have no difficulty in envisaging further ramifications and applications. Even with the simple model we choose there are unexpected mathematical delicacies and difficulties which we have thought it worthwhile to analyze. As an aid to intuition we have phrased the problem we consider as one of a merchant selling goods to the public walking past his store. While we do not claim that our results have a realistic significance for him, it will be apparent that the type of decisions with which he is confronted have manifold extensions to other areas and activities and have, in a simplified way, many features in common with the model we treat. Though our problem could, no doubt, be formulated as one of an optimum inventory type or as an example of a dynamic programming 2 problem we have developed it independently in the present paper, which assumes no background in these subjects. 1. This work was partially supported by the Office of Naval Research. Some of the material in this paper appeared in unpublished form in a report, "A type of inventory problem" by W. M. Kincaid and D. A. Darling issued as Report M720- 1 R33 by the Engineering Research Institute, University of Michigan (1952), 2. R. Bellman, Dynamic Programming, Princeton University Press (1957), particularly Chapter XI)^

-2 -1. Statement of the Problem Let us consider the following situation. A seller has a stock of goods to dispose of within a specified time. Potential buyers arrive in accordance with a Poisson process, and the probability distribution of prices they are willing to pay is known to the seller, who attempts to set his prices so as to maximize his expected cash receipts during the sale. Two variants of this situation are of interest. In the first, the seller posts a price for each item in his stocko In the second, the seller does not post prices, but receives offers from potential buyers, which he either accepts or rejects. Although the first case is closer to the usual commercial practice, the second is simpler mathematically, and will be treated first. Although the principles developed are undoubtedly capable of wider application, attention will be confined to the case where all the items in the seller's stock are the same and no buyer is interested in purchasing more than one item. Under these circumstances, the situation is sufficiently described by stating that the expected number of potential buyers appearing during any time interval of length T isXT, where X is a positive constant, and that the probability that a potential buyer appearing at time t prior to the conclusion of the sale is not willing to pay as many as z monetary units 3. This statement implies that unsold items are worthless to the seller. If in fact they have fixed salvage values, the situation is changed only verbally, with the difference between the selling price and the salvage value taking the role played by the selling price in the present discussion.

-3 -for an item is a specified function e(z, t). (Hereafter potential buyers will be referred to simply as buyers. ) While one might suppose that the duration of the sale and the number of items held by the seller at its outset would be relevant parameters, it will turn out that this is true only in a trivial sense. The assumption that the average rate of arrival of buyers is fixed is really a very mild one, since the time scale could be expanded or compressed locally if desired. In fact, we shall take advantage of this freedom forthwith by declaring the time scale so chosen that \ = 1. 2. Some Useful Lemmas. It will be convenient to present at this point some mathematical results that will be referred to repeatedly later. The proofs involve only elementary arguments and will not be given here. Lemma 1. Let f be a function such that for a < t < b f(t) J j(x) dx+ t(t), a where j and i are real-valued functions satisfying the following conditions on [a, b] (1) j is integrable; (2) i is monotone increasing and continuous, and A(a) > 0. Then f is non-negative on [ a, b], unless both f(t) < 0 and i (t)< 0 on a common set of positive measure.

-4 -Lemma 2. Let the conditions of Lemma 1 be satisfied, and suppose further that j (t) = f(t) i (t) + 8(t), where and 9 are measurable and bounded, (t) < 0, and 0(t)> O. Let t be any point of (a, b]. Then either f(t )> 0 or 6(t) = (t) = 0 for almost all t in [a, t ], in which case f(t) 0 for a < t < t Lemma 3. Let f be a function having a derivative f' on [ a, b], and let f(a) > 0. Then the following statements may be made for a < t < b: (a) Either f(t) > 0 for all t, or f(t) < 0 and f'(t) < 0 for some t. (b) Either f(t) > 0 for all t, or f(t)< 0 and f'(t) < 0 for some t. (c) If f'lu) >min[ -A f(u), 0] for some A> 0 and f(u) ~0 for a < u< t, then f(t)> 0. 3. Sale of a Single Item, Selling Price not Announced A natural starting point for the discussion is the case where the seller's initial stock consists of one item. It will turn out that little in the way of additional ideas is required to handle the general case once the optimal pricing policy for a single item is determined. As noted earlier, we shall begin by supposing that the seller does not quote a price, but decides whether or not to accept each buyer's offer when it is made. Intuitively, one might argue as follows. Let Z(t) be the least offer that the seller would accept at time t prior to the end of the sale, and let E(t) be the seller's expected gain from a sale of duration t. For the sake of simplicity, the value of the item to the seller will be taken as zero if

-5 -it remains unsold, so that E(O) = 0; no real loss of generality results from this assumption. Then it is reasonable to suppose that under an optimal pricing policy Z(t) = E(t); that is, the item will be sold only if the amount offered is at least equal to the expected amount that will ultimately be received for it if the offer is rejected. Although the conclusion just stated is correct, the argument is clearly not rigorous, and embodies an apparent circularity, for E(t) is not known in advance, but depends on Z(t), which is what we are trying to determine. To establish the optimality of a particular pricing policy, which will henceforth be referred to as a strategy, a class of admissible strategies must first be specified. For this purpose, any rule giving the probability with which the seller will accept an offer of any given amount at any given time will be called an admissible strategy. That is, any (measurable) function p(z, t) with domain z > O, t > 0 and range 0 < p < 1 defines a strategy; for convenience, the function associated with a strategy s will be written p(s, z, t). Thus if the strategy s is followed, the seller will accept an offer z at time t prior to the end of the sale with probability p(s, z, t). The set of admissible strategies is very broad, since the seller is not required to accept all offers above some lower limit, and may/even let acceptance or rejection hinge on the toss of a coin. Although it might seem more natural to restrict attention to treasonable' strategies, the proofs to be given below would not be substantially simplified by doing so -

-6 -indeed, the essential ideas would emerge less clearly. (Note, incidentally, that any strategy is applicable to a sale of arbitrary duration. ) Since the end of the sale is the most convenient temporal reference point, it will be understood henceforth that 'the time t' means t time units before the sale ends, and other expressions referring to time are to be interpreted similarly. In the following discussion, we shall frequently have occasion to use Stieljes integrals with respect to the distribution 9(z, t), with t held fixed. (Note that 8 is left continuous in z, so that such a Stieljes integral will include the jump, if any, at the lower end-point. ) For simplicity, the differential symbol will be written d e(z, t) in such cases. For example, z the expected total value of offers received between the times T and T 1 2 (0 < T < T2) is given by the integral [ TZ (3. 1) r J z d e(z9 t) dt. - T (This integral will be assumed to exist for all non-negative values of T and T. It will also be assumed that the value of the inner integral will not exceed a positive constant M for all values of t to be considered. ) Now suppose the seller follows the strategy s. If the sale item is unsold at time t + t t, the probability P that it will be sold by time t satisfies the inequality (3.2) P< / P p(s; z, x) d Q(z, x)dx, J t a} a n 0 z since the right member is the expected numtnber' of sales that would take place

-7 -if the number of sale items was unlimited. On the other hand, if Pk (k = 2, 3,...) is the probability that k sales would take place in this case, the right member of (3. 2) is equal to P + 2P2 + 3P3 +.... Since for k = 1, 2,..., the probability that exactly k buyers appear during the time interval is et ( t) /k! and the probability that k or more sales take place is at most equal to the probability that k or more buyers appear, a few manipulations lead to the inequality (3.3) 2Pz + 3P3 +... t (1 - e ) < (t) and thus to the lower bound t+ ft roo (3.4) P> / p(s; z, x) d 9(z, x)dx- (At) t J 0 Similar considerations can be applied to the estimation of the expected value E of payments received (for the single item) during the same-period, and lead to the bounds {t+At r 2o (3.5) 0 f z p(s; z, x) d E(z, x)dx - E < M(At) t 0 where M is an upper bound to the expected amount offered by a random buyer, as noted above. The expected amount received by the seller during a sale of length t will now be considered; it will be denoted by E(s, t). Referring again to the interval [t, t + / tl and using the notation introduced above, one has the relation

-8 -(3. 6) E(s, t + t) = E + (1 - P) E(s, t). Since E(s, t) > 0, the inequalities (3. 2), (3. 4), and (3. 5) may be substituted into (3. 6) to yield t+4t 0 oo (3.7) J I [z -E(s, t)]p(s;z, x)d 8(z,x)dx - M(A t) <E(s,t +'t) - E(st) ft+tt foo 2 < / [z - E(s, t)]p(s; z, x) d 6(z, x)dx + E(s, t)(^t). Jt J From (3. 1) the expected value of the total offers received between times t rco t and 0 is I / z d 6(z, x)dx, which does not exceed Mt; consequently OJO E(s, t) < Mt for any strategy s. The inequalities (3. 7) can be strengthened by making use of this fact and dropping positive and negative terms from the left and right members, respectively, yielding t+At ro 2 -Mt j / p(s; z, x)d 0(z, x)dx - M( t) < E(s, t + t) - E(s, t) z Jt Jo z rt+bt oo 2 < / z p(s; z, x)d (z, x)dx + Mt(&At) J t J Since J p(s; z, x)dO(z, x)< J d(z, x) = 1 and 0 O f p(s; z, x) d8(z, x) < z de(z, x) < M, we obtain the further result 202"O~ 2 (3.8) -Mt At -M(6t) < E(s, t + t) - E(s, t) < M t + Mt(A t) Since A t is a factor of both the left and right members of (3. 8), it follows that if upper bounds T and 6 are placed on t and A t, a constant K can be found such that E(s, t) satisfies the Lipschitz condition

-9 -(3.9) | E(s, t + At) - E(s, t) | < K ^ t whenever t < T and ^ t < 6. It follows from (3. 9) that replacing E(s, t) by E(s, x) in the integral appearing in the left and right members of (3. 7) changes the value of the integral by at most t+4t K 2 J K(x - t)dx= ~(2 t). t Combining this result with (3. 7) leads to the relation rt+&t t oo |E(s t + t) (st) z E(s t) -/ [z - E(s,x)]p(s;z,x)d 9(z,x)dx| J t J o (3. 10) K 2 K 2 < (z + M + E(s, t))(At) Z< (+ M + MT)(4t). Now let the interval [0, t] with t < T be divided into k subintervals of length k< 6. Applying (3. 10) to each interval and adding the results yields rt roo 2 [z- E(s, x)] p(s; z, x)d8(z, x)dxI < (~ + M + MT) - 2 k This inequality holds for all sufficiently large values of k, and it follows that the left member must be identically zero. Moreover, the restriction t < T has no real force, since T may be made arbitrarily large. Accordingly we have the result THEOREM 1. For all strategies s and all times t > 0, the expectation E(s, t) satisfies the equation rt J oo (3.11) Eis, t) =J [z-E(s, x)] p(s; z, x) d 9(z, x) dx. J0 Jo

-10 -While it is possible to find an explicit expression for E(s, t) - in fact the formula t ( at oo (3 1) E(s) z p(s,;zu)d9(zu)exp(-j p(s;z, x)d9 (z, x) x) du holds - equation (3. 11) is more useful for present purposes. It is now possible to establish the form of the optimal strategy. Equation (3. 11) suggests that E(s,t) will be maximal if p(s; z, x) = 1 when z> E(s, x) and p(s; z, x) - 0 when z < E(s, x). This remark is in harmony with the conjecture advanced in i 3. Theorems 2 and 3 below embody the result in precise form. The exposition will be simplified by introducing new notations that will permit the Stieljes integrals to be replaced by ordinary integrals. In effect this is done by setting y = O(z, t), and regarding z as a function of y and t defined by this relation. Discontinuities in 9 are taken care of by the formal definition (3. 12) z =z(y, t) < 86(z,t) < y < 9(z + 0, t) 0 0 - - 0 With this notation (3. 11) becomes (3. 13) E(s, t) = [ - E(s, x)] p(s; z, x) dy dx, 0o 70 with the understanding that z represents z(y, x) as defined by (3. 12). THEOREM 2. There exists a strategy O such that p( O; z, t) = 1 when z> E(O, t), (3. 14) = 0 when z < E(C, t).

-11 -Proof. Choose any strategy s, and define a new strategy sl by p(s; z, t) = 1 for z> E(s, t), 0 for z < E(z, t). We shall show that sl is an improvement on s. It follows from Theorem 1 that nt I1 E(sl't) - E(s,t) = | j {[z - E(s,x)] p(sl;z,x)-[z-E(s,x)] p(s;z,x)} dy dx. i 0 z 0 Suppose E(sl,t) < E(s, t). Then if z> E(s, t), we have p(s; z, t) = 1 > p(s; z, t). If z < E(s, t), then p(sl; z, t) = 0 and z - E(s, t)] p(s; z, t) < 0. In either case the integrand is non-negative and the conditions of Lemma 1 are satisfield'with f(t) = E(s, t) - E(s, t). Thus E(sl, t) > E(s, t) for all t> O. Now repeat the operation, defining the strategy s2 by p(s2; z, t) = 1 for z> E(s, t), =0 for z < E(s, t)o Then by the same reasoning E(s2, t) > E(s1, t). Continuing in this way, we define s by n p(s; z, t)= 1 for z> E(s, t), =0 for z <E(s, t). n-1 Thus for any t > 0, the sequence {E(s, t)} is monotone increasing, and since it is obviously bounded lim E(s, t) exists; call it E(t). Since n-~oo n the functions E(s, t) are continuous and satisfy a uniform Lipschitz conn dition, the same is true of E(t).

-12 -We may now define the strategy G7 either by p( c; z, t) = T p(s;z, t) n=l or by p(y;z, t) = 1 for z > E(t), = 0 for z < E(t). It remains to show that E(or,t) sE(t). Since {p(s;z,t)}, n = 1,2,... is a monotone decreasing sequence for all z> 0 and t > 0, the sequence { f p(s; z, x) dy dx}, n = 1, 2,... which represents the expected number of acceptable offers received during [O,t] if the strategy s is followed, is also monotone decreasing; its limit Bet fl n must be J p(<;z,x)dy dx. The difference J 0 J Pt r\ t If [p(s;zx) - p(:-;z,x)] dy dx is the expected number of offers that would be accepted under the strategy s but rejected under O, and is thus an upper bound to the probability a that the sale item will be sold (under the strategy s ) in response to such an offer. If such a sale takes place, the payment is necessarily less than max E(x), O<x<t which in turn cannot exceed Mt. Hence E(s, t) satisfies the inequalities n (1 - a ) E(C,t) < E(s,t) < (1 - a ) E(CO,t) + a Mt. n - n n n Since lim a = 0, it follows that E(Ct) = lim E(s,t) = E(t), completing n-^oo n n-oo n the proof. We shall now show that ' is optimal, not only with respect to the sequence {s }, but with respect to the set of all admissible strategies. Indeed, n we shall show that it is the only optimal strategy (except for a set of measure zero). Incidentally, this implies that the choice of s

-13 -in the above proof does not affect C. THEOREM 3. A strategy s is optimal if and only if p(s; z, t) = p(o; z, t) except on a set of probability measure zero, where. is any strategy satisfying (3. 14). Proof. Let s be any strategy. By Theorem 1 rt r1 E(C, t) - E(s,t) = J {Uz - E(, x)] p(';z,x) - [z-E(s,x)]p(s;z,x)}dy dx 0 0,t rl _f j|l {[E(s,x)-E(,x)]p(s;z,x) + [z-E(),x)] J 0 J 0 [p(,z, x) - p(s z, x)] dy dx. If z > E(5,x), then by (3. 14) p(6j;z,x) = > p(s; z, x); similarly z < E(Cr,x) implies p(C;z, x) = 0 < p(s; z, x). It follows that the conditions of Lemma 2 are satisfied with f(t) = E(CT,t) - E(s, t). Hence E(O,t) > E(s, t), and the equality holds only if p(s; z, t) = p(';z, t) except on a set of (probability) measure zero, as was to be proved. The optimal strategy 0- was defined as the limit of a sequence of strategies. Since we have proved that E(a0, t) = sup E(s, t), we may convert (3. 14) into the more elegant definition p(o;z, t) = 1 if z > sup E(s, t), (3. 15) = 0 if z < sup E(s, t). s

-14 -In view of the above results, we may simplify our notation by writing E(t) for E((',t); we shall refer to E(t) as the expectation for a sale of 4 length t. It follows from Theorem 1 and (3. 14) that E(t) satisfies the integral equation 0t I t (3. 16) E(t) = j [ z - E(x)]dy dx - E(x)] d (z, x)dx o0 @e(E(x), x) 0 E(x) and this gives us a means of determining E(t) in a particular case. Consider for example, the uniform distribution of z represented by (3. 17) 6(z, t) z, 0 < < 1, 1, z >. Here (3. 16) becomes t I E(t) = J [z - E(x)] dz dx 0 E (x) or 1 1 2 (3. 18) E'(t) = [z - E{t)] dz = 1 - E(t)] 2 E(t) 2 4. Some of the ideas presented here may be expressed in terms of concepts introduced by Dubins and Savage in a forthcoming book. In particular, the utility of the sellerss position at time t can be defined as the selling price if the item has been sold, and as sup E(s, t) otherwise. Corresponding to a given situation at time t, there will be an expected utility at any subsequent time t' that depends on the strategy followed between t and t'. Theorem 3 may be regarded as expressing the fact that the expected utility cannot exceed the initial utility, and will equal it only if an optimal strategy is followed. There is also a relationship with the principle of optimality enunciated by Bellman (op. cit., p. 83).

-15 -Solving (3. 18) subject to the condition E(0) = 0 gives us (3. 19) E(t)= t In this example E(t) has a continuous derivative. It is natural to ask whether this situation is typical. While it follows from (3. 16) that E(t) must have a derivative almost everywhere it is apparent that irregularities in E(z, t) as a function of t may induce irregularities in this derivative. It will be shown, however, that if 8 is well-behaved to the extent of satisfying a uniform Lipschitz condition with respect to t, then E(t) will have a continuous derivative, regardless of the character of 9 as a function of z. By (3. 16) E(t) is an integral of the function (3.20) E'(t) / [z E(t)] d e(z, t), ' E(t) which, it will be noted, is non-negative. Replacing t by t + at in (3. 20), subtracting (3. 20), and adding and subtracting suitable terms leads to E'(t +6 t) - E'(t) = [z - E(t + 6t)] d 9(z, t + At) E(t+^ t) -/ [z - E(t + t) d 9(z, t) J E(t + 4 t) (3. 21) + f [E(t) - E(t + A t)]d 9(z, t) (t +at) J E(t + t) / [z - E(t)] d 9(Z, t). E(t) As i t s- 0, the difference of the first two integrals in (3. 21) approaches 0 if 9 satisfied a uniform Lipschitz condition in t, while the other two

-16 -integrals approach 0 because E(t) is continuous. Thus we have the result THEOREM 4. If 9(z, t) satisfies a uniform Lipschitz condition in t for all z, the optimal expectation E(t) has a continuous non-negative derivative E'(t) satisfying the relation (3. 20). 4. Sale of a Single Item, Selling Price Announced Let the situation be the same as in the preceding section, except that the seller is required to announce a price, which can be a function of t, at which he will sell the single item he holds. Our first objective will be to develop an analogue of Theorem 1. As in the proof of that theorem, a passage to a limit is required; since this part of the argument involves no new ideas, it will not be presented in detail. Instead, symbols like O( L t) will be used where appropriate. The sale price at time t associated with a strategy s will be denoted by Z(s, t), and the corresponding expectation by F(s, t). If the item is unsold at time t + & t, the probability that a sale will take place by time t under this strategy is t+At o0 2 t+4t 2 (4. 1) P = d 6(z,x)dx + O(d t) = {l-[ Z(s, x)x]}dx+O(At) Jt AZ(s,x) t while the expected amount received is r tb+ t 2 (4.2) EJ Z(s, x) {l - 8[Z(s, x),x]}dx + O(^ t) t (It is assumed that all integrals exist; also our earlier assumption of an upper bound implies that the integrand in (4. 2) will not exceed M. ) For

-17 -convenience, we shall write (4.3) d(z, t) = 1 - (z, t). Equation (3. 6)suitably reinterpreted, is valid here. Substituting from (4. 1), (4. 2) and (4. 3) in (3. 6) yields as the analogue of (3. 7) the relation rt+6t 2 (4.4) F(s, t + t) F(s, t) =[Z(s, x) - F(s,t)] [Z(s,x),x]dx+ O() t), t Following our earlier reasoning, we conclude that F(s, t) satisfies a Lipschitz condition, and are led to the result stated below. THEOREM 5. The expected gain F(s, t) associated with the pricing function Z(s, t) satisfies the relation?t (4.5) F(s, t) = [Z(s, x)- F(s, x)] d[Z(s, x), x] dx. 0 To maximize F(s, t), it would seem that the integrand in (4. 5) should be made.as large as possible. Accordingly, for an arbitrarily chosen strategy s we shall define a modified strategy sl by choosing Z(sl, t) to be the least value of z for which the expression [z - F(s, t)] (z, t) attains its maximum value. (Since ^(z, t) is left continuous and monotone decreasing in z, the maximum is attained for each t). To show that sl is an improvement on s, we substitute in (4. 5) to obtain

-18 -t (4.6) F(s,t) - F(s,t) = {[Z(s,x) - F(s,x)] q[Z(s 1,x),x 0 - [Z(s, x) - F(s, x)l][Z(s x), x]}dx. Now suppose F(s,t) < F(s, t). Then Z(slt) - F(sl, t) > Z(slt) - F(s, t). Also, the definition of Z(sl, t) implies that [Z(sl,t) - F(s, t)] 4[ Z(s1, t), t] > [Z(s, t) - F(s, t)] 4[ Z(s, t), t]. Combining these inequalities shows that the integrand in (4. 6) is positive for x = t. Consequently Lemma 1 is applicable, and leads to the conclusion that F(s,t) > F(s,t) for all t. As in the proof of Theorem 2, we may repeat the operation, defining a sequence of strategies s2, s,... such that {F(s, t)}, n = 1, 2,... constitutes a monotone increasing sequence for all t > 0, having a limit F(t) as n — oo. The sequence {Z(s, t)} is also monotone increasing. To see this, let us write (4.7) G(x, t) = max {(z - x) d(z, t)} z for x > 0, and denote by X (x, t) the least value of z for which the maximum is attained. Lemma 4. The function. is monotone increasing and left continuous in x for t> 0, x> 0. Proof. Suppose z1 < z2, and that for some value x of x the inequality (4.8) (z1 - x) d(z1, t) < (z2, x) ^(z2' t) holds. Since q(z1, t) > ~(z2, t), (4. 8) will also hold for all x> x. Since

-19 -(4.8) will be true for all z < 2 if z2 = (x, t) and will be false for some z < z if 2 > 3 (x, t), we see that z <; (x, t) implies z1 < 3 (x, t) for x> x. Thus 3 is monotone increasing in x. 0 Now let z = lim r (x, t) be the limit of S (x, t) as x approaches o x-o -0 x from below. Since the definition of 3 (x, t) implies the inequality 0( )( t) ( (, t)-( t)] for all z, x, t, it follows from the monotonicity of; and the left continuity of 6 that for all z, x, t (4.o 9) (z- [z (x] (z, t) lim I[ z- (x, t) < lx]{ {[^3 (x, t)]X t} O ~ = [ lim ( (x,t) - x ] {[ lim ( (x,t),t= (z - x )g(z it). X-Xo-O x-.x-O 0 o o The inequality (4. 9) implies that t (x,t) < z; since t is monotone increasing, 3 (x,t) > z; thus X (xo,t) = z, and the left continuity of. is established. Incidentally, it is clear that I (x,t) > x in all cases. Since Z(s,t)= 3 [F(s t)] for n= 2,3,... and {F(s,t)} is a n n-1 ' n monotone increasing sequence, it follows from Lemma 4 that {Z(s,t)} is n a monotone increasing sequence for all t > 0 and that (4. 10) lim Z(s,t) = 3 ( lim F(s, t)) = (F(t)). n —oo n n -oo n If now the strategy Q' is defined by (4. 11) Z(& 9 t) = 3 (F(t)),

-20 -rt it follows from (4. 10) and the properties of ^(z, t) that ^[ Z(s, x)] dx}, Jo n = 1,,., is a monotone decreasing sequence having the limit rt J [ Z( S, x)] dx. The reasoning used in the preceding section to show that E(C, t) = E(t) can now be used to show that F(&,t) = F(t), that is, that o' has the property (4.12) Z(0, t)= (F(, t)). Paralleling our earlier argument, we now show that & is a uniquely optimal strategy. Let s be any strategy, and apply (4. 5) to obtain Ft (4.13) F(cr,t)- F(st)= {[Z(x) - F(C,x)] ^[Z(8,x),x] - [Z(,x) - F(s,x)] [ (s, x),x]}dx rt [= F(s,x) - F(,x)] [Z(s,x),x] 0 + [Z(o-,x) - F(c,x)] Q[Z(&,x),x] - [Z(s,x) - F(c,x)] [ Z(s, x),x]} dx. In view of the definition of 3, equation (4. 12) implies the relation (4.14) [Z(, t)F( t) - F([, t)] (,t) t] =max[z - F(&, t)]. (z, t), z whence (4. 15) [Z(6,t) - F(, t)] [ Z(&,t),t] - [ Z(s,t) - F(, t)l^[ Z(s,t),t] >_0.

-21 -The hypotheses of Lemma 2 are thus satisfied with f(t) = F(&,t) - F(s,t), t (t) = - [ Z(,,t),t], 8(t) equal to the left member of (4. 15), and i(t) = 0. It follows that F(P, t) > F(s,t), with equality holding for t = t only if (4. 16) [ Z(s,t) - F(6,t)]0[ Z(s,t),t] [ Z(,t) - F(,t)] Z(&,t),t] for almost all lesser values of t. In view of (4. 14) the condition (4. 16) means that the left member must take on its maximum value. If the function has a unique maximum, as will usually be the case, it is given by Z(s,t) = Z(et); in any case the maximum will be attained for this choice. Thus with this slight qualification, 3 is the only optimal strategy, and we may state the respilt? THEOREM 6. There exists a strategy ~ having the property Z(&,t) = r (F(c,t) for t> O. The strategy 0' is optimal in the sense that F(s,t) < F( t,t) for any strategy s and all t > 0. Moreover, F(s,t ) = F( 8 sto) if and only if (4. 16) is satisfied for almost all t in the interval 0 < t < t - -0o Now that this theorem is proved, it will be convenient to write F(t) and Z(t) for F(,t) and Z(e,t) respectively. In terms of the notation (4. 7) and in view of (4. 12), equation (4. 5) implies the relation rt (4. 17) F(t) = G[F(x),x] dx. Defining f(z, t) = [ z - F(t)]!(z, t), we see that since F is continuous, f will be continuous in t for all z if g is, that is, if 9(z, t) is continuous

-22 -in t for all z. If the further requirement that e(z, t) should satisfy a uniform Lipschitz condition is imposed, G[ F(t), t] = max f(z, t) will also be z continuous, and will therefore be the derivative of F(t). Also G[ F(t),t] > 0, and we have the analogue of Theorem 4; THEOREM 7. If 6(z, t) satisfies a uniform Lipschitz condition in t for all z, the optimal expectation F(t) has the continuous non-negative derivative F'(t) satisfying the equation (4. 18) F'(t) = G[ F(t), t]. It is interesting to consider again the example of a uniform distribution. Since q(z, t) = 1 - z for t > 0, 0 < z < 1 (and <(z, t) = 0 btherwise) we have G(x,t) = max(z - x)(l - z). The maximum is attained for z z= (x, t) (x+ 1); thus G(x,; ) = (1 - x) and (4.18) becomes 1 2 (4. 19) F'(t) [ 1 - F(t)] From (4. 19) we conclude (4. 20) F(t) t=, Z(t) [ F(t)] = t + 2 40tt + --- t+4 Comparing (4. 20) with the result obtained earlier, we note that F(t) < E(t) for t > 0, as is to be expected since the situation is less favorable for the seller.

-23 -5. Multiple Items. Let us now take up the more general situation where the seller's initial stock consists of n items, rather than one. Starting with the case n = 2, note that once one item has been sold, the seller's optimal strategy is the same as for a one-item sale; the only question to be settled is what the seller does if a buyer appears when both items are still on hand. Consider first the case where no selling price is announced, and a buyer appearing at time t makes an offer z. If the offer is accepted, the seller receives the amount z, and his expected further receipts for the item still unsold are E(t). That is, his total expected gain, if the offer is accepted, is z + E(t). His situation is the same as it would be if he had a single item for sale and received this amount in payment for it. To be more precise, a two-item sale with the distribution function 8(z, t) is equivalent to a one-item sale with the distribution function a'(z, t) _ 9(z - E(t), t). Accordingly, Theorems 2 and 3 are applicable; they assure the existence of an optimal strategy and define its properties. To avoid confusion, it is convenient to denote the optimal expectation when two items are for sale at time t by E (t), and the optimal expectation for one item, hitherto denoted by E(t), by El(t). Similarly, the optimal expectation when the stock consists of 3, 4,... items will be denoted by Es(t)} E4(t),... It follows from Theorems 2 and 3 that the optimum strategy is characterized by the property that an offer z at time t is accepted if z + El(t) > EZ(t), that is, if z > E2(t) - E (t). 2- 1c J

-24 -A suitable analogue of (3. 16) is obtained by replacing E(t) by E2(t), z(y, x) by z(y, x) + E1(x), and 6[E(x), x] by 6[E2(x) - E1(x), x]. The result is E2(t) = J [z + E (x) - E2(x)] dy dx 0 e[ E2 (x) - E1 (x), x] (5. 1) et 0oo = fj [z + E (x) - E2(x)] d (z, x) dx. Jo E?(x)-E!(x) This reasoning can be applied repeatedly to derive the optimal strategy for a stock of any number of items, leading to THEOREM 8. Let the initial stock consist of n items, and let the expectation (with prices not announced) from following the strategy s be E (s, t) (k= 0, 1, 2,..., n) if k items are in stock at time t. An optimal strategy is defined by the rule that if k items are in stock at time t, an offer z made at that time will be accepted if and only if z satisfies the inequality (5. 2) z > sup Ek(s, t) - sup Ekl (s, t). - s s 1 Any optimal strategy is identical with this except for a set of possible offers of probability zero. The optimal expectation E (t) satisfies the equation En(t) = t fj [z + E (x) - E (x)] dy dx o r0 e[E (x)-E.(x)] (5. 3) = J J [z + E,(x) - E](x)] dz9(z, x) dx. n n-1

-25 -If 8(z, x) satisfies a uniform Lipschitz condition in t for all z > 0, E (t) has a continuous non-negative derivative E' (t) satisfying the relation n (5. 4) En(t) = [z + (t} E (t)] dz(z, t). nE (t)-E (t)n z n n-l Very similar reasoning is applicable to the case where a price is announced; the result is THEOREM 9. Let the initial stock consist of n items, let the expectation (with announced prices) from following the strategy s be F, (s, t) (k = 0,.., n) if k items are in stock at time t, and let Fk(t) be the corresponding optimal expectation. An optimal strategy is defined by the set of price functions (5.5) Zk(t) = [ sup Fk(s, t) - sup Fk (s, t) t], which specify the price to be charged if k = 1,., n items are in stock at time t. If the strategy s is optimal, its price functions Zk(s, t) satisfy the equations (5.6) [Zk(s, t) + Fkl(t) - Fk(t)l6[Zk(st)tt] =G[Fk lit) Fk(t), t] (k = 1,.., n) for almost all t > 0. The optimal expectation F (t) satisfies the equation -tn (5.7) F (t) = G[F (x) - F x), x] dx. If 6(z, t) satisfies a uniform Lipschitz condition in t for all z, F (t) has the continuous non-negative derivative Fv (t) satisfying the relation n

-26 -(5.8) F'(t) = G[ F(t) - F (t), t] n n n-1 Note that (5. 5) implies the formula (5.9) Zn(t) = ~ [F (t) - F (t),t] (n = 1,..). These results may be illustrated with an example. Let the distribution of offers be given by (5. 10) 9(z, t) = 1 - e for z > 0, t > 0. Then by (3. 20) (or (5. 4) for n = 1) we have (oo E'(t) = [z - El(t)] e dz; E(t) integrating the right member yields the differential equation (5. 11) E'(t) = eEl(t) Since E1(0) = 0, (5. 11) may be seen to have the solution El(t) (5. 12) e =t + or (5. 13) El(t) = In(t + 1). Repeating the same steps with n = 2, we get -E (t)+E (t) (5. 14) El(t) = e 2 Substituting from (5. 12) into (5. 14), solving, and applying the condition Eg(0) = O yields (5. 15) E2(t) = In(l + t +. ). Equations (5. 13) and (5. 15) suggest that the general formula is

-27 - n t (5. 16) E (t) = In(l + t +... + ) 'n n this is readily verified by induction. Note incidentally that lim E (t) = t, n -4oo n which is the expected total value of all offers made during a sale of length t. Let us compare these results with those obtained when prices are announced. We have (5. 17) Q(z, t) = 1 - 9(z, t) = e and in order to proceed we must find the maximum of the expression (5. 18) (z - x) (z, t) = (z-x) e. The maximum can clearly be obtained by differentiating (5. 18); it is attained for (5. 19) z= ~ (x, t) =x+ 1, and has the value (5. 20) G(x, t) = e - ( Substituting from (5. 20) into (5. 8) yields the set of differential equations -F (t)+F (t) (- (5. 21) F' (t) = e n= 1 2.. n The equations (5. 21) are similar to those obtained1in the preceding case; they have the solutiom (5. 22) F(t) =in[ 1 + e).. + - '.' (e)n] The price functions may be determined by substituting from (5. 22) into (5. 9), taking account of (5. 19); the result may be written

-28 -1 t )n (5. 23) Z (t) 1 + F (t) - F (t) + In1 + n. (n 1, 2...). n n n-1 n-1 k__~ 1 t k k! e 6. Further Properties of the Optimal Strategies. In this section attention will be confined to the situation where the distribution of offers does not vary with time, and the notation will be modified accordingly; e. g. 9(z, t) will be written simply 9(z). Before proceeding further, it is convenient to introduce the function Ad 1 (6. 1) a(Z1) j (z - Z) d (z) (y) Z) dy,Z ' 9(Z) With this definition, (5. 3) and (5. 4) become (6.2) E (t) -J En(X) - E (x)]dx, n ^/ n n-1 (6. 3) E' (t) = aE (t) - E (t)]. n n n-1 If there are n items in stock at time t, there is a probability, which will be denoted by R (t), that all the items will be sold if the optimal strategy is followed. There is an interesting relationship between the functions E and R n n THEOREM 10. The relation (6.4) E'(t) = a(0)[ 1 - R (t)] holds for n = 1, 2,..., and t> 0. Proof. Consider a modification of the optimal strategy in which the time scale is translated by a t; that is, an offer is accepted at time t if

-29 -it would be accepted at time t + t t under the optimal strategy. If, t < 0O all offers are accepted between - \t and 0. If t t > 09 one may imagine the sale extended by Z t beyond its termination at t = 09 in which case the seller's expectation would be E (t + t t) To find his actual expectation9 this must be, diminished by n the portion attributable to the 'overtime' period. If the seller has k items for sale at the beginning of this period, his expected gain during the period is Ek( t)o If k> 1, it follows from (6. 3) that one may write (6. 5) E,(at) EI(O) tt + O( t)2 = a(0) t + O(at)2, while if k = 0, E ( t) = O0 The probability that at least one item remains for sale at the end of the period is by definition 1 - R (t + \ t); consequently, the probability that one remains at the beginning is 1 - R (t+ 6t)+O(At). n Reasoning similar to that used in establishing Theorem 1 leads to the relation (tt+t 2 (6. 6) R (t + t t) - R (t) =[R R(t)- / R[E (x)-E (x)]dx+ O(bt) t and since R (t), R,L(t), and ~[E (x) E ((x)], being probabilities, must n n~'l n n=l be between 0 and 1, we conclude that R (t + t t) = R (t) + O(/ t). Combining n n all these considerations, we see that the expectation under the modified strategy is E (t +At) ~ a(0)[ 1 - R (t)] At + O( A t) n n (6.7) 2 = E (t) + {E' (t) - a(0)[ 1 - R (t)] } Lt + O(t). n n n

-30 -If ~ t <0, the expectation is the sum of E (t + t6 t) and the exn pectation for a period of length | At during which any offer is accepted if an item remains for sale. This latter expectation is seen to be (1 - R (t)) a(0)(-zAt), and we again conclude that the expectation is given n by (6.7). Since E (t) is the expectation from the optimal cstrategy, the expression (6. 7) must attain its maximum for Za t = 0, which can be true only if the coefficient of. t vanishes. But the vanishing of this coefficient is equivalent to (6. 4); thus the theorem is established. Very similar reasoning can be applied to the case of announced prices. Since F (0) = 0 for n = 1, 2,..., we have by (5. 9) Z (0) =. (0) for all n. If this price were maintained for a time interval 6 t, the expected number of buyers during the interval would be ([; (0)] At + O(^t), and hence the expected receipts, if there were an item for sale, would be 2 2; (0) [ ] (0)] A t + O( At), which by definition equals G(O)A t + O(6t) Also, from (4. 18) (6. 8) Fk(A t) = Ft(0) a t + O(At) = G(O), t + O(At) for k = 1, 2,.... Denoting by S (t) the probability that n items held at n time t are all disposed of, we obtain the following analogue of Theorem 10: THEOREM 1. The relation (6. 9) Fn(t) = G(0)[ 1 - S (t)] holds for n = 1,2,... and t > 0.

-31 -Comparing (6. 4) with (6. 3), and (6. 9) with (5. 8), leads to the identities (6. 10) a(0)[ - R (t)] = jE (t)- E (t)] n n n 1 -(6,. 11) G()[ 1- S (t)] G[ F (t) -F (t)] n n n-1 which hold for t > 0 and n 1, 2,... These last relationships exhibit a parallelism between the cases of unannounced and announced prices, and also suggest that the properties of the functions a and G are worth examining. To begin with, we note that (6. 1) is equivalent to IO (6. 12) a(z) (z)dz9 J Z as may be seen upon integration by parts. This shows that a(Z) is monotone decreasing for Z > 0, and is strictly decreasing for all Z such that ~(Z) > 0. Also9 it possesses right and left derivatives, which are equal except for a coutable number of points (the discontinuities of 6(Z), and are both monotone increasing. It will now be shown that G(Z) has similar properties. It is convenient to define g(z, x) = (z - x) (z)o Then G(x) = max g(z, x) z and 3 (x) = [inf z I g(z x) = G(x)] We shall also introduce (x) [ up z I g(z, x) G(x)]. Some difficulties arise if ^(x) = 0 or if g(z) = 0 for all z > x, since then g(z, x) < 0 for z > 0 and g(z, x) 0 for z > x. It will be convenient to define g (x) = x9 7 (x) = x + 1 in these cases. Although they will be ignored in the following discussion9 it may readily be verified that the results stated remain true. Note that these definitions g(x, x) = 0 and hence A^

-32 -(x) > x and WI (x)> x for all x > 0; moreover N (x)> x unless q(z) = 0 for all z> x. Lemma 5. The function D is monotone increasing and right continuous. Proof. The argument used in the proof of Lemma 4 to show that J^ is monotone increasing applies equally to. To show that ' is right continuous, let z = lim y (x) be the 0 x-*xo+O right-hand limit of ] (x) at x = x. Then since g(z, x) < G(x) = g(y (x),x) and g is continuous in x for x> 0, z > 0, we have g(zxo li g(z, x) < = im g (x), x) -0 x-X+x +0 x -.Xo + 0 (6. 13) = lim [' (x) - x] lirn [ (x - ln)] < [ z - x ] [ lim 0 (x)] x-).x +0 / x,x+0 ~ x-x, +0 =(z - x () (ZO) g(zo, x). As in the proof of Lemma 4, the inequality (6. 13), together with the monotonicity of y (x), implies that 7 (x ) = z and thus that a is right continuous. From the definitions of 3 (x) and -7 (x) and Lemmas 4 and 5 it is clear that 3 (x) < y (x) for all x, with equality holding except for a countable number of values of x. Lemma 6. The functions St[ 3 (x)] and 6[ ' (x)] are respectively left and right continuous. Proof. The left continuity of (4[ (x)] follows from the left continuity of Q and 3 and the monotonicity of ~.

-33 -To see that ([1 (x)] is right continuous, note that if 0< x < x we have the chain of inequalities gj-< G(x) =g( (x),x) < g(- (x),x) < G(x ) = g(- (xo),X)o Since lim g( (xo) X) = g( (x ),x), it follows that o~ x_ —x+ 0 0o lim g( (x),xo) = g(-(xo), x ), that is, that x —x +0 o o 0 (6. 14) lim [ (x) - xl] 6[1( (x)] =[ (X) - x ] ^[ (x)] 0 Since v1 (x) is right continuous and I (x ) - x > 0, (6. 14) can only be true if lim i[q (x)] = ^[^ (x )] that is, if i[{ (x)] is right continuous. Incidentally, this argument shows that G is right continuous; it is easily seen to be left continuous, and is thus continuous. THEOREM 12. The function G(x) has the left derivative (6. 15) G (x) = - {[ (x)] and the right derivative (6. 16) G (x) - [ (x) for all x> 00 Proof~ Suppose 0 < x < x o Then we have G(x) - G(xo) = g('(x),x) - g((x),x ) < g(3 (x),x) g(3(x),x ) = (xo x)[ ()]; also G(x) - G(xo) > g( (xo),x) - g( (x ), ) = X [ (x) (xo)] Hence (6. 1L7) - 4 3 (x)] < G(x) - ^-[ ) (xo)] < 0 and on applying Lemma 6 taking the limit of (6. 17) as x- -x - 0 we see that o

-34 -(6. 15) is verified. Writing G(x) - G(Xo) = g(' (x),x) - g( (x ),x ) with 0 < x < x and following similar reasoning establishes (6. 16). Note that the right and left derivatives are both monotone increasing and can differ only at a coutntable number of points. Corollary. The function G may be expressed in either of the forms (6. 18) G(x) = [3 (z)] dz = J [ (z)] dz. X x For convenience, we shall write q W[ (z)] = t(z); thus (6. 12) has the analogue -oo (6. 19) G(Z) = / t (z) dz. Comparing (6. 12) with (6. 19), and (6. 3) with (5. 8), we conclude that the expected gain from a sale without announced prices with a distribution of offers given by ~ (z) will be the same as for a sale with announced prices and a distribution of offers given by e (z). -Z For example, if 6(z) = e for z > 0, we have, as noted earlier, k X) = x 1, and consequently z) = e - e. This AistTOution could be derived from the previous one by eliminating all but a fraction - e of the buyers, and would thus correspond to changing the time scale in the same proportion. Comparing (5. 22) with (5. 16), we see that this is indeed the relationship of E (t) with F (t). n n It follows from these remarks that to every example with announced prices there corresponds a mathematically equivalent one without announced prices. Consequently any properties that the functions E can be shown to n

-35 -possess will also be possessed by the functions F n n It is convenient to define (60 20) D (t) = E (t) ~ E (t) n = 1 2, t > 0 with the understanding that E (t) 0O It is intuitively apparent that D (t) increases with t for n = 1,2,. n and decreases with n for all t > 0' This result may be stated formally as THEOREM 13. The inequalities D' (t) > 0 and D (t) > D (t) hold n n n+l for n = 1, 2,,,, and t> 0O Proof. Proceeding by induction, we note first that a[ El(t)] > 0 for all t > 0, since the probability that the sale price is greater than the expected receipts must be positive. Hence by (6. 3) (6 21) D( t) = E(t) = 4E(t)] > 0O Now suppose DI (t) > 0 for some n> 2 and all t > 0 By (6 3) (6. 22) D" (t) = E (t) E (t) = D (t)] o D (t)] n n n-I n n-1 If D (t) > D (t), it follows from (6. 22) and the properties of a that n - n. i D' (t) <0 and hence that D ) (t) - D (t) > D (t) > 0 It follows from part (b) n -I n-1 n ~ of Lemma 3 with f(t) = D (t) - D (t) that D -(t) - D (t) > 0 for t> 0, and n=l1 n n-1 n - hence that D'(t) > 0 unless a[D (t)] = [ D (t)] = 0 Since n n n-1 D' (t) = [ D (t)] - 4{ D 2(t)l the latter possibility would contradict the n-1 n- A n-2 assumption that D' (t) > 0. n-I By induction D' (t) > 0 for n = 1, 2,..: the second part of the conclusion follows by rewriting (60 22) with n replaced by n + 1.

-36 -A final result of this kind is stated without proof. It may be proved by means of Lemma 3 and the properties of a. THEOREM 14. If for some n> 1, > 0, and h> 0, the equality D ( ) = D+i ( + h) holds, then D (t) > Dn+ (t + h) for all t > 7. Concluding Remarks A number of lines of further inquiry are suggested by the foregoing discussion. First, many interesting questions can be raised about the behaviour of the functions E (t) and other related functions. It would be particularly n desirable to obtain asymptotic formulas for large values of n. Second, generality would be gained by permitting the buyer to purchase more than one item, and by allowing the stock to consist of more than one kind of goods. A variety of assumptions could be made about the distribution of buyers' offers in this case. Finally, it seems apparent that the principles developed above could be applied to the case where the seller can replenish his stock at various times during the sale. It would be especially interesting to see whether the treatment could be extended to the case of a continuing business. University of Michigan

I UNMY OOF MS1QtC 3 111111 1111123111 8611 3 9015 03023 8607