  We study the combinatorial contracting problem of D\"utting et al. [FOCS
'21], in which a principal seeks to incentivize an agent to take a set of
costly actions. In their model, there is a binary outcome (the agent can
succeed or fail), and the success probability and the costs depend on the set
of actions taken. The optimal contract is linear, paying the agent an $\alpha$
fraction of the reward. For gross substitutes (GS) rewards and additive costs,
they give a poly-time algorithm for finding the optimal contract. They use the
properties of GS functions to argue that there are poly-many "critical values"
of $\alpha$, and that one can iterate through all of them efficiently in order
to find the optimal contract.
  In this work we study to which extent GS rewards and additive costs
constitute a tractability frontier for combinatorial contracts. We present an
algorithm that for any rewards and costs, enumerates all critical values, with
poly-many demand queries (in the number of critical values). This implies the
tractability of the optimal contract for any setting with poly-many critical
values and efficient demand oracle. A direct corollary is a poly-time algorithm
for the optimal contract in settings with supermodular rewards and submodular
costs. We also study a natural class of matching-based instances with XOS
rewards and additive costs. While the demand problem for this setting is
tractable, we show that it admits an exponential number of critical values. On
the positive side, we present (pseudo-) polynomial-time algorithms for two
natural special cases of this setting. Our work unveils a profound connection
to sensitivity analysis, and designates matching-based instances as a crucial
focal point for gaining a deeper understanding of combinatorial contract
settings.

Computer Science and Game Theory