# Contract Design Under Approximate Best Responses

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2025.

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

- [Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts](https://mlsanity.com/paper/2609.20353/) (2026)

## Abstract (arXiv)

Principal-agent problems model scenarios where a principal incentivizes an agent to take costly, unobservable actions through the provision of payments. Such problems are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal's payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This positive result is perhaps surprising, since, in Stackelberg games, computing an optimal commitment under approximate best responses is computationally intractable. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal has no prior knowledge about the environment.