# Multi-Agent Contracts

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2022.

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

- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Deep Contract Design via Discontinuous Networks](https://mlsanity.com/paper/2307.02318/) (2023)
- [Delegated Classification](https://mlsanity.com/paper/2306.11475/) (2023)
- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [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)
- [Emergent Risk Awareness in Rational Agents under Resource Constraints](https://mlsanity.com/paper/2505.23436/) (2025)
- [The Backfiring Effect of Weak AI Safety Regulation](https://mlsanity.com/paper/2503.20848/) (2025)
- [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025)
- [Deep Incentive Design with Differentiable Equilibrium Blocks](https://mlsanity.com/paper/2603.07705/) (2026)
- [Steering No-Regret Agents in MFGs under Model Uncertainty](https://mlsanity.com/paper/2503.09309/) (2025)
- [Hypernetwork-based approach for optimal composition design in partially controlled multi-agent systems](https://mlsanity.com/paper/2502.12605/) (2025)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)
- [Microeconomic Foundations of Multi-Agent Learning](https://mlsanity.com/paper/2601.03451/) (2026)

## Abstract (arXiv)

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value oracles for submodular reward functions and value and demand oracles for XOS reward functions. It relies on an unconventional use of ``prices'' and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. As our second main result, we show that constant approximation is the best we can get for submodular reward functions, even with both value and demand oracles. For the larger class of subadditive reward functions, we establish an Omega(√n) impossibility for settings with n agents. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This rapid degradation presents a surprising departure from previous literature, e.g., on combinatorial auctions, where approximation guarantees tend to deteriorate more