Theorem A-3(Kuhn-Tucker). For differentiable f: R-R and G: R-R,let LAx=f()+A G(x) If x' is a solt Appendix: Math Preparation max f(r) G(x)≥0, then there exists AER such that(Kuhn-Tucker condition)A G(r)=0 and 1. Lagrange method for Constrained Optimization FOC:D,L(Ax)=0.■ The following classical theorem is from Takayama(1993, p. 114) Theorem A-d (Sufficiency). Let f and g, i=L., m, be quasi-concave, where Theorem A-1.(Lagrange). For f: R+R and G: R-R, consider the following G=(8-g). Let r'satisfy the Kuhn-Tucker condition and the FOC for(A 2). Then, x' (1)Df(x)=0, and f is locally twice continuously differentiable, or Let L(Ar=f(x)+A G(r) Lagrange function Kuhn-Tucker Theorem is not useful. We usually use Lagrange Theorem only J solves(4. I)and jf DG(r)has full rank, then there exists AER agrange e A mapping H: R+R is linear if it can be written as H()=Ax+B, where A is FOC: D L(A,r)=0. Theorem A-5. Let f:R”→ R and g:R"→R" be concave,andH:R"→ r be linear Also, Ex, s.t. G(x,)>0. Then, ris a solution of SONC: hDf(r)hs0, for h satisfying DG(rh=0 max f(r) s.G(x)≥0, If the FoC is satisfied, G(r)=0, and SC: hD f(r)h0,k≥2m+1 Example A-1. For a>0 and b>0, consider
-1- Appendix: Math Preparation 1. Lagrange Method for Constrained Optimization The following classical theorem is from Takayama (1993, p.114). Theorem A-1. (Lagrange). For n f : → and n m G : → , consider the following problem max ( ) s t ( ) 0. x f x .. = G x (Α.1) Let L x ( ) () () λ λ , ≡ f x Gx + ⋅ (Lagrange function). • If x∗ solves (A.1) and if DG x( )∗ has full rank, then there exists k λ ∈ (Lagrange multiplier) such that FOC ( ) 0 DL x x λ ∗ : , = , and 2 SONC ( ) 0 for satisf h D f x h h DG x h ying () 0 ′∗ ∗ : ≤ , = . • If the FOC is satisfied, G x() 0 ∗ = , and 2 SOSC ( ) 0 for 0 satisfying ( ) 0 h D f x h h DG x h ′∗ ∗ : ∀ ≥ + . Example A-1. For 0 a > and b > , 0 consider 1 2 2 2 1 2 1 2 ( ) max s t 1. x x F a b ax bx x x , , ≡ −− .. + = Is the solution indeed optimal? -2- Theorem A-3 (Kuhn-Tucker). For differentiable n f : → and n m G : → , let L x ( ) () () λ λ , ≡ f x Gx + ⋅ . If x∗ is a solution of max ( ) st ( ) 0 x f x . . G x ≥ , (Α.2) then there exists m λ ∈ + such that (Kuhn-Tucker condition) λ G x() 0 ∗ ⋅ = and FOC ( ) 0 DL x x λ ∗ : , =. Theorem A-4 (Sufficiency). Let f and i g , i m =, , , 1 … be quasi-concave, where 1 (… )T Gg g = ,, . m Let x∗ satisfy the Kuhn-Tucker condition and the FOC for (A.2). Then, x∗ is a global maximum point if (1) Df x() 0 ∗ ≠ , and f is locally twice continuously differentiable, or (2) f is concave. Kuhn-Tucker Theorem is not useful. We usually use Lagrange Theorem only. A mapping n k H : → is linear if it can be written as ( ) H x Ax B = +, where A is matrix and B is a vector. Theorem A-5. Let n f : → and n m G : → be concave, and n k H : → be linear. Also, 0 ∃ x s.t. 0 G x() 0 > . Then, x∗ is a solution of max ( ) . . ( ) 0, ( ) 0. x f x st G x H x ≥ = if and only if ( ) 0 ( ) 0 Gx hx ∗ ∗ ≥ , =, and there exist m λ ∈ + and k µ ∈ such that λ G x() 0 ∗ ⋅ = and x∗ is a solution of max ( ) ( ) ( ) ( ) x L x λ, , µ ≡ f x Gx Hx +λ⋅ +µ⋅ . Example A-2. Given utility function 1 1 2 12 ( ) a a ux x xx − ,= , consider 1 2 1 2 12 0 11 2 2 ( ) max ( ) s t x x vp p m ux x p x p x m , ≥ , , ≡ , .. + ≤
2. Hamilton Method for Dynamic Optimization Theorem A-Z( Special Model I.Letx∈R,u∈R,g:R"x]×R→R R"xRxR→R.For 991). See also Chiang(1992) The following theorem is from Kamien-Schwartz( 1981, p 16) (x4)≡mJ几 Theorem A-6. For H: RXRXR-R, consider problem s.t. i(n=gr().u(t).I x(l0)=xx()≥0 HLu(o),u(oldt define the Hamiltonian as u(to)=lo, I(T) H=f(x,a,1)+A·g(xa where the set of admissible controls is Under certain differentiability conditions, if ur' is a solution, then there exists a fimction A=(continuously differentiable functions u: I'o, T-R A: [o, T]-R such that t'is a solution of If H is continuous w.r. L. its first argument, continuously differentiable w.r. It. its second and H=0 third arguments, then the solution t' must satisfy the euler equation (A.1) If the terminal ralue idT)is free, the transversality condition is (A.12) HA T, u(T)i(n=0 Theorem A-8( Special Model Il.ietr∈R,u∈R,g:R"xRxR→R"and f: RxKXR→R. For problem If the initial value u(to)is free. the transversality condition is H[,'()i’4)=0 A.6) J(xx,4)≡max几x(a"d If the terminal condition is u(T)>0, the transversality conditions are st. x=gx(n), u(o). x()=xxT)20 I'(TH u().i'(T)=0. H:T, u(T),i(T)Iso define the Hamiltonian as Comersely, if H(t, u, i) is concave inu, i ), then any I'E A satisfying the Euler equation H=f(x,a)+A·g(xL,l A.4)and the initial and terminal conditions is a solution of(A3). There is no SOSC, there is only a SONC Under certain differentiability conditions, if ui is a solution, then there exists a finction A: to, T]+IR such that u is a solution of Legendre Condition:Hs【,u(n)i(m)≤0. Example A-3. The mJ中-y(a (A8) with transversality conditie ∫叫y(a24+ mkre=0,XT)≥0. (A.15) Example A-4. Consider Example A-5. Consider consumer's probl (+( J(4)≡ma stx(0>0 st A=rA+y-c
-3- 2. Hamilton Method for Dynamic Optimization A good reference for this section is Kamien–Schwartz (1991). See also Chiang (1992). The following theorem is from Kamien-Schwartz (1981, p.16). Theorem A-6. For : k k H × × → , consider problem 0 0 0 max [ ( ) ( )] st ( ) ( ) , T u A t T H t u t u t dt ut u uT u ∈ , , .. = , = ∫ (Α.3) where the set of admissible controls is {continuously differentiable functions [ ] 0 }k A u tT ≡ : , → . If H is continuous w.r.t. its first argument, continuously differentiable w.r.t. its second and third arguments, then the solution u∗ must satisfy the Euler equation: [ ( ) ( )] [ ( ) ( )] u u d H tu t t H tu t t u u dt ∗ ∗ ∗ ∗ ,, =,, . (Α.4) If the terminal value u T( ) is free, the transversality condition is [ ( ) ( )] 0 H Tu T T u u ∗ ∗ , , =. (Α.5) If the initial value 0 u t is free, the transversality condition is ( ) 00 0 [ ( ) ( )] 0 Htut t u u ∗ ∗ , , =. (Α.6) If the terminal condition is u T() 0 ≥ , the transversality conditions are ( ) [ ( ) ( )] 0 [ ( ) ( )] 0 u u u TH Tu T T H Tu T T u u ∗∗ ∗ ∗ ∗ , , =, , , ≤ . (Α.7) Conversely, if H tuu ( ) , , is concave in ( ) u u, , then any u A ∗ ∈ satisfying the Euler equation (A.4) and the initial and terminal conditions is a solution of (A.3). There is no SOSC; there is only a SONC: * * Legendre Condition: [ , ( ), ( )] 0. H tu t u t uu ≤ Example A-3. The principal’s problem is ( ) [ ] [ ] max ( ) ( ) st ( ) ( ) ( ) a s v y s y f y a dy u s y fy a dy ca u , ⋅ − , .. , ≥ + . ∫ ∫ (Α.8) Example A-4. Consider ( ) { () () } ( ) ( ) max st 0 x u x v x dF x θ θ θθ θθ θ θ ⋅ ′ ⎡ ⎤⎡ ⎤ ,+ , ⎣ ⎦⎣ ⎦ . . ≥ . ∫ (Α.9) -4- Theorem A-7 (Special Model I). Let n k nk n xug ∈ , ∈ ,: × × → and n k f :×× → . For problem 0 0 0 0 0 ( ) max [ ( ) ( ) ] st ( ) [ ( ) ( ) ] () () 0 T T u t Jx x t f x t u t t dt x t g xt ut t xt x xT , , ≡ , , .. = , , = , ≥ ∫ define the Hamiltonian as H f = ,, + () () xut λ⋅ g xut ,, . Under certain differentiability conditions, if u∗ is a solution, then there exists a function 0 [ ] n λ : , t T → such that u∗ is a solution of 0 Hu = , (Α.10) λ =−Hx, (Α.11) with transversality conditions: lim 0 ( ) 0 t T λ λ x T → = , ≥ . (Α.12) Theorem A-8 (Special Model II). Let n k nk n xug ∈ , ∈ ,: × × → and n k f :×× → . For problem 0 0 ( ) 0 0 0 0 ( ) max [ ( ) ( )] st ( ) [ ( ) ( ) ] () () 0 T t t T u t J xxt f x t u t e dt xt gxt ut t xt x xT − − θ , , ≡ , .. = , , = , ≥ ∫ define the Hamiltonian as H = ,+ f () ( ) x u λ⋅ g xut ,, . Under certain differentiability conditions, if u∗ is a solution, then there exists a function 0 [ ] n λ : , t T → such that u∗ is a solution of 0 Hu = , (Α.13) λ θλ = −Hx, (Α.14) with transversality condition lim 0 ( ) 0 t t T xe T θ λ λ − → = , ≥ . (Α.15) Example A-5. Consider consumer’s problem: 0 0 0 ( ) max ( ) s t (0) t c J A u c e dt A rA y c A A −ρ ≡ .. = + − = . ∫
3. Envelope Theorem 4. The Nash Bargaining Solution Theorem A-2(Envelope) Suppase f: Xx A+R is differentiable, XCR ACR, and r(a) is an interior maximum point of There are two players i=l and 2. Let X be a set of potential bargaining outcomes and F(a)≡maxf(x,a) d be the outcome(the disagreement outcome) if the bargaining fails An agreement xeX is the Nash solution if The then(i', p D, I-pA, x for J Example A-6. For Example A-1. find dF(a,b) Theorem A-10. There exists a tmique Nash solution. And, an agreement xE X is a Nash max-(x)-4(D)42(x)-a2(D) Example A-7. Suppose the two players are risk neutral and u(D)=r, where r is the reservation value of player i. Assume the size of the pie is R, called the revenue. Then, for x=(,I,) with 4+l=R, the utility values are u(x)=t and u(x)=t. The Nash A generalized Nash solution is where 0>0 and 6 +8=1. is the bargaining power of player i. Obviously, we can extend this formula to a case with n individuals
-5- 3. Envelope Theorem Theorem A-9 (Envelope). Suppose fX A : × → is differentiable, n X ⊂ , k A⊂ , and x ( ) a ∗ is an interior maximum point of ( ) max ( ) x X F a f x a ∈ ≡ , . Then, ( ) () ( ) . xxa dF a f x a da a ∗ = ∂ , = ∂ Example A-6. For Example A-1, find Fab ( ) a ∂ , . ∂ -6- 4. The Nash Bargaining Solution There are two players 1 i = and 2. Let X be a set of potential bargaining outcomes and D be the outcome (the disagreement outcome) if the bargaining fails. An agreement x X ∗ ∈ is the Nash solution if ( ) ( ) * * If , ; ,1 for some , [0, 1] and , then , ; ,1 for . i j x pD p x i N p x X x pD p x j i − ∈∈ ∈ − ≠ (Α.16) Theorem A-10. There exists a unique Nash solution. And, an agreement x X ∗∈ is a Nash solution iff it is the solution of the following problem: [ ][ ] max ( ) ( ) ( ) ( ) 1 12 2 x X ux uD ux uD ∈ − − , (Α.17) where i u is the expected utility index of Vi for i =,. 1 2 Example A-7. Suppose the two players are risk neutral and ( ) i i uD r = , where ir is the reservation value of player i. Assume the size of the pie is R, called the revenue. Then, for 1 2 x = , ( ) t t with 1 2 tt R + =, the utility values are 1 1 ux t ( ) = and 2 2 ux t ( ) = . The Nash solution is ( ) 1 2 12 i i t r Rr r ∗ = + − − . A generalized Nash solution is ( ) i ii 1 2 t r Rr r θ ∗ = + − − , where 0 i θ ≥ and 1 2 θ θ + =. 1 i θ is the bargaining power of player i. Obviously, we can extend this formula to a case with n individuals