One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Feldman, Michal; Gal-Tzur, Yoav; Ponitka, Tomasz; Schlesinger, Maya

doi:10.4230/LIPIcs.ITCS.2026.58

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Michal Feldman

Tel Aviv University, Israel
Microsoft ILDC, Herzliya, Israel Yoav Gal-Tzur

Tel Aviv University, Israel Tomasz Ponitka

Tel Aviv University, Israel Maya Schlesinger

Tel Aviv University, Israel

Abstract

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 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.

Keywords and phrases:

Combinatorial Contracts, Algorithmic Contract Design, Budget-Feasible Contracts

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algorithmic game theory

Related Version:

Full Version: https://arxiv.org/abs/2511.20110

Funding:

This project has been partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 program (grant agreement No. 866132), by the European Union’s Horizon Europe Program (grant agreement No. 101170373), by an Amazon Research Award, by the Israel Science Foundation Breakthrough Program (grant No. 2600/24), and by a grant from TAU Center for AI and Data Science (TAD), and by the NSF-BSF (grant number 2020788).

DOI:

10.4230/LIPIcs.ITCS.2026.58

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Contract design is a central area in microeconomics that studies how to incentivize strategic agents to exert costly effort in their tasks, e.g., [46, 40, 53, 48, 47]. The significance of this field to modern economics was highlighted by the 2016 Nobel Prize awarded to Hart and Hölmstrom for their contributions to contract theory [54]. In recent years, the rapid emergence of computerized markets for services has fueled increasing interest in the algorithmic aspects of contract design, e.g.,[33, 26, 5, 19]; see [32, 37] for recent surveys.

In this work, we focus on the algorithmic challenges of incentivizing teamwork, e.g., [47, 5, 27]. Consider the following illustrative example of a startup hiring a team of engineers. The startup seeks to build a successful product, whose probability of success depends both on the team’s composition (for instance, the degree to which the engineers’ expertise overlaps or complements each other), and on each individual’s effort (for example, whether every engineer carefully reviews code). To encourage engineers to exert costly effort, the startup offers them equity: each employee receives a fraction of ownership in the company.

Scenarios of this type are captured by the multi-agent combinatorial-actions model for contract design [27, 28]. In this model a principal (she, the startup founder) delegates a binary-outcome project to a pool of $n$ potential agents (engineers). The project yields the principal a reward of $1$ upon success and $0$ if it fails. Each agent $i\in[n]$ has a set $T_{i}$ of available actions, and may choose any subset $S_{i}\subseteq T_{i}$ of them. Each action $j\in T_{i}$ has a non-negative cost $c_{j}$ , and the agent $i$ pays the total cost of their chosen actions, $\sum_{j\in S_{i}}c_{j}$ . A set function $f$ maps every profile of actions $S=S_{1}\sqcup\ldots\sqcup S_{n}$ to the project’s success probability $f(S)$ . Since the reward is normalized to $1$ , $f(S)$ also denotes the expected reward. To incentivize effort, the principal offers each agent a linear contract $\alpha_{i}\in[0,1]$ , denoting the fraction of the reward that goes to agent $i$ if the project succeeds. So agent $i$ ’s utility, under action profile $S$ , is $\alpha_{i}f(S)-\sum_{j\in S_{i}}c_{j}$ . Every contract $\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{n})$ induces a game among the agents. An action profile $S$ is a Nash equilibrium of the game if, given the contract offered, no agent can increase his utility by deviating. In this case, we say that the contract incentivizes action profile $S$ .

The principal’s objective in [28] is to incentivize an action profile $S$ maximizing her profit, defined as her expected reward minus the total expected payments to the agents, i.e., $f(S)\cdot(1-\sum_{i\in[n]}\alpha_{i})$ . They present an efficient algorithm that, for submodular $f$ , attains a constant-factor approximation to the optimal profit using demand queries to $f$ (see Section 2 for definitions).

However, practical applications may introduce additional objectives and constraints. Principals may pursue objectives that go beyond profit maximization; for example, maximizing the probability of success $f(S)$ , or maximizing total welfare, $f(S)-\sum_{i\in[n]}\sum_{j\in S_{i}}c_{j}$ . At the same time, they often face constraints, such as budget constraints (e.g., a given portion of the company’s equity must be allocated to investors).

Polynomial-time approximation algorithms for multi-agent contract settings, under key objectives, including reward and welfare, and budget constraints, have been obtained by [38, 1], but only within the binary-actions model, where each agent either exerts effort or shirks. In this work, we extend the multi-agent combinatorial-actions model of [28] to incorporate budget constraints and to accommodate a broader range of objectives.

1.1 Our Results

We study the design of near-optimal contracts in the multi-agent combinatorial-actions model of [28], under budget constraints, for a broad class of objective functions. In this setting, each agent $i\in[n]$ can select any subset from a given action set, and the principal is restricted by a budget constraint $B$ , i.e., agents may receive at most a $B$ -fraction of the reward. The case of $B=1$ corresponds to the unbudgeted setting. The class of objectives we consider – termed BEST (BEyond STandard) by [38] – includes reward, welfare, profit, or any convex combination thereof (see Definition 2.4). In what follows we present our main results (also illustrated in Figure 1).

Figure 1: The three vertices of the triangle represent the dimensions along which the settings we consider differ: (i) the structure of

f

(general submodular vs. gross substitutes), (ii) the presence of budget constraints, and (iii) the type of the agents’ action space (binary vs. combinatorial). Any pair of properties admits a constant-factor approximation, as indicated along each edge of the triangle. The figure illustrates that the impossibility arises only from the combination of all three properties: the interior inapproximability region corresponds to submodular

f

with budgets and combinatorial actions simultaneously.

(\star)

All results shown hold for all BEST objectives, except for the

O(1)

-approximation for the multi-agent combinatorial-actions setting without budget constraints of [28], which holds only for profit maximization.

Inapproximability for Submodular Instances

Our first main result establishes a strong impossibility: when the reward function $f$ is submodular, there is no efficient approximation algorithm to any BEST objective. This impossibility is information theoretic, and does not rely on any computational conjectures.

Theorem 1 (Inapproximability for Submodular Instances; Theorem 3.1).

For the class of instances with submodular $f$ , any BEST objective $\varphi$ (including profit, reward, and welfare), any budget $B\in(0,1)$ , and any approximation guarantee $K:\mathbb{N}\to[1,\infty)$ , any randomized algorithm can achieve a $K(n)$ -approximation with respect to $\varphi$ under budget $B$ only with exponentially small probability in $n$ , assuming it makes at most polynomially many value and demand queries to $f$ .

This impossibility is particularly striking in light of known positive results for multi-agent settings with submodular $f$ : (i) constant-factor approximation to profit for combinatorial actions without budget constraints [28], and (ii) constant-factor approximation to any BEST objective in the binary-actions setting with budget constraints [1, 38]. Our result shows that combinatorial actions and budget constraints together rule out any approximation. Moreover, our hardness construction constitutes the minimal extension needed to obtain such an impossibility: All agents have binary actions, except for one agent which has one extra action.¹¹1In fact, we do not use the combinatorial nature of the agent’s actions, just that there is more than one.

Beyond establishing hardness of approximation, this result provides two important separations. First, between binary and combinatorial actions: Under budget constraints, the optimal-contract problem admits constant-factor approximation guarantees for binary actions but becomes inapproximable once agents have combinatorial actions. Second, between budgeted and unbudgeted settings: For combinatorial actions, profit maximization admits a constant-factor approximation without budgets, yet becomes inapproximable with budgets.

Constant-Factor Approximation for Gross Substitutes Instances

On the positive side, our second main result shows that efficient constant-factor approximations are possible when $f$ lies in the class of gross substitutes (GS), an important and well-studied subclass of submodular functions [49, 41, 51].

Theorem 2 (Constant-Factor Approximation for Gross Substitutes Instances; Corollary 4.2).

For the class of instances with gross substitutes $f$ and any BEST objective $\varphi$ (including profit, reward, and welfare), there exists a deterministic polynomial-time algorithm that achieves an $O(1)$ -approximation to $\varphi$ under any budget $B\in[0,1]$ . This algorithm requires only value oracle access to $f$ and $\varphi$ .

Theorems 1 and 2 together establish a separation between approximation guarantees under gross substitutes and general submodular functions. Interestingly, a parallel (yet not directly related) separation is known for the problem of computing the exact optimal contract in the single-agent combinatorial-actions setting: this problem admits a poly-time algorithm for GS rewards, whereas it is NP-hard for submodular rewards [26].²²2Whether a separation between GS and submodular rewards also appears in the multi-agent binary-actions setting remains an open problem: While constant-factor approximations are known for all submodular $f$ [27], it remains unknown whether better approximation (e.g., PTAS/FPTAS) can be achieved for GS. We note that computing the exact optimal contract is hard even for additive $f$ .

Finally, we highlight two other aspects of tightness. Our inapproximability result applies even when the algorithm has access to both value and demand oracles, while our positive approximation guarantee relies only on value oracle access.³³3This follows from the fact that when $f$ is GS, a demand query can be computed with poly-many value queries. Moreover, our hardness result applies to any randomized algorithm, whereas our proof for gross substitutes $f$ uses a deterministic algorithm.

Discussion: A Three-Way Barrier to Approximation

The multi-agent settings considered in this work differ along three dimensions: (i) the structure of $f$ (general submodular vs. gross substitutes), (ii) the presence of budget constraints, and (iii) the richness of the agents’ action space (binary vs. combinatorial). Combined with previous literature, our results show that the inapproximability arises only from the combination of all three properties, whereas any pair admits a constant-factor approximation. This is illustrated in Figure 1.

FPTAS for Special Cases

We give an FPTAS for two special cases of interest: instances with additive $f$ and instances with a single agent.

Theorem 3 (FPTAS for Additive Instances; Theorem 5.1).

For any budget $B\in[0,1]$ , each of the objectives profit, reward, and welfare admits a deterministic FPTAS with value queries, when $f$ is additive.

This result establishes the first FPTAS for the multi-agent combinatorial-actions model, even without budgets. It generalizes the FPTAS of [27, 38] for the multi-agent binary-actions model, where the latter also considers budgets. We note that, whereas our previous results apply to all BEST objectives, Theorem 3 applies only to profit, reward, and welfare.

We also generalize the FPTAS of [28] for maximizing profit in the single-agent setting with combinatorial actions to the budgeted setting.⁴⁴4Maximizing welfare and reward can be achieved by paying the agent the entire budget upon success. The proof is deferred to the full version.

Theorem 4 (FPTAS for Single-Agent Instances).

In the single-agent setting, there exists an FPTAS for maximizing the principal’s profit under any budget $B\in[0,1]$ , when $f$ is monotone. This algorithm requires access to a demand oracle to $f$ .

1.2 Our Techniques

Inapproximability for Submodular Instances

A key property in the binary-actions setting with submodular $f$ is the best-response monotonicity: given a contract and a Nash equilibrium $S$ , any agent in $S$ continues to find effort a best response, even if a subset of the remaining agents in $S$ shirk. This property is central to achieving constant-factor approximations in the binary-actions setting, both with and without budget constraints [27, 1, 38]. In contrast, best-response monotonicity fails in the combinatorial-actions setting with submodular $f$ : under a fixed contract and an equilibrium, if some agents reduce their action sets, the best response of an agent $i$ may also be to reduce his; see, e.g., [28, Example 1.1]. We identify non-monotonicity of the best response as a core aspect of the complexity of the combinatorial-actions setting and our proof of Theorem 1 leverages a carefully engineered violation of this property.

Our construction consists of $n-1$ binary-action (work or shirk) agents and one special agent with two non-shirking actions: a good action $\mathcal{G}$ and a bad action $\mathcal{B}$ . The reward function is at least ${1}/{2}$ when the special agent takes $\mathcal{G}$ , and infinitesimally small otherwise. Incentivizing the special agent to take $\mathcal{G}$ alone, however, would necessarily violate the budget constraint. By carefully constructing the reward function $f$ , we ensure that there exists a budget-feasible contract that incentivizes the special agent to take $\mathcal{G}$ , but only if it simultaneously incentivizes a unique subset $A^{\prime}$ of exactly half of the remaining agents to exert effort. Since $\mathcal{G}$ can be incentivized only in combination with other agents, this constitutes a violation of best-response monotonicity. The “good” equilibrium – $A^{\prime}$ together with $\mathcal{G}$ – yields a profit of at least $(1-B)\cdot({1}/{2})$ , while any other budget-feasible contract fails to incentivize the action $\mathcal{G}$ and thus achieves only an infinitesimally small reward. Therefore, an algorithm must incentivize the “good” equilibrium to achieve any desirable approximation. Yet the number of candidate subsets $A^{\prime}$ is exponential, and we prove that no efficient method can identify $A^{\prime}$ using poly-many value or demand queries, establishing our inapproximability result.

Crucially, this construction breaks down for profit maximization in the unbudgeted setting ( $B=1$ ), where [28] provide an approximation algorithm. Indeed, when $B=1$ , the “good” equilibrium in our construction yields a profit of $(1-B)\cdot({1}/{2})=0$ , nullifying the argument.

Constant-Factor Approximation for Gross Substitutes Instances

The first step toward establishing our positive result is proving that when $f$ is gross substitutes, best-response monotonicity holds even when agents have combinatorial actions. The key idea in the proof of this observation is to connect agents’ best responses with demand bundles (see Section 2 for formal definitions). More precisely, we observe that agent $i$ ’s best response for a given profile of actions of the other agents is a demand bundle with respect to a carefully chosen price vector. We then show that when the set of actions taken by the other agents is reduced to any subset, the corresponding price vector increases coordinate-wise. Therefore, by the gross-substitutes property, agent $i$ is incentivized to take a (weak) superset of the original actions, establishing best-response monotonicity.

We find that best-response monotonicity, combined with tools from [28], yields an up-to-a-constant-factor equivalence between any two BEST objectives under any two budgets, paralleling the result of [38] for the binary-actions case. This equivalence, together with the $O(1)$ -approximation for profit from [28], implies a constant-factor approximation for any BEST objective under any budget.

