Optimal Delegation in a Multidimensional World

Consider an indirect utility $U$ that corresponds to some incentive-compatible mechanism. In general, there are many incentive-compatible mechanisms that induce the same indirect utility; however, all such mechanism induce the same payoff for the principal. To see this, let $m$ be an incentive-compatible mechanism with corresponding indirect utility $U$. Using $\nabla U(s)=\mathbb{E}[m(s)]$ (by an Envelope theorem) and $U(s)=\nabla U(s)\cdot s+b(m(s))$, the principal’s payoff from mechanism $m$ in state $s$ is completely determined by $U$:

$\displaystyle\mathbb{E}[m(s)]\cdot g(s)+\kappa b(m(s))=\nabla U(s)\cdot[g(s)-\kappa s]+\kappa U(s).$

This observation implies that the principal’s payoff is a linear function of $U$. Therefore, a solution to the principal’s problem can be found at an extreme point of the feasible set. Returning to Figure 2, it is easy to see that the indirect utilities in Figures 2(a)–2(c) are extremal in that they cannot be written as a nontrivial convex combination of two feasible indirect utilities. In contrast, the indirect utility in 2(d) can be written as such a convex combination. This implies that whenever this mechanism is optimal, there is another (and simpler) mechanism which is also optimal. Intuively, one can write this indirect utility as a convex combination because two adjacent regions obtain distinct stochastic actions. This insight shows how, without loss of optimality, one can restrict attention to a smaller class of mechanism.⁷⁷7[22] develop this point more formally in the context of one-dimensional types/actions and quadratic utilities and characterize the set of extremal mechanisms. Formulating the problem in terms of indirect utilities and using our Lemma 1, one can obtain this characterization more directly. It would be interesting to extend this characterization of extremal mechanisms to the multidimensional setting. For multidimensional settings, analogous arguments show that many complicated mechanisms are not extremal and therefore the principal need not consider these mechanisms.

As is standard in multidimensional mechanism design [[, see, for example,]]rochet1998ironing, we can use the divergence theorem to reformulate the objective function as follows:

		$\displaystyle\int\big{[}\kappa U(s)+\nabla U(s)\cdot[g(s)-\kappa s]\big{]}\,\mathrm{d}F(s)$
	$\displaystyle=$	$\displaystyle\int U(s)\big{[}\kappa f(s)-\operatorname{div}[(g(s)-\kappa s)f(s)]\big{]}\,\mathrm{d}s+\int_{\operatorname{bd}S}U(s)[g(s)-\kappa s]f(s)\cdot\hat{\mathbf{n}}_{S}(s)\,\mathrm{d}\mathcal{H}(s),$

where $\div$ denotes the divergence of a function, for any set $A$, $\operatorname{bd}A$ denotes the boundary of $A$, $\mathcal{H}$ denotes the $n-1$-dimensional Hausdorff measure on the boundary of $S$, and $\hat{\mathbf{n}}_{S}(s)$ denotes the outward normal vector to the convex set $S$ at $s\in\operatorname{bd}S$.

This allows us to write the principal’s problem as⁸⁸8The existence of a maximizer follows from standard arguments.

	$\displaystyle\max_{U\text{ convex}}\int U(s)\,\mathrm{d}\mu(s)$
	$\displaystyle\text{s.\,t. }U\leq h,$

where the measure $\mu$ is defined by

$\displaystyle\mu(E)=\int_{E}\nu(s)\,\mathrm{d}\lambda(s),$

$\lambda$ is the Lebesgue measure on $S$ plus the Hausdorff measure on the boundary of $S$, and

$\displaystyle\nu(s):=\begin{cases}\kappa f(s)-\operatorname{div}[(g(s)-\kappa s)f(s)]&\text{ if }s\in\operatorname{int}S\\ [g(s)-\kappa s]f(s)\cdot\hat{\mathbf{n}}_{S}(s)&\text{ if }s\in\operatorname{bd}S.\end{cases}$

Cearly, $\nu$ plays an important role in determining which mechanisms are optimal. Heuristically, $\nu(s)$ measures how much the prinicipal’s payoff increases if the indirect utility of type $s$ is increased, but where types on the boundary get extra weight.

