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.\)