Solution Horizons for a Class of Nonstationary Dynamic Optimization Problems and Games Alfredo Garcia Robert <.Smith Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109 Technical Report 96-17 November 1996

Solution Horizons for a Class of Nonstationary Dynamic Optimization Problems and Games. Alfredo Garcia and Robert L. Smith Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 1 Introduction. Infinite Horizon planning problems are motivated by the difficulty in establishing a rationale for a fixed finite "planning" horizon.If a finite horizon is used, "end of horizon" effects can alter the validity of the model in question. Hence, it has been argued that an Infinite Horizon is a better way to model instances in which for dynamic optimization problems or dynamic games, the decision makers do not have a clear and prespecified ending date. However, the gains in modeling accuracy are severely compromised by the technical difficulties that render intractable the analysis. This is particularly troublesome in instances in which the parameters are not known precisely and are assumed to vary in time. In other words, the case with "nonstationary" parameters. This last consideration leads to the problem of finding a finite horizon such that the first optimal or equilibrium outcomes for such horizon coincide with the Infinite Horizon counterparts. If such a horizon exists (which is called "solution horizon"), not only provides a rationale to set such horizon as the decision makers "planning" horizon, but interestingly enough motivates a finite algorithm to solve an infinite problem. In this chapter, we tackle the problem of proving existence of "solution horizon" for a class of Nonstationary dynamic optimization problems and games. We make use of "lattice programming" techniques that allow to prove monotonicity of first period optimal solution; then by a limit argument and compactness we obtain the existence of the Solution Horizon. 1.1 Preliminaries. We consider the following family of Dynamic Optimization Problems: 1

* At time period t, At C R the set of all feasible actions, and St C R the set of attainable states, and finally At(st) C At the (closed) subset of feasible actions given current state St. * If an action at C At(st) C At is taken given state st E St, a reward rt(st,at) E R is accrued and the next state to be attained is st+i = ft(st, ut) where the state dynamics mapping ft(.,.) and the reward function rt(.,.) are assumed continuous. * The T-period horizon optimization problem is, for a given initial state so: T max rt(st, at) t=O s.t St+I = ft(st, at) at E At(st) C At = 0,2,...,T We will use a more compact notation for this problem, as follows: T Let A(T) C fJ At, the closed subset of T-long feasible sequence of actions with product t=0 topology and for aT e A(T), let (So, S1, 2,...,ST) the sequence of states attained by following the sequence of actions aT; that is: s1 = fo(so,ao) 82 = fi(sl,al) 3 = f2(2,a2)... then, the total reward accrued is: T-1 RT(aT) = rt(st, at) t=O so the T-period horizon optimization problem above is equivalent to: 'R = max RT(aT) aTEA(T) and: A*(T) = arg max CT(aT) aTEA(T) * The Infinite Horizon Problem: T-1 max lim inf E rt(st,at) T-oo t=0 s.t St+l = ft(St,at) at E At(st) C At t = 0,1,2,... As above, we will use a more compact notation for this problem, as follows: 2

00 Let A C 1 At, the closed subset of infinite feasible sequences of actions with product t=O topology and for a E A, let (so, sl,s2,...) the sequence of states attained by following the.sequence of actions a, then we set the criteria as follows: T-1 R(a) = lim inf S rt(st, at) T-+c<> t=o so the infinite horizon optimization problem above is equivalent to: R* = max R(a) aEA and: A* = arg max R(a) aEA 1.2 Standing Assumptions Throughout this chapter we will assume the following: Assumption 1 For every planning horizon T, A*(T) 7 0 and A* 7 0.Moreover, for an indexed collection {aT C A*(T)}T such that: lim aT = a T- oo we have a E A* For a thourough study of sufficient conditions that imply Assumption 1, the reader is refered to Flam and Fougeres[7] and Schochetman and Smith [10] and [11]. Assumption 2 (Compactness) For every t, At is compact. 2 Examples. In this section we give three classes of dynamic optimization problems that belong to the family introduced in the previous section. 2.1 Optimal Exploitation of Renewable Natural Resources. We are given an initial stock so of a natural resource. We have to choose an exploitation level Ct at time period t, from which we experiment a net reward rt(ct). The remaining stock if the 3

