# Optimal Common Contract with Heterogeneous Agents

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

## Key facts

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

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

- [On classification of strategic agents who can both game and improve](https://mlsanity.com/paper/2203.00124/) (2022)
- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Setting Fair Incentives to Maximize Improvement](https://mlsanity.com/paper/2203.00134/) (2022)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)

## Abstract (arXiv)

We consider the principal-agent problem with heterogeneous agents. Previous works assume that the principal signs independent incentive contracts with every agent to make them invest more efforts on the tasks. However, in many circumstances, these contracts need to be identical for the sake of fairness. We investigate the optimal common contract problem. To our knowledge, this is the first attempt to consider this natural and important generalization. We first show this problem is NP-complete. Then we provide a dynamic programming algorithm to compute the optimal contract in O(n2m) time, where n,m are the number of agents and actions, under the assumption that the agents' cost functions obey increasing difference property. At last, we generalize the setting such that each agent can choose to directly produce a reward in [0,1]. We provide an O(log n)-approximate algorithm for this generalization.