# Lecture 8: Comparative Statics, Envelopes, and Fixed Points Lectures 6 and 7 solve one optimization problem at a time. Economics rarely stops there: the interesting question is usually how the solution and its value respond when a parameter moves. What does a tax do to the equilibrium price? What does an extra unit of capacity add to profit? The solved problem almost never has a closed form, so the answers must be read from the equations that characterize the solution. This method is called _comparative statics_. The main tool of comparative statics is the _implicit function theorem_, which differentiates through a system of equations. ## 1 The implicit function theorem ### 1.1 Scalar implicit differentiation Let $F:U\to\mathbb{R}$ be $C^{1}$ on an open set $U\subseteq\mathbb{R}^{2}$, with the arguments written $F(x;\theta)$: an equation in the endogenous variable $x$, indexed by the parameter $\theta$. Suppose a differentiable function $x(\theta)$ solves the equation identically, $$ F\left(x(\theta);\theta\right)=0 , $$ on some interval of parameters. Such a function is a _solution branch_ of the equation. Differentiating the identity using the chain rule from Lecture 4, we get $$ F_{x}\left(x(\theta);\theta\right)\,x'(\theta) +F_{\theta}\left(x(\theta);\theta\right)=0 , $$ and at any point where $F_{x}\neq0$, $$ x'(\theta) =-\frac{F_{\theta}\left(x(\theta);\theta\right)} {F_{x}\left(x(\theta);\theta\right)} . $$ The calculation is conditional: _if_ a differentiable solution branch runs through the point, its slope is determined by the equation above. ### 1.2 The system theorem The same logic runs for systems. Let $X\subseteq\mathbb{R}^{n}$ and $\Theta\subseteq\mathbb{R}^{r}$ be open, and let $F:X\times\Theta\to\mathbb{R}^{n}$ collect $n$ equations in the $n$ endogenous variables $x$, with $r$ parameters $\theta$. The scalar condition $F_{x}\neq0$ becomes invertibility of the endogenous Jacobian. **Theorem 1.1 (Implicit function theorem).** Let $F$ be $C^{1}$, let $F(x^{0};\theta^{0})=0$, and let $\mathrm{D}_{x}F(x^{0};\theta^{0})$ be invertible. Then there are neighborhoods $\mathcal{U}$ of $\theta^{0}$ and $\mathcal{V}$ of $x^{0}$ and a unique $C^{1}$ function $x:\mathcal{U}\to\mathcal{V}$ such that $$ x(\theta^{0})=x^{0} \qquad\text{and}\qquad F\left(x(\theta);\theta\right)=0 \quad\text{for every }\theta\in\mathcal{U} , $$ and for each $\theta\in\mathcal{U}$ the point $x(\theta)$ is the only solution of $F(x;\theta)=0$ in $\mathcal{V}$. The derivative satisfies $$ \mathrm{D}_{x}F\left(x(\theta);\theta\right)\,\mathrm{D}_{\theta}x(\theta) =-\mathrm{D}_{\theta}F\left(x(\theta);\theta\right) . $$ (1) We use the system statement without proof; the scalar case can be proved with the tools of Lectures 2 and 4. _Proof (optional, for one equation and one parameter)._ The two signs are symmetric, so suppose $F_{x}(x^{0};\theta^{0})>0$. Since $F_{x}$ is continuous, there is a rectangle $[x^{0}-\delta,x^{0}+\delta]\times[\theta^{0}-\eta,\theta^{0}+\eta]$ on which $F_{x}>0$, so on this rectangle $F$ is strictly increasing in $x$ for each fixed $\theta$. Since $F(\,\cdot\,;\theta^{0})$ increases through its zero at $x^{0}$, $$ F(x^{0}+\delta;\theta^{0})>0 \qquad\text{and}\qquad F(x^{0}-\delta;\theta^{0})<0 . $$ Both signs survive small moves of the parameter: $F$ is continuous in $\theta$, so there is $\varepsilon\in(0,\eta]$ such that $F(x^{0}+\delta;\theta)>0$ and $F(x^{0}-\delta;\theta)<0$ for every $\theta$ within $\varepsilon$ of $\theta^{0}$. For each such $\theta$, the [Theorem 3.7](https://maria-titova.com/courses/math-camp/02-analysis-for-existence.md#thm:lec02-ivt) from Lecture 2 gives a solution $x(\theta)\in(x^{0}-\delta,x^{0}+\delta)$ of $F(x;\theta)=0$, and strict monotonicity in $x$ makes it the only one in the interval: this is the branch. Repeating the argument with a smaller $\delta$ traps the branch in a smaller rectangle, so $x(\theta)\to x^{0}$ as $\theta\to\theta^{0}$: the branch is continuous. We take the differentiability of the branch without proof; its derivative is then the chain-rule formula of [Section 1.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#sec:lec08-scalar-ift). ◻ Everything in the theorem is local: invertibility at one solution gives a branch near that solution and carries no information about solutions elsewhere. Equation [(1)](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#eq:lec08-ift) is the scalar calculation written with matrices: differentiate the identity $F(x(\theta);\theta)=0$ by the chain rule and solve. For each of the $r$ parameters, the corresponding column of $\mathrm{D}_{\theta}x$ solves one linear system with the same coefficient matrix $\mathrm{D}_{x}F$, as in Lecture 3; in practice, the matrix is inverted once, or each system is solved directly. **Example 1.2 (Incidence of a per-unit tax).** Fix demand and supply primitives $a,c\in\mathbb{R}$ and $b,s>0$. The parameter is the per-unit tax $t$. The endogenous variables are the producer price $p$ and quantity $q$; consumers pay $p+t$. Demand and supply are $$ q=a-b\,(p+t), \qquad q=c+s\,p . $$ At a reference tax $t^{0}$, suppose an equilibrium $x^{0}=(p^{0},q^{0})^{\top}$ exists. How do the local equilibrium price $p(t)$, quantity $q(t)$, and consumer price $p(t)+t$ respond to the tax? _Solution._ With endogenous vector $x=(p,q)^{\top}$, equilibrium is the system $$ F(p,q;t)= \begin{pmatrix} q-a+b\,(p+t)\\ q-c-s\,p \end{pmatrix} =0 , \qquad \mathrm{D}_{(p,q)}F= \begin{pmatrix} b & 1\\ -s & 1 \end{pmatrix}, $$ with $\det\mathrm{D}_{(p,q)}F=b+s>0$, so [Theorem 1.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-ift) applies at any equilibrium: the equilibrium price and quantity are differentiable functions of the tax. Differentiating with respect to $t$ as in [(1)](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#eq:lec08-ift), $$ \begin{pmatrix} b & 1\\ -s & 1 \end{pmatrix} \begin{pmatrix} p_{t}\\ q_{t} \end{pmatrix} = \begin{pmatrix} -b\\ 0 \end{pmatrix} \qquad\Longrightarrow\qquad p_{t}=-\frac{b}{b+s}, \quad q_{t}=-\frac{bs}{b+s} . $$ The consumer price moves by $$ \frac{\mathrm{d}(p+t)}{\mathrm{d}t} =1+p_{t} =\frac{s}{b+s}\in(0,1) . $$ The tax splits between the two sides of the market in proportion to the slopes: the producer price falls by $b/(b+s)$ of the tax, the consumer price rises by the complementary share $s/(b+s)$, and quantity falls. Note that we never computed the equilibrium. ## 2 Comparative statics of optimizers and values ### 2.1 Optimizing systems When the equations being differentiated are optimality conditions, the implicit function theorem turns into the comparative statics of choice. Let $f:X\times\Theta\to\mathbb{R}$ be $C^{2}$ with $X\subseteq\mathbb{R}^{n}$ and $\Theta\subseteq\mathbb{R}^{r}$ open. At a parameter $\theta^{0}$, suppose $x^{0}$ is a critical point satisfying Lecture 6’s first-order condition, $$ \nabla_{x}f(x^{0};\theta^{0})=0 . $$ This is a system $F(x;\theta)=\nabla_{x}f(x;\theta)$, and its endogenous Jacobian is the Hessian: $$ \mathrm{D}_{x}F(x;\theta)=H_{f}(x;\theta) . $$ If the Hessian is invertible at $(x^{0};\theta^{0})$, [Theorem 1.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-ift) yields a $C^{1}$ branch of critical points with $$ H_{f}\left(x(\theta);\theta\right)\,\mathrm{D}_{\theta}x(\theta) =-\mathrm{D}_{\theta}\,\nabla_{x}f\left(x(\theta);\theta\right) . $$ For constrained problems, we differentiate the Lagrange system. For $\max_{x}f(x;\theta)$ subject to $h(x;\theta)=0$, Lecture 7’s Lagrangian $L(x,\mu;\theta)=f(x;\theta)+\mu\cdot h(x;\theta)$ produces the system $$ G(x,\mu;\theta)= \begin{pmatrix} \nabla_{x}L(x,\mu;\theta)\\ h(x;\theta) \end{pmatrix} =0 $$ in the stacked endogenous vector $(x,\mu)$. Its endogenous Jacobian is written in blocks, each block a matrix whose dimensions are read off the grouping of equations and variables: $$ \mathrm{D}_{(x,\mu)}G= \begin{pmatrix} H_{L}(x,\mu;\theta) & \mathrm{D}_{x}h(x;\theta)^{\top}\\[1mm] \mathrm{D}_{x}h(x;\theta) & 0 \end{pmatrix}, $$ where $H_{L}$ is the Hessian of $L$ in $x$ alone. When this matrix is invertible at a stationary feasible pair, the implicit function theorem gives a differentiable branch $(x(\theta),\mu(\theta))$ of such pairs. Once the branch is established to consist of optimizers and their multipliers, we write it $(x^{*}(\theta),\mu^{*}(\theta))$. Inequality constraints use the same technique. On a parameter region where the same constraints bind and every slack constraint stays slack, the binding constraints can be carried as equalities and everything above applies; the derivatives are valid strictly within that region, and [Section 2.5](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#sec:lec08-limits) discusses what happens at its boundary. ### 2.2 Envelope theorems So far we differentiated a critical point of an optimization problem. The second object of comparative statics is the optimized value $$ V(\theta)=f\left(x^{*}(\theta);\theta\right) , $$ whose derivative is even simpler. **Theorem 2.1 (Envelope theorems).** Assume the functions appearing below are $C^{1}$ in $(x,\theta)$. 1. If $x^{*}(\theta)$ is a differentiable branch of interior optimizers, so that $\nabla_{x}f(x^{*}(\theta);\theta)=0$, then $$ \mathrm{D}_{\theta}V(\theta) =\mathrm{D}_{\theta}f\left(x^{*}(\theta);\theta\right) . $$ 2. If $x^{*}(\theta)$ is a differentiable branch of optimizers and $\mu^{*}(\theta)$ is its differentiable multiplier branch satisfying Lecture 7’s stationarity and feasibility conditions, $\nabla_{x}L(x^{*}(\theta),\mu^{*}(\theta);\theta)=0$ and $h(x^{*}(\theta);\theta)=0$, then $$ \mathrm{D}_{\theta}V(\theta) =\mathrm{D}_{\theta}L\left(x^{*}(\theta),\mu^{*}(\theta);\theta\right) =\mathrm{D}_{\theta}f+\mu^{*}(\theta)^{\top}\mathrm{D}_{\theta}h , $$ with every derivative on the right taken in $\theta$ alone and evaluated along the branch. 3. For a problem with equalities $h(x;\theta)=0$ and inequalities $g(x;\theta)\geq0$, suppose $x^{*}(\theta)$ is a differentiable branch of optimizers, $\mu^{*}(\theta)$ and $\lambda^{*}(\theta)$ are its differentiable multiplier branches satisfying the KKT conditions, and the active set is constant near the parameter under consideration. Then $$ \mathrm{D}_{\theta}V(\theta) =\mathrm{D}_{\theta}L\left(x^{*}(\theta),\mu^{*}(\theta),\lambda^{*}(\theta);\theta\right) =\mathrm{D}_{\theta}f+\mu^{*}(\theta)^{\top}\mathrm{D}_{\theta}h +\lambda^{*}(\theta)^{\top}\mathrm{D}_{\theta}g . $$ _Proof._ For the interior case, the chain rule gives $$ \mathrm{D}_{\theta}V =\nabla_{x}f^{\top}\,\mathrm{D}_{\theta}x^{*}+\mathrm{D}_{\theta}f , $$ and the first term vanishes by stationarity. For the constrained case, the same chain rule step and stationarity $\nabla_{x}f^{\top}=-(\mu^{*})^{\top}\mathrm{D}_{x}h$ give $$ \mathrm{D}_{\theta}V =\mathrm{D}_{\theta}f+\nabla_{x}f^{\top}\,\mathrm{D}_{\theta}x^{*} =\mathrm{D}_{\theta}f-(\mu^{*})^{\top}\mathrm{D}_{x}h\,\mathrm{D}_{\theta}x^{*} . $$ Differentiating the feasibility identity $h(x^{*}(\theta);\theta)=0$ gives $\mathrm{D}_{x}h\,\mathrm{D}_{\theta}x^{*}=-\mathrm{D}_{\theta}h$, and substituting finishes the proof of part 2. For part 3, let $I$ be the active set, which is constant by hypothesis. The equations $h=0$ and $g_I=0$ form one equality system, so part 2 applies with multipliers $(\mu^{*},\lambda_I^{*})$. Every inactive multiplier is zero by complementary slackness. Adding those zero terms gives the displayed formula with the full vectors $\lambda^{*}$ and $g$. ◻ Notice that $\mathrm{D}_{\theta}x^{*}$ does not appear on any right-hand side. To first order, the response of the choice does not affect the value, because the first-order condition makes the objective flat in the choice direction; only the direct effect of the parameter remains. **Example 2.2 (The envelope formula on the quadratic family).** For each parameter $\theta\in\mathbb{R}$, the scalar choice variable $x$ solves $$ \max_{x\geq0}\ \theta x-\tfrac12x^{2} . $$ The optimizer and value, respectively, are known to be $x^{*}(\theta)=\max\{\theta,0\}$ and $$ V(\theta)= \begin{cases} \tfrac12\theta^{2}, & \theta>0,\\ 0, & \theta\leq0 . \end{cases} $$ (see [Example 3.3](https://maria-titova.com/courses/math-camp/06-general-optimization.md#ex:lec06-parameterized-quadratic) in Lecture 6). What does the envelope theorem give for $V'(\theta)$ on the interior and corner regimes, and does it agree with the known value function? _Solution._ On the interior regime $\theta>0$, part 1 of [Theorem 2.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-envelope) predicts $$ V'(\theta) =\frac{\partial}{\partial\theta} \left(\theta x-\tfrac12x^{2}\right)\Big|_{x=x^{*}(\theta)} =x^{*}(\theta)=\theta , $$ and differentiating $\tfrac12\theta^{2}$ directly confirms it. On the corner regime $\theta<0$, write the constraint as $g(x)=x\geq0$. The active set is constant, $x^{*}=0$, and part 3 gives $V'(\theta)=\partial f/\partial\theta=x^{*}(\theta)=0$, again matching the derivative of the constant value. ### 2.3 Interpretation of Lagrange multipliers Lecture 7 introduced a Lagrange multiplier as an additional unknown in the first-order conditions. We can now interpret that unknown. Start with the equality-constrained problem $$ \max_{x}\ f(x) \qquad\text{subject to}\qquad r(x)=b . $$ Here $x$ is the vector of choice variables, $f$ and $r$ are fixed primitives, and $b$ is the constraint’s right-hand side. Depending on the application, $b$ could be a budget, capacity, time limit, or available material. Changing $b$ shifts the constraint and therefore changes the best attainable value. Using the course’s sign convention, write the constraint and Lagrangian as $$ h(x;b)=b-r(x)=0, \qquad L(x,\mu;b)=f(x)+\mu h(x;b). $$ Let $$ V(b)=f\left(x^{*}(b)\right) $$ be the optimized value. Suppose the optimizer $x^{*}(b)$ and its multiplier $\mu^{*}(b)$ form differentiable local branches. The equality-constrained envelope formula, restated for this problem, is $$ V'(b) =\frac{\partial L}{\partial b} \left(x^{*}(b),\mu^{*}(b);b\right) =\mu^{*}(b). $$ The last equality follows immediately from the Lagrangian: $b$ enters $L$ with coefficient $\mu$. Thus the multiplier is the _shadow price_ of the constraint’s right-hand side—the marginal increase in the optimized value from increasing $b$. For a small change $\Delta b$, the first-order approximation is $$ \Delta V \equiv V(b+\Delta b)-V(b) \approx\mu^{*}(b)\,\Delta b. $$ Its units are units of optimized value per unit of $b$. For an upper-bound inequality $r(x)\leq b$, use the course’s KKT convention $$ g(x;b)=b-r(x)\geq0, \qquad L(x,\lambda;b)=f(x)+\lambda g(x;b), \qquad \lambda\geq0 . $$ On a differentiable regime with a fixed active set, a binding constraint has $$ V'(b) =\frac{\partial L}{\partial b} =\lambda^{*}(b). $$ A slack constraint has $\lambda^{*}(b)=0$ by complementary slackness and therefore no marginal value on that regime. More generally, if constraint $i$ is written as $g_i(x)+c_i\geq0$, a positive $c_i$ relaxes it and $$ \frac{\partial V}{\partial c_i}=\lambda_i^{*}. $$ The sign of a multiplier cannot be separated from the way its constraint is written. If the equality constraint is instead $r(x)-b=0$ with multiplier $\widetilde\mu^{*}$, then $\widetilde\mu^{*}=-\mu^{*}$ and $V'(b)=-\widetilde\mu^{*}(b)$. Writing the constraint as $b-r(x)=0$ makes the multiplier itself equal to the shadow price. **Example 2.3 (Capacity valued by the envelope formula).** Fix parameters $a>0$ and $K>0$. The scalar choice variable $q$ solves $$ \max_{q}\ aq-\tfrac12q^{2} \qquad\text{subject to}\qquad q\geq0, \quad g_{2}(q;K)=K-q\geq0 . $$ The optimizer and capacity multiplier are known to be $q^{*}(a,K)=\min\{a,K\}$ and $\lambda_{2}^{*}(a,K)=\max\{a-K,0\}$ (see [Example 3.3](https://maria-titova.com/courses/math-camp/07-constrained-optimization.md#ex:lec07-capacity) in Lecture 7). What do the envelope formulas give for the effects of capacity $K$ and productivity $a$ on the value, and do those effects agree with the known closed-form solution? _Solution._ The value function is available in closed form: $$ V(a,K)= \begin{cases} \tfrac12 a^{2}, & a\leq K,\\[1mm] aK-\tfrac12 K^{2}, & a>K, \end{cases} \qquad\text{so}\qquad \frac{\partial V}{\partial K}= \begin{cases} 0, & aK, \end{cases} $$ which is $\lambda_{2}^{*}(a,K)$, as part 3 of [Theorem 2.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-envelope) predicts with $\mathrm{D}_{K}f=0$ and $\mathrm{D}_{K}g_{2}=1$: the marginal value of capacity is zero while the capacity constraint is slack and positive once it binds. Differentiating in $a$ instead gives $\partial V/\partial a=\min\{a,K\}=q^{*}(a,K)$ on both regimes, which is the direct effect $\mathrm{D}_{a}f=q$ evaluated at the optimum. On each regime the active set is constant and the branch $q^{*}(a,K)$ is differentiable, so the formulas apply regime by regime; the switch points belong to [Section 2.5](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#sec:lec08-limits). ### 2.4 Behavior from optimized values One classical corollary applies the envelope theorem to the theory of the firm. **Example 2.4 (Hotelling’s lemma).** A firm chooses an input vector $x\in\mathbb{R}^{n}$ and produces output $y(x)$. The parameters are the output price $p$ and input-price vector $w\in\mathbb{R}^{n}$, and profit is $$ \pi(x;p,w)=p\,y(x)-w\cdot x . $$ Suppose $x^{*}(p,w)$ is a differentiable branch of interior profit maximizers, with maximized profit $\Pi(p,w)$. What are the derivatives of $\Pi$ with respect to $p$ and each $w_{i}$? _Solution._ Part 1 of [Theorem 2.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-envelope) gives $$ \frac{\partial\Pi}{\partial p}=y\left(x^{*}(p,w)\right), \qquad \frac{\partial\Pi}{\partial w_{i}}=-x_{i}^{*}(p,w) : $$ the derivative of maximized profit with respect to the output price is the optimal output, and with respect to an input price it is the negative of the optimal input use. Differentiating the value function recovers the firm’s behavior without re-solving its problem. The same calculation with a budget constraint produces Roy’s identity in consumer theory, and with a cost-minimization problem produces Shephard’s lemma; both appear early in the first-year sequence, and both are [Theorem 2.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-envelope) applied to a particular value function. ### 2.5 Limits of the formulas Every formula in this section is local and conditional: it needs a differentiable branch through a regular solution, and for inequality problems it needs the active set to stay constant. The following example shows how the formulas fail where the active set changes. **Example 2.5 (No single marginal value at an active-set change).** The scalar choice variable is $x$, and the scalar parameter is $b>0$. Consider $$ \max_{x}\ x \qquad\text{subject to}\qquad x\geq0, \quad b-x\geq0, \quad 1-x\geq0 . $$ What are the optimizer and value, and how does the value derivative compare with the multiplier on the constraint $b-x\geq0$ for $b<1$, $b>1$, and at the switch point $b=1$? _Solution._ The feasible set is $[0,\min\{b,1\}]$, and the objective is increasing in $x$, so the optimizer and value are $x^{*}(b)=V(b)=\min\{b,1\}$. For $b<1$ the constraint $b-x\geq0$ binds alone and carries multiplier $1$; for $b>1$ it is slack and carries multiplier $0$. At $b=1$ both upper constraints are active, stationarity only requires the two multipliers to sum to one, $$ \lambda_{b}^{*}\in[0,1], \qquad \lambda_{\text{cap}}^{*}=1-\lambda_{b}^{*} , $$ and the value function has left derivative $1$ and right derivative $0$. At the switch point the value function is not differentiable, so there is no single marginal value, and correspondingly the multiplier is not unique. On either side of the switch, the formulas hold regime by regime. [Example 2.2](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#ex:lec08-quadratic-envelope) shows the benign case: the active set changes at $\theta=0$, yet the two regime values $\tfrac12\theta^{2}$ and $0$ join with matching derivative, so the value is differentiable even at $\theta=0$. After an active-set change, the value may or may not remain differentiable, and this must be checked. ## 3 Fixed-point theorems A fixed-point argument looks for a point that a map sends to itself. This section introduces several theorems that give conditions under which such points exist. ### 3.1 Fixed points and Brouwer’s theorem **Definition 3.1 (Fixed point).** Let $X$ be a set and $f:X\to X$. A point $x^{*}\in X$ is a _fixed point_ of $f$ if $f(x^{*})=x^{*}$. For a function of one variable, a fixed point is a crossing of the graph of $f$ with the $45$\-degree line. Lecture 2 closed with our first fixed point theorem, Brouwer in $\mathbb{R}$: every continuous $f:[a,b]\to[a,b]$ has a fixed point. The proof applied the intermediate value theorem to $g(x)=f(x)-x$, which is nonnegative at $a$ and nonpositive at $b$. [Figure 3.1](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#fig:lec08-brouwer) shows the picture: a continuous graph that starts on or above the diagonal and ends on or below it must cross it. ![Figure 3.1. A continuous function from [a,b\] to itself. At x^{*} the graph of f meets the line y=x, so f(x^{*})=x^{*}.](https://maria-titova.com/courses/math-camp/assets/fig-lec08-brouwer.svg) **Figure 3.1.** A continuous function from $[a,b]$ to itself. At $x^{*}$ the graph of $f$ meets the line $y=x$, so $f(x^{*})=x^{*}$. In $\mathbb{R}^{n}$ the interval is replaced by a compact convex set. **Theorem 3.2 (Brouwer).** Let $D\subseteq\mathbb{R}^{n}$ be nonempty, compact, and convex, and let $f:D\to D$ be continuous. Then $f$ has a fixed point. ### 3.2 Set-valued maps and Kakutani’s theorem **Definition 3.3 (Set-valued map).** A _set-valued map_ (_correspondence_) $\Gamma:X\rightrightarrows Y$ assigns to every $x\in X$ a nonempty set $\Gamma(x)\subseteq Y$. A _fixed point_ of $\Gamma:X\rightrightarrows X$ is a point $x^{*}$ with $x^{*}\in\Gamma(x^{*})$. For correspondences, the continuity hypothesis of Brouwer’s theorem is replaced by a condition on the set of pairs $\{(x,y):x\in X,\ y\in\Gamma(x)\}$, the _graph_ of $\Gamma$: the graph must be a closed set, in the sequential sense of Lecture 2. In words, if $x_{k}\to x$, $y_{k}\to y$, and $y_{k}\in\Gamma(x_{k})$ for every $k$, then $y\in\Gamma(x)$. **Theorem 3.4 (Kakutani).** Let $D\subseteq\mathbb{R}^{n}$ be nonempty, compact, and convex, and let $\Gamma:D\rightrightarrows D$ have convex values and a closed graph. Then $\Gamma$ has a fixed point. **Example 3.5 (Ties close the gap).** The variable is $x\in D=[0,1]$; there are no parameters. Let $f:D\to D$ be the jump map $f(x)=1$ for $x<\tfrac12$ and $f(x)=0$ for $x\geq\tfrac12$, which has no fixed point. Replace its value at the jump by the whole interval, defining $\Gamma:D\rightrightarrows D$ by $$ \Gamma(x)= \begin{cases} \{1\} & x<\tfrac12,\\ [0,1] & x=\tfrac12,\\ \{0\} & x>\tfrac12. \end{cases} $$ Does Kakutani’s theorem apply, and what is the fixed point? Why would replacing $\Gamma(\tfrac12)=[0,1]$ by the two-point set $\{0,1\}$ destroy the conclusion? _Solution._ The jump map $f$ has singleton values but not a closed graph: the pairs $(\tfrac12-\tfrac1k,1)$ lie in the graph and converge to $(\tfrac12,1)$, yet $f(\tfrac12)=0$. Under $\Gamma$, the graph gains the vertical segment $\{\tfrac12\}\times[0,1]$ and becomes closed, every value is convex, and [Theorem 3.4](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-kakutani) applies. The fixed point is visible in [Figure 3.2](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#fig:lec08-kakutani): the segment meets the diagonal at $x^{*}=\tfrac12$, and indeed $\tfrac12\in\Gamma(\tfrac12)$. If the value at the jump were the two-point set $\{0,1\}$ instead, the graph would still be closed, but the value would not be convex and no fixed point would exist. In a game, the interval is the set of mixtures available to a player who is indifferent; allowing the tie restores equilibrium existence. ![Figure 3.2. Left: the graph of the jump map passes over the diagonal without touching it. Right: the set-valued map whose value at x=\tfrac12 is [0,1\]; the added segment meets the diagonal at x^{*}.](https://maria-titova.com/courses/math-camp/assets/fig-lec08-kakutani.svg) **Figure 3.2.** Left: the graph of the jump map passes over the diagonal without touching it. Right: the set-valued map whose value at $x=\tfrac12$ is $[0,1]$; the added segment meets the diagonal at $x^{*}$. ### 3.3 The contraction mapping theorem Brouwer and Kakutani establish existence only: they do not say whether the fixed point is unique, and they do not provide a way to compute it. The third theorem strengthens the hypothesis on the map and gives both uniqueness and an algorithm. **Definition 3.6 (Contraction).** Let $S\subseteq\mathbb{R}^{n}$. A map $f:S\to S$ is a _contraction with modulus $\beta$_ if $0\leq\beta<1$ and $$ \lVert f(x)-f(y) \rVert\leq\beta\,\lVert x-y \rVert \qquad\text{for all }x,y\in S. $$ A contraction shrinks the distance between any two points to at most $\beta$ times its original value. Every contraction is continuous: if $x_{k}\to x$, then $\lVert f(x_{k})-f(x) \rVert\leq\beta\lVert x_{k}-x \rVert\to0$. **Theorem 3.7 (Contraction mapping theorem).** Let $S\subseteq\mathbb{R}^{n}$ be nonempty and closed, and let $f:S\to S$ be a contraction with modulus $\beta$. Then $f$ has exactly one fixed point $x^{*}\in S$. Moreover, from any starting point $x_{0}\in S$, the iterates $x_{k+1}=f(x_{k})$ converge to $x^{*}$, and $$ \lVert x_{k}-x^{*} \rVert\leq\beta^{k}\,\lVert x_{0}-x^{*} \rVert . $$ **Remark 3.8 (Why the fixed point is unique).** Uniqueness follows in two lines, and the argument uses $\beta<1$ directly. If $x^{*}$ and $y^{*}$ are both fixed points, then $$ \lVert x^{*}-y^{*} \rVert =\lVert f(x^{*})-f(y^{*}) \rVert \leq\beta\,\lVert x^{*}-y^{*} \rVert , $$ so $(1-\beta)\lVert x^{*}-y^{*} \rVert\leq0$. Since $\beta<1$, this forces $\lVert x^{*}-y^{*} \rVert=0$, that is, $x^{*}=y^{*}$. The error bound is the same inequality applied $k$ times: $\lVert x_{k}-x^{*} \rVert=\lVert f(x_{k-1})-f(x^{*}) \rVert \leq\beta\lVert x_{k-1}-x^{*} \rVert$. Note that in [Theorem 3.7](https://maria-titova.com/courses/math-camp/08-comparative-statics-envelopes.md#thm:lec08-contraction) the set $S$ need not be bounded or convex; the strong hypothesis on $f$ replaces both. **Example 3.9 (A discounted sum as a fixed point).** Fix parameters $a\in\mathbb{R}$ and $\beta\in(0,1)$. The fixed-point variable is $x\in S=\mathbb{R}$, and the map is $T:S\to S$ defined by $T(x)=a+\beta x$. Starting from $x_{0}=0$, does $T$ have a unique fixed point, what are the iterates $x_{k+1}=T(x_{k})$, and what economic object does their limit represent? _Solution._ We have $\lvert T(x)-T(y) \rvert=\beta\lvert x-y \rvert$, so $T$ is a contraction with modulus $\beta$, and its fixed point solves $x=a+\beta x$: $$ x^{*}=\frac{a}{1-\beta} . $$ Starting the iteration at $x_{0}=0$, $$ x_{k}=a\left(1+\beta+\cdots+\beta^{k-1}\right) =a\,\frac{1-\beta^{k}}{1-\beta} \longrightarrow\frac{a}{1-\beta}, $$ since $\beta^{k}\to0$ for $0<\beta<1$. The fixed point of “today’s reward plus $\beta$ times the continuation” is the value of receiving $a$ in every period, discounted by $\beta$. In Lecture 9, the central operator has this form, with a function in place of the number $x$.
Table 3.1. The fixed-point theorems used in the first-year sequence. The first two assert existence only; the third requires the contraction property and also gives uniqueness and convergence of iteration.
TheoremThe setThe mapConclusion
Brouwer (Theorem 3.2)nonempty, compact, convexcontinuous $f:X\to X$a fixed point exists
Kakutani (Theorem 3.4)nonempty, compact, convexconvex values, closed grapha fixed point exists

Contraction (Theorem 3.7)

nonempty, closedcontraction with modulus $\beta<1$exactly one fixed point
--- Previous: [Lecture 7: Constrained Optimization](https://maria-titova.com/courses/math-camp/07-constrained-optimization.md) · Next: [Lecture 9: Dynamic Programming and the Bellman Equation](https://maria-titova.com/courses/math-camp/09-dynamic-programming.md)