1.3 Related Work

Combinatorial Contracts

A combinatorial model for contracting agents with binary actions was introduced by [5, 8], where the principal selects a subset of agents to incentivize, and the reward function $f$ is Boolean. This foundational model was later extended to allow mixed strategies [6], and subsequent work studied free-riding in this setting [7].

[27] generalized this framework by considering richer reward functions drawn from the complements-free hierarchy [50], showing that for XOS functions, constant-factor approximations are achievable using demand and value queries. In subsequent work, the same authors extended this to a multi-action setting [28], where agents choose arbitrary subsets of actions, and demonstrated that for submodular $f$ , poly-many demand queries suffice for approximation. [2] considered a multi-project setting where each project corresponds to a binary-action problem, and showed constant-factor approximations for XOS valuations. [16] examined project allocation under fairness constraints, proving inapproximability of envy-freeness in the general case and tractability in constant-size markets.

In the single-agent variant, [26] introduced a model where the agent selects subsets of $n$ costly actions, and the principal’s reward is given by a set function $f$ . They showed tractability for gross-substitutes functions using value queries. Follow-up works [22, 30, 34, 29, 39] further refined the complexity landscape in this combinatorial-action setting. Another flavor of the single agent setting, studied in [35], considers a scenario where the agent takes actions sequentially, rather than simultaneously, observing intermediate outcomes. They provide algorithms and hardness results for independent and correlated actions.

The recent work of [36] relaxes the hidden-action assumption by introducing a combinatorial inspection model, where the principal can pay to verify whether the agent’s chosen action belongs to a given set, and the inspection cost is combinatorial.

Linear Contracts

Linear contracts are those in which the principal pays each agent a fixed fraction of the reward. The robustness of linear contracts was first established by [14], who proved that linear contracts are max-min optimal when the principal is unaware of the agent’s full action set. This result was later generalized to randomized actions and contracts by [52]. Robustness was also established in a different model of uncertainty by [33], who additionally provided approximation guarantees for linear contracts relative to the optimal ones. Another desirable trait of linear contracts is ambiguity-proofness. That is, unlike general contracts, the principal cannot benefit from introducing ambiguity into linear contracts [31, 25].

Contracts under Budget Constraints

There has been growing interest in the study of budgets in algorithmic contract design. [44] studied the budgeted multi-agent setting where each agent performs an independent task with an observable (binary) outcome. [23] studied a setting where the agent has a budget constraint and show how to convert algorithms for the agent’s utility maximization problem to an approximation algorithm with multiplicative and additive guarantees.

Closer to our setting, [38] and [1] introduced budget constraints into the binary-action model of [27]. [38] introduced the notion of BEST objectives and showed that, via a downsizing lemma, any two BEST objectives and any two budgets are equivalent up to a constant factor. As a result, their work also yields constant-factor approximations for XOS and submodular objectives via demand and value queries, respectively. [1] focused on social welfare maximization and studied its divergence from the principal’s profit. They have also given constant factor approximation algorithm for the social welfare when the budget $0\leq B\leq 2-\Theta(1)$ .

Other Contractual Models

Non-combinatorial multi-agent settings with agent externalities are studied in [55, 56, 11]. A complexity measure for the implementation of multi-agent contracts was proposed by [9]. More recently, [13, 19] have studied multi-agent contracts beyond binary outcomes. Contracts where agents have private types are studied in [4, 3, 15, 17, 43, 42, 18]. Several recent works explore the intersection of contracts and learning [57, 21, 45, 10, 20, 24].

2 Model and Preliminaries

In this section we present the multi-agent combinatorial-actions model of [28], the family of BEST (BEyond STandard) objectives of [38].

2.1 The Multi-Agent Combinatorial-Actions Setting

We consider a contractual setting involving a single principal and a set $A$ of $n$ agents. The principal is the owner of a project, which can either succeed or fail. Upon success, the project yields a reward of $1$ for the principal, and $0$ otherwise. The success probability of the project is determined by the (costly) actions that the agents perform, as specified below. The principal does not observe these actions, only the outcome. In order to incentivize the agents, she offers each $i\in A$ a linear contract $\alpha_{i}\in[0,1]$ that specifies their payment upon success, while the payment upon failure is always $0$ .⁵⁵5One can also view this model as a multiple-outcome project, where the principal only observes the reward and is restricted to using only linear contracts. As we formally establish in the full version of the paper, for all objectives considered in this paper, it is without loss of generality to restrict attention to linear contracts.

Each agent $i\in A$ has a set of actions $T_{i}$ from which they may choose any subset. In particular, $T_{i}=\{j\}$ corresponds to the binary-actions case [27, 38], as the agent may choose either $j$ or $\emptyset$ . We assume that any two agents have disjoint sets of actions, i.e., $T_{i}\cap T_{i^{\prime}}=\emptyset$ for any $i\neq i^{\prime}$ . Each action $j\in T_{i}$ is associated with a non-negative cost $c_{j}\geq 0$ , and the cost of a set of actions is additive, i.e., $c(S_{i})=\sum_{j\in S_{i}}c_{j}$ for any $S_{i}\subseteq T_{i}$ . In particular, $c(\emptyset)=0$ . The disjoint union of all possible actions is denoted by $T=\bigsqcup_{i\in A}T_{i}$ . Given a profile of actions $S\subseteq T$ , we denote by $S_{i}$ the actions in $S$ taken by agent $i$ , i.e., $S_{i}=S\cap T_{i}$ . Similarly, we use $S_{-i}=\bigsqcup_{i^{\prime}\in A\setminus\{i\}}S_{i^{\prime}}$ to denote the actions taken by all agents except for agent $i$ , in the profile of actions $S$ .

As mentioned, we consider a binary-outcome project that yields a reward of 1 to the principal upon success and 0 otherwise. At the heart of the model is a monotone combinatorial set function $f:2^{T}\to[0,1]$ , which maps every profile of actions, $S=\bigsqcup_{i\in A}S_{i}$ , chosen by the agents to the project’s success probability. Since the principal’s reward upon success is normalized to $1$ , $f(S)$ also represents the principal’s expected reward. We assume that $f(\emptyset)=0$ .

A problem instance is a tuple $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ . Here, $A$ is the set of agents, $T_{i}$ denotes the set of available actions for each agent $i\in A$ , $f$ is the reward function, and $c=\{c_{j}\}_{j\in T}$ represents the costs associated with each action. Recall that the principal offers a (linear) contract $\boldsymbol{\alpha}\in[0,1]^{A}$ , where $\alpha_{i}$ is the transfer from the principal to agent $i\in A$ , if the project succeeds.

Utilities and Equilibria.

For a given contract $\boldsymbol{\alpha}$ and a profile of actions $S=(S_{1},\dots,S_{n})$ , agent $i$ ’s expected utility is given by $\alpha_{i}\cdot f(S_{i}\sqcup S_{-i})-c(S_{i})$ , i.e., by the expected payment minus cost. We say that a contract $\boldsymbol{\alpha}$ incentivizes the profile $S$ if $S$ forms a Nash equilibrium (NE) under $\boldsymbol{\alpha}$ . Namely, for every agent $i\in A$ and every alternative set of actions $S^{\prime}_{i}\subseteq T_{i}$ , the following holds:

\alpha_{i}\cdot f(S_{i}\sqcup S_{-i})-c(S_{i})\geq\alpha_{i}\cdot f(S^{\prime}% _{i}\sqcup S_{-i})-c(S^{\prime}_{i}).

It was shown in [28] that every contract $\boldsymbol{\alpha}$ incentivizes at least one pure Nash equilibrium. A contract $\boldsymbol{\alpha}$ may incentivize multiple equilibria, and we denote this collection by $\mathsf{NE}(\boldsymbol{\alpha})$ .

Given a contract $\boldsymbol{\alpha}$ and an equilibrium $S\in\mathsf{NE}(\boldsymbol{\alpha})$ , the principal’s utility, or profit, is defined to be the expected reward minus payment, i.e.,

u_{P}(\boldsymbol{\alpha},S)=\left(1-\sum_{i\in A}\alpha_{i}\right)f(S).

Maximizing Profit Under Budget Constraints.

Given a budget $B$ , we call a contract $\boldsymbol{\alpha}$ budget-feasible if $\sum_{i\in A}\alpha_{i}\leq B$ . For convenience, we denote the set of all pairs of budget-feasible contracts and incentivized equilibria⁶⁶6A contract may incentivize multiple equilibria, in which case it will appear in $\mathcal{C}(B)$ more than once. by $\mathcal{C}(B)$ , namely,

\mathcal{C}(B)=\{(\boldsymbol{\alpha},S)\mid\sum_{i\in A}\alpha_{i}\leq B\text% { and }S\in\mathsf{NE}(\boldsymbol{\alpha})\}.

The standard goal of contract design is to maximize the profit, $u_{P}(\boldsymbol{\alpha},S)$ , which we use to illustrate the budgeted contract design problem: Given a budget $B$ we seek a contract and an equilibrium which approximately maximize the profit., i.e., $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ such that $\gamma\cdot u_{P}(\boldsymbol{\alpha},S)\geq\max_{(\boldsymbol{\alpha}^{\prime% },S^{\prime})\in\mathcal{C}(B)}u_{P}(\boldsymbol{\alpha}^{\prime},S^{\prime})$ , for some constant $\gamma\geq 1$ . In this work, we also consider additional important objectives, beyond profit maximization, which we elaborate on below.

In light of the observation made in [38, Proposition 3.13], we cannot guarantee to find a contract $\boldsymbol{\alpha}$ for which every incentivized equilibrium $S\in\mathsf{NE}(\boldsymbol{\alpha})$ yields a $\gamma$ -approximation to the optimal profit, so we must settle for a contract $\boldsymbol{\alpha}$ for which some incentivized equilibrium yields a $\gamma$ -approximation. Therefore, our algorithms output a contract along with an equilibrium which provide the desired guarantees.

Subset Stability and the Doubling Lemma.

The notion of subset stability and the doubling lemma play a crucial role in the analysis of the algorithm of [28], which computes a near-optimal contract with respect to profit without budget constraints. Subset stability is a relaxation of the Nash equilibrium condition: A profile of actions $S=\bigsqcup_{i\in A}S_{i}$ is subset-stable with respect to a contract $\boldsymbol{\alpha}$ if no agent $i\in A$ strictly benefits from deviating to a subset of $S_{i}$ .

Definition 2.1 (Subset Stability, Definition 3.2 of [28]).

A set of actions $S$ is subset-stable with respect to contract $\boldsymbol{\alpha}$ , if for every agent $i$ , every subset of his actions $S^{\prime}_{i}\subseteq S_{i}$ satisfies

\alpha_{i}\cdot f(S_{i}\sqcup S_{-i})-c(S_{i})\geq\alpha_{i}\cdot f(S^{\prime}% _{i}\sqcup S_{-i})-c(S^{\prime}_{i}).

The doubling lemma shows how a subset-stable profile $S$ with respect to a contract $\boldsymbol{\alpha}$ can be used to incentivize a Nash equilibrium that guarantees at least a half of the expected reward.

Lemma 2.2 (Doubling Lemma, Lemma 3.3 of [28]).

Let $f$ be a submodular function and let $\varepsilon>0$ . If $S$ is a subset-stable set of actions with respect to a contract $\boldsymbol{\alpha}$ , then any equilibrium $S^{\prime}$ with respect to the contract $2\boldsymbol{\alpha}+\boldsymbol{\varepsilon}$ satisfies $f(S^{\prime})\geq(1/2)\cdot f(S)$ , where $\boldsymbol{\varepsilon}=(\varepsilon,\dots,\varepsilon)$ .

Restricted Contracts.

For any contract $\boldsymbol{\alpha}\in\mathbb{R}^{n}_{+}$ and any set of agents $G\subseteq A$ , we denote by $\boldsymbol{\alpha}|_{G}$ the contract obtained by restricting payments to the agents in $G$ . Namely, we let

\boldsymbol{\alpha}|_{G}=\begin{cases}\alpha_{i}&\text{if }i\in G,\\ 0&\text{otherwise}.\end{cases}

When $G=\{i\}$ is a singleton, we often omit the brackets and write $\boldsymbol{\alpha}|_{i}$ .

Reward Functions and Access Oracles.

In this work we focus on monotone reward function $f$ . We denote by $f(S^{\prime}\mid S)$ the marginal contribution of $S^{\prime}$ to $f$ , given $S$ , i.e., $f(S^{\prime}\mid S)=f(S^{\prime}\cup S)-f(S)$ . We also use the notation $f_{S}(i)=f(\{i\}|S)$ . We consider reward functions that belong to one of the following (nested) classes:

$\blacksquare$

Additive: $f(S)=\sum_{a\in S}f(\{a\})$ for any $S\subseteq T$ .
$\blacksquare$

Gross-Substitutes: For any two price vectors $p,q\in\mathbb{R}^{|T|}$ , such that $p\leq q$ coordinate-wise, and any $S^{\star}\in\operatorname*{arg\,max}_{S\subseteq T}\{f(S)-\sum_{a\in S}p_{a}\}$ , there exists a demand bundle with respect to $q$ , i.e., $S^{\prime}\in\operatorname*{arg\,max}_{S\subseteq T}\{f(S)-\sum_{a\in S}q_{a}\}$ , such that $S^{\star}\cap\{j\mid p_{j}=q_{j}\}\subseteq S^{\prime}$ .
$\blacksquare$

Submodular: For any $S^{\prime}\subseteq S\subseteq T$ and any $a\notin S$ , it holds that $f{{}_{S^{\prime}}}(a)\geq f_{{S}}(a)$ .
$\blacksquare$

Subadditive: For any $S^{\prime},S\subseteq T$ , it holds that $f(S)+f(S^{\prime})\geq f(S\cup S^{\prime})$ .

It is well-known that, $\text{additive}\subsetneq\text{gross-substitutes}\subsetneq\text{submodular}% \subsetneq\text{subadditive}$ [50]. As $f$ may have an exponential representation in $n$ (and $|T|$ ) we assume algorithms access $f$ via two standard models:

