Source-linked AI summary
An Introduction to Contract Theory for Computer Scientists
Paul Duetting, Michal Feldman, Inbal Talgam-Cohen
TL;DR
Outcome-based contracts offer a way to incentivize effort in settings that include online services, algorithmic classification, and AI agents. This survey introduces computational tools for analyzing contracts, including linear programming for optimal contracts and guarantees for simpler linear contracts. It also identifies opacity and non-monotonicity as limitations of optimal contracts.
Problem
Strategic responses to algorithms can involve effort rather than truthful reporting, raising questions about payment design, teams of agents, and contracts under incomplete information.
Source: §1 · pp. 2–3Method
Results
Takeaways & Limitations
Performance-based contracts connect economic incentives with computational questions in online markets, algorithmic classification, and AI-agent delegation.
Source: §1 · p. 2Optimal contracts can be opaque and non-monotone, sometimes paying less for a higher-reward outcome.
Source: §3 · p. 6
Abstract
from arXiv · showhide
This survey introduces contract design to computer scientists: using outcome-based payments to incentivize effort. We discuss applications that motivate a computational approach to contract design, ranging from online labor markets, to incentive-aware algorithmic classification, to emerging ecosystems of AI agents. We present the classic principal-agent model and introduce basic concepts. We show how optimal contracts are computable via linear programming, and why they can be opaque and brittle. Motivated by this we turn to simpler contract formats, specifically linear contracts. We discuss approximation guarantees, and robust (max-min) optimality of such contracts. We then move beyond the single-agent setting to combinatorial contract settings with multiple agents, mapping the algorithmic landscape of tractability and approximation. Finally, we discuss partial information settings through the lens of learning algorithms, and outline open directions. The goal is a concise, accessible entry point that connects economic foundations with algorithmic tools and highlights opportunities for new theory and applications.
1. INTRODUCTION
Algorithmic contract design studies outcome-based payments that motivate agents to exert effort, complementing mechanism design’s focus on truthful reporting. The survey introduces this area for computer scientists through applications and core computational questions.
1. INTRODUCTION
- Contracts tie an agent’s compensation to performance and created value, incentivizing effort rather than truthful reporting.This distinction motivates contract design as a frontier for algorithmic game theory.Source: §1 · p. 2
- Online service markets create opportunities for computational contract design as their importance and scale grow.Influencer marketing illustrates choices between flat payments and payments tied to views or conversions.Source: §1 · p. 2
- Classification subjects may strategically modify their features, so contract theory can help steer those efforts toward productive avenues.Examples include credit scoring and university or MOOC exams.Source: §1 · p. 2
- AI-agent ecosystems depend on effective delegation and cooperation, while performance-based contracts can tie agent payments to profit or audience engagement.These measures contrast with per-token or subscription-based LLM monetization.Source: §1 · p. 2
- A central question is how a simple profit-share linear contract compares with contracts using multiple performance indicators.The introduction also asks how teams should split profit and how to design contracts when relevant information must be learned.Source: §1 · pp. 2–3
- The survey offers computer scientists an accessible entry point, covering the canonical model, optimal and linear contracts, multi-agent settings, learning, and future directions.A more comprehensive survey and a separate survey on multi-agent and multi-action combinatorial settings provide broader or deeper coverage.Source: §1 · p. 3
2. MODEL
The hidden-action principal-agent model represents effort through costly actions that stochastically produce observable outcomes. The principal pays based on outcomes, and the agent chooses an action that maximizes expected utility.
2. MODEL
- The agent chooses among costly actions whose stochastic outcomes are observed by the principal, while the actions themselves remain hidden.The model includes a zero-cost action, representing the option to opt out.Source: §2 · p. 3
- Action distributions may satisfy additional regularity conditions, including first-order stochastic dominance, MLRP, or CDFP.These structures capture conditions under which more rewarding outcomes become more likely with more costly effort.Source: §2 · p. 4
- A contract assigns a non-negative transfer to each outcome because the principal cannot condition payment on the hidden action.The principal receives outcome rewards, while the agent bears the action cost; both are risk neutral.Source: §2 · p. 4
- For an action, the agent’s expected utility is expected payment minus cost, and the principal’s is expected reward minus payment.The example contract (0, 1, 3) induces action 2 and gives the principal utility 2.Source: §2 · p. 4
- The principal chooses a contract first, then the agent selects an action maximizing expected utility; ties are broken in the principal’s favor.A utility-maximizing action is incentive compatible and, under the stated assumptions, individually rational for the agent.Source: §2 · pp. 4–5
3. OPTIMAL CONTRACTS
Optimal contracts can be computed in polynomial time by solving a linear program for each action. The section also characterizes implementability, describes simple special cases, and identifies limitations of optimal contracts.
3. OPTIMAL CONTRACTS
- An optimal contract can be computed in polynomial time by solving one linear program per action and selecting the action that maximizes the principal’s utility.For each action, the LP tests implementability and finds the minimum expected payment needed to implement it.Source: §3 · p. 5
- Action i is implementable exactly when no convex combination of other actions yields the same outcome distribution at a lower weighted cost.The characterization follows from LP duality: such a lower-cost replication makes the dual unbounded.Source: §3 · pp. 5–6
- With binary outcomes, an optimal contract is linear; with binary actions, it pays only for the outcome maximizing the likelihood ratio.The single-outcome structure also holds beyond two actions when a zero-cost action produces a zero-reward outcome with certainty; the running example pays only for outcome 3.Source: §3 · p. 6
- Optimal contracts can be opaque and non-monotone, and they rely on accurate input distributions and costs while being sensitive to small perturbations.A higher principal reward can correspond to a lower payment to the agent.Source: §3 · p. 6
4. LINEAR CONTRACTS
Linear contracts pay the agent a fixed share of rewards, making payments simple and interpretable, but they can underperform nonlinear contracts. The section characterizes their approximation guarantees and shows that they are max-min optimal under two forms of partial information.
Linear contracts
- Linear contracts share a fixed fraction α of rewards with the agent, yielding simple, interpretable payments and monotonicity.The agent’s utility depends on αR_i − c_i; at α = 1, the agent chooses the welfare-maximizing action.Source: §4 · pp. 6–7
Geometric perspective
- Tracing the upper envelope of agents’ utility lines αR_i − c_i identifies their best responses, while the principal’s utility is piecewise linear in α.The principal can find an optimal linear contract by checking the critical α values where the agent switches actions.Source: §4 · pp. 7–8, Figure 3 · p. 7
Example 4
- In Example 4, linear contracts yield at most 3 in expected utility for the principal, versus 3.5 under the optimal nonlinear contract.The figure plots agent and principal expected utility against α for this example.Source: Figure 3 · p. 7, §4 · p. 8
Approximation guarantees
- The worst-case ratio between optimal-contract and optimal-linear-contract utility is n for n actions, Θ(log H) for reward spread H, and Θ(log C) for cost spread C.The upper bounds also hold against optimal welfare, while the lower bounds hold even under MLRP; an equal-revenue construction makes the n-action bound tight.Source: §4 · p. 8
Robust optimality
- Linear contracts are max-min optimal when the principal knows a subset of available actions or knows costs, rewards, and actions’ expected rewards.The first result allows the actual action set to be any superset of the known subset; the second allows distributions compatible with the known expected rewards.Source: §4 · pp. 8–9
5. COMBINATORIAL CONTRACTS
Combinatorial contracts extend the principal-agent problem to teams, where a project’s success probability depends on which agents exert effort. The survey describes equilibrium-based contract design and maps both approximation algorithms and computational limits.
Multiple agents
- For a team of agents, a set function determines project success probability, and a linear contract assigns each agent a reward share.Each agent pays a cost to exert effort; the project yields reward 1 on success and 0 on failure.Source: §5 · pp. 9–10
- A contract induces a game among agents, and the design objective is to maximize the principal’s utility in the contract’s best pure Nash equilibrium.An equilibrium requires that no agent benefits by switching between exerting effort and shirking.Source: §5 · p. 10
- For a chosen effort set S, the optimal shares pay participating agents in proportion to cost and inversely to marginal contribution, reducing contract design to selecting S.Agents outside S receive zero; the payment rule reflects the need to limit free riding.Source: §5 · p. 10
Approximation results
- For complement-free success functions, the problem is NP-hard even with additive f, though an FPTAS exists for additive f.The work also studies approximation using value and demand queries for broader function classes.Source: §5 · p. 10
- An O(1)-approximation is computable with polynomially many value queries for submodular success functions, and value plus demand queries for XOS functions.The proof uses demand queries to identify promising agent sets and a scaling argument to keep payments low while preserving sufficient marginal contributions.Source: §5 · p. 10
Impossibility results
- Oracle-based approximation has limits: for submodular functions, constant-factor approximation is ruled out under stated query or complexity assumptions, while XOS value queries cannot achieve a factor better than Ω(n^1/6).The cited results include a P ≠ NP assumption for polynomial-time value-oracle algorithms and a sub-exponential query bound for value-and-demand access.Source: §5 · p. 11
6. LEARNING CONTRACTS
Learning-contract research studies repeated contracting when agent types are unknown, and compares regret for general bounded and linear contracts. The results sharply separate the formats: general bounded contracts have essentially linear regret, while linear contracts admit sublinear regret.
Online Learning with Bandit Feedback
- The survey also covers online contract learning with bandit feedback and points to variants with restricted action spaces, added distributional conditions, or different feedback models.Other work proposes a deep neural network architecture for near-optimal contracts from samples.Source: §6 · p. 11
- The learning model has one principal repeatedly contracting with a single agent whose type is drawn independently each round from an unknown distribution.Rewards and costs are bounded in [0, 1], and the principal observes the outcome and reward after posting each contract.Source: §6 · p. 11
- The principal aims to minimize regret against the best single contract in hindsight, with policies allowed to randomize and depend on observed history.Because regret is additive, the model normalizes rewards and costs to [0, 1].Source: §6 · pp. 11–12
Separation: General vs. Linear Contracts
- General bounded contracts have essentially linear regret, while linear contracts admit sublinear regret, with near-tight bounds for both classes.For general bounded contracts, the upper bound is ˜O(√m · S^(1−1/(2m+1))) and the lower bound is Ω(S^(1−1/(m+2))); linear contracts have matching ˜O(S^(2/3)) and Ω(S^(2/3)) bounds.Source: §6 · p. 12
- For bounded contracts, the principal’s utility has only weak continuity, whereas linear-contract utility is right-continuous and loses at most ϵ utility when the optimal contract is overshot by ϵ.The geometry supports a cover-by-cones upper bound for general contracts, but the lower bound indicates no additional structure for more efficient learning.Source: §6 · p. 12
- The lower bound for general bounded contracts holds even for a fixed agent, but requires exponentially many actions in the number of outcomes.Whether additional structure such as MLRP circumvents it remains open; the bound can be avoided for instances satisfying FOSD and CDFP.Source: §6 · p. 12
7. LOOKING AHEAD
The survey identifies several partially explored directions in contract design, including typed contracts and links to adjacent frameworks. It also points to challenges from autonomous AI agents acting as principals and agents.
7. LOOKING AHEAD
- Typed contract design studies Bayesian settings with privately informed agents and calls for a unified treatment of mechanism and contract design.The cited work includes Guruganesh et al. (2021), Alon et al. (2021, 2023), and Castiglioni et al. (2025, 2023).Source: §7 · p. 12
- Partially explored directions include monitoring, information revelation, ambiguous contracts, sequential decisions, and classification, alongside connections to scoring rules and delegation.The survey cites work on each of these directions.Source: §7 · pp. 12–13
- Autonomous AI agents acting as principals and agents raise challenges involving dynamic action spaces, rationality, and commitment.The survey describes these as new challenges only beginning to be addressed.Source: §7 · p. 13