CS Paper Radar

An Introduction to Contract Theory for Computer Scientists

Paul Duetting, Michal Feldman, Inbal Talgam-Cohen

cs.GT ·submitted 2026-10-12 19:44 UTC · v1
publishedsurvey

Abstract

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.

Journal ref
ACM SIGecom Exchanges, Vol. 24, No. 1, June 2026, Pages 31-46

Closest papers

Nearest neighbours by meaning across the whole index.

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

cs.GT ·2026-10-22 ·Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
benchmark similarity 0.71
Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

0.31

Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts

cs.LG ·2026-09-17 ·Rui Ai, David Simchi-Levi, Han Zhong
benchmarktheoryhot direction similarity 0.69
Abstract

We study repeated contract design when a principal observes outcomes but not the actions that generate them. The principal may use any bounded outcome-contingent payment vector, and the agent's best response can make expected profit discontinuous in those payments. For every fixed number $m\ge2$ of outcomes, the minimax regret over $T$ rounds is of order $T^{m/(m+1)}$, up to logarithmic factors. The upper bound allows arbitrary action spaces and agent heterogeneity, without smoothness or monotone-surplus assumptions. Its key is an effective-dimension reduction that the benchmark can be normalized even when fixed tie-breaking is not shift invariant, after which revealed preference yields a monotone response map in payment-difference coordinates. A learning policy built on a Lipschitz parametrization of this map attains the rate using only observed outcome categories. The lower-bound construction accounts for how incentive losses accumulate across outcome dimensions. It shows that each additional contractible outcome creates a precise and unavoidable increase in the worst-case cost of learning.

0.31

Anytime Contracts for AI Services

cs.GT cs.AIcs.LG ·2026-10-16 ·Boris Velasevic, Eden Saig, Eric Mazumdar
similarity 0.66
Abstract · 19 pages, 3 figures

AI services are prone to moral hazard, as model providers can silently route requests to cheaper, lower-quality models, and the inherent stochasticity of model outputs makes this degradation hard to detect. Contract theory addresses moral hazard by designing payment rules that reward high-quality outputs and prevent strategic overcharging. However, existing frameworks assume interactions of fixed duration, whereas AI services are typically consumed through subscriptions and pay-as-you-go APIs that users can terminate at any time based on observed performance. We show that this flexibility can break standard contracts, opening them up to abuse by either the providers or users. To address this, we extend contract theory to account for unknown exit rules. We formalize the problem as a Principal-Agent game, and show that budget-optimal contracts in this setting are proportional to anytime-valid hypothesis tests based on likelihood-ratio e-values. We give an efficient algorithm for computing anytime contracts and show how betting e-processes can be used to approximate them when the models are unknown. Finally, we evaluate our findings on synthetic data and data from deployed LLMs.

0.59

Strategic Disclosure of Action Space in Principal-Agent Contracts

cs.GT econ.TH ·2026-09-21 ·Xiaotie Deng, Ningyuan Li
theory similarity 0.64
Abstract · Full version of the manuscript accepted at WINE 2026. A one-page extended abstract will appear in the conference proceedings. A substantiall…

We study strategic disclosure of the action space in principal-agent contracting, where an agent selects a disclosed action set to shape the principal's perception of her capabilities before contract design. Unaware of the strategic disclosure, the principal designs a revenue-optimal contract as if the disclosed action set were complete and accurate. We consider two variants distinguished by cost verifiability. When costs are unverifiable, the agent can extract the entire first-best surplus, leaving the principal with zero revenue. When costs are verifiable, we characterize the agent's optimal disclosure strategy in binary-outcome settings and, more generally, when the principal is restricted to linear contracts, reducing the agent's problem to a two-variable convex optimization problem. We prove that the agent can secure utility of at least a $1/e$ fraction of the first-best surplus, which also yields a $1/e$ welfare guarantee under optimal disclosure. While the principal's revenue can be arbitrarily small compared to the first-best surplus, when the ratio of maximum to minimum expected reward among non-null base actions is at most $L$, we establish a revenue guarantee of $Θ(1/\log L)$ relative to the first-best surplus. We also compare utilities and welfare under strategic disclosure with their counterparts in the canonical model. Finally, we extend the agent's $1/e$ utility guarantee to general outcome spaces without restricting the principal to linear contracts. Our results show how strategic action-space disclosure changes the distribution of surplus while preserving a constant-factor welfare guarantee under the agent's optimal disclosure.

0.31

BROCADE: Broker-based Contract Design for the Multi-Agency Model

cs.GT ·2026-10-26 ·Yangguang Shi, Ron Lavi, Jie Zhang
benchmarktheory similarity 0.63
Abstract

