# A CLASS OF EXAMPLES

In this section, I develop an example in which cost-minimizing contracts are ordered by the supplement partial ordering, and the operator $$\hat w\left( {\bar w} \right)$$ is monotone. Let $$W = \left\{ {w \ge 0:y \ge y' \Rightarrow w\left( y \right) \ge w\left( {y'} \right)} \right\}$$ be the set of non-negative, weakly increasing contracts on $$Y$$. Let $$Y = \left\{ {0,1} \right\}$$, $$E = \left[ {0,1} \right]$$, and $$\Pr \left[ {y = 1|e} \right] = e$$. I will take no stance on the functional form of $$c\left( e \right)$$ except that it is (weakly) increasing.

Define $${E^{feas}} \subset E$$ to be the set of $$e$$ for which there is some $$w \in W$$ such that $w \cdot \phi \left( e \right) - c\left( e \right) \ge U\left( w \right),$ where $U\left( w \right) = \mathop {\sup }\limits_{\tilde e \in E} w \cdot \phi \left( {\tilde e} \right) - c\left( {\tilde e} \right).$Define $$\tilde c\left( e \right)$$ to be the largest convex function such that $$\tilde c\left( e \right) \le c\left( e \right)$$ for all $$e \in E$$. Then $${E^{feas}} = \left\{ {e \in E:\tilde c\left( e \right) = c\left( e \right)} \right\}$$.

When there are only two possible output levels, it is straightforward to characterize the set of cost-minimizing contracts. They are characterized in lemmas 6 and 7.

Lemma 6: If $$w \cdot \phi \left( e \right) - c\left( e \right) \ge U\left( w \right)$$, then there is a $$\tilde w \in W$$ with $$\tilde w\left( 0 \right) = 0$$ such that $$\tilde w \cdot \phi \left( e \right) - c\left( e \right) \ge U\left( {\tilde w} \right)$$ and $$\tilde w \cdot \phi \left( e \right) \le w \cdot \phi \left( e \right)$$.

As a corollary of Lemma 6, we have that all cost-minimizing contracts pay the agent only when $$y = 1$$.

Corollary 2: For each $$e \in {E^{feas}}$$, $$w_e^*\left( 0 \right) = 0$$.

Next, cost-minimizing contracts implementing higher effort levels involve higher payments conditional on high output.

Lemma 7: If $$e \ge e'$$, $$w_e^*\left( 1 \right) \ge w_{e'}^*\left( 1 \right)$$.

