# The Pseudo-Dimension of Contracts

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 24 Jan 2025.

## Builds on (most cited first, 23 of 23)

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Bayesian Agency: Linear versus Tractable Contracts](https://mlsanity.com/paper/2106.00319/) (2021)
- [Combinatorial Contracts](https://mlsanity.com/paper/2109.14260/) (2021)
- [Designing Menus of Contracts Efficiently: The Power of Randomization](https://mlsanity.com/paper/2202.10966/) (2022)
- [Algorithmic Contract Theory: A Survey](https://mlsanity.com/paper/2412.16384/) (2024)
- [Automated Design of Affine Maximizer Mechanisms in Dynamic Settings](https://mlsanity.com/paper/2402.08129/) (2024)
- [Multi-Agent Contract Design: How to Commission Multiple Agents with Individual Outcome](https://mlsanity.com/paper/2301.13654/) (2023)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [The Pseudo-Dimension of Near-Optimal Auctions](https://mlsanity.com/paper/1506.03684/) (2015)
- [The Power of Menus in Contract Design](https://mlsanity.com/paper/2306.12667/) (2023)
- [On Supermodular Contracts and Dense Subgraphs](https://mlsanity.com/paper/2308.07473/) (2023)
- [Machine Learning-Powered Combinatorial Clock Auction](https://mlsanity.com/paper/2308.10226/) (2023)
- [On the (In)approximability of Combinatorial Contracts](https://mlsanity.com/paper/2311.18425/) (2023)
- [Multi-Agent Contract Design beyond Binary Actions](https://mlsanity.com/paper/2402.13824/) (2024)
- [Combinatorial Contracts Beyond Gross Substitutes](https://mlsanity.com/paper/2309.10766/) (2023)
- [A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design](https://mlsanity.com/paper/2404.03476/) (2024)
- [Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All](https://mlsanity.com/paper/2411.09355/) (2024)

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

- [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)
- [Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts](https://mlsanity.com/paper/2609.20353/) (2026)

## Abstract (arXiv)

Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is drawn from an unknown distribution, and formalize an offline learning framework for learning near-optimal contracts from sample agent types. A central tool in our analysis is the notion of pseudo-dimension from statistical learning theory. Beyond its role in establishing upper bounds on the sample complexity, pseudo-dimension measures the intrinsic complexity of a class of contracts, offering a new perspective on the tradeoffs between simplicity and optimality in contract design. Our main results provide essentially optimal tradeoffs between pseudo-dimension and representation error (defined as the loss in principal's utility) with respect to linear and bounded contracts. Using these tradeoffs, we derive sample- and time-efficient learning algorithms, and demonstrate their near-optimality by providing almost matching lower bounds on the sample complexity. Conversely, for unbounded contracts, we prove an impossibility result showing that no learning algorithm exists. Finally, we extend our techniques in three important ways. First, we provide refined pseudo-dimension and sample complexity guarantees for the combinatorial actions model, revealing a novel connection between the number of critical values and sample complexity. Second, we extend our results to menus of contracts, showing that their pseudo-dimension scales linearly with the menu size. Third, we adapt our algorithms to the online learning setting, where we show that, a polynomial number of type samples suffice to learn near-optimal bounded contracts. Combined with prior work, this establishes a formal separation between expert advice and bandit feedback for this setting.