# Designing Menus of Contracts Efficiently: The Power of Randomization

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

## Key facts

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

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

- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [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)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2312.07929/) (2023)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Optimal Pricing for Data-Augmented AutoML Marketplaces](https://mlsanity.com/paper/2310.17843/) (2023)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)

## Abstract (arXiv)

We study hidden-action principal-agent problems in which a principal commits to an outcome-dependent payment scheme (called contract) so as to incentivize the agent to take a costly, unobservable action leading to favorable outcomes. In particular, we focus on Bayesian settings where the agent has private information. This is collectively encoded by the agent's type, which is unknown to the principal, but randomly drawn according to a finitely-supported, commonly-known probability distribution. In Bayesian principal-agent problems, the principal may be better off by committing to a menu of contracts specifying a contract for each agent's type, rather than committing to a single contract. This induces a two-stage process that resembles interactions studied in classical mechanism design: after the principal has committed to a menu, the agent first reports a type to the principal, and, then, the latter puts in place the contract in the menu that corresponds to the reported type. Thus, the principal's computational problem boils down to designing a menu of contracts that incentivizes the agent to report their true type and maximizes expected utility. Previous works showed that computing an optimal menu of contracts is APX-hard. Crucially, previous works focus on menus of deterministic contracts. Surprisingly, we show that, if one considers menus of randomized contracts defined as probability distributions over payment vectors, then an "almost-optimal" menu can be computed in polynomial time. Indeed, the problem of computing a principal-optimal menu of randomized contracts may not admit a maximum, but only a supremum. Nevertheless, we show how to design a polynomial-time algorithm that guarantees the principal with an expected utility arbitrarily close to the supremum. Besides this main result, we also close several gaps in the analysis of menus of deterministic contracts.