$\blacksquare$

Value oracle: accepts a set $S\subseteq T$ and returns $f(S)$ .
$\blacksquare$

Demand oracle: accepts a vector $p\in\mathbb{R}^{|T|}$ and returns $S^{\star}\in\operatorname*{arg\,max}_{S\subseteq T}\{f(S)-\sum_{a\in S}p_{a}\}$ .

Generally, demand oracles are strictly stronger that value oracles [12]. However, for gross-substitutes $f$ a demand query can be computed in poly-time with value oracle access [51].

2.2 Objectives and Maximization Problems

Our results apply to a variety of objectives beyond the standard goal of maximizing profit. Analogously to [38], we consider a family of natural objectives that are defined with respect to a contract $\boldsymbol{\alpha}$ and the set of actions $S=\bigsqcup_{i\in A}S_{i}$ taken by the agents. We begin by presenting a precise definition of an objective.

Definition 2.3 (Objectives in the Multi-Agent Combinatorial-Actions Model).

An objective $\varphi$ is defined by a poly-time algorithm that, given a problem instance $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ , a contract $\boldsymbol{\alpha}$ , and a subset of actions $S\subseteq T$ , outputs a non-negative real number, denoted $\varphi_{\langle A,\{T_{i}\}_{i\in A},f,c\rangle}(\boldsymbol{\alpha},S)$ . This algorithm has value oracle access to $f$ . We omit the subscript if the instance is clear from context.

Observe that the standard goal of maximizing profit adheres to this definition: Given a contract $\boldsymbol{\alpha}$ and a set of actions $S$ a simple poly-time algorithm can compute $u_{P}(\boldsymbol{\alpha},S)=(1-\sum_{i\in A}\alpha_{i})\cdot f(S)$ using a single value query to $f$ .

For a given objective $\varphi$ and budget $B\in(0,1]$ , we denote by $\textsc{Max-}\varphi(B)$ the problem of finding a budget-feasible contract and equilibrium $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ , that maximize $\varphi$ . We sometimes abuse notation and use $\textsc{Max-}\varphi(B)$ to denote the maximal value of $\varphi$ achievable under budget $B$ .

Below we define the class of BEST objectives, which naturally extends the definition for the binary-actions setting of [38].

Definition 2.4 (BEST Objectives).

An objective $\varphi$ belongs to the class of beyond standard (BEST) objectives if, for any instance $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ , it is:

(i)

Sandwiched between profit and reward: For any $\boldsymbol{\alpha}$ and $S\subseteq T$ , $u_{P}(\boldsymbol{\alpha},S)\leq\varphi(\boldsymbol{\alpha},S)\leq f(S)$ .
(ii)

Decomposable: For any $\boldsymbol{\alpha}$ , any $S\subseteq T$ , and any $i\in A$ , $\varphi(\boldsymbol{\alpha},S)\leq f(S_{-i})+\varphi(\boldsymbol{\alpha}|_{i},% S_{i})$ .
(iii)

Weakly increasing in $S$ : For any $\boldsymbol{\alpha}$ and any $S\subseteq S^{\prime}\subseteq T$ , $\varphi(\boldsymbol{\alpha},S)\leq\varphi(\boldsymbol{\alpha},S^{\prime})$ .
(iv)

Weakly decreasing in $\boldsymbol{\alpha}$ : For any $\boldsymbol{\alpha}\leq\boldsymbol{\alpha}^{\prime}$ (coordinate-wise) and $S\subseteq T$ , $\varphi(\boldsymbol{\alpha},S)\geq\varphi(\boldsymbol{\alpha}^{\prime},S)$ .

The first two conditions generalize the definition of BEST objectives from [38]. The richer combinatorial-actions setting considered here also requires conditions $(iii)$ and $(iv)$ , which are natural, and clearly hold for common objectives such as profit, welfare and reward.

In the full version of the paper we show that the class of BEST objectives includes the standard objectives of profit (maximizing the principal’s utility), welfare ( $\max_{\boldsymbol{\alpha},S\in\mathsf{NE}(\boldsymbol{\alpha})}f(S)-c(S)$ ) and reward ( $\max_{\boldsymbol{\alpha},S\in\mathsf{NE}(\boldsymbol{\alpha})}f(S)$ ). We also show that this class is closed under convex combinations.

3 Inapproximability Result for Submodular Instances

In this section we show that when $f$ is submodular, for any budget $B\in(0,1)$ , and any BEST objective $\varphi$ , it holds that $\textsc{Max-}\varphi(B)$ cannot be efficiently approximated with demand query access. This presents a significant departure from the unbudgeted case, where [28] present a poly-time constant-factor approximation algorithm for profit, i.e., for $\textsc{Max-Profit}(1)$ .

Theorem 3.1 (Inapproximability for Submodular Instances).

Fix any BEST objective $\varphi$ and any budget $B\in(0,1)$ . For any approximation guarantee $K:\mathbb{N}\to[1,\infty)$ , any (randomized) poly-time algorithm with demand oracle access to $f$ may only achieve a $K(n)$ -approximation to $\textsc{Max-}\varphi(B)$ with exponentially-small probability (in $n$ ).

By setting $K(n)=2^{n}$ in Theorem 3.1, we derive the following corollary.

Corollary 3.2 (Exponential Lower Bound on Expected Approximation Ratio).

Fix any $B E S T$ objective $\varphi$ , and any budget $B\in(0,1)$ . Let $\mathcal{A}$ be any (randomized) poly-time algorithm with demand oracle access to $f$ , and denote its output by $(\boldsymbol{\alpha},S)$ . Then, there exists a family of instances such that ${\textsc{Max-}\varphi(B)}/{\mathbb{E}_{\mathcal{A}}[\varphi(\boldsymbol{\alpha% },S)]}=2^{\Omega(n)}$ .

Our result is information-theoretic: We construct an instance with a probability distribution over submodular reward functions and establish an upper bound on the expected performance of any deterministic algorithm with demand oracle access on this randomized input. By Yao’s principle, this directly implies the statement of the theorem.

Let us now define the instances used in the proof of Theorem 3.1.

Definition 3.3 (Parameterized Instances).

Fix a budget $B\in(0,1)$ , an approximation guarantee $K:\mathbb{N}\to[1,\infty)$ , and any even $n>0$ . Fix any $\varepsilon>0$ such that:

\displaystyle\varepsilon<\min\left(\frac{1-B}{K(n)\cdot(n+4)},\frac{4\cdot n}{% B}\right).

For any $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=n/2$ , we define an instance $\mathcal{I}^{(A^{\prime})}=\langle A,\bigsqcup T_{i},f^{(A^{\prime})},c\rangle$ as follows.

$\blacksquare$

The set of agents is $A=\{1,\ldots,n+1\}$ .
$\blacksquare$

Each agent $i\in[n]$ controls a single action $T_{i}=\{i\}$ . Additionally, agent $n+1$ controls two actions $T_{n+1}=\{\mathcal{B},\mathcal{G}\}$ . That is, the total set of actions is $T=[n]\cup\{\mathcal{B},\mathcal{G}\}$ , ( $\mathcal{B}$ for “bad”, $\mathcal{G}$ for “good”).
$\blacksquare$

The costs of the actions are:

$\displaystyle c_{i}=\varepsilon^{3}\text{ for all }i\in[n],\quad c_{\mathcal{G% }}=(1/2)\cdot\left(B-(n/2)\cdot\varepsilon^{2}\right)\quad\text{and}\quad c_{% \mathcal{B}}=(3/2)\cdot\varepsilon\cdot B.$
$\blacksquare$

The reward function $f^{(A^{\prime})}$ is defined as a sum of three set functions. Specifically, we let $f^{(A^{\prime})}(S)=f_{1}(S)+f_{2}(S)-f_{3}(S,A^{\prime})$ , where:

$\displaystyle f_{1}(S)$ $\displaystyle=\max\left((1/2)\cdot\textbf{1}[\mathcal{G}\in S],\varepsilon% \cdot\textbf{1}[\mathcal{B}\in S]\right)$

$\displaystyle f_{2}(S)$ $\displaystyle=\varepsilon\cdot\min\left(|S\setminus\{\mathcal{G}\}|,n/2+1\right)$

$\displaystyle f_{3}(S,A^{\prime})$ $\displaystyle=(\varepsilon/2)\cdot\textbf{1}[S=\{\mathcal{B}\}\cup A^{\prime}]$

Whenever it is clear from the context, we omit $A^{\prime}$ from the reward function, and write simply $f$ . Observe that $f_{1}$ is a (weighted) unit-demand function over $\{\mathcal{G},\mathcal{B}\}$ and $f_{2}$ is a uniform $({n}/{2}+1)$ -demand⁷⁷7A set function $f:2^{A}\to\mathbb{R}_{\geq 0}$ is unit-demand if $f(S)=\;\max_{i\in S}f(\{i\})$ . Moreover, $f$ is uniform $k$ -demand if there exists $v\in\mathbb{R}_{\geq 0}$ such that $f(S)=\min\{\,|S|,\,k\,\}\cdot v$ over $[n]\cup\{\mathcal{B}\}$ .

We give a brief proof sketch for Theorem 3.1: First, we observe that obtaining a good approximation for any BEST objective requires a good approximation to $f$ . By design, this is only possible when agent $n+1$ chooses action $\mathcal{G}$ , since any set containing $\mathcal{G}$ has value greater than $1/2$ , whereas any set that excludes $\mathcal{G}$ has value at most $(n/2+2)\cdot\varepsilon$ . However, the only way to incentivize agent $n+1$ to take $\mathcal{G}$ instead of $\mathcal{B}$ , while complying with the budget, is to incentivize the set $A^{\prime}$ to take action. This is because the marginal reward of $\mathcal{B}$ is reduced when the agents of $A^{\prime}$ exerts effort (as captured by $f_{3}$ ). Consequently, a good approximation can only be achieved when the equilibrium satisfies $S_{-(n+1)}=A^{\prime}$ , implying that the algorithm must effectively “know” the set $A^{\prime}$ . In the case of value queries alone, a standard “hide a special set” argument shows that any algorithm identifying $A^{\prime}$ with non-negligible probability must make exponentially many value queries. Finally, to complete the proof, we demonstrate that access to demand queries does not help, as any demand query can be simulated using $O(1)$ value queries for our choice of $f$ .

We now move to the formal analysis. Before proving Theorem 3.1, we present some useful lemmas. We first establish that $f^{(A^{\prime})}$ is monotone and submodular. The proof is deferred to the full version.

Lemma 3.4.

For any $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=n/2$ , it holds that $f^{(A^{\prime})}$ is monotone and submodular.

We next show that demand queries to $f^{(A^{\prime})}$ are not more powerful than value queries.

Lemma 3.5.

For any $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=n/2$ , any demand query to $f^{(A^{\prime})}$ can be computed with $12$ value queries to $f^{(A^{\prime})}$ .

Proof.

Fix a subset $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=n/2$ . Let $p\in\mathbb{R}_{\geq 0}^{n+1}$ be a price vector. Without loss of generality, assume that $p_{1}\leq\dots\leq p_{n}$ . Let $k$ be a maximal index such that $p_{k}<\varepsilon$ or $0$ if no such index exists. Let $\tau=\min\{k,n/2+1\}$ .

We claim that one of the sets $\{\{1,\dots,\tau\},\{1,\dots,\tau-1\},\{1,\dots,\tau-2,\tau\}\}$ combined with one of $\{\emptyset,\{\mathcal{G}\},\{\mathcal{B}\},\{\mathcal{G},\mathcal{B}\}\}$ is a demand bundle. Once the claim is proven, it follows that $12$ value queries suffice to answer a demand query.

To prove the claim, let $S^{\star}\in\operatorname*{arg\,max}_{S\subseteq T}\{f(S)-\sum_{j\in S}p_{j}\}$ , be a set in the demand with respect to price vector $p$ , and let $S_{0}=S^{\star}\cap\{\mathcal{G},\mathcal{B}\}$ . The marginal utility of $S^{\prime}\subseteq[n]$ with respect to $S$ is:

	$\displaystyle u(S^{\prime}\mid S_{0})$	$\displaystyle=f(S^{\prime}\mid S_{0})-\sum_{i\in S^{\prime}}p_{i}$
		$\displaystyle=\begin{cases}\varepsilon\cdot\min(\|S^{\prime}\|,n/2+1)-\sum_{i\in S% ^{\prime}}p_{i}&\text{if }S_{0}=\emptyset\text{ or }S_{0}=\{\mathcal{G}\}\\ \varepsilon\cdot\min(\|S^{\prime}\|,n/2)-\sum_{i\in S^{\prime}}p_{i}&\text{if }S% _{0}=\{\mathcal{B},\mathcal{G}\}\\ \varepsilon\cdot\min(\|S^{\prime}\|,n/2)-(\varepsilon/2)\cdot\textbf{1}[S^{% \prime}=A^{\prime}]-\sum_{i\in S^{\prime}}p_{i}&\text{if }S_{0}=\{\mathcal{B}% \}\end{cases}$

We claim that one of $\{\{1,\dots,\tau\},\{1,\dots,\tau-1\},\{1,\dots,\tau-2,\tau\}\}$ maximizes $u(S^{\prime}\mid S_{0})$ .

