We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal's utility), reward, and welfare. Our first result is a strong impossibility: For submodular reward functions, no randomized poly-time algorithm can approximate the optimal budget-feasible value within \textit{any finite factor}, even with demand-oracle access. This result rules out extending known constant-factor guarantees from either (i) unbudgeted settings with combinatorial actions or (ii) budgeted settings with binary actions, to their combination. The hardness is tight: It holds even when all but one agent have binary actions and the remaining agent has just one additional action. On the positive side, we show that gross substitutes rewards (a well-studied strict subclass of submodular functions) admit a deterministic poly-time $O(1)$-approximation, using only value queries. Our results thus draw the first sharp separation between budgeted and unbudgeted settings in combinatorial contracts, and identifies gross substitutes as a tractable frontier for budgeted combinatorial contracts. Finally, we present an FPTAS for additive rewards, demonstrating that arbitrary approximation is tractable under any budget. This constitutes the first FPTAS for the multi-agent combinatorial-actions setting, even in the absence of budget constraints.

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.

The problem of computing near-optimal contracts in combinatorial settings has recently attracted significant interest in the computer science community. Previous work has provided a rich body of structural and algorithmic insights into this problem. However, most of these results rely on the assumption that the principal has an unlimited budget for incentivizing agents, an assumption that is often unrealistic in practice. This motivates the study of the optimal contract problem under budget constraints.

We study the combinatorial contracting problem of Dütting et al. [13], 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 α 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 α, and that one can iterate through all of them efficiently in order to find the optimal contract.