To illustrate $\nu$ and for later use, let use compute $\nu$ for a one-dimensional type space $S=[\underline{s},\overline{s}]$:

$\displaystyle\nu(s):=\begin{cases}\kappa f(s)-[g^{\prime}(s)-\kappa]f(s)-[g(s)-\kappa s]f^{\prime}(s)&\text{ if }s\in(\underline{s},\overline{s})\\ [g(\overline{s})-\kappa\overline{s}]f(\overline{s})&\text{ if }s=\overline{s}\\ [\kappa\underline{s}-g(\underline{s})]f(\underline{s})&\text{ if }s=\underline{s}.\end{cases}$

(1)

Given an indirect utility $U$, we let $\mathcal{Q}$ denote a coarsest partition of $\mathbb{R}^{n}$ such that $U$ is affine on each partition element. We denote by $\{\mu|_{Q}\}_{Q\in\mathcal{Q}}$ a conditional measure of $\mu$ given $Q$.

Two comments on the conditions in Theorem 1 are in order. First, if there is $s\in Q$ such that $U(s)=h(s)$ then it is unique because $U$ is affine on $Q$ and $h$ is strictly convex. Second, for the necessity result, observe that $U$ is differentiable Lebesgue-almost everywhere since it is a convex function. Since $|\mu|$ is absolutely continuous with respect to the Lebesgue measure on the interior of $S$, $U$ is differentiable $|\mu|$-almost everywhere if, for example, the density $f$ is zero on the boundary of $S$ or if $U$ is differentiable $\mathcal{H}$-almost everywhere on the boundary of $S$. In the one-dimensional case, this last condition can always be satisfied.

Why are the conditions in Theorem 1 sufficient for $U$ to be optimal? Consider a partition element $Q\in\mathcal{Q}$ and suppose $\delta_{Q}$ is a point mass at $s^{*}$. Then any feasible indirect utility $V$ will be convex and lie below $U$ at $s^{*}$. Also, $\mu|_{Q}\leq_{cx}\delta_{Q}$ implies $\int V(s)\,\mathrm{d}\mu|_{Q}(s)\leq\int V(s)\,\mathrm{d}\delta_{Q}(s)$. Moreover, if $a$ is an affine function that coincides with $V$ at the barycenter of $\mu|_{Q}$ then we get $\int V(s)\,\mathrm{d}\mu|_{Q}(s)\leq\int a(s)\,\mathrm{d}\mu|_{Q}(s)$. Since $U$ restricted to $Q$ is affine, lies above $V$ at $s^{*}$, and $\mu|Q(Q)\geq 0$, this implies that conditional on the type belonging to $Q$, the principal’s expected payoff under $U$ is higher than under $V$. And if $\delta_{Q}$ is the zero measure then $V$ might lie above $U$ but the same conclusion follows since $\mu|_{Q}(Q)=0$ and conditional on $Q$, adding a constant to the indirect utility does not change the principal’s payoff. The conclusion that these conditions are also essentially necessary shows that the problem can in some sense be decomposed: whenever the principal can improve $U$ conditional on $Q$, she can extend this improved version to a feasible indirect utility that yields unconditionally a higher payoff.

A particularly simple mechanism is if the principal delegates the decision to the agent, potentially restricting the agents action to belong to some set $A$. Note that any deterministic mechanism can be implemented as an indirect mechanism in this way. For a closed set $A\subseteq S$, we say that delegating to $A$ is optimal if an optimal mechanism takes the form that any type in $A$ gets her first-best action, and any other type gets her most preferred action among the first-best actions of types in $A$. For example, if $n=1$ and $A=[s_{1},s_{2}]$ then delegating to $A$ is optimal if there is an optimal mechanism in which any type below $s_{1}$ gets the first-best action of type $s_{1}$, any type in $[s_{1},s_{2}]$ gets her first best action, and any type above $s_{2}$ gets the first-best action of type $s_{2}$. In the following we will specialize Theorem 1 and discuss under what conditions such a mechanism is optimal.

