# The Complexity of Contracts

arXiv: https://arxiv.org/abs/2002.12034 · HTML: https://mlsanity.com/paper/2002.12034/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

## Built on by (most cited first, 16 of 16)

- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Principal-Agent Hypothesis Testing](https://mlsanity.com/paper/2205.06812/) (2022)
- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Deep Contract Design via Discontinuous Networks](https://mlsanity.com/paper/2307.02318/) (2023)
- [Online Learning in a Creator Economy](https://mlsanity.com/paper/2305.11381/) (2023)
- [Delegating Data Collection in Decentralized Machine Learning](https://mlsanity.com/paper/2309.01837/) (2023)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Harnessing the Continuous Structure: Utilizing the First-order Approach in Online Contract Design](https://mlsanity.com/paper/2403.07143/) (2024)
- [Operationalizing Counterfactual Metrics: Incentives, Ranking, and Information Asymmetry](https://mlsanity.com/paper/2305.14595/) (2023)
- [Disinformation, Stochastic Harm, and Costly Effort: A Principal-Agent Analysis of Regulating Social Media Platforms](https://mlsanity.com/paper/2106.09847/) (2021)
- [Incentivizing High-Quality Human Annotations with Golden Questions](https://mlsanity.com/paper/2505.19134/) (2025)
- [Scalable Principal-Agent Contract Design via Gradient-Based Optimization](https://mlsanity.com/paper/2510.21177/) (2025)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)

## Abstract (arXiv)

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.