论文标题
合同的复杂性
The Complexity of Contracts
论文作者
论文摘要
我们在简洁的主体代理设置中启动计算（接近）最佳合同的研究。在这里，最优性意味着最大化校长对所有与激励兼容的合同的预期收益 - 在经济学中被称为“第二好的”解决方案。我们还研究了自然放松，以大致与激励兼容的合同。 我们专注于主要描述（和指数较大）的结果空间的主要代理设置。我们表明，计算近乎最佳合同的计算复杂性从根本上取决于代理动作的数量。 For settings with a constant number of actions, we present a fully polynomial-time approximation scheme (FPTAS) for the separation oracle of the dual of the problem of minimizing the principal's payment to the agent, and use this subroutine to efficiently compute a delta-incentive-compatible (delta-IC) contract whose expected payoff matches or surpasses that of the optimal IC contract. 有了任意数量的动作，我们证明了在任何常数c中都难以近似问题。即使对于Delta-IC合同，DELTA是C的足够快速付费函数，即使是Conta-IC合同也可以。在正面，我们表明，具有恒定三角洲的简单线性delta-iC合同足以实现“第一最好”（全福利提取）解决方案的恒定因素近似，并且可以在多项式时间内计算此合同。
We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing the principal's expected payoff over all incentive-compatible contracts---known in economics as "second-best" solutions. We also study a natural relaxation to approximately incentive-compatible contracts. We focus on principal-agent settings with succinctly described (and exponentially large) outcome spaces. We show that the computational complexity of computing a near-optimal contract depends fundamentally on the number of agent actions. For settings with a constant number of actions, we present a fully polynomial-time approximation scheme (FPTAS) for the separation oracle of the dual of the problem of minimizing the principal's payment to the agent, and use this subroutine to efficiently compute a delta-incentive-compatible (delta-IC) contract whose expected payoff matches or surpasses that of the optimal IC contract. With an arbitrary number of actions, we prove that the problem is hard to approximate within any constant c. This inapproximability result holds even for delta-IC contracts where delta is a sufficiently rapidly-decaying function of c. On the positive side, we show that simple linear delta-IC contracts with constant delta are sufficient to achieve a constant-factor approximation of the "first-best" (full-welfare-extracting) solution, and that such a contract can be computed in polynomial time.