We can simplify the conditions in Theorem 1 by recalling that the convex order has a simple structure for one-dimensional spaces. A cdf $H_{1}$ on a one-dimensional interval $[x,y]$ dominates a cdf $H_{2}$ in the convex order if and only if $H_{2}$ majorizes $H_{1}$:

$$\int_{s}^{y}H_{1}(z)\,\mathrm{d}z\leq\int_{s}^{y}H_{2}(z)\,\mathrm{d}z$$

for all $s\in[x,y]$ with equality for $s=x$ [[]Theorem 3.A.1]shaked2007stochastic. This observation simplifies the characterization in Theorem 1 whenever $U$ is affine on at most one-dimensional sets. As we will see, this is useful even if the type space is multidimensional. To illustrate the simpler conditions, we first consider when interval delegation is optimal with one-dimensional types [[, for earlier characterizations, see]]AM:08,AB:13.

• Proof.

  Note that the partition $\mathcal{Q}$ induced by $U$ has elements $[\underline{s},s_{1}]$, $[s_{2},\overline{s}]$, and $\{s\}$ for all $s\in(s_{1},s_{2})$. For all $s\in(s_{1},s_{2})$, $\nu(s)\geq 0$ is equivalent to $\mu|_{Q}(Q)\geq 0$ and $\mu|_{Q}\leq_{cx}\delta_{Q}$ for $Q=\{s\}$.⁹⁹9For $s\in\{s_{1},s_{2}\}$, if $s\in\operatorname{int}S$ then $\nu(s)\geq 0$ follows because $\nu$ is continuous on the interior of $S$. And if $s\in\operatorname{bd}S$, there is $Q\in\mathcal{Q}$ with $Q\cap S=\{s\}$ and hence $\mu|_{Q}(Q)\geq 0$ implies $\nu(s)\geq 0$. Now consider $Q=[s_{2},\overline{s}]$ and let $\lambda(x|x\geq s_{2})$ denote the conditional distribution of $\lambda$ conditional on $x\geq s_{2}$. Since $\delta_{Q}$ is a point mass of mass $\mu|_{Q}(Q)$ at $s_{2}$, we can use majorization to rewrite $\mu|_{Q}\leq_{cx}\delta_{Q}$ as

  $$\int_{s}^{\overline{s}}\int_{x}^{\overline{s}}\nu(z)\,\mathrm{d}\lambda(z|z\geq s_{2})\,\mathrm{d}x\leq 0$$

  for all $s\geq s_{2}$ with equality for $s=s_{2}$. Integrating by parts, this becomes condition (ii). Moreover, since the derivative with respect to $s$ of the left-hand side evaluated at $s_{2}$ is negative, we obtain $\mu|_{Q}(Q)\geq 0$. The argument for $Q=[\underline{s},s_{1}]$ is analogous. ∎

Figure 3 illustrates condition (ii). Suppose that starting with interval delegation (represented by the solid indirect utility), the principal changes the mechanism and assigns a lottery with expected value strictly above $\nabla U(s_{2})$ to all types above $s$. This tilts the indirect utility starting at $s$ upwards (see the dashed indirect utility) and therefore increases the indirect utility for every type $x\geq s$ in proportion to $x-s$. The change in the principal’s expected payoff is therefore proportional to $\int_{s}^{\overline{s}}(x-s)\nu(x)\,\mathrm{d}\lambda(x|x\geq s_{2})$. Consequently, condition (ii) ensures that such changes are not profitable. Equality for $s=s_{2}$ implies, in addition, that it would not be profitable to marginally reduce the action for all types above $s_{2}$ either.

Interestingly, the conditions identified in Corollary 1 are in our setting equivalent to the ones obtained in [2, Proposition 2a ]. This might initially be surprising since we characterize optimality of interval delegation in the class of stochastic mechanisms and [2] characterize optimality in the class of deterministic mechanisms (and stochastic mechanisms can do strictly better in general). Figure 3 illustrates why the conditions are the same: Suppose the principal strictly benefits from deviating to the dashed indirect utility, which represents a stochastic mechanism. Since her payoff is linear in $U$, the arguments in the previous paragraph imply that she also benefits from deviating to the dotted indirect utility. Since the dotted linear utility corresponds to a deterministic mechanism, we conclude that conditions (ii) in (iii) in Corollary 1 are necessary for interval delegation to be optimal in the class of deterministic mechanisms (and necessity of condition (i) can be shown easily). Later, it will become clear that this equivalence is specific to the one-dimensional setting.

