Envelope theorem

Envelope theorem This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2021) (Learn how and when to remove this template message) In mathematics and economics, the envelope theorem is a major result about the differentiability properties of the value function of a parameterized optimization problem.[1] As we change parameters of the objective, the envelope theorem shows that, in a certain sense, changes in the optimizer of the objective do not contribute to the change in the objective function. The envelope theorem is an important tool for comparative statics of optimization models.[2] The term envelope derives from describing the graph of the value function as the "upper envelope" of the graphs of the parameterized family of functions {displaystyle left{fleft(x,cdot right)right}_{xin X}} that are optimized.

Contents 1 Statement 2 For arbitrary choice sets 3 Applications 3.1 Applications to producer theory 3.2 Applications to mechanism design and auction theory 3.3 Applications to multidimensional parameter spaces 3.4 Applications to parameterized constraints 3.5 Other applications 4 See also 5 References Statement Let {displaystyle f(x,alpha )} and {displaystyle g_{j}(x,alpha ),j=1,2,ldots ,m} be real-valued continuously differentiable functions on {displaystyle mathbb {R} ^{n+l}} , where {displaystyle xin mathbb {R} ^{n}} are choice variables and {displaystyle alpha in mathbb {R} ^{l}} are parameters, and consider the problem of choosing {displaystyle x} , for a given {displaystyle alpha } , so as to: {displaystyle max _{x}f(x,alpha )} subject to {displaystyle g_{j}(x,alpha )geq 0,j=1,2,ldots ,m} and {displaystyle xgeq 0} .

The Lagrangian expression of this problem is given by {displaystyle {mathcal {L}}(x,lambda ,alpha )=f(x,alpha )+lambda cdot g(x,alpha )} where {displaystyle lambda in mathbb {R} ^{m}} are the Lagrange multipliers. Now let {displaystyle x^{ast }(alpha )} and {displaystyle lambda ^{ast }(alpha )} together be the solution that maximizes the objective function f subject to the constraints (and hence are saddle points of the Lagrangian), {displaystyle {mathcal {L}}^{ast }(alpha )equiv f(x^{ast }(alpha ),alpha )+lambda ^{ast }(alpha )cdot g(x^{ast }(alpha ),alpha ),} and define the value function {displaystyle V(alpha )equiv f(x^{ast }(alpha ),alpha ).} Then we have the following theorem.[3][4] Theorem: Assume that {displaystyle V} and {displaystyle {mathcal {L}}} are continuously differentiable. Then {displaystyle {frac {partial V(alpha )}{partial alpha _{k}}}={frac {partial {mathcal {L}}^{ast }(alpha )}{partial alpha _{k}}}={frac {partial {mathcal {L}}(x^{ast }(alpha ),lambda ^{ast }(alpha ),alpha )}{partial alpha _{k}}},k=1,2,ldots ,l} where {displaystyle partial {mathcal {L}}/partial alpha _{k}=partial f/partial alpha _{k}+lambda cdot partial g/partial alpha _{k}} .

For arbitrary choice sets Let {displaystyle X} denote the choice set and let the relevant parameter be {displaystyle tin lbrack 0,1]} . Letting {displaystyle f:Xtimes lbrack 0,1]rightarrow R} denote the parameterized objective function, the value function {displaystyle V} and the optimal choice correspondence (set-valued function) {displaystyle X^{ast }} are given by: {displaystyle V(t)=sup _{xin X}f(x,t)}         (1) {displaystyle X^{ast }(t)={xin X:f(x,t)=V(t)}}         (2) "Envelope theorems" describe sufficient conditions for the value function {displaystyle V} to be differentiable in the parameter {displaystyle t} and describe its derivative as {displaystyle V^{prime }left(tright)=f_{t}left(x,tright){text{ for each }}xin X^{ast }left(tright),}         (3) where {displaystyle f_{t}} denotes the partial derivative of {displaystyle f} with respect to {displaystyle t} . Namely, the derivative of the value function with respect to the parameter equals the partial derivative of the objective function with respect to {displaystyle t} holding the maximizer fixed at its optimal level.

Traditional envelope theorem derivations use the first-order condition for (1), which requires that the choice set {displaystyle X} have the convex and topological structure, and the objective function {displaystyle f} be differentiable in the variable {displaystyle x} . (The argument is that changes in the maximizer have only a "second-order effect" at the optimum and so can be ignored.) However, in many applications such as the analysis of incentive constraints in contract theory and game theory, nonconvex production problems, and "monotone" or "robust" comparative statics, the choice sets and objective functions generally lack the topological and convexity properties required by the traditional envelope theorems.

