When Contracts Get Complex: Information-Theoretic Barriers

In the combinatorial-action contract model (Dütting et al., FOCS'21) a principal delegates the execution of a complex project to an agent, who can choose any subset from a given set of actions. Each set of actions incurs a cost to the agent, given by a set function c, and induces an expected reward to the principal, given by a set function f . To incentivize the agent, the principal designs a contract that specifies the payment upon success, with the optimal contract being the one that maximizes the principal's utility.

It is known that with access to value queries no constant-approximation is possible for submodular f and additive c. A fundamental open problem is: does the problem become tractable with demand queries? We answer this question to the negative, by establishing that finding an optimal contract for submodular f and additive c requires exponentially many demand queries. We leverage the robustness of our techniques to extend and strengthen this result to different combinations of submodular/supermodular f and c; while allowing the principal to access f and c using arbitrary communication protocols.

Our results are driven by novel equal-revenue constructions when one of the functions is additive, immediately implying value query hardness. We then identify a new propertysparse demand -which allows us to strengthen these results to demand query hardness. Finally, by augmenting a perturbed version of these constructions with one additional action, thereby making both functions combinatorial, we establish exponential communication complexity.