Abstract
This research investigates the design of optimal common contracts for a principal interacting with a set of heterogeneous agents. While personalized contracts are computationally straightforward, the requirement for a single common contract—often driven by fairness or legal constraints—introduces significant complexity. We prove that the general Multiple Agents Contract (MAC) problem is strongly NP-complete. To address this, we identify the Increasing Difference Property (IDP) as a structural condition that enables an efficient $O(n^2m)$ dynamic programming solution. Furthermore, we provide a logarithmic approximation for the continuous reward setting.
Introduction
The principal-agent framework is a cornerstone of economic theory, modeling how a principal can incentivize an agent to take actions that maximize the principal's utility despite conflicting interests. Traditionally, models assume the principal can tailor contracts to individual agents. However, in many practical scenarios, social norms or regulations necessitate a "common contract" applied uniformly to all agents. When agents possess varying skill levels or cost structures (heterogeneity), the principal faces a non-trivial optimization problem: how to set a single payment schedule that effectively motivates a diverse workforce.
Complexity Analysis
A central contribution of this work is the formal proof that finding an optimal common contract is computationally difficult. We demonstrate that the Multiple Agents Contract (MAC) problem is strongly NP-complete. This is achieved through a reduction from the Not-All-Equal 3-Satisfiability (NAE3SAT) problem. The reduction involves constructing specific "variable" and "clause" gadgets that map the satisfiability of a boolean formula to the existence of a high-utility contract for the principal.
The reduction relies on a carefully constructed cost table that defines how different agents (representing variables and clauses) respond to the principal's incentives based on their assigned roles in the boolean formula.
Algorithmic Solutions
To overcome the general NP-hardness, we identify a natural structural property called the Increasing Difference Property (IDP). IDP assumes that agents can be ordered such that more "efficient" agents have a growing cost advantage as the difficulty of the action increases. Under this assumption, the principal can optimally "sort" agents into different effort levels. We provide a dynamic programming algorithm that solves the MAC problem under IDP in $O(n^2m)$ time, where $n$ is the number of agents and $m$ is the number of possible actions.
Continuous Rewards and Approximations
The research also extends to the "Real Number Actions" setting, where rewards are continuous. This setting is shown to be even more challenging than the discrete case. We develop a payment function that guarantees an $O(\log n)$-approximation of the optimal payoff, providing a robust solution for large-scale systems where exact optimization is infeasible.
Conclusion
This study highlights the "computational cost of fairness." Moving from personalized to common contracts transforms a simple linear optimization into a complex combinatorial problem. By identifying the IDP and providing approximation algorithms for continuous settings, this work offers practical tools for designing equitable and efficient incentive structures in heterogeneous environments. Future work may explore stochastic outcomes or competitive environments with multiple principals.
Summary updated