available amount of resource is st, is then st - ct which shall renew at a pace ft(st - ct) (with the convention that ft(O) = 0). The T-Planning Horizon problem is to choose exploitation levels so to maximize total discounted reward: T-1 max E rt(t)' t t=O s.t St+i = ft(st - Ct) ct E [O, st] t = 0, 1,2,..., T -1 2.2 Production Planning. The T-long horizon time varying production planning problem, with given initial inventory level Jo, cost of finding a production schedule that satisfies demand at minimum cost. T-1 min E (Ct(xt) + ht(xt t - dt)) '/3t t=O It+l = max{It + xt - dt, 0} t=... Mt > Xt 0 -,,,, where Xt is the production level at time period t,Ct(xt) is the t-th-period production cost function and: h K () K.t I if > 0 h() = pt tI otherwise where Kt is the unit inventory holding cost at time period t and pt is the unit shortage cost for unfilled demand at time period t Also, Mt is the maximum production level allowed at time period t and (3 is the discount factor. 2.3 Equipment Replacement. The problem is to find a replacement strategy that minimizes the discounted total cost of acquiring, operating and retiring assets over the planning horizon. Let MlIt the cardinality of the set of equipment technologies that were at least once available up to time period t. We shall denote by At C {0, 1, 2,.., Mt} the set of available tecnologies at time period t and let Xt E At represent the choice made at time period t ( Xt = 0 meaning to keep current equipment ). Moreover, let Lt(x) represent the economic life of asset choice x (with Lt(0) = 0) and Ct(x) the cost (including first cost, operating cost and salvage value) of acquiring an asset of type x at the beginning of period t. Finally let us denote by it the residual life at the end of period t of the last asset acquired. Formally, the finite horizon problem is: 4

T-1 min Z Ct(Xt) ft t=O lt+l = it + Lt(xt) - 1 2,...9 T - 1 t = 0, 1,2,...,T- 1 xt E At C {0, 1,2,..,Mr} where fi is the discount factor.It is worth pointing out that under this construction the cost functions Ct(.) are not convex in general. 3 Existence of Solution Horizon. Let us assume now that for every T-period horizon optimization problem there exists an optimal solution such that the first period decision behaves monotonically with respect to the planning's horizon length.A straightforward existence of solution horizon result follows: Theorem 3.1 (Solution Horizon Existence) Under Assumptions 1 and 2 and assuming that there exist an indexed collection {aT E A*(T)} such that for all T: either aT > aT+1 or aT < aT+1 then for some a E A*, and for any e > 0, there exist a planning horizon T such that for T > T we have d(aTo, ao) < Such horizon is called a "Solution" horizon. Proof. By compactness the indexed collection {aT E A*(T)}T has some converging subsequence: {aTk A*(Tk)}k We denote by a the limit of such subsequence: lim aTk = a k,r By assumption 1, a C A*. By monotonicity of first period decision and compactness, the sequence {aT} converges, moreover by comnponentwise convergence: lim ao7 - ao T-, X 1 5

4 Pathways to Monotonicity of Optimal Solutions. We now present new weaker conditions that allow for monotonicity of first period optimal solutions. In general, monotonicity results can be found in many different settings with proofs strongly relying on the specificities of the various settings ( see for instance Heyman and Sobel's [6] Chapter 8 1984 ). Donald Topkis [1] provided a unified treatment of monotonicity of optimal solutions by working with lattice theory. However, it was noted that the conditions he required for monotonicity (Super and Sub -modularity) as we shall review below, were far from necessary and were constantly obtained by assuming Concavity or Convexity, which in itself was not surprising given that most of the available results were based on these assumptions (see for instance Veinnot [8]) More recently, Milgrom and Shannon [2] have defined a surrogate of Super and Submodularity, called Quasi Super and Submodularity which is both necessary and sufficient for monotonicity of optimal solutions. 4.1 Lattice Theory. A set S with a partial order "-" (i.e a reflexive, transitive and antisymmetric binary relation) is a Lattice if the "join" x V y and the "meet"x A y of any two elements x, y E S are both in S. A lattice is complete if the "join" and the "meet" of any collection of elements in S is in S. A real valued function f: S - R is isotone(resp. antitone) if x F> y implies f(x) S> f(y) (resp. f(x) < f(y) ). Let P(S) denote the set of all non-empty subsets of S and L(S) the set of all non-empty sublattices (So E P(S) is a sublattice if for any two x, y E So then x V y E So and x A y E So ). An ordering "_p" can be defined on P(S) as follows, for X, Y E P(S): X _>p Y C: x C a y C xVy an E d x A y E Y. L(S) is partially ordered by '-p". An isotone(resp. antitone) function F from a partially ordered set T into L(S) is called ascending (resp.descending ). In other words, F is ascending if t > t' in T and for any x E F(t) and y G F(t') then x V y E F(t) and x A y E F(t'). 6

A real valued function f: S H R is submodular (resp. supermodular) if for any x, y E S f(x) + f(y) > (<) f(x V y) + f(x A y) If S = R2 then this is equivalent to, with (x1, y1), (X2, Y2) E R2 and x2 > XI, Y1 > Y2: f(xI, yi) + f(x2, Y2) > (<) f(x2, Yi) + f(xi, Y2) If f is twice differentiable this is equivalent to: a <(~>)0 OxOy - Assume now that f is a real valued function defined on a subset S C X x T where X is a lattice and T a poset. We say that f has antitone (resp. isotone ) differences in (x,t) E S iff for x > x' and t > t' we have: f(x, t) - f(x, t') < (>) f(x', t) - f(x', t') or equivalently: f(x, t) - f(x', t) < (>) f(x, t') - f(x', t') For the case when the sets X and T are chains then the following results yields a powerful method to prove submodularity. Lemma 4.1 Iff: X x T H-4 R has antitone(resp. isotone) differences on (x,t) and X and T are chains then f is submodular(resp. supermodular ) on X x T. Proof. See Topkis[l] theorem 3.2 Theorem 4.2 Topkis[l] 4.1 Let f: S R be a real-valued submodular function where S is a lattice, then the set of points S*, at which f attains its minimum on S is a sublattice. 7

Proof. Pick any x, y E S*.By submodularity on S and optimality of x and y: 0 < f(x V y)-f(x) < f(y)-f(x A y) < 0 Hence xVy,xAy E S*. In a poset S, a natural way to induce a topology is by using the partial ordering. The interval topology is defined as the one for which the sets: [x, ) = {y: y E S,x _ y} (-oo, x] = {yy: E S,x y} form a subbasis of the closed sets. The next result indicates why this topology is widely used, see Frink [12] and Birkhoff [13] Theorem 4.3 Complete Latice Characterization Theorem: A lattice is complete in the interval topology if and only if it compact. A very important corollary of Theorem 0 is then viable through this characterization: Corollary 4.4 If S is a compact lattice ( in the interval topology or finer ) and f: S -* R is submodular and lower semicontinuous then the set S* is a non-empty compact and complete sublattice, and hence it has a greatest and a least element. Proof. By Theorem 1, S* is a sublattice. By standard result in real analysis, S* is non-empty and compact. Thus, by the characterization of complete lattices, S* is complete. U 4.2 Topkis's Results. Submodularity is preserved after the minimization operation. If X and T are lattices, S is a sublattice on X x T, St = {x: (x, t) E S} is the section of S at t E T and the projection of S on T, which we shall denote by nT S, {t: St is not empty}. Theorem 4.5 Topkis[l] 4.3 If X and T are lattices, S is a sublattice of X x.T, f is submodular on S, St is the section of S at t G T and v(t) = inf f(x,t) is finite on the XESt projection HT S, then v(t) is submodular on nT S Proof. We pick any t, b E HT S and x C St, y E Sb.Because S is a sublattice of X x T: (xVy,tV b) S (x Ay,t A b) C S 8

Thus: v(t V b) + v(t A b) < f(x V y,t V b) + f(x Ay,t A b) f(x,t) + f(y, b) Now, by taking the infimum on the right hand side over x E St,y E Sb we obtain the desired result. U The next theorem points to sufficient conditions for the monotonicity of the optimal solution set. Theorem 4.6 Topkis[1] 6.1 Let f: S C X x T - R be a real-valued function with S a lattice and T a poset such that: * f(x, t) is submodular in x on X for each t E T. * f(x, t) has antitone differences in X x T * St E L(X) is ascending on T then S = {x: x E argminf(y,t)} is ascending in t. yESt Proof. For each t E T, by theorem 1 S is a sublattice of S. Let us pick t, b E T* with t < b where: T* {t: S is not empty} and x E S and y E Sb. By hypothesis,,St Sb and: x Ay E St and x Ay E Sb Then by hypothesis: f(x A y,t) - f(x, t) < f(y,t)- f(x V y, t) < f(y, b) - f(x V y, b) then by optimality of x in St and y in Sb, we have: 0 < f(x A y, t) - f(x, t) < f (y, b) - f(x V y, b) < 0 Hence, xA y ES andxVy Sb * The characterization of complete lattices yields then the following corollary Corollary 4.7 In addition to the hypothesis of the above theorem, if St is compact for all t E T and f is lower semi-continuous, then S*(t) has a greatest x(t), and a least element x(t) both of which are isotone on t C T. 9

4.3 Tarki's Intersection Point Theorem. A lattice S is said to be completely ordered if for all x, y E S there exists z e S such that: Given a real valued function f we denote by f(X) = {f(x): x E X} where X is a certain subset of its domain. A function g: S - S is quasi-increasing if for X C S: g(sup X) > inf g(X) and supg(X) > g(inf X) where the "inf" and "sup" are taken with respect to the partial ordering in S Similarly, A function g:S - S is quasi-decreasing if for X C S: g(sup X) < sup g(X) and infg(X) < g(inf X) These notions are algebraic equivalents of a function having no downward jumps and a function having no upward jumps respectively. Theorem 4.8 Tarski's Theorem:Let S be a densely ordered complete lattice, f S - S quasi-increasing and g: S H-* S and: g(inf S) < f(inf S) and g(sup S) > f(sup S) then P = {x S: f(x) = g(x)} is non-empty. Proof. See Tarski [4]. U 5 Solution Horizon Existence. We now present a "monotonicity" result of optimal first period decisions with respect to Planning Horizon's length by using the lattice theoretic approach reviewed above. It turns out that for the set of applications presented, the requirements are relatively "weak" when compared to other available monotonicity results in the specific field of application. We first state the standing assumption for the analysis: Assumption 3: For t = 0, 1, 2,... we assume: * The reward functions rt(s, a) are convex in their first argument, supermodular on (s, a) 10

* The functions ft(s, a) are non-decreasing in (s, a) and convex in s. * There exists a uniform upper bound on the set of attainable states at time t,i.e: M = sup s < oo t,sESt Hence St C S = (-oo, M] for all t. * The action sets At(s) are "ascending" in (t, s) and convex. We now introduce the notation and assumptions needed for the analysis. We will denote by VT(s) the net present optimal value for the T-horizon dynamic optimization problem of the above presented family with given initial state s that starts at time period t E A. Analytically, that is: (PT) V(s) = max {t * rt(s, a) + VT+l(ft(s, a))} aEA(s) where we set VT +1 = 0 and Vo~ = 0.We now state the most important assumption: We first show how for a fixed finite horizon T, the value functions VT(.) t c Kv are convex. Lemma 5.1 Under assumption 3, for fixed planning horizon T, the value functions VT(.) t e jA are convex. Proof. We first show that VTT(.) is convex. We notice that by convexity: rT(A + (1 - A) s', a) < A rT(S, a) + (1 - ) V rT(s',a) Or equivalently, 13T* rT(As + (1 - A) s',a) < A _SOT rT(S,a) +(1 _- A).T rT(s', a) Hence, by definition: /3T rT(A, +(1 - A) s',a) < A. VT(s) + ( - A). V7T(s') In particular: VT(As + (1 - A)s') < A. Vf(s)+ (1 - A). VT(') 11

By induction, let us assume VT(.) is convex, we have to prove that VT-1(.) is convex.As above we first notice that by convexity: pt-lrt-l(s + (1 - A)s',a) + VT(ft-i(As + (1 - A)s',a)) < A' [t-l1rt-_(S, a) + VT(ft- (s, a))]+ (1 - A) [t-lrtl(s, a) + VT(ft-l(s', a))] Hence, in particular: t-lrtl(As + (1 - )s', a) + VT(ft-(As + (1 - A)s',a)) < A. VT-(s) + (1 - A)X VT-(') Finally, VT-(As + (1 - A)s') < A. VT-1(s) + (1-A) VT-1(s') Lemma 5.2 Under assumption 3 the objective functions of the collection of optimization problems (Pt) are supermodular on (s, a) for t e A. Proof. We first prove it for optimization problem (PTT). Let LT the set of all feasible pairs (s, a), that is: LT = {(s,a) such that s ST, a E AT(s)} We note that LT is a lattice since by assumption AT(S) is "ascending" in s.Let us take two two-tuples (s, a),(s', a') e LT such that s > s' and a' > a. Hence, with respect to product ordering, we have: (s V s', a V a') = (s,-a') (s A s', a A. a') = (s', a) So we need to show that: *T rT(S, a') + iT rT(s', a)) > /T. rT(s. a) + /T 3 r'T(S', a') which is exactly the first part of assumption 3. For (PT) t E {O, 1, 2,..., T -1} we use the result given in Lemma 1 as follows; pick any two pairs (s, a),(s, a') E Lt,where Lt is the lattice Lt {(s,a) such that s C St,a C At(s)} we have by monotonicity of ft(.,.):.ft(s, a') ~> ft(s, a) > ft(s', a) ft(S, a') > ft(s', a') > ft(s', a) 12

There exist A E (0,1) such that: ft(s, a) = X ft(s, a') + (1- A) ft(s',a) ft(s', a') = (1 - A) ft(s, a') + A ft(s', a) Thus by convexity of VT+I(.) we have that: VT+ (ft(s, a)) < A * VT+ (ft(s, a')) + (1 - A) * V+ (ft(s', a)) VT+'(ft(s', a')) < (1 - A). V+(ft(s, a')) + A X VT+l(ft(s', a)) Adding the previous two inequalities and by the assumption that rt(.,.) is supermodular we obtain the desired result: t. rt(, a') + VTl(ft(s, a')) + 3t. rt(s', a) + VT+(ft(s', a) 3t. rt(s, a) + VT+1(ft(s, a)) + 3t rt(s', a') + VT+l(ft(s', a') 5.1 Monotonicity of Optimal Solutions. We now state and prove the main result of this paper. For this result we need a second key assumption. We shall denote by AX in what follows the set of natural numbers. Assumption 4: For any t E A/ and a' > a, s' > s we require: * [rt(s, a') - rt(S, a)] > rt-1(s, a') - rt-1(s, a) 3 * [rt(s', a) - rt(, a)] > rtl(s', a) - rt-i(s, a) One way of interpreting this assumption is when reward functions are partially differentiable, where the last two requirements translate into: rt(s, a + 6a) - rt(s, a) + 6a) - rti(s, a) p 3lim > lim 6a —0O ba a- -O ba lim rt(s + 6s, a)- rt(s, a) > lim t-(s + 6s, a) - rt-1 (s, a) pdlim > lim ( ' ) ( ---6s-,O Es - s-0 So or equivalently: 9rt(s, a) rt-I(s, a) da da 13

art(s,a) rti_(s, a) Os Os In words this says that discounted marginal utilities are non-decreasing in time.This assumption corresponds intuitively to the fact that technological progress allows for larger marginal utilities (via cost reduction, etc...). Theorem 5.3 Under assumptions 1,2,3 and 4, for fixed initial state s,there exist monotone optimal solutions for the collection of problems (PT), i.e there exist aT A*(s T), where A(s, T) = arg max {ro(s, a) + V (fo(s, a))} aeAo(s) such that for any aT E A(s, T): and: aT > > rTi a0T 0 aT > a__T+I Proof. We need to show that V~T(fo(sa)) is supermodular on (a,T) for a fixed initial state s.In order to do so, it suffices to show that VT1(x) is supermodular on (x, T), since fo(s, a) is monotone nondecreasing in (s, a) For ease of exposition let us denote by LT, the set of all feasible triplets (an action that is feasible for a given initial state and a given planning horizon), at time period T i.e: LT = {(s, a,T) such that s E S, a E AT(s) and T C A} We first notice that LT is a lattice since by assumption AT(s) is "ascending" in (T, s) We first note that the maximand for the T-th stage objective function is supermodular on (s, a, T) C LT.Indeed, for the 3-tuples (s, a, n),(s', a, n - 1) LT such that s < s we have: (s V s' a V a, n V (n - 1)) = (s a,n) (s A I, a A a,n A (n - 1)) = (s,a,n - 1) and by assumption 4: /3 rn(S', a) + rn_-(s, a) > /3 rn(s, a) + rn_l(s', a) 14

Also, for the 3-tuples (s, a, n),(s, a', n- 1) E Lt such that a < a'. Then: (s V s, a V a', n V (n - 1)) = (s, a', n) (s A s, a A a', n A (n - 1)) = (s, a, n - 1) But by assumption 4, we have: rn (S, a') + /3 rn(s, a) + rn-_(s, a') For planning horizons that differ in more than one period the proof follows by iteratively invoking assumption 4. We now invoke Topkis'[l] Theorem 4.3 to prove that the T-th stage value function, i.e VTT(s), is supermodular on (s, T) X S x JA (or equivalently has isotone differences in (s, T) e ST x A). With a backward induction argument we assume now that the t+l-th stage (O < t+1 < T) value function is supermodular on (s, T) E S x g/.We note that the t-th stage objective function with planning horizon T, i.e:. rt(s, a) + VT (ft(s, a)) is supermodular on (s, a, T) C Lt where Lt is the lattice: Lt= {(s, a, T) such that s E S, a E At(s) and T E A/ Indeed, as above,for the 3-tuples (s, a, n)(s', a, n - 1) E Lt such that s < s' and: (s V s', a V a, n V (n - 1)) = (s', a, n) (s A s', a A a, n A (n - 1)) = (s,a,n -1) by the backward induction hypothesis we have that: V+2 (ft+(s', a)) + Vn+f1 (ft+s. a')) > V,+2 (ft+l(S, a))+ Vtn1 (ft+l(a)) hence: /trt(s', a) + Vn+l (.ft(',a)) +,(trt(s, a) + Vt+ (f(s, a')) 3tr(s, a) + Vt+l (ft (.. a)) + 1trt (SI, a)+ Vt+l (f(s', a)) Similarly, for for the 3-tuples (s, a, n),(s, a', 7n - 1) E Lt such that a < a'. We have: (s V s, a V a.. V (n - 1)) = (s, a', n) (s A s, a A a'. n A (n. - 1)) = (s, a, n - 1) 15

But by the backwards induction hypothesis: V+l (ft(s, a')) + Vn+l (ft(s, a)) > Vn+ (ft(s, a)) + Vni (ft(s, a')) Hence: /trt(, a') + Vnt+l(ft(s, a')) + /3trt(, a) + Vnt (ft, a))!trt(s, a) + Vt+l (ft(s, a)) + /trt(s, a') + V (ft/ ( a')) So we conclude that VT(s) (O < t + 1 < T) is supermodular on (s, T) E S x N/. In particular, VT(fo(s, a)) is supermodular on (a,T) for a fixed initial state s Finally, we apply Topkis's [1] Theorem 6.1 to the first period optimization problem for a fixed initial state s: max {ro(s, a) + VT(fo(s, a))} aEAo(s) The objective function in this problem has been shown to be supermodular on (a, T) and since by assumption the feasible set Ao(s) is compact, the result follows. U 5.2 Application to Optimal Exploitation of Natural Resources. In the context of Exploitation of Renewable Natural resource, the assumptions are equivalent to: Assumption 3: For t = 0,1,2,... the reward functions rt(c) are continuous and the dynamics of renewal modeled by ft(.) must satisfy: ft(O) 0 and it is monotone increasing. * There exists Xt > 0 such that for'every x > Xt we have: ft() < Xt Hence, the state space at time period t + 1 is St+l = [0, xt] and M = sup Xt t so that S = [0, M]. 16

Assumption 4: /3r.(c) > r_1(c) Discounted marginal consumption rewards are non-decreasing in time.This assumption corresponds intutively to the fact that technological progress allows for smaller marginal extraction costs. 5.3 Application to Production Planning. In the context of Production planning, the assumptions are equivalent to: Assumption 3: The requirement that At(s) is "ascending" in (ts) im, s) impliesgiven that in this case we identify this to the set [0, Mt] which is independent of the state It,: MAt < Mt+l In words, nondecreasing in time maximal production capacity. Moreover, supIt < M t An uniform upper bound to the set of attainable inventory levels. Assumption 4:By linearity of Inventory/Shortage costs this assumption translates into: /3 [CN(X) - CN(X)] < CN-1(x) - CN-1(X) For the case when: CN () = 'KN c + CN x x > O 0 Otherwise The assumption implies: 3 I A < A'N-I That is, nonincreasing discounted set up costs andl: 3- (' < Cv-1 which means nonincreasing discounted marlginlal production costs This assumption corresponds intutiovel to the fact that technological progress allows for smaller marginal production costs. 17

5.4 Application to Equipment Replacement. In the context of equipment replacement, the assumptions are equivalent to: Assumption 3: The "ascending" requirement on the feasible action set can be satisfied by requiring: At C At+l and: Mt < Mt+1 In words, there will appear new technologies and no available technology exits the market. Moreover, sup It < M t There is a uniform upper bound on the set of "technical" lifes of the equipment for the various technologies in time. Assumption 4: The condition: d ' [CN(') - CN(X)] < CN-1(X) - CN-I(X) implies that relative cost advantages decrease uniformly in time. One particular instance is the case of Stationary costs. 6 Of Further Research: The Stochastic Case. Let us now consider briefly the case where the state dynamics is not deterministic. Given state s at time period t, and if the action a E At(s) is taken, we will denote by Qt(/s,a) the t- period stochastic kernel (see Hernandez-Lerma[14] ) the Dynamic Programming functional Equations are: (p) VT(s) = max {i *rt(s, a) + f +l(y)Qt(dy/s, a)} aEAt(s) s for t E {0,1,2,..,T- 1} and: (PT) TVf(s)= max {/3. rT(s, a)} aEAT(s) 18

In order to extend the proof of Theorem I to the stochastic case, the key step is to prove that submodularity is preserved after maximization, and for this it is crucial to prove that the term J Vt+ (y)Qt(dy/s, a) S is supermodular (s, a, T) and t E {0, 1, 2,.., T - 1, T}. Pairwise, this leads to: * Qt(/s, a) supermodular on (s, a) for fixed t. * For the 3-tuples (s, a, n),(s', a, n - 1) E Lt such that s < s' and: (s V s', a V a, n V (n - 1)) = (s', a, n) (s A s', a A a, n A (n - 1)) = (s, a, n - 1) we require: f Vt+l(y)Qt(dy/s', a) - f Vt+l(y)Qt(dy/s, a) S S Vt+l (y)Qt(dy/s', a) - f Vt+y (y)Qt(dy/s, a) S S for t {0, 1,2,..,n-1, n}. * For the 3-tuples (s, a, n),(s, a', n - 1) E Lt such that a < a' and (s V s, a V a', n V (n - 1)) = (s, a', n) (s A s, a A a', n A (n - 1)) = (s, a, n - 1) we require: f Vt+ (y)Qt(dy/s, a') - f Vt+ (y)Qt(dy/s, a) S S V, 1 (y)Qt(dy/s, a') - f Vt1 (y)Qt(dy/s, a) s. S for t E {0,1,2,.., n- 1,n}. The particular forms that these requirements can take depend upon the specifics of each application. 7 Solution Horizon for a Class of Dynamic Games. R. Amir [3] pioneered the application of Lattice theoretic motonicity results to prove existence of Markov Perfect Equilibria for a class of stationary dynamic games. In this section, we consider the nonstationary case and prove a Solution Horizon Existence result. 19

7.1 Common Pool Resource Dynamic Games. We present the class of nonstationary dynamic exploitation of common pool resources. Given "consumption" levels c] and c2 at time period t, and the current level Xt of the Common Property resource, the dynamics is modeled by: Xt+1 - ft(xt - cL - c2) t = 0, 1,2,... where we assume that ft(O) = 0 and it is monotone increasing. Moreover, there exists Xt > 0 such that for every x > Xt we have: ft(z) < Xt Hence, the state space at time period t + 1 is St+1 = [0, xt],regardless of "consumption" levels c1 and C2.Moreover, let us assume that: M = sup Xt < ox t and we will denote by S = [0, M]. Given that there is no over-consumption, i.e: 0 < c < t i =1,2 c1 + c2 < Xt t = 0, 1, 2,... the Payoffs for the Infinite Horizon Game are: 00 E IUt(c) i = 1,2 t=O where we assume that sup U(c) < M < <oo i,t,c Under these basic assumptions, this class of dynamic games is "continuous at infinity" as defined in Fudenberg and Levine [5]. 7.2 Markov Perfect Equilibria. A strategy for player i = 1,2 is a sequence of maps of the form: 'yi = (%,7071,72,...) where 7': St > R+. We will restrict our attention to strategies that do not lead to over exploitation, i.e: a, + 7t < Xt Xt = ft2i(xt-i - -71) t = 1,2,... YLt t-I(Xt-i~ - It_i - yt_ 20

A pair of strategies (715,7'2) is called a Nash Equilibrium of the dynamic game if: 00 00 E nt * T(7 (t)) > E * U(Xt)) t=O t=O 00oo oo00 E Ut2(2(x,)) > E -t Ut(a2 (Xt)) t=O t=O In words, this says that no player gains strictly more by following a different consumption plan from the intial state xo. To avoid non-credible equilibria, that is those that may not prescribe equilibrium play after a subsequent state, the notion of Markov Perfect Equilibria (MPE) is introduced. We say that a pair of strategies (5Y1,' Y2) is called a Markov Perfect Nash Equilibrium (MPE) of the dynamic game if for every feasible state Xk E Sk at time period k > 0,we have: oo00 00 E U ( (X)) > E Rt U/ l()) t=k t=k 00 00 E * Ut2(72(Xt)) > E * U2(72(X,)) t=k t=k For a finite planning horizon the above definitions apply by simply considering total discounted payoffs up to the planning's horizon length. 7.2.1 Solution Horizon Existence. The class of dynamic games presented belong to the family of so called "continuous at infinity" games ( see Fudenberg and Levine [5] ). One of the most interesting features of this family, is that limit points of MPE of Finite Planning Horizon versions of the game are MPE of the Infinite Horizon game. Thus, if first period MPE outcomes are monotone in Planning's Horizon length then a solution horizon can be easily proved to exist along the guidelines of theorem 3.1 7.3 Solution by Dynamic Programming. 7.3.1 The last stage game. Let us consider the T-long planning horizon version of the dynamic game. In particular, let u s focus on the last period's game. We recall that a strategy combination, i.e (1s, 72) is "admissible" for the last stage game if for every s C S, there is no over consumption,i.e: y7(s) + 72(S) < 21