Indeed, if $S_{0}=\emptyset$ or $S_{0}=\{\mathcal{G}\}$ , clearly $S^{\prime}=\{1,\dots,\tau\}$ maximizes $u(S^{\prime}\mid S_{0})$ , and we are done. If $S_{0}=\{\mathcal{B},\mathcal{G}\}$ , clearly $S=\{1,\dots,\min(k,n/2)\}$ maximizes $u(S^{\prime}\mid S_{0})$ , and by definition of $\tau$ , we have $\min(k,n/2)\in\{\tau,\tau-1\}$ , implying that either $\{1,\dots,\tau\}$ or $\{1,\dots,\tau-1\}$ maximizes $u(S^{\prime}\mid S_{0})$ , as needed. Otherwise, $S_{0}=\{\mathcal{B}\}$ . If $\{1,\dots\tau-1\}=A^{\prime}$ , then since $|A^{\prime}|=n/2$ , we must have $\tau={n}/{2}+1$ , and so either $\{1,\dots,\tau-2,\tau\}$ or $\{1,\dots\tau-1\}$ maximizes $u(S^{\prime}\mid S_{0})$ . If $\{1,\dots\tau\}=A^{\prime}$ , then since $|A^{\prime}|=n/2$ , we must have $p_{\tau+1}\geq\varepsilon$ . We get that either $\{1,\dots,\tau-1\}$ or $\{1,\dots,\tau\}$ maximizes $u(S^{\prime}\mid S_{0})$ . If $\{1,\dots\tau-1\}\neq A^{\prime}$ and $\{1,\dots\tau\}\neq A^{\prime}$ , then, either $\{1,\dots,\tau-1\}$ or $\{1,\dots,\tau\}$ maximizes $u(S^{\prime}\mid S_{0})$ . $\hfill\blacktriangleleft$

Given the lemma above, it is enough to show that no algorithm can obtain a good approximation using only value queries.

The following lemma shows that it is possible to incentivize the set of actions $A^{\prime}\cup{\mathcal{G}}$ without violating the budget constraints.

Lemma 3.6.

For any instance $\mathcal{I}^{(A^{\prime})}$ with $A^{\prime}\subseteq[n]$ and $|A^{\prime}|=n/2$ , there exists a contract $\boldsymbol{\alpha}$ such that $(\boldsymbol{\alpha},A^{\prime}\cup\{\mathcal{G}\})\in\mathcal{C}(B)$ .

Proof.

Consider the contract

\alpha_{i}=\begin{cases}\varepsilon^{2}&\text{if }i\in A^{\prime}\\ B-(n/2)\cdot\varepsilon^{2}&\text{if }i=n+1\\ 0&\text{otherwise},\end{cases}

and let $S=A^{\prime}\cup\{\mathcal{G}\}$ . Clearly $f(S)\geq f(\mathcal{G})\geq 1/2$ , we now show that $S\in\mathsf{NE}(\boldsymbol{\alpha})$ . Let $j\in[n]\setminus A^{\prime}$ . Since $\alpha_{j}=0$ , $S_{j}=\emptyset$ is a best response for agent $j$ . Let $i\in A^{\prime}$ . Note that

\alpha_{i}\cdot f(i\mid S_{-i})=\varepsilon^{2}\cdot f_{2}(i\mid S_{-i})=% \varepsilon^{2}\cdot\varepsilon=c_{i},

so $S_{i}=\{i\}$ is a best response for agent $i$ since his only choices are $\{i\}$ and $\emptyset$ . We now turn to agent $n+1$ . Note that

\alpha_{n+1}\cdot f(\mathcal{B}\mid S_{-(n+1)})=\alpha_{n+1}\cdot f(\mathcal{B% }\mid A^{\prime})=\left(B-(n/2)\cdot\varepsilon^{2}\right)\cdot(3/2)\cdot(% \varepsilon)<c_{\mathcal{B}},

and so since $f$ is submodular, it holds that agent $(n+1)$ ’s best response does not contain $\mathcal{B}$ . It therefore remains to show that agent $(n+1)$ ’s utility from $\mathcal{G}$ is non-negative. Indeed,

\alpha_{n+1}\cdot f(\mathcal{G}\mid S_{-(n+1)})=\alpha_{n+1}\cdot f(\mathcal{G% }\mid A^{\prime})=\left(B-({n}/{2})\cdot\varepsilon^{2}\right)\cdot({1}/{2})=c% _{\mathcal{G}},

as needed. $\hfill\blacktriangleleft$

Next, we show that incentivizing $A^{\prime}\cup{\mathcal{G}}$ is necessary to get a non-trivial approximation to $f$ .

Lemma 3.7.

For any instance $\mathcal{I}^{(A^{\prime})}$ with $A^{\prime}\subseteq[n]$ and $|A^{\prime}|=n/2$ , for any $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ with $S\neq\{\mathcal{G}\}\cup A^{\prime}$ , it holds that $f(S)\leq(n/2+2)\cdot\varepsilon$ .

Proof.

Fix a subset $A^{\prime}\subseteq[n]$ with $|A^{\prime}|=n/2$ . Let $(\boldsymbol{\alpha},S)$ be such a budget-feasible contract and equilibrium. We first observe that it cannot be that $\{\mathcal{G},\mathcal{B}\}\subseteq S$ . This is because if $\{\mathcal{G},\mathcal{B}\}\subseteq S$ , then $S$ is not budget-feasible due to submodularity of $f$ :

\displaystyle\alpha_{n+1}\geq{c_{\mathcal{B}}}/{f_{S}(\mathcal{B})}\geq{c_{% \mathcal{B}}}/{f(\mathcal{B}\mid\mathcal{G})}\geq{c_{\mathcal{B}}}/{% \varepsilon}=(3/2)\cdot B>B.

Note that for any $S\subseteq[n]\cup\{\mathcal{B}\}$ , it holds that $f(S)\leq f_{1}(S)+f_{2}(S)\leq(n/2+2)\cdot\varepsilon$ , so proving $\mathcal{G}\notin S$ is sufficient. Assume towards contradiction that $\mathcal{G}\in S$ . Since $\{\mathcal{G},\mathcal{B}\}\subsetneq S$ , we must have $S_{n+1}=\{\mathcal{G}\}$ , and

\displaystyle\alpha_{n+1}\geq{c_{\mathcal{G}}}/{f_{S}(\mathcal{G})}\geq{c_{% \mathcal{G}}}/{f(\{\mathcal{G}\})}=B-(n/2)\cdot\varepsilon^{2}.

Observe that $|S\cap[n]|\leq n/2$ since incentivizing any agent $i\in[n]$ to exert effort takes at least ${c_{i}}/{f(\{i\})}=\varepsilon^{2}$ , and therefore we can only incentivize ${n}/{2}$ such agents, as the remaining budget is $B-\alpha_{n+1}\leq({n}/{2})\cdot\varepsilon^{2}$ . Since $|S\cap[n]|\leq n/2$ , $S_{n+1}=\{\mathcal{G}\}$ , and $S\neq\{\mathcal{G}\}\cup A^{\prime}$ , we have $f(\mathcal{B}\mid S_{-(n+1)})=2\varepsilon$ . Then, we have

\alpha_{n+1}f(\mathcal{B}\mid S_{-(n+1)})-c_{\mathcal{B}}\geq\left(B-(n/2)% \varepsilon^{2}\right)\cdot(2\varepsilon)-(3/2)B\varepsilon\geq(B/2)% \varepsilon-n\varepsilon^{3}>(B/2)\varepsilon-n\varepsilon^{2}.

Moreover, by budget feasibility we have $\alpha_{n+1}\leq B$ , and by the definition of $f$ we have $f(\mathcal{G}\mid S_{-(n+1)})\leq 1/2$ , which gives:

\alpha_{n+1}\cdot f(\mathcal{G}\mid S_{-(n+1)})-c_{\mathcal{G}}\leq B\cdot(1/2% )-(1/2)\cdot\left(B-(n/2)\cdot\varepsilon^{2}\right)=(n/4)\cdot\varepsilon^{2}% <n\cdot\varepsilon^{2}.

By our choice of $\varepsilon$ , we have $\varepsilon<4n/B$ , and agent $n+1$ would therefore benefit from deviating to $S_{n+1}=\{\mathcal{B}\}$ , which gives a contradiction. $\hfill\blacktriangleleft$

We are now ready to prove Theorem 3.1.

Proof of Theorem 3.1.

Fix a BEST objective $\varphi$ and a budget $B\in(0,1)$ . By Yao’s principle, it suffices to prove the statement for a deterministic algorithm against a randomized input. We consider a randomized instance $\mathcal{I}^{(A^{\prime})}$ , where $A^{\prime}\subseteq[n]$ is chosen uniformly at random from all subsets of size $n/2$ . By Lemma 3.4, this defines a distribution over monotone and submodular instances. Now, consider a polynomial-time deterministic algorithm with access to value and demand oracles on this randomized input.

By Lemma 3.6 and the definition of BEST objectives, the optimal value of $\varphi$ is at least a $(1-B)$ -fraction of the profit from the budget-feasible contract $(\boldsymbol{\alpha},A^{\prime}\cup{\mathcal{G}})\in\mathcal{C}(B)$ , meaning that:

\displaystyle\textsc{Max-}\varphi(B)\geq\varphi(\boldsymbol{\alpha},A^{\prime}% \cup{\mathcal{G}})\geq u_{P}(\boldsymbol{\alpha},A^{\prime}\cup{\mathcal{G}})% \geq(1-B)\cdot f(A^{\prime}\cup{\mathcal{G}})\geq(1-B)\cdot(1/2).

Moreover, by Lemma 3.7, the value of $\varphi$ for a contract and equilibrium $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ with $S\neq\{\mathcal{G}\}\cup A^{\prime}$ is:

\displaystyle\varphi(\boldsymbol{\alpha},S)\leq f(S)\leq(n/2+2)\cdot\varepsilon.

Thus, unless the algorithm outputs the equilibrium $A^{\prime}\cup{\mathcal{G}}$ , it achieves at best an approximation of $(1-B)\cdot(1/2)/((n/2+2)\cdot\varepsilon)>K(n)$ , since by our choice of $\varepsilon$ we have $\varepsilon<(1-B)/(K(n)\cdot(n+4))$ .

By Lemma 3.5, a polynomial-time algorithm with access to value and demand queries can be simulated using polynomially many value queries. Thus, it remains to show that any algorithm making only polynomially many value queries cannot output ${\mathcal{G}}\cup A^{\prime}$ with better than exponentially small probability.

We assume, without loss of generality, that the algorithm queries the value of the set $S_{-(n+1)}\cup\{\mathcal{B}\}$ (where $S$ is the output equilibrium). This is without loss because any algorithm can be modified to perform one additional value query before terminating, without affecting its polynomial query complexity. We will upper bound the probability that the algorithm queries $A^{\prime}\cup\{\mathcal{B}\}$ , thereby establishing the same upper bound on the probability that it achieves a $K(n)$ -approximation.

Let $S_{1},\dots,S_{\ell}$ be the sequence of value queries that the (deterministic) algorithm makes on the instance $\mathcal{J}=\langle A,\bigsqcup T_{i},f_{1}+f_{2},c\rangle$ . Unless the algorithm queries $A^{\prime}\cup\{\mathcal{B}\}$ , this instance $\mathcal{J}$ is indistinguishable from $\mathcal{I}^{(A^{\prime})}$ . Thus, the probability that the algorithm queries $A^{\prime}\cup\{\mathcal{B}\}$ is upper bounded by the probability that $A^{\prime}\cup\{\mathcal{B}\}\in\{S_{1},\dots,S_{\ell}\}$ . Therefore, by the union bound, the probability of querying $A^{\prime}\cup\{\mathcal{B}\}$ is at most ${\ell}/\binom{n}{n/2}$ . Since $\ell$ is polynomial in $n$ , this probability is exponentially small in $n$ , as needed. $\hfill\blacktriangleleft$

4 Constant-Factor Approximation for Gross Substitutes Instances

In this section we establish an up-to-a-constant-factor equivalence between any two BEST objectives, generalizing the result of [38] to the multi-agent combinatorial-actions setting under gross substitutes $f$ . This equivalence is cast in the following theorem.

Theorem 4.1 (Equivalence of All BEST Objectives and Budgets).

Fix any two BEST objectives $\varphi,\varphi^{\prime}$ and any two budget $B,B^{\prime}\in(0,1]$ . For gross substitutes $f$ , there exists a poly-time reduction from $\textsc{Max-}\varphi(B)$ to $\textsc{Max-}\varphi^{\prime}(B^{\prime})$ that loses only a constant factor in the approximation. This reduction requires value oracle access to $f$ .

The following corollary follows directly from combining the above equivalence with the poly-time algorithm of [28] for maximizing profit with budget $B=1$ for submodular (and hence also gross substitutes) $f$ .

Corollary 4.2 (Constant-Factor Approximations Under Budget Constraints).

When $f$ is gross substitutes, for any BEST objective $\varphi$ and any budget $B\in[0,1]$ , there exists a polynomial-time algorithm that achieves $O(1)$ -approximation to $\textsc{Max-}\varphi(B)$ using value queries.

To establish Theorem 4.1, we follow a scheme similar to that of [38], which proved an analogous result in the binary-action setting. In Section 4.1, we identify a key property, best-response monotonicity, that enables this equivalence. This property holds both in the binary-action case for submodular $f$ and in the combinatorial-actions case for gross substitutes $f$ (Lemma 4.3). Crucially, for combinatorial actions with submodular $f$ , best-response monotonicity fails to hold, an observation we exploit in the negative result of Section 3. We use best-response monotonicity to prove a downsizing lemma (Lemma 4.5) for the combinatorial-actions setting, analogous to the argument in [38].

In Section 4.2 we define an auxiliary problem, $\textsc{Max-Reward-Bounded}(B)$ . We show that for any BEST objective $\varphi$ and any budget $B$ , a constant-factor approximation to $\textsc{Max-}\varphi(B)$ can be obtained either from the solution to $\textsc{Max-Reward-Bounded}(B)$ or from a contract that incentivizes only a single agent to take some actions.

4.1 Best-Response Monotonicity for Gross Substitutes Instances

In this section we present the main property of gross substitutes that allows us to apply our techniques. Roughly speaking, we show that when $f$ is gross substitutes, incentivizing an agent to take a given subset of actions is always cheapest for the principal when all other agents do nothing. This does not hold for submodular $f$ , as exemplified by our construction in Section 3.

Lemma 4.3 (Best-Response Monotonicity).