We study welfare maximization in a contract model with $m$ principals who privately value a public project's success and $n$ agents whose costly effort is unobservable. Contracts induce truthful dominant strategies for principals and equilibrium effort by agents, maximizing the expected total value of eligible principals. We develop three tools: a broker that separates payments from principals and payments to agents, an extension of Myerson's Lemma characterizing dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. When the success probability is a strictly monotone XOS function of agents' actions, these tools yield three results. First, a deterministic DSIC contract achieves a constant approximation against a benchmark that qualifies every principal and maximizes success probability using budget $\sum_j v^j$, but may violate budget balance (BB). Second, against benchmarks with budgets at least the largest principal value, deterministic DSIC and BB contracts admit no finite approximation guarantee, even with two agents. Universally DSIC and universally BB randomized contracts have an $Ω(n)$ approximation lower bound, even for a fixed number of principals. Third, using one quarter of the optimal fixed-price revenue supported by at least two principals as the benchmark budget, we obtain a universally DSIC and universally BB randomized contract with an $O(\log m)$ approximation ratio independent of $n$.

0.11

Evaluating Rational Contracting in Natural Language

cs.AI cs.CLcs.GT ·2026-08-11 ·Bhavyesh Sajja, Max Kleiman-Weiner, Roger Zimmermann, Tan Zhi-Xuan
similarity 0.63
Abstract · 10 pages, 7 figures, 2 tables (Appendix: 40 pages, 8 figures, 10 tables)

The emergence of language-based AI agents promises to transform the scope of machine economic activity. Instead of just proposing bids or following hard-coded protocols, such agents can be used to negotiate and execute agreements in natural language. However, most evaluations of these abilities have focused on one-off exchanges or simple economic games, leaving open the rich space of time-extended, contingent, and incomplete contracts expressible in language; they also focus on raw profit, without measuring the qualities required for trustworthy contracting. We address this by formulating a rational framework for how agents should negotiate and perform natural language contracts in uncertain multi-step environments. Using this framework, we develop metrics and baselines for quantifying rational and cooperative play. We instantiate our framework in ContractSim, an evaluation suite where two players negotiate and execute a multi-turn supplier contract under environmental and inter-player uncertainty. We find that LLM-based agents agree on efficient contracts when environmental uncertainty is low, but under high uncertainty, often fail to negotiate satisfiable, efficient, or mutually beneficial contracts, underperforming even heuristic baselines. When executing contracts, LLM agents are also frequently uncooperative, violating contracts for extra profit even when they are easy to satisfy. These findings highlight room for improvement in the design of language agents that can negotiate and execute contracts both rationally and cooperatively.

0.40

Contracting for LLM Delegation: Moral Hazard in Technology and Effort Choice

cs.MA ·2026-08-18 ·Nanda Kishore Sreenivas, Kate Larson
similarity 0.62
Abstract

We extend the standard Principal-Agent framework to scenarios where the Agent selects from a suite of technologies, each characterized by a distinct cost-capability profile. This framework is increasingly critical in the era of Large Language Models (LLMs), where Agents choose both a model and an associated effort level (e.g., token budget). We model the relationship between output quality and effort as a concave, saturating function, which depends on the Agent's hidden two-dimensional action choice balancing technology selection and effort allocation. We derive the optimal linear contract for the Principal, demonstrating that the Agent's best response is characterized by a threshold reward share that triggers technology switching. Finally, we calibrate our model using open-weight LLM pairings across the MATH and MMLUPro benchmarks. We show that both Principal and Agent, when employing bandit algorithms to navigate this environment, converge to strategies that closely align with our theoretical equilibrium. These results suggest that simple linear contracts can effectively incentivize complex, technology-aware delegation in agentic workflows.

0.48

Transparency in Team Contracts

cs.GT econ.TH ·2026-11-05 ·Paul Dütting, Yingkai Li, Inbal Talgam-Cohen, Jinzhao Wu
similarity 0.62
Abstract

In contract design, the principal is often better informed about the project's chances of succeeding than the agents. To incentivize effort, the principal has two main tools: first, to design a contract, sharing part of the project's success among the agents; second, to design a (Bayesian) persuasion scheme, selectively sharing information with the agents. In this work we are interested in the optimal combination of both these tools. We tackle the joint problem through the prism of simplicity vs. optimality, and establish a stark dichotomy: The simple disclosure scheme of full transparency achieves a tight $4/3$-approximation to the optimal combination of information disclosure and team contract, when the team's production function is submodular. In contrast, full transparency can be arbitrarily far from optimal when production is supermodular. The techniques that we develop to bound the gap for submodular functions, also yield a new deterministic polynomial-time approximation algorithm for pure multi-agent contract design, with a significantly improved approximation ratio of $2.311$, and thus a $3.081$-approximation algorithm for the joint information and contracting problem.

0.40