Ultra Efficient Contracts: Pushing the Boundaries of Tractable Contract Design

Understand

We study the optimal contract problem in the \emph{combinatorial actions} framework of D\"utting et al.~[FOCS'21], where a principal delegates a project to an agent who chooses a subset of hidden, costly actions, and the resulting reward is given by a monotone set function over the actions.

• The principal offers a contract that specifies the fraction of the reward the agent receives, and the goal is to compute a contract that maximizes the principal's expected utility.
• Prior work established polynomial-time algorithms for \emph{gross substitutes} rewards, while showing NP-hardness for general submodular rewards; subsequent work extended tractability to \emph{supermodular} rewards, demonstrating that tractable cases exist in both the substitutes and complements regimes.
• This left open the precise boundary of tractability for the optimal contract problem.