Consider any instance with a gross substitutes $f$ . Fix a contract $\boldsymbol{\alpha}$ , an equilibrium $S\in\mathsf{NE}(\boldsymbol{\alpha})$ , and an agent $i\in A$ . Take any subset of actions $S^{\prime}_{-i}\subseteq S_{-i}$ . Then, there exists $S^{\prime}_{i}\subseteq T_{i}$ such that $S_{i}\subseteq S^{\prime}_{i}$ and $S^{\prime}_{i}$ is agent $i$ ’s best response to $S^{\prime}_{-i}$ , i.e., for every alternative set of actions $\tilde{S}_{i}\subseteq T_{i}$ , it holds that $\alpha_{i}\cdot f(S^{\prime}_{i}\sqcup S^{\prime}_{-i})-c(S^{\prime}_{i})\geq% \alpha_{i}\cdot f(\tilde{S}_{i}\sqcup S^{\prime}_{-i})-c(\tilde{S}_{i})$ .

Proof.

Fix agent $i\in A$ , contract $\boldsymbol{\alpha}$ , actions $S\in\mathsf{NE}(\boldsymbol{\alpha})$ , and $S^{\prime}_{-i}\subseteq S_{-i}$ satisfying the above conditions. Consider two price vectors $\{p_{a}\}_{a\in T}$ and $\{q_{a}\}_{a\in T}$ defined as:

p_{a}=\begin{cases}-1&\text{if }a\in S_{-i}\\ 2&\text{if }a\in T_{-i}\setminus S_{-i}\\ (1/\alpha_{i})\cdot c_{a}&\text{if }a\in T_{i},\end{cases}\qquad\qquad q_{a}=% \begin{cases}-1&\text{if }a\in S^{\prime}_{-i}\\ 2&\text{if }a\in T_{-i}\setminus S^{\prime}_{-i}\\ (1/\alpha_{i})\cdot c_{a}&\text{if }a\in T_{i}.\end{cases}

We observe that the following equivalences hold for any action profile $S^{\prime}=S^{\prime}_{i}\sqcup S^{\prime}_{-i}$ :

		$S^{\prime}_{i}$ is agent $i$ ’s best response to $S^{\prime}_{-i}$ given $\alpha_{i}$
	$\displaystyle\Longleftrightarrow\quad$	$\displaystyle S^{\prime}_{i}\in\operatorname*{arg\,max}_{U^{\prime}_{i}% \subseteq T_{i}}\left\{f(U^{\prime}_{i}\cup S^{\prime}_{-i})-\sum_{a\in U^{% \prime}_{i}}(1/\alpha_{i})\cdot c_{a}\right\}$
	$\displaystyle\Longleftrightarrow\quad$	$\displaystyle S^{\prime}=S^{\prime}_{i}\sqcup S^{\prime}_{-i}\in\operatorname*% {arg\,max}_{V\subseteq T}\left\{f(V)-\sum_{a\in V}q_{a}\right\}.$

The first equivalence is observed by [28]. We next show the second equivalence. Let $Q\in\operatorname*{arg\,max}_{V\subseteq T}\{f(V)-\sum_{a\in V}q_{a}\}$ . We argue that $Q_{-i}=S^{\prime}_{-i}$ ; combined with the definition of $q$ , this implies the equivalence. On the one hand, since $f(U)\leq 1$ for all $U\subseteq T$ and $q_{a}>1$ for all $a\in T_{-i}\setminus S^{\prime}_{-i}$ , we have $Q_{-i}\subseteq S^{\prime}_{-i}$ . On the other hand, since $f$ is weakly monotone and $q_{a}=-1$ for all $a\in S^{\prime}_{-i}$ , it must be that $S^{\prime}_{-i}\subseteq Q_{-i}$ . Thus, $Q_{-i}=S^{\prime}_{-i}$ .

A similar equivalence also holds with respect to $S$ and $p$ . Namely, $U_{i}\subseteq T_{i}$ is agent $i$ ’s best response to $S_{-i}$ given $\alpha_{i}$ if and only if $U_{i}\cup S_{-i}\in\operatorname*{arg\,max}_{V\subseteq T}\{f(V)-\sum_{a\in V}% p_{a}\}$ . Thus, since $S$ is an equilibrium, it is a demand bundle with respect to $f$ and $p$ . Note that $p_{a}\leq q_{a}$ for all $a\in T$ by the assumption that $S_{-i}^{\prime}\subseteq S_{-i}$ . Thus, by the gross substitutes property of $f$ , there exists a set $S^{\prime}_{i}$ such that $S_{i}\subseteq S^{\prime}_{i}\subseteq T_{i}$ and $S_{i}^{\prime}\cup S_{-i}^{\prime}\in\operatorname*{arg\,max}_{V\subseteq T}\{% f(V)-\sum_{a\in V}q_{a}\}$ , as needed. $\hfill\blacktriangleleft$

Lemma 4.3 immediately yields the following important corollary. Recall that $\boldsymbol{\alpha}|_{i}$ is the contract which offers $\alpha_{i}$ to agent $i$ and zero to all other agents.

Corollary 4.4.

Consider an instance with a gross substitutes $f$ . Fix a contract $\boldsymbol{\alpha}$ , an equilibrium $S\in\mathsf{NE}(\boldsymbol{\alpha})$ , and any agent $i\in A$ . Then there exists an equilibrium $S^{\prime}\in\mathsf{NE}(\boldsymbol{\alpha}|_{i})$ such that $S_{i}\subseteq S_{i}^{\prime}$ and $S^{\prime}_{j}=\emptyset$ for any $j\neq i$ .

Corollary 4.4 together with Lemma 2.2 enable us to prove a downsizing lemma akin to [38, Lemma 3.2] for the combinatorial-actions setting. We defer the details of the algorithm and the proof of the lemma to the full version.

Lemma 4.5 (Downsizing Lemma for Combinatorial Actions).

Let $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ be any multi-agent combinatorial-actions instance with gross substitutes $f$ . For any integer $M\geq 3$ and any $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ , there exists $(\boldsymbol{\alpha}^{\prime},S^{\prime})\in\mathcal{C}(B)$ such that:

\displaystyle\left(\sum_{i\in A}\alpha_{i}^{\prime}\leq\frac{5}{M}\cdot\sum_{i% \in A}\alpha_{i}\;\text{ or }\;\exists i\in A{\text{ s.t. }}{\boldsymbol{% \alpha}^{\prime}=\boldsymbol{\alpha}|_{i}}{{\text{ and }}S^{\prime}\subseteq T% _{i}}\right)\;\text{ and }\;f(S^{\prime})\geq\frac{f(S)}{2M-2}.

Moreover, such a pair $(\boldsymbol{\alpha}^{\prime},S^{\prime})\in\mathcal{C}(B)$ can be computed in poly-time with value query access to $f$ .

4.2 BEST Objectives Are Equivalent

To establish the up-to-a-constant-factor equivalence between any two BEST under any two budgets, we define two maximization problems (i) finding the optimal budget-feasible contract which incentivizes a single agent, and (ii) finding an optimal budget-feasible contract and an equilibrium where the payment to each agent is at most a $3/4$ -fraction of the budget.

Definition 4.6 ( $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ ).

For any given objective $\varphi$ and budget $B\in(0,1]$ , the problem of $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ is the problem of finding an optimal single-agent contract for agent $i$ :

\textsc{Best-Single}_{i}\textsc{-}\varphi(B)=\max_{(\boldsymbol{\alpha},S)\in% \mathcal{C}(B)}\varphi(\boldsymbol{\alpha},S)\quad\text{subject to}\quad% \boldsymbol{\alpha}=\boldsymbol{\alpha}|_{i}\text{ and }S\subseteq T_{i}.

When clear from context, we also use $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ to denote a pair $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ maximizing $\varphi$ subject to $\boldsymbol{\alpha}=\boldsymbol{\alpha}|_{i}\text{ and }S\subseteq T_{i}$ .

Definition 4.7 ( $\textsc{Max-Reward-Bounded}(B)$ ).

Let $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ be an problem instance. For any $B\in(0,1]$ , the $\textsc{Max-Reward-Bounded}(B)$ problem is defined as

\textsc{Max-Reward-Bounded}(B)=\max_{(\boldsymbol{\alpha},S)\in\mathcal{C}(B)}% f(S)\quad\text{subject to}\quad\alpha_{i}\leq 3B/4\text{ for all }i\in A.

The best-response monotonicity of gross substitutes instances (Corollary 4.4) is crucial for the proof of the following lemma.

Lemma 4.8 (Decomposition Lemma).

Fix an instance $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ with gross substitutes $f$ , a budget $B\in(0,1]$ , and a BEST objective $\varphi$ . It holds that

\textsc{Max-}\varphi(B)\leq 2\cdot\textsc{Max-Reward-Bounded}(B)+\max_{i\in A}% \textsc{Best-Single}_{i}\textsc{-}\varphi(B).

Proof.

Let $(\boldsymbol{\alpha}^{\star},S^{\star})\in\mathcal{C}(B)$ be a solution to $\textsc{Max-}\varphi(B)$ .

If $\alpha_{i}^{\star}\leq(3/4)\cdot B$ for all agents $i\in A$ , then $f(S^{\star})\leq\textsc{Max-Reward-Bounded}(B)$ and we get

$\displaystyle\textsc{Max-}\varphi(B)$	$\displaystyle=\varphi(\boldsymbol{\alpha}^{\star},S^{\star})$	(by the choice of $(\boldsymbol{\alpha}^{\star},S^{\star})$ )
	$\displaystyle\leq f(S^{\star})$	(by Definition 2.4 i)
	$\displaystyle\leq\textsc{Max-Reward-Bounded}(B)$	(as $(\boldsymbol{\alpha}^{\star},S^{\star})\in\mathcal{C}(B)$ and by assumption),

as needed.

Otherwise, let $i\in A$ be the agent such that $\alpha_{i}^{\star}>(3/4)\cdot B$ ; observe that by budget-feasibility there can be at most one such agent. It follows from Definition 2.4 ii that

\textsc{Max-}\varphi(B)=\varphi(\boldsymbol{\alpha}^{\star},S^{\star})\leq f(S% ^{\star}_{-i})+\varphi(\boldsymbol{\alpha}^{\star}|_{i},S_{i}^{\star}).

It remains to bound each of the summands, i.e., $f(S^{\star}_{-i})\leq 2\cdot\textsc{Max-Reward-Bounded}(B)$ , and $\varphi(\boldsymbol{\alpha}^{\star}|_{i},S_{i}^{\star})\leq\textsc{Best-Single% }_{i}\textsc{-}\varphi(B)$ .

Let us first bound $f(S^{\star}_{-i})$ . Note that

\sum_{j\in A\setminus\{i\}}\alpha^{\star}_{j}=\sum_{j\in A}\alpha^{\star}_{j}-% \alpha_{i}^{\star}<B-(3/4)\cdot B=(1/4)\cdot B.

(1)

By applying the doubling lemma (Lemma 2.2) to $\boldsymbol{\alpha}^{\star}|_{-i}$ with $\varepsilon=(1/4)\cdot(B/n)$ , we obtain a contract $\boldsymbol{\alpha}^{\prime}=2\boldsymbol{\alpha}^{\star}|_{-i}+\boldsymbol{\varepsilon}$ , where $\boldsymbol{\varepsilon}=(\varepsilon,\dots,\varepsilon)$ , that satisfies the following properties:

(i)

$\boldsymbol{\alpha}^{\prime}$ is budget-feasible, since $\sum_{j\in A}\alpha^{\prime}_{j}=2\sum_{j\in A\setminus\{i\}}\alpha^{\star}_{j% }+n\varepsilon\leq(1/2)\cdot B+(1/4)\cdot B<B$ , where the first inequality follows from Inequality (1).
(ii)

The payment to every agent $j\in A\setminus\{i\}$ is $\alpha^{\prime}_{j}=2\cdot\alpha^{\star}_{j}+\varepsilon\leq(1/2)\cdot B+(1/4)% \cdot B\leq(3/4)\cdot B$ .
(iii)

The payment to agent $i$ is $\alpha_{i}^{\prime}=\varepsilon<(3/4)\cdot B$ .
(iv)

Any equilibrium $S^{\prime}\in\mathsf{NE}(\boldsymbol{\alpha}^{\prime})$ satisfies $f(S^{\prime})\geq(1/2)\cdot f(S^{\star}_{-i})$ , by Lemma 2.2.

Thus, taking any $S^{\prime}\in\mathsf{NE}(\boldsymbol{\alpha}^{\prime})$ , we get

	$\displaystyle f(S^{\star}_{-i})$	$\displaystyle\leq 2\cdot f(S^{\prime})$	(by (iv))
		$\displaystyle\leq 2\cdot\textsc{Max-Reward-Bounded}(B)$	$\displaystyle\text{(by (i)-(iii))}.$

Next, let us bound $\varphi(\boldsymbol{\alpha}^{\star}|_{i},S_{i}^{\star})$ . Observe that, from Corollary 4.4 it holds that there exists an equilibrium $S^{\prime}$ of the contract $\boldsymbol{\alpha}^{\star}|_{i}$ such that $S^{\prime}\subseteq T_{i}$ and $S_{i}^{\star}\subseteq S^{\prime}$ . Thus,

\varphi(\boldsymbol{\alpha}^{\star}|_{i},S_{i}^{\star})\leq\varphi(\boldsymbol% {\alpha}^{\star}|_{i},S^{\prime})\leq\textsc{Best-Single}_{i}\textsc{-}\varphi% (B),

where the first inequality is by Definition 2.4 iii. This concludes the proof. $\hfill\blacktriangleleft$

Our reductions will take the better contract between the one achieved by (approximately) solving the problem we reduce to, $\textsc{Max-Reward-Bounded}(B)$ , and the best single-agent contract. In the binary-actions case, the best single-agent contract for agent $i\in A$ is simply the ratio between their cost and the success probability when only $i$ exerts effort. In the combinatorial-actions case, solving $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ is not as straightforward, but the following lemma shows we can still do so in polynomial time when $f$ is gross substitutes.

Lemma 4.9.

Fix some objective $\varphi$ and budget $B\in(0,1]$ . When $f$ is gross substitutes, there exists a poly-time algorithm which (exactly) solves $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ with value oracle access to $f$ .