Proof of Lemma 7: We know from corollary 2 that $$w_e^*\left( 0 \right) = 0$$. Further, we know that $w_e^*\left( 1 \right) \cdot e - c\left( e \right) \ge w_e^*\left( 1 \right) \cdot e' - c\left( {e'} \right)$and$w_{e'}^*\left( 1 \right) \cdot e' - c\left( {e'} \right) \ge w_{e'}^*\left( 1 \right) \cdot e - c\left( e \right),$which implies that$w_e^*\left( 1 \right) \cdot \left( {e - e'} \right) \ge c\left( e \right) - c\left( {e'} \right) \ge w_{e'}^*\left( 1 \right) \cdot \left( {e - e'} \right)$or$\left( {w_e^*\left( 1 \right) - w_{e'}^*\left( 1 \right)} \right) \cdot \left( {e - e'} \right) \ge 0.$Since $$e \ge e'$$, it must therefore be the case that $$w_e^*\left( 1 \right) \ge w_{e'}^*\left( 1 \right)$$. Q.E.D.

Putting together corollary 2 and lemma 7, let $$\tilde w = \left( {0,w_e^*\left( 1 \right) - w_{e'}^*\left( 1 \right)} \right)$$. Clearly, $$\tilde w \in W$$, and therefore $$w_e^* = w_{e'}^* + \tilde w$$, so that $$w_e^*{ \ge _W}w_{e'}^*$$.

Now, we will turn to the second part of the problem, which is to show that the operator $$\hat w\left( {\bar w} \right)$$ is monotone. We will show this in a couple steps. First, note that we can write $${\tilde B_{\bar w}} = B + \left( {N - 1} \right)\bar w$$ and for $$e \in E_{\bar w}^{feas}$$, ${C_{\bar w}}\left( e \right) = \mathop {\min }\limits_{w \in W + \left( {1 - 1/N} \right)\bar w} \left\{ {w \cdot \phi \left( e \right)|w \in \partial c\left( e \right)} \right\},$where $$E_{\bar w}^{feas}$$ is an increasing function of $$\bar w$$. An increase in $$\bar w$$ increases $${\tilde B_{\bar w}}$$, and it constrains the cost-minimization problem for implementing $$e$$ in two ways: for $$\bar w{ \ge _W}\bar w'$$, $$E_{\bar w}^{feas} \subset E_{\bar w'}^{feas}$$, and secondly, it impacts the set of feasible contracts for implementing $$e \in E_{\bar w}^{feas}$$ at lowest cost and will therefore potentially increase the cost of implementing $$e$$. It will be useful to break this analysis up into three steps. First, I will show how an increase in $$\bar w$$ impacts the cost-minimization problem. Then, I will argue that any contract in $$\hat w\left( {\bar w} \right)$$ is a cost-minimizing contract relative to $$\bar w$$. Finally, I will explore how an increase in $$\bar w$$ affects $${\tilde B_{\bar w}}$$.

For the first step, define a cost-minimizing contract relative to $$\bar w$$ as $$w_e^{*\bar w}$$ that solves $\mathop {\min }\limits_{w \in W + \left( {1 - 1/N} \right)\bar w} w \cdot \phi \left( e \right)$subject to incentive compatibility, which we can write as$w \in \partial c\left( e \right).$

Lemma 8: If $$\bar w{ \ge _W}\bar w'$$, then $$w_e^{*\bar w}{ \ge _W}w_e^{*\bar w'}$$. Further, $${C_{\bar w}}\left( e \right) = C\left( e \right) + \left( {1 - 1/N} \right)\bar w\left( 0 \right)$$, where $$C\left( e \right) = w_e^* \cdot \phi \left( e \right)$$.

Proof of Lemma 8: In the case of binary output, the subdifferential becomes$\partial c\left( e \right) = \left\{ {w:\tilde c{'^ - }\left( e \right) \le w\left( 1 \right) - w\left( 0 \right) \le \tilde c{'^ + }} \right\},$where $$\tilde c\left( e \right)$$ is the largest convex function such that $$\tilde c\left( e \right) \le c\left( e \right)$$ for all $$e$$, and $$\tilde c{'^ - }$$ and $$\tilde c{'^ + }$$ are, respectively, the left and right derivatives of $$\tilde c$$.

The constrained cost-minimization problem is then$\mathop {\min }\limits_{w \in W + \left( {1 - 1/N} \right)\bar w} \left\{ {w \cdot \phi \left( e \right):w \in \partial c\left( e \right)} \right\},$or equivalently$\mathop {\min }\limits_{\Delta \in W} \left\{ {\left( {\left( {1 - 1/N} \right)\bar w + \Delta } \right) \cdot \phi \left( e \right):\left( {1 - 1/N} \right)\bar w + \Delta \in \partial c\left( e \right)} \right\},$or since $$\left( {1 - 1/N} \right)\bar w \cdot \phi \left( e \right)$$ is independent of $$\Delta$$,$\mathop {\min }\limits_{\Delta \in W} \left\{ {\Delta \cdot \phi \left( e \right):\left( {1 - 1/N} \right)\bar w + \Delta \in \partial c\left( e \right)} \right\}.$Next, note that we can write $$\left( {1 - 1/N} \right)\bar w + \Delta \in \partial c\left( e \right)$$ as follows:$\tilde c{'^ - }\left( e \right) \le \left( {1 - 1/N} \right)\bar w\left( 1 \right) + \Delta \left( 1 \right) - \left( {1 - 1/N} \right)\bar w\left( 0 \right) - \Delta \left( 0 \right) \le \tilde c{'^ + }\left( e \right),$or equivalently$- \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) + \tilde c{'^ - }\left( e \right) \le \Delta \left( 1 \right) - \Delta \left( 0 \right) \le - \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) + \tilde c{'^ + }\left( e \right).$Since $$\Delta \left( 1 \right) \ge \Delta \left( 0 \right)$$ in order for $$\Delta \in W$$, if $$\left( {1 - 1/N} \right)\bar w + \Delta \in \partial c\left( e \right)$$, then there is a $$\tilde \Delta$$ such that $$\tilde \Delta \left( 0 \right) = 0$$, $$\tilde \Delta \left( 1 \right) \le \Delta \left( 1 \right)$$, $$\tilde \Delta \in W$$, and $$\left( {1 - 1/N} \right)\bar w + \tilde \Delta \in \partial c\left( e \right)$$. Any constrained optimum must therefore have $${\Delta ^*}\left( 0 \right) = 0$$, so the problem is to find the smallest $$\Delta \left( 1 \right) \ge 0$$ such that$- \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) + \tilde c{'^ - }\left( e \right) \le \Delta \left( 1 \right) \le - \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) + \tilde c{'^ + }\left( e \right)$ or${\Delta ^*}\left( 1 \right) = - \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) + \tilde c{'^ - }\left( e \right),$so that$w_e^{*\bar w}\left( 1 \right) = \left( {1 - 1/N} \right)\bar w\left( 1 \right) + {\Delta ^*}\left( 1 \right) = \left( {1 - 1/N} \right)\bar w\left( 0 \right) + \tilde c{'^ - }\left( e \right).$Therefore, if $$\bar w{ \ge _W}\bar w'$$, then $$w_e^{*\bar w}\left( 0 \right) = w_e^{*\bar w'}\left( 0 \right) = 0$$,$w_e^{*\bar w}\left( 1 \right) - w_e^{*\bar w'}\left( 1 \right) = \left( {1 - 1/N} \right)\left( {\bar w\left( 0 \right) - \bar w'\left( 0 \right)} \right) \ge 0.$Let $$\tilde w = \left( {0,w_e^{*\bar w}\left( 1 \right) - w_e^{*\bar w'}\left( 1 \right)} \right)$$. Then $$\tilde w \in W$$ and $$w_e^{*\bar w} = w_e^{*\bar w'} + \tilde w$$, so $$w_e^{*\bar w}{ \ge _W}w_e^{*\bar w'}.$$

Finally, note that${C_{\bar w}}\left( e \right) = \left( {\left( {1 - 1/N} \right)\bar w\left( 0 \right) + {\Delta ^*}\left( {0;\bar w} \right)} \right)\left( {1 - e} \right) + \left( {\left( {1 - 1/N} \right)\bar w\left( 1 \right) + {\Delta ^*}\left( {1;\bar w} \right)} \right)e$for each $$\bar w$$ so that${C_{\bar w}}\left( e \right) - {C_0}\left( e \right) = \left( {1 - 1/N} \right)\bar w\left( 0 \right),$and therefore, as long as$$e \in E_{\bar w}^{feas}$$,${C_{\bar w}}\left( e \right) = {C_0}\left( e \right) + \left( {1 - 1/N} \right)\bar w\left( 0 \right),$which was the final claim. Q.E.D.

Next, I will show that any solution to the program$\mathop {\max }\limits_{w \in W + \left( {1 - 1/N} \right)\bar w} \left( {{{\tilde B}_{\bar w}} - Nw} \right) \cdot \phi \left( {e\left( w \right)} \right)$is a cost-minimizing contract relative to $$\bar w$$.

Lemma 9: Suppose $$\hat w\left( {\bar w} \right)$$ is a solution to the above program. Then $$\hat w\left( {\bar w} \right)$$ is a cost-minimizing contract relative to $$\bar w$$.

Proof of Lemma 9: Suppose $$\hat w\left( {\bar w} \right)$$ is not a cost-minimizing contract relative to $$\bar w$$. Let $$\hat e = {e^*}\left( {\hat w\left( {\bar w} \right)} \right)$$. Since $$w_{\hat e}^{*\bar w}$$ is a cost-minimizing contract relative to $$\bar w$$, it is feasible, and we have that$w_{\hat e}^{*\bar w} \cdot \phi \left( e \right) < \hat w\left( {\bar w} \right) \cdot \phi \left( e \right),$which implies that$\left( {{{\tilde B}_{\bar w}} - Nw_{\hat e}^{*\bar w}} \right) \cdot \phi \left( e \right) > \left( {{{\tilde B}_{\bar w}} - N\hat w\left( {\bar w} \right)} \right) \cdot \phi \left( e \right),$which contradicts the claim that $$\hat w\left( {\bar w} \right)$$ was a solution to the problem. Q.E.D.

Lemma 9 implies that, given $$\bar w$$, instead of solving for the optimal contract, we can solve instead for the optimal effort level $$e$$. That is, we want to solve $\mathop {\max }\limits_{e \in E_{\bar w}^{feas}} {\tilde B_{\bar w}} \cdot \phi \left( e \right) - N{C_{\bar w}}\left( e \right).$We know from lemma 8 that $$N{C_{\bar w}}\left( e \right) = NC\left( e \right) + \left( {N - 1} \right)\bar w\left( 0 \right)$$, so the problem is actually just$\mathop {\max }\limits_{e \in E_{\bar w}^{feas}} {\tilde B_{\bar w}} \cdot \phi \left( e \right) - NC\left( e \right).$That is, $$\bar w$$ only affects the optimal effort level through its effect on $${\tilde B_{\bar w}}$$ and through the set $$E_{\bar w}^{feas}$$.

Lemma 10: Suppose $$\bar w{ \ge _W}\bar w'$$. If we define$\hat e\left( {\bar w} \right) = \mathop {\arg \max }\limits_{e \in E_{\bar w}^{feas}} {\tilde B_{\bar w}} \cdot \phi \left( e \right) - NC\left( e \right),$then $$\hat e\left( {\bar w} \right)$$ is increasing in $$\bar w$$.

Proof of Lemma 10: Since $$E_{\bar w}^{feas}$$ is increasing in $$\bar w$$ (i.e., if $$\bar w{ \ge _W}\bar w'$$ and $$e \in E_{\bar w}^{feas}$$ and $$e' \in E_{\bar w'}^{feas}$$, then $$\min \left\{ {e,e'} \right\} \in E_{\bar w'}^{feas}$$ and $$\max \left\{ {e,e'} \right\} \in E_{\bar w}^{feas}$$), and since $${\tilde B_{\bar w}} \cdot \phi \left( e \right)$$ satisfies increasing differences in $$\left( {\bar w,e} \right)$$, by Topkis's theorem, $$\hat e\left( {\bar w} \right)$$ is increasing in $$\bar w$$. Q.E.D.

When there are only two possible output levels, it is straightforward to characterize the set of cost-minimizing contracts. For all $$e \in {E^{feas}},$$ $$w_e^*\left( 0 \right) = 0$$, and $$\tilde c{'^ - }\left( e \right) \le w_e^*\left( 1 \right) \le \tilde c{'^ + }\left( e \right)$$, where $$\tilde c{'^ - }\left( e \right)$$ and $$\tilde c{'^ + }\left( e \right)$$ are the left and right derivatives of $$\tilde c$$ at $$e$$.

Given a proposed aggregate contract $$\bar w \in W$$, the minimal effort level that can be implemented is defined as the $${e_{\min }}\left( {\bar w} \right)$$ that satisfies $$\tilde c{'^ - }\left( {{e_{\min }}\left( {\bar w} \right)} \right) \le \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right) \le \tilde c{'^ + }\left( {{e_{\min }}\left( {\bar w} \right)} \right).$$ Given $$\bar w$$, define $$E_{\bar w}^{feas} = {E^{feas}} \cap \left[ {{e_{\min }}\left( {\bar w} \right),1} \right]$$ to be the set of feasible effort levels relative to $$\bar w$$. Next, define $${C_{\bar w}}\left( e \right) = \left( {1 - 1/N} \right)\left( {\bar w\left( 1 \right) - \bar w\left( 0 \right)} \right)e + \left( {1 - 1/N} \right)\bar w\left( 1 \right)$$ if $$e = {e_{\min }}\left( {\bar w} \right)$$ and $${C_{\bar w}}\left( e \right) = C\left( e \right) + \left( {1 - 1/N} \right)\bar w\left( 1 \right)$$ if $$e > {e_{\min }}\left( {\bar w} \right).$$ Finally, define the operator$\hat e\left( {\bar e} \right) = \mathop {\arg \max }\limits_{e \ge {e_{\min }}\left( {w_{\bar e}^*} \right)} \left( {B + \left( {N - 1} \right)w_{\bar e}^*} \right) \cdot \phi \left( e \right) - N{C_{w_{\bar e}^*}}\left( e \right).$

Theorem 1: $$\bar e$$ is an equilibrium effort level if and only if $$\bar e \in \hat e\left( {\bar e} \right)$$.

Proof of Theorem 1: Suppose $$\bar e$$ is an equilibrium effort level. Then by Lemma X, $$w_{\bar e}^*$$ is an equilibrium aggregate contract. This implies that$w_{\bar e}^* \in \mathop {\arg \max }\limits_{w \in W + \left( {1 - 1/N} \right)w_{\bar e}^*} \left( {B + \left( {N - 1} \right)w_{\bar e}^* - Nw} \right) \cdot \phi \left( {e\left( w \right)} \right),$which by Lemma Y implies that $$\bar e \in \hat e\left( {\bar e} \right)$$.

Next, suppose $$\bar e \in \hat e\left( {\bar e} \right)$$. Then $$\bar e > {e_{\min }}\left( {w_{\bar e}^*} \right)$$, which implies that$w_{\bar e}^* \in \mathop {\arg \max }\limits_{w \in W + \left( {1 - 1/N} \right)w_{\bar e}^*} \left( {B + \left( {N - 1} \right)w_{\bar e}^* - Nw} \right) \cdot \phi \left( {e\left( w \right)} \right),$which implies that $$\bar e$$ is an equilibrium effort level, since by construction, $$e\left( {w_{\bar e}^*} \right) = \bar e$$, and $$w_{\bar e}^*$$ is an equilibrium aggregate contract.

We can therefore focus on the much simpler problem of solving for the fixed points of $$\hat e\left( {\bar e} \right).$$  Further, $$\hat e\left( {\bar e} \right)$$ has some nice properties, which the following proposition shows.

Proposition 1: $$\left( {B + \left( {N - 1} \right)w_{\bar e}^*} \right) \cdot \phi \left( e \right) - N{C_{w_{\bar e}^*}}\left( e \right)$$ satisfies increasing differences in $$\left( {e,\bar e} \right)$$, and $${e_{\min }}\left( {w_{\bar e}^*} \right)$$ is increasing in $$\bar e$$.

Proof of Proposition 1 [work in progress]: The second part of this proposition follows from the definition of $${e_{\min }}\left( {w_{\bar e}^*} \right)$$ and convexity of  $$\tilde c$$. The first part of this proposition just involves computing second differences. Define the function$\tilde \Lambda \left( {e,w_{\bar e}^*} \right) = \left( {B + \left( {N - 1} \right)w_{\bar e}^*} \right) \cdot \phi \left( e \right) - N{C_{w_{\bar e}^*}}\left( e \right).$We want to show that $$\tilde \Lambda \left( {e,w_{\bar e}^*} \right)$$ satisfies increasing differences in $$\left( {e,\bar e} \right)$$, which is equivalent to satisfying increasing differences in $$\left( {e,w_{\bar e}^*} \right)$$, since $${w_{\bar e}^*}$$ is increasing (in the supplement partial ordering) in $$\bar e$$. Consider $$\bar e \ge \bar e'$$, and take $$e > e'$$. There are three cases to consider. First, $$e' > {e_{\min }}\left( {w_{\bar e}^*} \right).$$ Increasing differences is straightforward to show here [still need to do it]. The second case is $$e' = {e_{\min }}\left( {w_{\bar e}^*} \right) > {e_{\min }}\left( {w_{\bar e'}^*} \right),$$and the proof is currently in "Constrained Cost Minimization problem March 25 2015.tex." The third case is$$e' = {e_{\min }}\left( {w_{\bar e}^*} \right) = {e_{\min }}\left( {w_{\bar e'}^*} \right),$$ and the proof is also in that file. In all three cases, $$\tilde \Lambda$$ satisfies increasing differences in $$\left( {e,\bar e} \right)$$. Q.E.D.

By Topkis's theorem, we therefore have that $$\hat e\left( {\bar e} \right)$$ defines a monotone operator on a compact space. The intuition behind this proposition is that, given any cost-minimizing target contract $$w_{\bar e}^*$$, each principal either wants to leave $$\left( {1 - 1/N} \right)w_{\bar e}^*$$ in place by contributing $$w = 0$$, or they want to top up $$\left( {1 - 1/N} \right)w_{\bar e}^*.$$ If they choose to top it up, they will top it up to a cost-minimizing contract, which is feasible, because $$w_{\bar e}^*$$ is increasing in $$e$$. As a result of the monotonicity of $$\hat e\left( {\bar e} \right)$$, by an extension of Tarski's fixed-point theorem, there is at least one fixed point, and the set of fixed points forms a complete lattice.

Theorem 2: The set of equilibrium effort levels $${E^*}$$ is a complete lattice with least and greatest elements $$e_L^*$$ and $$e_H^*$$.

Further, the program described by the operator $$\hat e\left( {\bar e} \right)$$ can be solved explicitly given any (weakly increasing) cost function $$c\left( e \right)$$ and aggregate benefits $$B$$. We can therefore ask when it is the case that $$e_L^* < e_H^* < {e^{SB}}$$ so that the worst equilibrium effort level is strictly worse than the second-best equilibrium effort level. In particular, given $$B$$, I think we will be able to say that for any $$c$$ such that $$\tilde c$$ has points $$e < e_H^*$$ at which it is non-differentiable, for sufficiently large $$N$$, then the smallest such point is an equilibrium effort level. This is satisfied, for instance, by $$c$$ such that $$c\left( 0 \right) = 0$$ and $$c\left( e \right) = F + \frac{c}{2}{e^2},$$ in which case $$\tilde c\left( e \right)$$ is not differentiable at $$0$$. If this conjecture is correct, it is actually nondifferentiability of $$\tilde c$$ , rather than nonconvexities in $$c$$, that leads to coordination failures. In some cases, such as the example with fixed costs, nonconvexities in $$c$$ lead to nondifferentiabilities in $$\tilde c$$, but they are neither necessary nor sufficient. They are not necessary, because our initial example with $$E = \left\{ {0,1} \right\}$$, $$\tilde c$$ is linear (and therefore convex), but it is not differentiable at $$0.$$