  We study the combinatorial contract design problem, introduced and studied by
Dutting et. al. (2021, 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.
  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 Dutting et. al. (2021).
  This result has two technical components, the first of which applies beyond
supermodular or submodular utilities.
  This result strengthens and simplifies analogous enumeration algorithms from
Dutting 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 Dutting 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 Dutting 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.
