On Supermodular Contracts and Dense Subgraphs

We study the combinatorial contract design problem, introduced and studied by Dütting et al. (2021Dütting et al. ( , 2022)), in both the single and multi-agent settings. Prior work has examined the problem when the principal's utility function is submodular in the actions chosen by the agent(s). We complement this emerging literature with an examination of the problem when the principal's utility is supermodular. Our results apply to the unconstrained contract design problem in the binary outcome case (i.e., the principal's task succeeds or fails), and to the linear contract design problem more generally.

In the single-agent setting, we obtain a strongly polynomial time algorithm for the optimal contract. This stands in contrast to the NP-hardness of the problem with submodular principal utility due to Dütting et al. (2021). This result has two technical components, the first of which applies beyond supermodular or submodular utilities. First, we describe a simple divide-andconquer algorithm which enumerates all the "breakpoints" of the principal's utility function in strongly polynomial time. This result strengthens and simplifies analogous enumeration algorithms from Dütting et al. (2021), and applies to any nondecreasing valuation function for the principal. Second, we show that supermodular valuations lead to a polynomial number of breakpoints, analogous to a similar result by Dütting et al. (2021) for gross substitutes valuations.

In the multi-agent setting, we obtain a mixed bag of positive and negative results. First, we show that it is NP-hard to obtain any finite multiplicative approximation, or an additive FPTAS. This stands in contrast to the submodular case, where efficient computation of approximately optimal contracts was shown by Dütting et al. (2022). Second, we derive an additive PTAS for the problem in the instructive special case of graph-based supermodular valuations, and equal costs. En-route to this result, we discover an intimate connection between the multi-agent contract problem and the notorious k-densest subgraph problem. We build on and combine techniques from the literature on dense subgraph problems to obtain our additive PTAS. We leave open the intriguing, and seemingly quite challenging, question of whether an additive PTAS exists more generally for multi-agent supermodular contracts.