Player's 1 best response to strategy y2 S - R is the solution set of.: VT(S; r O) -= O max [/T T UT(c)] (1) Similarly, Player's 2 best response to strategy y1: S H R is the solution set of: VT(S;^,)- O<<max T[/T. U(C)] (2) 0<<,c-'-y1 (S) Let us restrict our attention to the next set of strategies: L= {y: S - R, 7y(O) =0 y is l.s.c and 7(x) -(y) < x-y Vx, y such that x > y} If we define a partial order >lin L as follows, for 71, 72 E L: '71 -l 72 if and only if Vs E S we have 1 (s) > 72(s) Then the next result justifies the partial ordering choice. Lemma 7.1 The set (L, _1) is a densely ordered complete lattice. Proof. See Amir[3]. The following lemma will prove helpful in the next discussion. Lemma 7.2 Let 71,y2 E L.If for every s E S and c' > c /[U+(c) - UW(c)] > U_1(C') - U_-(c) then the value functions VTT(S; y2) and /T2T(s; y 1) are supermodular in (s,T). Proof. We give the proof for the optimization problem (1), that is: VT(s; 7 ) = max [fiUTV(c)] VTT(Sv) O<c<Ss-y2 (s) We note that the set 0 < c < s - 2(s) is ascending in (s, T) and by assumption the objective function is supermodular in (s, c, T) S x [0, s - y2(s)] x A ( note that this cartesian product 22

is a lattice, since the set [0, s - 72(s)] is ascending in s ). Hence by Topkis's Theorem 6.3, there exist an extremal monotone best reply, i.e: BR(s;-2)} E arg max U[[TiU(c)] BR~T(s; a) E arg maO<c<xs- 2 (s) BR4(s; y2) in (s, T).Moreover, by Topkis' Theorem 4.1, the value function VTT(s;2) is supermodular in (s, T) E S x A'. Lemma 7.3 For fixed s E S and 7, i E L such that 7 > Iz then: BR'(s; a) BR'(s; y) Proof. It simply follows form the fact that Optimization problems (1) and (2) are supermodular in (c, y) with 7 E L being the opponent's strategy. The feasible consumption set 0 < c < s-y(s) is ascending in 7 E L fro fixed s E S. After noting these facts, the results follows from Topkis'Theorem 6.1 We now use the previous results in conjunction with Tarski's Theorem to prove existence of monotone equilibria in T for last stage game. Theorem 7.4 For fixed s C S there exist a Nash Equilibrium for the last stage subgame in strategies that belong to L. Proof. We define two relevant maps as follows: P:LxL - LxL (7, l) H ((7 + it) A s, (7 +.) A s) We note that the identity function f(s) = s is tlhe lowest upper bound of lattice L. P is clearly isotone in L x L with respect to product ordering and: P(0.O) (0,0) P(ss) = (s,) The other useful map is: QT: L x L X - L x L (7, A) I.(BR'(.; i) +,, + BR (.; )) L r L T TL Tt. 23

By the Lemma 2proven above the map QT is isotone in L x L with respect to product ordering. Moreover: QT(O, O) _Ix, P(O, O) QT(X, X) = (, x) Hence the conditions on Tarki's intersection Theorem are met, i.e there exist (7*, *) E L x L such that (7*+*) As =BR(.;=*) +* (7*+ t*) A s = BR(.; 7*) + * from where we conclude the result. 7.4 Bacward Induction. We now consider the t stage game, to prove existence of MPE for all feasible subgames starting at time period t, and assuming existence for the subgames starting at the remaining stages of the game and the monotonicity properties as shown for the last stage game. If for every s E S, there is no over consumption, i.e: y (s) + y2(s) < s Player's 1 best response to strategy -2 S -> R is the solution set of: VtT(s; 2)= O<ax [/' ~ U(c) + Vt+,T(ft(s - - 72(s)))] (1) 0<c<s —y2 (s) Similarly, Player's 2 best response to strategy y1: S '->R is the solution set of: VtT (; 71) O[t U2(c)+. Vt+, (ft(s-c- 7(s)))] (2) 0<C<s —y1 (s) We now replicate the results in the previous section for the t period stage game with initial state s. Lemma 7.5 Let y-,7y2 E L. Under the same assumptions as in Lemma 1 above the value V1 (S;,22 functions VTa(s;y2) and VtT(s; y),re supermodular in (s,T) E S x Jf, moreover, for fixed s C S there exist extremal monotone decreasing optimal solutions in T Proof. We give the proof for the optinization problem (1), that is: Vt,T(S; ) ax [. U(c) + Vt+,T(ft(S-c-2()))] O<c<s-y2(s) 24

We note that the set 0 < c < s - 72(s) is ascending in (s, T). Let us make a change of variable as follows: - - c - -2(s) Thus the equivalent to player's 1 optimization problem is: Vt T(S; ) = max [. I Ut(s - y y-72(s)) + Vt+l,T(.fT(Y))] O<y<s-y2 (s) The objective function of this problem is supermodular in (s, y, T) E S x [0, s - 72(s)] x. We note first that for the two tuples (y', T) and (y, T - 1) such that y' < y we have: (y'V y, T VT-) = (y, T) (y'Ay,TAT-1) = (y',T- 1) and by supermodularity of Vt+lT(s) on (s, T) by backward induction and by monotonicity of ft(.) we have that: 1,T(fT(Y)) + Vt+lT-(fT(Y')) > Vt+l,T(fT(Y')) + Vt+,T-i(fT(Y)) Hence: { Ut- y( - y 72(s)) + V1 (fT(y)) + P stUJ( - y- y2(s)) + VT-l(fT(Y)) - - 72()) + Vt+lT(fT( )) + tUt(S - y - 72()) + VlT-(fT(y)) We finally show that the aforementioned objective function is supermodular in (s, y).Indeed, for the two tuples (s', y') and (s, y) such that s' > s and y' < y we have: (s'V s, y' Vy) (s', y) (s'As, y'Ay) = (s,y') Moreover: I - y - y2(S) 2> s' - y2(s') > s - y (s) s' - y/- _2(s/) > s y, - 2(s) > s - y - y(s) hence, there exist A C (0, 1) such that: '- y - 2(s') = A (' - -y2(s')) + (1 - A) ( - y - 2(s)) s- y'- 72(s ) ( s' -y'- 2(s')) + A (s - y - 2(s)) and by concavity: Ut(S' - y- 72(')) > A Ut(s' - - y'72(s')) + (1 - A) Ut ( - y - 2()) Ut(s -y'- 72(s)) > (1 - A) _ U(s' -y'- 72(s')) + A Ut( - y - 72()) 25

The claim follows by adding the previous inequalities. Finally, by Topkis's Theorem 4.1, the value function VT-_1T(S; 72) is supermodular in (s, T) If we apply Topkis' Theorem 6.3 to the optimization problem: Vt1 (8; _2) = I7_2U1 8 _ _ _ 2(8)) tTr(s;) -= max [ U(s-y- ())+ Vt+lT(fT(y))] 0<y<s-v2 (s) Since we have shown that the objective function of this problem is supermodular in (y, s, T) there exist extremal monotone optimal solutions in T. E Lemma 7.6 For fixed s E S and y,t C L such that y > f, then for each player i = 1,2 there exist an extremal monotone best reply, i.e there exist BRt(s; s) and BR/(s; y) where: BRt (;;/) E arg max [3it Ut (c) + Vt+l,T(ft(S - c - /(S)))] O<c<s-,4(s) BRt(s; 7) E arg max [ U(c) + Vt+l,T(ft(S - c- 7(S)))] O<c<s-y(s) such that BR'i(s; ) BR'(s; ) and BR;(s;/,),BRi'(s;-y) E L. Proof. Let us make a change of variable such that: y = s - c-,(s) Thsu the equivalent to player's 1 optimization problem is: max [/ t U (s -y - u(s)) + Vt+lT(fT(y))] 0<y<,s-i^(s) We note that the constraint set is "descending" in a E L by the very definition of the partial ordering in L. Moreover, the objective function is submodular in (y, /). Indeed, let us consider the two-tuples (y',,) and (y, 7) such that y' > y and 7y ~ - we have: (y'V y,, V )= (y', Y) (y' A y, 7 A ^) = (y, u) Moreover: s -y - (s) > S - Y -y 7() s - y' - 7(s) s - y - u(s) > s - y'- u(s) > s - y' - 7(s) hence, there exist A E (0,1) such that: 26

s-y- 7(s) = A (s - y - u(s)) + (1 - A) (s - y'- (s)) s - y'- (s) = (1 - A) (s - y - (s)) + A (s - y'-7(s)) Hence by concavity: Ut(s - y- 7(s)) > A Ut(s - y - (s)) + (1 - A) Ut(s - y'- 7(s)) Ut(s - y'- /(s)) > (1 - A) - Ut(s - y - /(s)) + A. Ut(s - y'- 7()) By adding the previous inequalities we obtain the desired result. We now invoke the Dual Statement of Topkis' Theorem 6.1, to get the existence of a monotone decreasing optimal solution. By the change of variable this is tantamount to the claimed result. U We now use the previous results in conjunction with Tarski's Theorem to prove existence of equilibria for the t stage game that has initial state s. Theorem:For fixed s E S there exist a Nash Equilibrium for the t stage subgame in strategies that belong to L. Proof: We define two relevant maps as follows: P:LxLi -LxL (7Y,/) -' ((7 +/ ) A s, (7 +/ ) A s) Pt is clearly isotone in L x L with respect to product ordering and: P(O,0) =(0,0) P(s, S) =(s,s) The other useful map is: Qt: L - L x L (7, )l) '(BR/ (.; A) + t, 7 +BR2(.; )) By the lemma proven above the map Qt is isotone in L x L with respect to product ordering. Moreover: Qt(O, O) Ixl P(O, O) Qt (x,x) = (x,x) Hence the conditions on Tarki's intersection Theorem are met, i.e there exist (y*, *) E L x L such that: (7a + A* ) A. = BR' (.; p*) + * (7 *+ )As n BR2(.; 7*) + 7* from where we conclude the result. 27

7.5 Monotonicity of First Period Outcome of an MPE. The next theorem is just a straightforward application of the above stated chain of results. Theorem 7.7 For the T-Planning Horizon game, there exist a Markov Perfect Equilibrium such that for a given fixed initial state so, the first period outcome is monotonically decreasing in T. Proof. Let (O*,T, P/,T) be the first stage pair of equilibrium strategies for the T-planning horizon game, as constructed by the backward induction procedure outlined in the previous section. By definition: oE arg O max [UJ(c) + V1,T(fO(S - c- tOT(S)))] (1) 0<C<5-i(s~0,T() and p-* E arg max [U0(c) + VT(fo - c - 7*,T)))] (2) T O<c<s —* T[UA (C) + VT1,(f(S - C- 70,T()))] (2) For fixed initial state so, Lemma 2 above yields: 7YO,T(SO) < 7O,T+1(SO) O*0,T(SO) < //,T+1(O0) 8 Conclusions. We have used lattice programming techniques to obtain monotonicty of first period outcomes with respect to planning horizon's length. The set of sufficient conditions derived are relatively weak when compared to other similar results and have nice economic interpretations. This monotonicity result is then used to prove the existence of a "solution" horizon for a class of nonstationary dynamic optimization problems and games. For production planning problems, the sufficent conditions are pretty weak in that production cost functions are not required to be convex or concave and in the context of equipment replacement, this is the first solution horizon existence result that we are aware of. Finally, for a class of common pool resource exploitation dynamic games, the existence of a solution horizon is established with little additional work. 28

References [1] "Minimizing a Submodular Function on a Lattice" Donald Topkis Operations Research Vol. 26 No.2 1978, p.p 305-321 [2] "Monotone Comparative Statics" Milgrom P. and Shannon C. Econometrica 14 (1994) 1-16 [3] "A Lattice Theoretic Approach to a Class of Dynamic Games" Amir R. Computers Math Applic.(1989) Voll7 No. 8 pp1345-1349 [4] "A lattice theoretical fixpoint and applications" A. Tarski Pacific J. of Mathematics (1955)4, 185-309 [5] "Subgame-Perfect equilibria of Finite and Infinite-Horizon Games", D.Fudenberg and D.Levine Journal of Economic Theory 31 (1983) 251-267 [6] "Stochastic Models in Operations Research" Vol II", Heyman D. and Sobel M. MccGraw Hill N. Y,1984 [7] "Infinite Horizon Programs: Convregence of Approximate Solutions" Flam, S and Fougeres A. Annals of Operations Research 29 (1991) pp 333-350 [8] "Production Planning with Convex Costs: A parametric study"' Veinnott A. Management Science 10 441-460 (1964) [9] "Conditions for the Discovery of Solutions Horizons" Bean J. and Smith R.L Mathematical Programming 59 218-225 1993 [10] "Infinite Horizon Optimization" Scllochetman I. and Smith R.L Mathematics of Operations Research Vol 1-1 No. 3 1989 pp 559-554 [11] "Existence and Discovery of Average C(ost Optimal Solutions in Deterministic Infinite Horizon Optimization" Schochetman I. and Smith R.L mimeo 1995 29

[12] "Lattice theory" Birkhoff G. American Mathematical Society Colloquiuum Publications 25, Providence RI 1967 [13] "Topology in Lattices" Frink O. Transactions of The American Mathematical Society 51, pp 569-582 (1960) [14] "Adaptive Markov Control Processes" Hernandez-Lerma Onesimo Springer Verlag, New York (1989) 30