Bayesian agency: Linear versus tractable contracts

We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme (a.k.a. contract) so as to induce an agent to take a costly, unobservable action. We relax the assumption that the principal perfectly knows the agent by considering a Bayesian setting where the agent's type is unknown and randomly selected according to a given probability distribution, which is known to the principal. Each agent's type is characterized by her own action costs and action-outcome distributions. In the literature on non-Bayesian principal-agent problems, considerable attention has been devoted to linear contracts, which are simple, pure-commission payment schemes that still provide nice approximation guarantees with respect to principal-optimal (possibly non-linear) contracts. While in non-Bayesian settings an optimal contract can be computed efficiently, this is no longer the case for our Bayesian principal-agent problems. This further motivates our focus on linear contracts, which can be optimized efficiently given their single-parameter nature. Our goal is to analyze the properties of linear contracts in Bayesian settings, in terms of approximation guarantees with respect to optimal contracts and general tractable contracts (i.e., efficiently-computable ones). First, we study the approximation guarantees of linear contracts with respect to optimal ones, showing that the former suffer from a multiplicative loss that grows linearly in the number of agent's types. Nevertheless, we prove that linear contracts can still provide a constant multiplicative approximation ρ of the optimal principal's expected utility, though at the expense of an exponentially-small additive loss 2^−Ω(ρ). Then, we switch to tractable contracts, showing that, surprisingly, linear contracts perform well among them. In particular, we prove that it is NP-hard to design a contract providing a multiplicative loss sublinear in the number of agent's types, while the same holds for contracts that provide a constant multiplicative approximation ρ at the expense of an additive loss 2^−ω(ρ). We conclude by showing that, in Bayesian principal-agent problems, an optimal contract can be computed efficiently if we fix either the number of agent's types or the number of outcomes.