Paul Milgrom and Segal (2002) observe that the traditional envelope formula holds for optimization problems with arbitrary choice sets at any differentiability point of the value function,[5] provided that the objective function is differentiable in the parameter: Theorem 1: Let {displaystyle tin left(0,1right)} and {displaystyle xin X^{ast }left(tright)} . If both {displaystyle V^{prime }left(tright)} and {displaystyle f_{t}left(x,tright)} exist, the envelope formula (3) holds.

Proof: Equation (1) implies that for {displaystyle xin X^{ast }left(tright)} , {displaystyle max _{sin left[0,1right]}left[fleft(x,sright)-Vleft(sright)right]=fleft(x,tright)-Vleft(tright)=0.} Under the assumptions, the objective function of the displayed maximization problem is differentiable at {displaystyle s=t} , and the first-order condition for this maximization is exactly equation (3). Q.E.D.

While differentiability of the value function in general requires strong assumptions, in many applications weaker conditions such as absolute continuity, differentiability almost everywhere, or left- and right-differentiability, suffice. In particular, Milgrom and Segal's (2002) Theorem 2 offers a sufficient condition for {displaystyle V} to be absolutely continuous,[5] which means that it is differentiable almost everywhere and can be represented as an integral of its derivative: Theorem 2: Suppose that {displaystyle f(x,cdot )} is absolutely continuous for all {displaystyle xin X} . Suppose also that there exists an integrable function {displaystyle b:[0,1]} {displaystyle rightarrow } {displaystyle mathbb {R} _{+}} such that {displaystyle |f_{t}(x,t)|leq b(t)} for all {displaystyle xin X} and almost all {displaystyle tin lbrack 0,1]} . Then {displaystyle V} is absolutely continuous. Suppose, in addition, that {displaystyle f(x,cdot )} is differentiable for all {displaystyle xin X} , and that {displaystyle X^{ast }(t)neq varnothing } almost everywhere on {displaystyle [0,1]} . Then for any selection {displaystyle x^{ast }(t)in X^{ast }(t)} , {displaystyle V(t)=V(0)+int _{0}^{t}f_{t}(x^{ast }(s),s)ds.}         (4) Proof: Using (1)(1), observe that for any {displaystyle t^{prime },t^{prime prime }in lbrack 0,1]} with {displaystyle t^{prime }0} for all {displaystyle tin left[0,1right]} . Under these assumptions, it is well known that the above constrained optimization program can be represented as a saddle-point problem for the Lagrangian {displaystyle Lleft(x,lambda ,tright)=f(x,t)+lambda cdot gleft(x,tright)} , where {displaystyle lambda in mathbb {R} _{+}^{K}} is the vector of Lagrange multipliers chosen by the adversary to minimize the Lagrangian.[20][page needed][21][page needed] This allows the application of Milgrom and Segal's (2002, Theorem 4) envelope theorem for saddle-point problems,[5] under the additional assumptions that {displaystyle X} is a compact set in a normed linear space, {displaystyle f} and {displaystyle g} are continuous in {displaystyle x} , and {displaystyle f_{t}} and {displaystyle g_{t}} are continuous in {displaystyle left(x,tright)} . In particular, letting {displaystyle left(x^{ast }(t),lambda ^{ast }left(tright)right)} denote the Lagrangian's saddle point for parameter value {displaystyle t} , the theorem implies that {displaystyle V} is absolutely continuous and satisfies {displaystyle V(t)=V(0)+int _{0}^{t}L_{t}(x^{ast }(s),lambda ^{ast }left(sright),s)ds.} For the special case in which {displaystyle fleft(x,tright)} is independent of {displaystyle t} , {displaystyle K=1} , and {displaystyle gleft(x,tright)=hleft(xright)+t} , the formula implies that {displaystyle V^{prime }(t)=L_{t}(x^{ast }(t),lambda ^{ast }left(tright),t)=lambda ^{ast }left(tright)} for a.e. {displaystyle t} . That is, the Lagrange multiplier {displaystyle lambda ^{ast }left(tright)} on the constraint is its "shadow price" in the optimization program.[21][page needed] Other applications Milgrom and Segal (2002) demonstrate that the generalized version of the envelope theorems can also be applied to convex programming, continuous optimization problems, saddle-point problems, and optimal stopping problems.[5] See also Maximum theorem Danskin's theorem Hotelling's lemma Le Chatelier's principle Roy's identity Value function References ^ Border, Kim C. (2019). "Miscellaneous Notes on Optimization Theory and Related Topics" (PDF). Lecture Notes. California Institute of Technology: 154. ^ Carter, Michael (2001). Foundations of Mathematical Economics. Cambridge: MIT Press. pp. 603–609. ISBN 978-0-262-53192-4. ^ Afriat, S. N. (1971). "Theory of Maxima and the Method of Lagrange". SIAM Journal on Applied Mathematics. 20 (3): 343–357. doi:10.1137/0120037. ^ Takayama, Akira (1985). Mathematical Economics (Second ed.). New York: Cambridge University Press. pp. 137–138. ISBN 978-0-521-31498-5. ^ Jump up to: a b c d e Milgrom, Paul; Ilya Segal (2002). "Envelope Theorems for Arbitrary Choice Sets". Econometrica. 70 (2): 583–601. CiteSeerX 10.1.1.217.4736. doi:10.1111/1468-0262.00296. ^ Jump up to: a b Myerson, Roger (1981). "Optimal Auction Design". Mathematics of Operations Research. 6: 58–73. doi:10.1287/moor.6.1.58. S2CID 12282691. ^ Mirrlees, James (2002). "An Exploration in the Theory of Optimal Taxation". Review of Economic Studies. 38 (2): 175–208. doi:10.2307/2296779. JSTOR 2296779. ^ Jump up to: a b c Holmstrom, Bengt (1979). "Groves Schemes on Restricted Domains". Econometrica. 47 (5): 1137–1144. doi:10.2307/1911954. JSTOR 1911954. S2CID 55414969. ^ Laffont, Jean-Jacques; Eric Maskin (1980). "A Differentiable Approach to Dominant Strategy Mechanisms". Econometrica. 48 (6): 1507–1520. doi:10.2307/1912821. JSTOR 1912821. ^ Riley, John G.; Samuelson, William S. (1981). "Optimal Auctions". American Economic Review. 71 (3): 381–392. JSTOR 1802786. ^ Fudenberg, Drew; Tirole, Jean (1991). Game Theory. Cambridge: MIT Press. ISBN 0-262-06141-4. ^ Williams, Steven (1999). "A Characterization of Efficient, Bayesian Incentive Compatible Mechanism". Economic Theory. 14: 155–180. doi:10.1007/s001990050286. S2CID 154378924. ^ Myerson, Roger (1991). Game Theory. Cambridge: Harvard University Press. ISBN 0-674-34115-5. ^ Green, J.; Laffont, J. J. (1979). Incentives in Public Decision Making. Amsterdam: North-Holland. ISBN 0-444-85144-5. ^ Myerson, R.; M. Satterthwaite (1983). "Efficient Mechanisms for Bilateral Trading" (PDF). Journal of Economic Theory. 29 (2): 265–281. doi:10.1016/0022-0531(83)90048-0. hdl:10419/220829. ^ Jehiel, Philippe; Moldovanu, Benny (2001). "Efficient Design with Interdependent Valuations". Econometrica. 69 (5): 1237–1259. CiteSeerX 10.1.1.23.7639. doi:10.1111/1468-0262.00240. ^ McAfee, R. Preston; John McMillan (1992). "Bidding Rings". American Economic Review. 82 (3): 579–599. JSTOR 2117323. ^ Weber, Robert (1983). "Multiple-Object Auctions" (PDF). In Engelbrecht-Wiggans, R.; Shubik, M.; Stark, R. M. (eds.). Auctions, Bidding, and Contracting: Uses and Theory. New York: New York University Press. pp. 165–191. ISBN 0-8147-7827-5. ^ Milgrom, Paul (2004). Putting Auction Theory to Work. Cambridge University Press. ISBN 9780521536721. ^ Luenberger, D. G. (1969). Optimization by Vector Space Methods. New York: John Wiley & Sons. ISBN 9780471181170. ^ Jump up to: a b Rockafellar, R. T. (1970). Convex Analysis. Princeton: Princeton University Press. ISBN 0691015864. Categories: Production economicsCalculus of variationsEconomics theoremsTheorems in analysis