The proof of Lemma 4.9 relies on the “critical point” analysis of [26], who proved the lemma for the special case of maximizing profit for $B=1$ , and is deferred to the full version. We now have all the building blocks for our reductions. We begin by proving a reduction from $\textsc{Max-}\varphi(B)$ to $\textsc{Max-Reward-Bounded}(B)$ .

Lemma 4.10 (Reduction to $\textsc{Max-Reward-Bounded}(B)$ ).

Fix an instance of the problem, $\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ , with gross substitutes $f$ , a budget $B\in(0,1]$ , and a BEST objective $\varphi$ . For any $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ that is a $\gamma$ -approximation to $\textsc{Max-Reward-Bounded}(B)$ , let $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ be the result of applying the downsizing lemma (Lemma 4.5) to $(\boldsymbol{\alpha},S)$ with $M=6$ . Then, it holds that one of $\{\textsc{Best-Single}_{i}\textsc{-}\varphi(B)\}_{i\in A}\cup\{(\boldsymbol{% \alpha}^{\prime},S^{\prime})\}$ is a $(120\gamma+1)$ -approximation to $\textsc{Max-}\varphi(B)$ .

Proof.

Let $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ be a $\gamma$ -approximation to $\textsc{Max-Reward-Bounded}(B)$ and let $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ be the result of applying Lemma 4.5 to $(\boldsymbol{\alpha},S)$ with $M=6$ . This yields a contract-equilibrium pair $(\boldsymbol{\alpha}^{\prime},S^{\prime})\in\mathcal{C}(B)$ such that $f(S^{\prime})\geq(1/10)\cdot f(S)$ and either $\boldsymbol{\alpha}^{\prime}=\boldsymbol{\alpha}|_{i}$ for some $i\in A$ or $\sum_{i\in A}\alpha_{i}^{\prime}\leq(5/6)\cdot\sum_{i\in A}\alpha_{i}\leq(5/6)% \cdot B\leq 5/6$ . In the case where there exists an agent $i\in A$ such that $\boldsymbol{\alpha}^{\prime}=\boldsymbol{\alpha}|_{i}$ , we have $\sum_{j\in A}\alpha^{\prime}_{j}=\alpha_{i}\leq(3/4)\cdot B\leq 3/4$ , where the first inequality is because $(\boldsymbol{\alpha},S)$ satisfies the constraints of $\textsc{Max-Reward-Bounded}(B)$ . Therefore, it holds in both cases that $\sum_{j\in A}\alpha^{\prime}_{j}\leq 5/6$ . Now, it follows that:

$\displaystyle\varphi(\boldsymbol{\alpha}^{\prime},S^{\prime})$	$\displaystyle\geq u_{P}(\boldsymbol{\alpha}^{\prime},S^{\prime})$	$\displaystyle(\text{since $\varphi$ is a BEST objective})$
	$\displaystyle=\left(1-\sum_{i\in A}\alpha_{i}^{\prime}\right)f(S^{\prime})$	$\displaystyle(\text{by the definition of $u_{P}$})$
	$\displaystyle\geq(1/6)\cdot f(S^{\prime})$	$\displaystyle(\text{since $\sum_{j\in A}\alpha^{\prime}_{j}\leq 5/6$})$
	$\displaystyle\geq(1/60)\cdot f(S)$	$\displaystyle(\text{since $f(S^{\prime})\geq(1/10)\cdot f(S)$})$
	$\displaystyle\geq(1/{60\gamma})\cdot\textsc{Max-Reward-Bounded}(B)$	$\displaystyle(\text{since $S$ is $\gamma$-approximation})$

Let $V=\max\{\{\textsc{Best-Single}_{i}\textsc{-}\varphi(B)\}_{i\in A}\cup\{\varphi% (\boldsymbol{\alpha}^{\prime},S^{\prime})\}\}$ . By Lemma 4.8, we get:

	$\displaystyle\textsc{Max-}\varphi(B)$	$\displaystyle\leq 2\cdot\textsc{Max-Reward-Bounded}(B)+\max_{i\in A}\textsc{% Best-Single}_{i}\textsc{-}\varphi(B)$
		$\displaystyle\leq(120\gamma)\cdot\varphi(\boldsymbol{\alpha}^{\prime},S^{% \prime})+\max_{i\in A}\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$
		$\displaystyle\leq(120\gamma+1)\cdot V.$

This concludes the proof. $\hfill\blacktriangleleft$

Next, we establish reduction from $\textsc{Max-Reward-Bounded}(B)$ to $\textsc{Max-}\varphi(B)$ .

Lemma 4.11 (Reduction from $\textsc{Max-Reward-Bounded}(B)$ ).

Fix an instance of the problem $\mathcal{I}=\langle A,\{T_{i}\}_{i\in A},f,c\rangle$ with gross substitutes $f$ and two budgets $B,B^{\prime}\in(0,1]$ , and let $\mathcal{I}^{\prime}=\langle A,\{T_{i}\}_{i\in A},f,c^{\prime}\rangle$ , be an instance with scaled costs, $c^{\prime}=c\cdot(4/3)\cdot(B^{\prime}/B)$ . For any BEST objective $\varphi$ , if $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ is a $\gamma$ -approximation to $\textsc{Max-}\varphi(B^{\prime})$ in instance $\mathcal{I}^{\prime}$ , then one of $\{\textsc{Best-Single}_{i}\textsc{-}f(B)\}_{i\in A}\cup\{(\boldsymbol{\alpha}^% {\prime}\cdot(3/4)\cdot(B/B^{\prime}),S^{\prime})\}$ is a $50\gamma$ -approximation to $\textsc{Max-Reward-Bounded}(B)$ in instance $\mathcal{I}$ .

Proof.

Let $(\boldsymbol{\alpha}^{\star},S^{\star})\in\mathcal{C}(B)$ be a solution to $\textsc{Max-Reward-Bounded}(B)$ in the instance $\mathcal{I}$ , and let $(\boldsymbol{\alpha},S)\in\mathcal{C}(B)$ be the result of applying the downsizing lemma (Lemma 4.5) on $(\boldsymbol{\alpha}^{\star},S^{\star})$ with $M=14$ . By the guarantees of Lemma 4.5, $f(S)\geq(1/26)\cdot f(S^{\star})$ and either (i) $\boldsymbol{\alpha}=\boldsymbol{\alpha}|_{i}$ and $S\subseteq T_{i}$ for some $i\in A$ , or (ii) $\sum_{i\in A}\alpha_{i}\leq(5/14)\cdot\sum_{i\in A}\alpha_{i}^{\star}\leq(5/14% )\cdot B$ .

In case (i) holds, we get that $\textsc{Best-Single}_{i}\textsc{-}f(B)$ is a $26$ -approximation to the problem of $\textsc{Max-Reward-Bounded}(B)$ , which concludes the proof.

Suppose that case (ii) holds. Recall that $(\boldsymbol{\alpha},S)$ is a contract-equilibrium pair in $\mathcal{I}$ , and $\mathcal{I}^{\prime}$ is the same as $\mathcal{I}$ except the costs are scaled by $(4/3)\cdot(B^{\prime}/B)$ . Thus, if we scale the agent payments by the same factor, namely $\boldsymbol{\alpha}^{\ddagger}=(4/3)\cdot(B^{\prime}/B)\cdot\boldsymbol{\alpha}$ , we have that $(\boldsymbol{\alpha}^{\ddagger},S)$ is a contract-equilibrium pair in $\mathcal{I}^{\prime}$ . Observe that:

\displaystyle\sum_{i\in A}\alpha_{i}^{\ddagger}\leq(4/3)\cdot(B^{\prime}/B)% \cdot(5/14)\cdot B=(10/21)\cdot B^{\prime}\leq\min(10/21,B^{\prime}).

Therefore, $\boldsymbol{\alpha}^{\ddagger}$ is budget-feasible with respect to $B^{\prime}$ , and the principal’s profit from the contract-equilibrium pair $(\boldsymbol{\alpha}^{\ddagger},S)$ is at least:

	$\displaystyle u_{P}(\boldsymbol{\alpha}^{\ddagger},S)$	$\displaystyle\geq\left(1-{10}/{21}\right)\cdot f(S)=(11/21)\cdot f(S)$		(2)
		$\displaystyle\geq(11/21)\cdot(1/26)\cdot f(S^{\star})>(1/50)\cdot f(S^{\star}).$

Let $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ be a $\gamma$ -approximation to $\textsc{Max-}\varphi(B^{\prime})$ in $\mathcal{I}^{\prime}$ . Then it holds that:

$\displaystyle f(S^{\prime})$	$\displaystyle\geq\varphi_{\mathcal{I}^{\prime}}(\boldsymbol{\alpha}^{\prime},S% ^{\prime})$	$\displaystyle(\text{since $\varphi$ is BEST})$
	$\displaystyle\geq\textsc{Max-}\varphi(B^{\prime})/\gamma$	$\displaystyle(\text{since $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ is a $% \gamma$-approximation})$
	$\displaystyle\geq\varphi(\boldsymbol{\alpha}^{\ddagger},S)/\gamma$	$\displaystyle(\text{since $\boldsymbol{\alpha}^{\ddagger}$ is budget-feasible % w.r.t. $B^{\prime}$})$
	$\displaystyle\geq u_{P}(\boldsymbol{\alpha}^{\ddagger},S)/\gamma$	$\displaystyle(\text{since $\varphi$ is BEST})$
	$\displaystyle\geq(1/50\gamma)\cdot f(S^{\star})$	$\displaystyle(\text{by \lx@cref{creftypecap~refnum}{eq:bbb}})$

Let $\boldsymbol{\alpha}^{\dagger}=(3/4)\cdot(B/B^{\prime})\cdot\boldsymbol{\alpha}% ^{\prime}$ . We show that the pair $(\boldsymbol{\alpha}^{\dagger},S^{\prime})$ makes up a $50\gamma$ -approximation to $\textsc{Max-Reward-Bounded}(B)$ . First, since $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ is a contract-equilibrium pair in $\mathcal{I}^{\prime}$ , $(\boldsymbol{\alpha}^{\dagger},S^{\prime})$ make up such a pair with respect to $\mathcal{I}$ . Since $f(S^{\prime})\geq(1/50\gamma)\cdot f(S^{\star})$ , it remains to show that the contract $\boldsymbol{\alpha}^{\dagger}$ satisfies the feasibility constraints. Observe that $\boldsymbol{\alpha}^{\dagger}$ is budget-feasible with respect to $B$ , as $\sum_{i\in A}\alpha_{i}^{\dagger}=(3/4)\cdot(B/B^{\prime})\cdot\sum_{i\in A}% \alpha_{i}^{\prime}\leq(3/4)\cdot B$ , where the inequality follows from budget feasibility of $\boldsymbol{\alpha}^{\prime}$ with respect to $B^{\prime}$ . Similarly, for any $i\in A$ , $\alpha_{i}^{\prime}\leq B^{\prime}$ and thus $\alpha_{i}^{\dagger}=(3/4)\cdot(B/B^{\prime})\cdot\alpha_{i}^{\prime}\leq(3/4)\cdot B$ . This concludes the proof. $\hfill\blacktriangleleft$ Together, the two lemmas above imply Theorem 4.1.

5 FPTAS for Additive Instances

In this section, we consider instances with additive $f$ . Specifically, we show that the FPTAS for multi-agent binary-action settings of [27], later generalized to budget constraints by [38], can be adapted to the combinatorial-actions setting.

Theorem 5.1.

When $f$ is additive, for each objective of maximizing profit, reward, and welfare, there exists a deterministic FPTAS under any budget $B\in[0,1]$ , using only value oracle access to $f$ .

At a high level, our proof for profit maximization relies on discretizing the function $f$ and minimizing payments using the dynamic programming approach as in [27], while adapting the core ideas to the combinatorial-actions setting. For reward and welfare maximization, [38] noted that these problems can be reduced to the Knapsack problem. However, this is not the case in the combinatorial-actions setting, and so we use the ideas from profit maximization to solve those problems as well.

Fix an additive function $\varphi:2^{T}\to[0,1]$ with $\varphi(\emptyset)=0$ and a real number $b\in[0,1]$ . We will later specify $\varphi(S)$ to be either the reward $f(S)$ or the welfare $f(S)-c(S)$ . We begin by defining a discretization $\tilde{\varphi}$ of $\varphi$ . Let $\delta=\epsilon/|T|$ . Define $\tilde{\varphi}(S)=\sum_{a\in S}\lfloor\varphi(\{a\})/(\delta b)\rfloor(\delta b)$ . Note that $\tilde{\varphi}(S)$ is a multiple of $\delta b$ for every $S$ .

For each $j\in\{0,\ldots,n\}$ and $x\in\{0,\delta b,2\delta b,\ldots,\lceil|T|/\delta\rceil\delta b\}$ , we define

\displaystyle A^{(\varphi)}(j,x)=\min_{S,\boldsymbol{\alpha}}\left\{\sum_{i\in A% }\alpha_{i}\mid\tilde{\varphi}(S)\geq x,S\in\mathsf{NE}(\boldsymbol{\alpha}),S% \subseteq T_{1}\cup\ldots\cup T_{j}\right\}.

This table can be computed in polynomial time via dynamic programming, as we show below.

Lemma 5.2.

The table $A^{(\varphi)}$ can be computed in polynomial time in $|T|$ and $\epsilon$ .

Proof.

Observe that for $j=0$ , we have $A(0,0)=0$ and $A(0,x)=\infty$ for all $x>0$ .

Let us now fix $j>0$ . Let $T_{j}=\{a_{1},\ldots,a_{k}\}$ and assume without loss of generality that $c_{a_{1}}/f(\{a_{1}\})\leq c_{a_{2}}/f(\{a_{2}\})\leq\ldots\leq c_{a_{k}}/f(\{% a_{k}\})$ . Note that for a given payment $\alpha_{i}$ , agent $i$ ’s best response $S_{i}$ for $S_{-i}$ belongs to:

	$\displaystyle\operatorname*{arg\,max}_{S_{i}\subseteq T_{i}}\left\{\alpha_{i}% \cdot f(S_{i}\sqcup S_{-i})-c(S_{i})\right\}$	$\displaystyle=\operatorname*{arg\,max}_{S_{i}\subseteq T_{i}}\left\{\alpha_{i}% \cdot f(S_{i})+\alpha_{i}\cdot f(S_{-i})-c(S_{i})\right\}$
		$\displaystyle=\operatorname*{arg\,max}_{S_{i}\subseteq T_{i}}\left\{\alpha_{i}% \cdot f(S_{i})-c(S_{i})\right\}$
		$\displaystyle=\operatorname*{arg\,max}_{S_{i}\subseteq T_{i}}\left\{\sum_{a\in S% _{i}}(\alpha_{i}\cdot f(\{a\})-c_{a})\right\}$

