Ultra Efficient Contracts: Pushing the Boundaries of Tractable Contract Design
This work addresses the tractability boundary in contract design for economic settings, offering a novel solution that is not incremental but bridges previously separate regimes.
The paper tackles the optimal contract problem in combinatorial actions by introducing a polynomial-time algorithm for Ultra rewards, which bridges substitutes and complements regimes, and extends it to handle additive and symmetric cost functions.
We study the optimal contract problem in the \emph{combinatorial actions} framework of Dütting 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. Our main result is a polynomial-time algorithm for the optimal contract problem under \Ultra\ rewards, a class that strictly contains gross substitutes but is not confined to subadditive rewards, thereby bridging the substitutes and complements regimes. We further extend our results beyond additive costs, establishing a polynomial-time algorithm for \Ultra\ rewards and cost functions that are the sum of additive and symmetric functions. To the best of our knowledge, this is the first application of \Ultra\ functions in a prominent economic setting.