The key insight for this result is that any pooling region (i.e., any $Q$ such that $Q\cap S$ is not a singleton) must contain types $s$ with $\nu(s)\geq 0$ (since $\mu|_{Q}(Q)\geq 0$) and types $s$ with $\nu(s)\leq 0$ (since no point measure $\delta_{Q}$ can dominate a distinct positive measure in the convex order). If $\nu$ is positive on an interval, it follows that there can be at most two pooling regions. A simple argument then shows that delegating to an interval is an optimal mechanism.

Corollary 2 extends Proposition 2(a) in [4], which in our notation requires $\nu$ to be positive on $(\underline{s},\overline{s})$. An simple implication of our result is the following, which can be useful for applications.

As another illustration, let us return to Example 1 specializing to a one-dimensional type space.

For a one-dimensional type space, the approach used in Corollary 1 can be used to simplify the conditions in Theorem 1 for any mechanism, not just interval delegation. More generally, this approach is useful even with multidimensional types. To see this, let $A$ be a closed and convex set and, for $s\in\operatorname{bd}A$, let $N_{A}(s)$ denote the normal cone to $A$ at $s$. With quadratic payoffs, if the principal delegates $A$ and $s\in\operatorname{bd}A$, then all types in $s+N_{A}(s)$ will choose action $s$. Moreover, if the boundary of $A$ is differentiable then $N_{A}(s)$ is a (one-dimensional) ray and we can again use majorization to simplify the convex dominance conditions in Theorem 1.

The conditions in Corollary 4 closely resemble those in Corollary 1. Indeed, Condition (i) in either case requires that $\nu$ is positive on the set of types that obtain their first-best payoffs, and Condition (ii) (and Conditions (ii) and (iii), respectively) impose that for each point on the boundary the analogous stochastic dominance condition holds.

The economic interpretation of Condition (ii) is analogous to how we interpreted Condition (ii) in Corollary 1. This condition ensures that the principal does not benefit from marginally tilting the indirect utility along line segments that are orthogonal to the boundary of $A$, e.g., the solid line segment in Figure 4. Observe that there is a stochastic mechanism in which the indirect utility is increased only in a small neighborhood of the solid line segment (by Lemma 1). On the other hand, there is no deterministic mechanism achieving this because for any deterministic action the indirect utility would have to increase significantly along the solid line segment (in order to reach the first-best payoff for some type) and convexity then requires that all types in a neighborhood of the line segment obtain higher indirect utilities. This indicates that our characterization relies in the multidimensional setting on stochastic mechanisms being feasible.

To proof Theorem 1, we use duality in linear programming. To formulate the dual program, it is more convenient to work with indirect utilities that are defined on a compact domain. But recall that it is not enough to only require that $U(s)\leq h(s)$ for all $s\in S$. The following technical result ensures that we can restrict the indirect utilities to have a compact domain as long as this domain is chosen large enough.

Formally, we show that if $X$ is chosen large enough then for any solution to the above problem there is a corresponding solution to the original problem. For a convex function $U$ defined on $S$, we consider the smallest convex function defined on $\mathbb{R}^{n}$ that extends $U$. If this extension lies below $h$ on a large set $X$ then $h(y)<U(y)$ for some $y$ is possible only if $\lVert\nabla U(s)\rVert$ is large for some $s\in S$, i.e., the expected action for some type is large. We show that this implies that the principal’s expected payoff is low, contradicting that $U$ is a solution.

Now let $X$ be as in the above lemma and denote by $\mathcal{U}$ the set of convex continuous functions that map $X$ to $\mathbb{R}$ and by $\mathcal{M}_{+}$ the set of positive measures on $X$. We can formulate the principal’s problem as follows (and call this formulation the primal problem):

		$\displaystyle\max_{U\in\mathcal{U}}\int U(s)\,\mathrm{d}\mu(s)$		(P)
		$\displaystyle\text{s.\,t. }U\leq h$