Therefore, the agent’s best response includes all actions such that $c_{a}\leq\alpha_{i}\cdot f(\{a\})$ , or equivalently $c_{a}/f(\{a\})\leq\alpha_{i}$ . In particular, any contract incentivizes a prefix of $\{a_{1},\ldots,a_{k}\}$ , and hence:

\displaystyle A^{(\varphi)}(j,x)=\min_{\ell\in\{0,1,\ldots,k\}}\left\{A\left(j% -1,x-\tilde{\varphi}(\{a_{1},\ldots,a_{\ell}\})\right)+\frac{c_{a_{\ell}}}{f(% \{a_{\ell}\})}\right\},

where we treat the term $c_{a_{\ell}}/f(\{a_{\ell}\})$ as $0$ when $\ell=0$ . This completes the proof. $\hfill\blacktriangleleft$

We are now ready to prove the main theorem. Below we present the proof for profit maximization, and we defer the proofs for reward and welfare maximization to the full version.

Proof of Theorem 5.1 for Profit Maximization.

We prove the existence of an FPTAS for profit maximization under budget $B$ . First, let $(\boldsymbol{\alpha}^{\star},S^{\star})$ be the optimal contract-equilibrium pair under budget $B$ . Let $b=\max_{a\in S^{\star}}f(\{a\})$ . Note that the algorithm does not have access to $b$ , as it does not have access to the optimal solution, but there are polynomially many candidate values, and we can iterate over all of them. From now on, we assume that we know the value of $b$ .

Note that by definition $A^{(f)}(n,x)$ is increasing in $x$ . Let:

\displaystyle\overline{x}=\max_{x\in\{0,\delta b,2\delta b,\ldots,\lceil|T|/% \delta\rceil\delta b\}}\left\{x\mid A^{(f)}(n,x)\leq B\right\}\;\text{and}\;x^% {\prime}\in\operatorname*{arg\,max}_{x\in\{0,\delta b,\ldots,\overline{x}\}}(1% -A^{(f)}(n,x))\cdot x.

Let $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ be the contract-equilibrium pair (with respect to the original $f$ ) that minimizes the sum of payments in the definition of $A^{(f)}(n,x^{\prime})$ . We will argue that $(\boldsymbol{\alpha}^{\prime},S^{\prime})$ yields a $(1-\epsilon)$ -approximation to the optimal profit, which will imply the theorem.

We begin by observing that $\tilde{f}(S^{\star})\leq\lceil|T|/\delta\rceil\delta b$ and that $\tilde{f}(S^{\star})\leq\overline{x}$ . For the first inequality, note that $\tilde{f}(S^{\star})=\sum_{a\in S^{\star}}\tilde{f}(\{a\})\leq|S^{\star}|\cdot b% \leq\lceil|T|/\delta\rceil\delta b$ . For the second inequality, we have $\sum_{i\in A}\alpha_{i}^{\star}\leq B$ by the budget-feasibility of the optimal contract. Therefore, by the choice of $x^{\prime}$ , we have:

\displaystyle(1-A^{(f)}(n,\tilde{f}(S^{\star})))\cdot\tilde{f}(S^{\star})\leq(% 1-A^{(f)}(n,x^{\prime}))\cdot x^{\prime}.

(3)

Moreover, we observe that:

\displaystyle\tilde{f}(S^{\star})\geq\sum_{a\in S^{\star}}f(\{a\})-|S^{\star}|% \cdot\delta b\geq\sum_{a\in S^{\star}}f(\{a\})-\epsilon\cdot\max_{a\in S^{% \star}}f(\{a\})\geq(1-\epsilon)\cdot f(S^{\star}).

(4)

It follows that:

$\displaystyle(1-\epsilon)\cdot u_{P}(\boldsymbol{\alpha}^{\star},S^{\star})$	$\displaystyle=(1-\epsilon)\cdot\left(1-\sum_{i\in A}\alpha_{i}^{\star}\right)% \cdot f(S^{\star})$	$\displaystyle(\text{by the definition of $u_{P}$})$
	$\displaystyle\leq\left(1-\sum_{i\in A}\alpha_{i}^{\star}\right)\cdot\tilde{f}(% S^{\star})$	$\displaystyle(\text{by \lx@cref{creftypecap~refnum}{eq:tildef}})$
	$\displaystyle\leq\left(1-A(n,\tilde{f}(S^{\star}))\right)\cdot\tilde{f}(S^{% \star})$	$\displaystyle(\text{by the definition of $A$})$
	$\displaystyle\leq\left(1-A(n,x^{\prime})\right)\cdot x^{\prime}$	$\displaystyle(\text{by \lx@cref{creftypecap~refnum}{eq:choiceofx}})$
	$\displaystyle\leq\left(1-\sum_{i\in A}\alpha_{i}^{\prime}\right)\cdot\tilde{f}% (S^{\prime})$	$\displaystyle(\text{by definition of $(\boldsymbol{\alpha}^{\prime},S^{\prime}% )$})$
	$\displaystyle\leq\left(1-\sum_{i\in A}\alpha_{i}^{\prime}\right)\cdot f(S^{% \prime})$	$\displaystyle(\text{since $\tilde{f}(S)\leq f(S)$ for all $S$})$
	$\displaystyle=u_{P}(\boldsymbol{\alpha}^{\prime},S^{\prime})$	$\displaystyle(\text{by the definition of $u_{P}$})$

Therefore, our algorithm returns a $(1-\epsilon)$ -approximation, which completes the proof. $\hfill\blacktriangleleft$

References

[1] Gil Aharoni, Martin Hoefer, and Inbal Talgam-Cohen. Welfare and beyond in multi-agent contracts. In EC 2025, 2025.
[2] Tal Alon, Matteo Castiglioni, Junjie Chen, Tomer Ezra, Yingkai Li, and Inbal Talgam-Cohen. Multi-project contracts. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 580–598, 2025. doi:10.1145/3736252.3742600.
[3] Tal Alon, Paul Duetting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian analysis of linear contracts. In EC 2023, page 66, 2023. doi:10.1145/3580507.3597795.
[4] Tal Alon, Paul Dütting, and Inbal Talgam-Cohen. Contracts with private cost per unit-of-effort. In EC 2021, pages 52–69, 2021. doi:10.1145/3465456.3467651.
[5] Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In EC 2006, pages 18–28, 2006. doi:10.1145/1134707.1134710.
[6] Moshe Babaioff, Michal Feldman, and Noam Nisan. Mixed strategies in combinatorial agency. In WINE 2006, pages 353–364, 2006. doi:10.1007/11944874_32.
[7] Moshe Babaioff, Michal Feldman, and Noam Nisan. Free-riding and free-labor in combinatorial agency. In SAGT 2009, pages 109–121, 2009. doi:10.1007/978-3-642-04645-2_11.
[8] Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. Combinatorial agency. J. Econ. Theory, 147(3):999–1034, 2012. doi:10.1016/J.JET.2012.01.010.
[9] Moshe Babaioff and Eyal Winter. Contract complexity. EC, 14:911, 2014. doi:10.1145/2600057.2602852.
[10] Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning optimal contracts: How to exploit small action spaces. In ICLR 2024, 2024.
[11] Shai Bernstein and Eyal Winter. Contracting with heterogeneous externalities. American Economic Journal: Microeconomics, 4(2):50–76, 2012.
[12] Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions i: demand queries. Technical report, Discussion paper, 2005.
[13] Federico Cacciamani, Martino Bernasconi, Matteo Castiglioni, and Nicola Gatti. Multi-agent contract design beyond binary actions. In EC 2024, page 1293, 2024. doi:10.1145/3670865.3673633.
[14] Gabriel Carroll. Robustness and linear contracts. Am. Econ. Rev., 105(2):536–563, 2015.
[15] Matteo Castiglioni, Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. A reduction from multi-parameter to single-parameter bayesian contract design. In SODA 2025, pages 1795–1836, 2025. doi:10.1137/1.9781611978322.56.
[16] Matteo Castiglioni, Junjie Chen, and Yingkai Li. Fair contracts. arXiv preprint arXiv:2507.11214, 2025. doi:10.48550/arXiv.2507.11214.
[17] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian agency: Linear versus tractable contracts. In EC 2021, pages 285–286, 2021. doi:10.1145/3465456.3467602.
[18] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Designing menus of contracts efficiently: the power of randomization. In EC 2022, pages 705–735, 2022. doi:10.1145/3490486.3538270.
[19] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Multi-agent contract design: How to commission multiple agents with individual outcomes. In EC 2023, pages 412–448, 2023. doi:10.1145/3580507.3597793.
[20] Yurong Chen, Zhaohua Chen, Xiaotie Deng, and Zhiyi Huang. Are bounded contracts learnable and approximately optimal? In EC 2024, pages 315–344, 2024. doi:10.1145/3670865.3673483.
[21] Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. Theoretical Computer Science, 980:114219, 2023. doi:10.1016/J.TCS.2023.114219.
[22] Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, and Aditya Prasad. On supermodular contracts and dense subgraphs. In SODA 2024, pages 109–132, 2024. doi:10.1137/1.9781611977912.6.
[23] Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler, and Inbal Talgam-Cohen. An algorithm-to-contract framework without demand queries. arXiv preprint arXiv:2507.20038, 2025. doi:10.48550/arXiv.2507.20038.
[24] Paul Duetting, Michal Feldman, Tomasz Ponitka, and Ermis Soumalias. The pseudo-dimension of contracts. In EC 2025, 2025.
[25] Paul Duetting, Michal Feldman, and Yarden Rashti. Succinct ambiguous contracts. arXiv preprint arXiv:2503.02592, 2025. doi:10.48550/arXiv.2503.02592.
[26] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In FOCS 2021, pages 815–826, 2021. doi:10.1109/FOCS52979.2021.00084.
[27] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In STOC 2023, pages 1311–1324, 2023. doi:10.1145/3564246.3585193.
[28] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combinatorial contracts. In SODA 2025, pages 1857–1891, 2025. doi:10.1137/1.9781611978322.58.
[29] Paul Dütting, Michal Feldman, and Yoav Gal-Tzur. Combinatorial contracts beyond gross substitutes. In SODA 2024, pages 92–108, 2024. doi:10.1137/1.9781611977912.5.
[30] Paul Dütting, Michal Feldman, Yoav Gal-Tzur, and Aviad Rubinstein. When contracts get complex: Information-theoretic barriers. In SODA 2026, 2026.
[31] Paul Dütting, Michal Feldman, Daniel Peretz, and Larry Samuelson. Ambiguous contracts. Econometrica, 92(6):1967–1992, 2024.
[32] Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic contract theory: A survey. Found. Trends Theor. Comput. Sci., 16(3-4):211–412, 2024. doi:10.1561/0400000113.
[33] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In EC 2019, pages 369–387, 2019. doi:10.1145/3328526.3329591.
[34] Tomer Ezra, Michal Feldman, and Maya Schlesinger. On the (in)approximability of combinatorial contracts. In ITCS, volume 287 of LIPIcs, pages 44:1–44:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.44.
[35] Tomer Ezra, Michal Feldman, and Maya Schlesinger. Contract design for sequential actions. In SODA 2026, 2026.
[36] Tomer Ezra, Stefano Leonardi, and Matteo Russo. Contracts with inspections. In SODA 2026, 2026.
[37] Michal Feldman. Combinatorial contract design: Recent progress and emerging frontiers. arXiv preprint arXiv:2510.15065, 2025. doi:10.48550/arXiv.2510.15065.
[38] Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. Budget-feasible contracts. In EC 2025, pages 353–353, 2025.
[39] Michal Feldman and Liat Yashin. Ultra-efficient contracts: Breaking the substitutes barrier in combinatorial contracts. arXiv preprint arXiv:2506.18008, 2025. doi:10.48550/arXiv.2506.18008.
[40] Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. Springer, 1992.
[41] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1):95–124, 1999.
[42] Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In EC 2021, pages 563–582, 2021. doi:10.1145/3465456.3467637.
[43] Guru Guruganesh, Jon Schneider, Joshua R. Wang, and Junyao Zhao. The power of menus in contract design. In EC 2023, pages 818–848, 2023. doi:10.1145/3580507.3597735.
[44] Wade Hann-Caruthers and Sumit Goel. Optimality of weighted contracts for multi-agent contract design with a budget. In EC 2024, page 1295, 2024. doi:10.1145/3670865.3673598.
[45] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In EC 2014, pages 359–376, 2014. doi:10.1145/2600057.2602880.
[46] Bengt Holmström. Moral hazard and observability. The Bell Journal of Economics, pages 74–91, 1979.
[47] Bengt Holmstrom. Moral hazard in teams. The Bell Journal of Economics, 13(2):324–340, 1982.
[48] Robert D Innes. Limited liability and incentive contracting with ex-ante action choices. Journal of economic theory, 52(1):45–67, 1990.
[49] Kelso Jr, Alexander S and Crawford, Vincent P. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pages 1483–1504, 1982.
[50] Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav., 55(2):270–296, 2006. doi:10.1016/J.GEB.2005.02.006.
[51] Renato Paes Leme. Gross substitutability: An algorithmic survey. Games and Economic Behavior, 106:294–316, 2017. doi:10.1016/J.GEB.2017.10.016.
[52] Bo Peng and Zhihao Gavin Tang. Optimal robust contract design. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 1294–1294, 2024.
[53] Stephen A Ross. The economic theory of agency: The principal’s problem. The American economic review, 63(2):134–139, 1973.
[54] Royal Swedish Academy of Sciences. Scientific background on the 2016 nobel prize in economic, 2016.
[55] Ilya Segal. Contracting with externalities. The Quarterly Journal of Economics, 114(2):337–388, 1999.
[56] Ilya Segal. Coordination and discrimination in contracting with externalities: Divide and conquer? Journal of Economic Theory, 113(2):147–181, 2003. doi:10.1016/S0022-0531(03)00114-5.
[57] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In EC 2023, page 1188, 2023. doi:10.1145/3580507.3597673.

[bib.bib1] [1] Gil Aharoni, Martin Hoefer, and Inbal Talgam-Cohen. Welfare and beyond in multi-agent contracts. In EC 2025, 2025.

[bib.bib2] [2] Tal Alon, Matteo Castiglioni, Junjie Chen, Tomer Ezra, Yingkai Li, and Inbal Talgam-Cohen. Multi-project contracts. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 580–598, 2025. doi:10.1145/3736252.3742600.

[bib.bib3] [3] Tal Alon, Paul Duetting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian analysis of linear contracts. In EC 2023, page 66, 2023. doi:10.1145/3580507.3597795.

[bib.bib4] [4] Tal Alon, Paul Dütting, and Inbal Talgam-Cohen. Contracts with private cost per unit-of-effort. In EC 2021, pages 52–69, 2021. doi:10.1145/3465456.3467651.

[bib.bib5] [5] Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In EC 2006, pages 18–28, 2006. doi:10.1145/1134707.1134710.

[bib.bib6] [6] Moshe Babaioff, Michal Feldman, and Noam Nisan. Mixed strategies in combinatorial agency. In WINE 2006, pages 353–364, 2006. doi:10.1007/11944874_32.

[bib.bib7] [7] Moshe Babaioff, Michal Feldman, and Noam Nisan. Free-riding and free-labor in combinatorial agency. In SAGT 2009, pages 109–121, 2009. doi:10.1007/978-3-642-04645-2_11.

[bib.bib8] [8] Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. Combinatorial agency. J. Econ. Theory, 147(3):999–1034, 2012. doi:10.1016/J.JET.2012.01.010.

[bib.bib9] [9] Moshe Babaioff and Eyal Winter. Contract complexity. EC, 14:911, 2014. doi:10.1145/2600057.2602852.

[bib.bib10] [10] Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning optimal contracts: How to exploit small action spaces. In ICLR 2024, 2024.

[bib.bib11] [11] Shai Bernstein and Eyal Winter. Contracting with heterogeneous externalities. American Economic Journal: Microeconomics, 4(2):50–76, 2012.

[bib.bib12] [12] Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions i: demand queries. Technical report, Discussion paper, 2005.

[bib.bib13] [13] Federico Cacciamani, Martino Bernasconi, Matteo Castiglioni, and Nicola Gatti. Multi-agent contract design beyond binary actions. In EC 2024, page 1293, 2024. doi:10.1145/3670865.3673633.

[bib.bib14] [14] Gabriel Carroll. Robustness and linear contracts. Am. Econ. Rev., 105(2):536–563, 2015.

[bib.bib15] [15] Matteo Castiglioni, Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. A reduction from multi-parameter to single-parameter bayesian contract design. In SODA 2025, pages 1795–1836, 2025. doi:10.1137/1.9781611978322.56.

[bib.bib16] [16] Matteo Castiglioni, Junjie Chen, and Yingkai Li. Fair contracts. arXiv preprint arXiv:2507.11214, 2025. doi:10.48550/arXiv.2507.11214.

[bib.bib17] [17] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian agency: Linear versus tractable contracts. In EC 2021, pages 285–286, 2021. doi:10.1145/3465456.3467602.

[bib.bib18] [18] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Designing menus of contracts efficiently: the power of randomization. In EC 2022, pages 705–735, 2022. doi:10.1145/3490486.3538270.

[bib.bib19] [19] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Multi-agent contract design: How to commission multiple agents with individual outcomes. In EC 2023, pages 412–448, 2023. doi:10.1145/3580507.3597793.

[bib.bib20] [20] Yurong Chen, Zhaohua Chen, Xiaotie Deng, and Zhiyi Huang. Are bounded contracts learnable and approximately optimal? In EC 2024, pages 315–344, 2024. doi:10.1145/3670865.3673483.

[bib.bib21] [21] Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. Theoretical Computer Science, 980:114219, 2023. doi:10.1016/J.TCS.2023.114219.

[bib.bib22] [22] Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, and Aditya Prasad. On supermodular contracts and dense subgraphs. In SODA 2024, pages 109–132, 2024. doi:10.1137/1.9781611977912.6.

[bib.bib23] [23] Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler, and Inbal Talgam-Cohen. An algorithm-to-contract framework without demand queries. arXiv preprint arXiv:2507.20038, 2025. doi:10.48550/arXiv.2507.20038.

[bib.bib24] [24] Paul Duetting, Michal Feldman, Tomasz Ponitka, and Ermis Soumalias. The pseudo-dimension of contracts. In EC 2025, 2025.

[bib.bib25] [25] Paul Duetting, Michal Feldman, and Yarden Rashti. Succinct ambiguous contracts. arXiv preprint arXiv:2503.02592, 2025. doi:10.48550/arXiv.2503.02592.

[bib.bib26] [26] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In FOCS 2021, pages 815–826, 2021. doi:10.1109/FOCS52979.2021.00084.

[bib.bib27] [27] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In STOC 2023, pages 1311–1324, 2023. doi:10.1145/3564246.3585193.

[bib.bib28] [28] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent combinatorial contracts. In SODA 2025, pages 1857–1891, 2025. doi:10.1137/1.9781611978322.58.

[bib.bib29] [29] Paul Dütting, Michal Feldman, and Yoav Gal-Tzur. Combinatorial contracts beyond gross substitutes. In SODA 2024, pages 92–108, 2024. doi:10.1137/1.9781611977912.5.

[bib.bib30] [30] Paul Dütting, Michal Feldman, Yoav Gal-Tzur, and Aviad Rubinstein. When contracts get complex: Information-theoretic barriers. In SODA 2026, 2026.

[bib.bib31] [31] Paul Dütting, Michal Feldman, Daniel Peretz, and Larry Samuelson. Ambiguous contracts. Econometrica, 92(6):1967–1992, 2024.

[bib.bib32] [32] Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic contract theory: A survey. Found. Trends Theor. Comput. Sci., 16(3-4):211–412, 2024. doi:10.1561/0400000113.

[bib.bib33] [33] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In EC 2019, pages 369–387, 2019. doi:10.1145/3328526.3329591.

[bib.bib34] [34] Tomer Ezra, Michal Feldman, and Maya Schlesinger. On the (in)approximability of combinatorial contracts. In ITCS, volume 287 of LIPIcs, pages 44:1–44:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.44.

[bib.bib35] [35] Tomer Ezra, Michal Feldman, and Maya Schlesinger. Contract design for sequential actions. In SODA 2026, 2026.

[bib.bib36] [36] Tomer Ezra, Stefano Leonardi, and Matteo Russo. Contracts with inspections. In SODA 2026, 2026.

[bib.bib37] [37] Michal Feldman. Combinatorial contract design: Recent progress and emerging frontiers. arXiv preprint arXiv:2510.15065, 2025. doi:10.48550/arXiv.2510.15065.

[bib.bib38] [38] Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. Budget-feasible contracts. In EC 2025, pages 353–353, 2025.

[bib.bib39] [39] Michal Feldman and Liat Yashin. Ultra-efficient contracts: Breaking the substitutes barrier in combinatorial contracts. arXiv preprint arXiv:2506.18008, 2025. doi:10.48550/arXiv.2506.18008.

[bib.bib40] [40] Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. Springer, 1992.

[bib.bib41] [41] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic theory, 87(1):95–124, 1999.

[bib.bib42] [42] Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In EC 2021, pages 563–582, 2021. doi:10.1145/3465456.3467637.

[bib.bib43] [43] Guru Guruganesh, Jon Schneider, Joshua R. Wang, and Junyao Zhao. The power of menus in contract design. In EC 2023, pages 818–848, 2023. doi:10.1145/3580507.3597735.

[bib.bib44] [44] Wade Hann-Caruthers and Sumit Goel. Optimality of weighted contracts for multi-agent contract design with a budget. In EC 2024, page 1295, 2024. doi:10.1145/3670865.3673598.

[bib.bib45] [45] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In EC 2014, pages 359–376, 2014. doi:10.1145/2600057.2602880.

[bib.bib46] [46] Bengt Holmström. Moral hazard and observability. The Bell Journal of Economics, pages 74–91, 1979.

[bib.bib47] [47] Bengt Holmstrom. Moral hazard in teams. The Bell Journal of Economics, 13(2):324–340, 1982.

[bib.bib48] [48] Robert D Innes. Limited liability and incentive contracting with ex-ante action choices. Journal of economic theory, 52(1):45–67, 1990.

[bib.bib49] [49] Kelso Jr, Alexander S and Crawford, Vincent P. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pages 1483–1504, 1982.

[bib.bib50] [50] Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav., 55(2):270–296, 2006. doi:10.1016/J.GEB.2005.02.006.

[bib.bib51] [51] Renato Paes Leme. Gross substitutability: An algorithmic survey. Games and Economic Behavior, 106:294–316, 2017. doi:10.1016/J.GEB.2017.10.016.

[bib.bib52] [52] Bo Peng and Zhihao Gavin Tang. Optimal robust contract design. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 1294–1294, 2024.

[bib.bib53] [53] Stephen A Ross. The economic theory of agency: The principal’s problem. The American economic review, 63(2):134–139, 1973.

[bib.bib54] [54] Royal Swedish Academy of Sciences. Scientific background on the 2016 nobel prize in economic, 2016.

[bib.bib55] [55] Ilya Segal. Contracting with externalities. The Quarterly Journal of Economics, 114(2):337–388, 1999.

[bib.bib56] [56] Ilya Segal. Coordination and discrimination in contracting with externalities: Divide and conquer? Journal of Economic Theory, 113(2):147–181, 2003. doi:10.1016/S0022-0531(03)00114-5.

[bib.bib57] [57] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In EC 2023, page 1188, 2023. doi:10.1145/3580507.3597673.

	$\displaystyle f_{1}(S)$	$\displaystyle=\max\left((1/2)\cdot\textbf{1}[\mathcal{G}\in S],\varepsilon% \cdot\textbf{1}[\mathcal{B}\in S]\right)$
	$\displaystyle f_{2}(S)$	$\displaystyle=\varepsilon\cdot\min\left(\|S\setminus\{\mathcal{G}\}\|,n/2+1\right)$
	$\displaystyle f_{3}(S,A^{\prime})$	$\displaystyle=(\varepsilon/2)\cdot\textbf{1}[S=\{\mathcal{B}\}\cup A^{\prime}]$

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Our Results

Inapproximability for Submodular Instances

Theorem 1 (Inapproximability for Submodular Instances; Theorem 3.1).

Constant-Factor Approximation for Gross Substitutes Instances

Theorem 2 (Constant-Factor Approximation for Gross Substitutes Instances; Corollary 4.2).

Discussion: A Three-Way Barrier to Approximation

FPTAS for Special Cases

Theorem 3 (FPTAS for Additive Instances; Theorem 5.1).

Theorem 4 (FPTAS for Single-Agent Instances).

1.2 Our Techniques

Inapproximability for Submodular Instances

Constant-Factor Approximation for Gross Substitutes Instances

1.3 Related Work

Combinatorial Contracts

Linear Contracts

Contracts under Budget Constraints

Other Contractual Models

2 Model and Preliminaries

2.1 The Multi-Agent Combinatorial-Actions Setting

Utilities and Equilibria.

Maximizing Profit Under Budget Constraints.

Subset Stability and the Doubling Lemma.

Definition 2.1 (Subset Stability, Definition 3.2 of [28]).

Lemma 2.2 (Doubling Lemma, Lemma 3.3 of [28]).

Restricted Contracts.

Reward Functions and Access Oracles.

2.2 Objectives and Maximization Problems

Definition 2.3 (Objectives in the Multi-Agent Combinatorial-Actions Model).

Definition 2.4 (BEST Objectives).

3 Inapproximability Result for Submodular Instances

Theorem 3.1 (Inapproximability for Submodular Instances).

Corollary 3.2 (Exponential Lower Bound on Expected Approximation Ratio).

Definition 3.3 (Parameterized Instances).

Lemma 3.4.

Lemma 3.5.

Proof.

Lemma 3.6.

Proof.

Lemma 3.7.

Proof.

Proof of Theorem 3.1.

4 Constant-Factor Approximation for Gross Substitutes Instances

Theorem 4.1 (Equivalence of All BEST Objectives and Budgets).

Corollary 4.2 (Constant-Factor Approximations Under Budget Constraints).

4.1 Best-Response Monotonicity for Gross Substitutes Instances

Lemma 4.3 (Best-Response Monotonicity).

Proof.

Corollary 4.4.

Lemma 4.5 (Downsizing Lemma for Combinatorial Actions).

4.2 BEST Objectives Are Equivalent

Definition 4.6 (Best-Singlei⁢-⁢φ⁢(B)).

Definition 4.7 (Max-Reward-Bounded⁢(B)).

Lemma 4.8 (Decomposition Lemma).

Proof.

Lemma 4.9.

Lemma 4.10 (Reduction to Max-Reward-Bounded⁢(B)).

Proof.

Lemma 4.11 (Reduction from Max-Reward-Bounded⁢(B)).

Proof.

5 FPTAS for Additive Instances

Theorem 5.1.

Lemma 5.2.

Proof.

Proof of Theorem 5.1 for Profit Maximization.

References

Definition 4.6 ( $\textsc{Best-Single}_{i}\textsc{-}\varphi(B)$ ).

Definition 4.7 ( $\textsc{Max-Reward-Bounded}(B)$ ).

Lemma 4.10 (Reduction to $\textsc{Max-Reward-Bounded}(B)$ ).

Lemma 4.11 (Reduction from $\textsc{Max-Reward-Bounded}(B)$ ).