\section{Submodular with Value Queries}\label{app:extension-to-submodular}

In this appendix we show how to adjust the proof of Theorem~\ref{thm:xos} in Section~\ref{sec:sm-and-xos} to submodular reward functions with value queries.

\subsection{Approximate Demand Query via Value Queries}

Our adjusted argument relies on the ability to compute an approximate demand set as formalized in the following lemma.

\begin{lemma}[\cite{SviridenkoVW17,Harshaw19a}]
\label{lem:approx-demand}
For submodular $f$ given access to a value oracle, there exists a poly-time algorithm that finds a set $S$  such that
\[
f(S) - \sum_{i \in S} p_i \geq (1-1/e)f(T) - \sum_{i \in T} p_i \quad \text{for all $T$.}
\]
\end{lemma}

We call the set $S$ a $\beta$-approximate demand set, where $\beta = 1-1/e$. Note that this notion of an approximate demand query is not a fully multiplicative approximation, it's weaker in that we need to subtract the full price of a set.

\subsection{Adjusting the Proof to Approximate Demand Queries}

We next show how to adapt our proof to the case of submodular $f$, using only value oracle calls.
To do so, we first show that if we modify Algorithm~\ref{alg:xos-contract-estimate} so that (1) we  initialize  $\Psi$ to be $\Psi=\frac{\beta^2 \cdot \tilde{y}}{32}-\max_{i\in A'} f(i)$, (2) we initialize  the prices to be $p_i=\frac{\beta}{2}\cdot \sqrt{c_i\cdot\tilde{y}}$, (3) we replace the initialization of $T$ to be a $\beta$-approximate demand set instead of an exact demand set (which can be done for $\beta = 1-\frac{1}{e}$ using value oracle by Lemma~\ref{lem:approx-demand}),
and (4) we remove actions with negative utility from $T$, then the algorithm returns  a set $U$ with the following guarantee:

\begin{lemma}
Algorithm~\ref{alg:submod-contract-estimate} runs in polynomial time with access to a demand and value oracle to $f$.
If $\tilde{y} \leq f(S^\star \cap A' )$, then the set $U \subseteq A'$ that it returns satisfies
\[
g(U) \geq \max\left\{\frac{\tilde{y}}{128}  - \frac{\max_{i \in A'} f(\{i\})}{4},0\right\}.
\]
\label{lem:gu128sub}
\end{lemma}

\label{app:lemma}
\input{app-lemma}

We next show that Algorithm~\ref{alg:xos-contract} that uses as a subroutine the modified algorithm (Algorithm~\ref{alg:submod-contract-estimate})  fulfills Theorem~\ref{thm:xos}.
\begin{proof}[Proof of Theorem~\ref{thm:xos} for the case of submodular]

If $f(S^\star\cap A') \leq {\frac{128 \xi}{\beta^2}} \cdot \max\{0,\max_{i\in A} g(\{i\}\}$ then by Lemma~\ref{lem:onebigagent} the best single action (or the empty set) gives at least an approximation of $\frac{\beta^2}{{128\xi+ \beta^2}}$. Else, $A' \neq \emptyset$ (thus $\Psi$ is well defined), and  it holds that
\[f(S^\star\capA')  \geq {\frac{128 \xi}{\beta^2}} \cdot \max\{0,\max_{i\in A'} g(\{i\})\} \geq \max_{i\in A'} f(\{i\})/2\geq \Psi,
\]
and  $ f(S^\star\cap A') \leq 2n \cdot \Psi$.

Let $j^\star$ be the unique $j$ in which $x_j \leq f(S^\star \cap A') < \xi \cdot x_j$.  Note that because of the bounds we just established we must have $j^\star\geq 0$ and $j^\star\leq \lceil\log_{\xi} 2n\rceil$. Now, since $ \frac{1}{\xi} \cdot f(S^\star \cap A') \leq x_j \leq f(S^\star \cap A')$,
\begin{eqnarray*}
g(U^{(j^\star)})    & \geq &  \frac{{\beta^2}x_{j^\star}}{128} - \frac{\max_{i\in A'} f(\{i\})}{4}  \\
&\geq & \frac{{\beta^2} f(S^\star\cap A')}{128\cdot \xi} - \frac{\max_{i\in A} g(\{i\})}{2}  \geq  {\beta^2} f(S^\star\cap A')\cdot \left(\frac{1}{128\cdot \xi} - \frac{1}{256\cdot \xi} \right) \\  & \geq &
{\beta^2}\frac{{\frac{128\xi}{\beta^2}} \cdot g(S^\star)}{{\frac{128\xi}{\beta^2}}+1}\frac{1}{256\cdot \xi} = \frac{\beta^2 \cdot g(S^\star)}{{256\xi+ 2\cdot \beta^2}},
\end{eqnarray*}
where the first inequality is by Lemma~\ref{lem:gu128sub}, the second inequality is since for every $i\in A'$ it holds that $\frac{c_i}{f(\{i\})}\leq \frac{1}{2}$ and thus $g(\{i\}) = f(\{i\})(1-\frac{c_i}{f(\{i\})}) \geq f(\{i\})/2$, the third and fourth inequalities are since we are considering the case that $f(S^\star\cap A') > {\frac{128 \xi}{\beta^2}} \cdot \max\{0,\max_{i\in A} g(\{i\})\}$.
This  gives an approximation of {$\frac{\beta^2}{256\xi+2\cdot \beta^2}$}.
\end{proof}

\section{Proof of Theorem~\ref{thm:xos-upper}}
\section{Inapproximability for XOS Reward Functions}
\label{app:upper-xos}

In this appendix, we provide details for the proof of Theorem~\ref{thm:xos-upper}. The claims, observations, and lemmas below refer to the function $f$ and $f_T$ defined in the proof of the theorem.

\begin{claim} \label{cl:f-xos}
For every $T$, the function $f_T$ is XOS.
\end{claim}

\begin{proof}
Consider the set of additive functions where there is for every agent $i
\in A$ an additive function $a_i$ such that $a_i(i) = 1+\frac{3}{n}$, and $a_i(j)=\frac{3}{n}$ for every $j\neq i$, and there is another additive function $a_i'$, where $a_i'(i)=0.5+\frac{4}{n}$, and $a_i'(j) = \frac{4}{n}$ for every $j\neq i$.
It is easy to verify that the maximum over $\{a_i,a_i'\}_{i\in A}$ is the function $f$.
To create $f_T$, we add another additive function $a_T$, where $a_T(i) = \frac{5}{n} \cdot \indicator{i\in T}$.
It holds that $a_T(T) = \frac{n+2}{2} \cdot \frac{5}{n} = 2.5+ \frac{5}{n}=f_T(T)$, and it holds that $a_T(S) \leq f_T(S)$ for every $S\neq T$,
since (1) If $|S| >n/2+1$, then $a_T(S) \leq a_T(T) = 2.5+ \frac{5}{n} \leq f_T(S)$. (2) If $|S| =n/2+1$ and $S \neq T$, then $a_T(S)  \leq \frac{n}{2} \cdot \frac{5}{n}  \leq f_T(S)$. (3) If $|S|< n/2+1$, then $a_T(S) \leq  |S| \cdot \frac{5}{n}  \leq f_T(S)$.
Thus $f_T$ is the maximum of $\{a_i,a_i'\}_{i\in A} \cup \{a_T\}$.
\end{proof}

\begin{lemma}\label{lem:onlyTXOS}
We have that $g_T(T) \geq \frac{5}{4}$ and $g_T(S) \leq \frac{11}{10}$ for all $S \neq T$.
\end{lemma}
\begin{proof}
First note that for every $i \in T$, $f_T(i \mid T \setminus \{i\})=\frac{5}{n}$.
Thus, $g_T(T)=f_T(T)\left(1-\sum_{i\in T}\frac{c_i}{f_T(i \mid T \setminus \{i\})}\right) = (2.5+\frac{5}{n})\cdot (1-\frac{1}{2}) \geq \frac{5}{4}$.
Next, consider any $S \neq T$. We can distinguish the following cases.
\begin{itemize}
    \item If $|S|\leq 1$, then $g_T(S)\leq f_T(S) \leq  1+\frac{3}{n}$.
    \item If $1 < |S| \leq \frac{n}{2}$, then $f_T(i \mid S \setminus \{i\}) = \frac{3}{n}$, thus
    $$
    g_T(S) = f_T(S)\left(1-\sum_{i\in S}\frac{c_i}{f_T(i \mid S \setminus \{i\})}\right) = \left(1+\frac{3\cdot |S|}{n}\right)\cdot \left(1-\frac{5\cdot |S|}{  3\cdot(n+2)}\right)\leq \frac{11}{10},
    $$
    where the last inequality holds for large enough $n$ and any $|S|\leq \frac{n}{2}$.
    \item If $|S| \geq \frac{n}{2}+1$ and $S\neq T$, then
    $f_T(i \mid S \setminus \{i\}) \leq \frac{4}{n}$ for all $i\in S$, thus
    $$g_T(S)\leq \left(1/2 +\frac{4\cdot |S|}{n}\right)\left(1-\sum_{i\in S}\frac{c_i}{f_T(i \mid S \setminus \{i\})}\right) \leq \left(1/2 +\frac{4\cdot |S|}{n}\right)\left(1-\frac{5\cdot |S|}{  4\cdot(n+2)}\right)\leq \frac{11}{10},$$
    where the last inequality holds for large enough $n$ and any $|S|\geq \frac{n}{2}+1$.
\end{itemize}
Hence for any $S \neq T$ it holds that $g_T(S) \leq \frac{11}{10}$.
\end{proof}

\begin{lemma} \label{lem:size-dem-xos}
For every vector of prices $p=(p_1,\ldots,p_n)$,
the set of $\{T^\star \mid D(f,p) \neq D(f_{T^\star},p)\}$ is at most of size $n^{29}$, where $D(f,p)$  (resp. $D(f_{T^\star},p)$) is the demand set\footnote{For simplicity of the proof, we assume that when there are multiple sets  in demand, the tie breaking is consistent across all $f_T$.} of function $f$ (resp. $f_{T^\star}$) with respect to prices $p$.
\end{lemma}
\begin{proof}

Let $S_p=\{i \mid p_i \leq \frac{3.25}{n}\}$, and $B_p=\{i \mid p_i \geq \frac{3.5}{n}\}$.

\begin{claim}
If $|B_p| \leq n/2 -3$, then for every $T$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:big-xos}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the value of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$, then, {because $|A \setminus B_p| \geq n/2+3$ and $|T| = n/2+1$}, the set $\Delta:= A \setminus B_p \setminus T $ is of size at least $2$. Let $x,y$ be four arbitrary different elements in $\Delta$, {and note that for these $p(x) <\frac{3.5}{n}$ and $p(y) < \frac{3.5}{n}$}.
Now $f(T\cup \{x,y\}) - p(T\cup \{x,y\}) \geq \frac{7}{n}+ f(T) -p(T) -p(x)-p(y) > f(T)-p(T)$, which contradicts that $T$ is the demand set.
\end{proof}

\begin{claim}
If $|S_p| \leq n/2 - 8$, then for every $T$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:small-xos}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the values of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$, then the set $\Delta:= T \setminus S_p  $ is of size at least $9$. Let $X$ be  an arbitrary subset of  $\Delta$ of size $9$. It holds that
$$f(T\setminus X)-p(T \setminus X) = f(T)-\frac{29}{n} - p(T) + p(X) \geq f(T)-p(T) +\frac{3.25 \cdot |X|}{n} -\frac{29}{n}  >  f(T)-p(T),$$
which contradicts that $T$ is the demand set.
\end{proof}

\begin{claim}
If  $|S_p| > n/2 - 8$ and  $|B_p| > n/2 -3$, then for all $T \notin \{S \mid (|S| =n/2+1) \wedge (|S\setminus SP_p| \leq 14) \}$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:mixed-xos}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the values of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$,
it holds that the set $\Delta_1:= B_p \cap T $ is of size at least of size $5$ since $|B_p \cap T| \geq |T\setminus S_p| -|A \setminus B_p \setminus S_p| \geq 14-9 =5 $, and the set $\Delta_{{2}}:= S_p \setminus T $ is of size at least $6$ since $|S_p \setminus T| = |T \setminus S_p | -  |T| +|S_p| \geq 14 - 8  =6.$
Let $X$ be  an arbitrary subset of  $\Delta_1$ of size $5$ and let $Y$ be an arbitrary subset of $\Delta_2$ of size $5$. It holds that
$$f((T\setminus X) \cup Y)-p((T \setminus X) \cup Y) = f(T)-\frac{1}{n}- p(T) + p(X) -p(Y) \geq f(T)-p(T) +\frac{|X|}{4n} -\frac{1}{n}  >  f(T)-p(T),$$
which contradicts that $T$ is the demand set.
\end{proof}

By combining Claim~\ref{cl:big-xos} and Claim~\ref{cl:small-xos},
{a demand query can only reveal information about $T$ if}
$|S_p| > n/2 - 8$ and  $|B_p| > n/2 -3$, and even then, by Claim~\ref{cl:mixed-xos},
{a demand query}
cannot distinguish between $T$'s not in $\{S \mid (|S| =n/2+1) \wedge (|S\setminus S_p| \leq 14) \}$.
{Now,} the lemma follows since for every choice of $S_p$ of {size} greater than $n/2-8$, the set $\{S \mid (|S| =n/2+1) \wedge (|S\setminus S_p| \leq 14) \}$ is at most of size $n^{29}$.
(One can bound it by counting the options to select  a set $S\setminus S_p$ of size at most $14$ and then select a set  $S_p\setminus S$ which is of size at most $15$ since $|S_p\setminus S| = |S\setminus S_p| +|S_p|-|S| \leq 14 + n - |B_p| - (n/2+1) \leq 14 +n - (n/2-2)-(n/2+1)  = 15$.)
\end{proof}

\section{Additive Reward Functions}\label{app:additive}

In this appendix we show that it is NP-hard to find the best contract for additive $f$, but it is possible to find an FPTAS for approximating the best contract.

\subsection{NP-hardness}
\begin{proposition}\label{prop:hardness-for-additive}
The optimal contract problem for additive reward functions over $n$ agents is NP-hard.
\end{proposition}

\begin{proof}
The proof is by reduction from \textsf{PARTITION}. We are given a multi-set  $\{w_1, \ldots, w_n\}$ of positive integers $w_j > 0$ with $\sum_{j = 1}^{n} w_j = W$, and have to decide whether $[n]$ can be partitioned into $I_1$ and $I_2 = [n] \setminus I_1$ such that $\sum_{j \in I_1} w_j = \sum_{j \in I_2} w_j = W/2.$

The corresponding contract problem is: $f$ is additive over $n$ agents, where agent $i$ has a value of $v_i = w_i$ and a cost $c_i = w_i^2/W $.
Since agent $i$'s marginal is $v_i$,
the indifference point for agent $i$ is $\alpha_i = c_i/v_i = w_i/W$. The principal's utility for incentivizing a set of
agents
$S \subseteq [n]$ is
\[
g(S) = \left(1- \sum_{i \in S} \frac{w_i}{W}\right) \cdot \sum_{i \in S} w_i.
\]
$g$ is maximized when $\sum_{i \in S} w_i$ is closest to $W/2$.
Thus, instance $\{w_1,\ldots,w_n\}$ is a yes-instance, if and only if $g(S^\star) = \frac{W}{4}$.
\end{proof}

\subsection{FPTAS}

\begin{proposition}\label{prop:fptas-for-additive}
There is an FPTAS for the optimal contract problem for an additive reward functions over $n$ agents.
\end{proposition}

Suppose we know $b = \max_{i \in S^\star} f(\{i\})$. We can assume this because there are only $n$ choices and can run the following algorithm with each choice.

Let $\delta = \frac{\epsilon}{n}$ and define an additive function $\tilde{f}$ by rounding down each $f(\{i\})$ to the next multiple of $\delta b$. That is, $\tilde{f}(\{i\}) = \left\lfloor \frac{f(\{i\})}{\delta b} \right\rfloor \delta b$ and $\tilde{f}(S) = \sum_{i \in S} \tilde{f}(\{i\})$. This way, each $\tilde{f}(S)$ is a
multiple of $\delta b$.

Let $T_x$ be the set $S$ that minimizes $\sum_{i \in S} \frac{c_i}{f(\{i\})}$ subject to $\tilde{f}(T) \geq x$. Our algorithm returns the set $T_x$ that maximizes $\left( 1 - \sum_{i \in T_x} \frac{c_i}{f(\{i\})}\right) x$ among all $x = k \delta b$ for $k \in \{0, 1, \ldots, \lceil \frac{n}{\delta} \rceil\}$.

\begin{claim}
The algorithm can be implemented in polynomial time in $n$ and $\frac{1}{\epsilon}$.
\end{claim}

\begin{proof}
Observe that we only need to compute polynomially many sets $T_x$. Furthermore, these sets can be computed by dynamic programming in polynomial time.

To this end, let $A(j, x) = \min\left\{ \sum_{i \in S} \frac{c_i}{f(\{i\})} \mid S \subseteq \{1, \ldots, j\}, \tilde{f}(S) \geq x \right\}$, $A(0, x) = 0$ if $x \leq 0$ and $A(0, x) = \infty$ if $x > 0$. Observe that
\[
A(j, x) = \min\left\{A(j-1,x), A(j-1, x-\tilde{f}(\{i\})) + \frac{c_i}{f(\{i\})}\right\},
\]
which completes the proof.
\end{proof}

\begin{claim}
The algorithm computes a $(1-\epsilon)$-approximation {to the optimal contract}.
\end{claim}

\begin{proof}
Note that for every set $S$, we have $\tilde{f}(S) \leq f(S)$. Therefore for every set $T_x$
\[
g(T_x) = \left( 1 - \sum_{i \in T_x} \frac{c_i}{f(\{i\})}\right) f(T_x) \geq \left( 1 - \sum_{i \in T_x} \frac{c_i}{f(\{i\})}\right) x.
\]

In particular, for the set $T_x$ that we return, we have
\[
\left( 1 - \sum_{i \in T_x} \frac{c_i}{f(\{i\})}\right) x \geq \left( 1 - \sum_{i \in T_{\tilde{f}(S^\star)}} \frac{c_i}{f(\{i\})}\right) \tilde{f}(S^\star) \geq \left( 1 - \sum_{i \in S^\star} \frac{c_i}{f(\{i\})}\right) \tilde{f}(S^\star)
\]
because $\tilde{f}(S^\star) = k \delta b$ for some $k$ in the range.

Finally, observe that we have
\[
\tilde{f}(S^\star) = \sum_{i \in S^\star} \tilde{f}(\{i\}) \geq \sum_{i \in S^\star} (f(\{i\}) - \delta b) {\geq} f(S^\star) - n \delta b \geq (1-\epsilon) f(S^\star).
\]
Therefore
\[
(1-\epsilon) g(S^\star) \leq \left( 1 - \sum_{i \in S^\star} \frac{c_i}{f(\{i\})} \right) \tilde{f}(S^\star),
\]
{as claimed.}
\end{proof}

\section{Non-Separable, Beyond Submodular}
\section{Inapproximability Results for XOS and Subadditive}
\label{sec:beyond-submodular}

In this section, we present our main inapproximability results. We show a lower bound of $\Omega(\sqrt{n})$ for subadditive reward functions, and a constant lower bound for XOS reward functions (both with demand queries).

A striking feature of both of these results is that the reward functions used in the proofs are constant-factor close to submodular
(see Observation~\ref{obs:subadditive-close})

\subsection{Inapproximability Result for Subadditive}

We begin by stating and proving our inapproximability result for subadditive reward functions.

\begin{theorem}\label{thm:subadditive-demand}
For every randomized algorithm that performs only polynomially many value and demand queries, there is a subadditive function $f$ such that the approximation ratio is $\Omega(\sqrt{n})$ with high probability.
\end{theorem}

To prove the theorem, we define a probability distribution over instances and consider an arbitrary deterministic algorithm on a randomly drawn instance. By Yao's principle, the worst-case approximation ratio of any randomized algorithm is lower-bounded  by the the approximation ratio of any deterministic algorithm on this randomized instance.

We describe the random instances in Section~\ref{sec:subadditive-instances}, and establish properties of the reward functions and the principal's utility function used in the construction in Section~\ref{sec:subadditive-reward} and Section~\ref{sec:subadditive-principal-utility}.
We prove a lemma that limits the power of demand queries in these random instances in Section~\ref{sec:subadditive-demand-queries}, and give the proof of Theorem~\ref{thm:subadditive-demand} in Section~\ref{sec:subadditive-proof}.

\subsubsection{Distribution over subadditive reward functions $f_T$}\label{sec:subadditive-instances}

To define the probability distribution over instances, let $n \in \mathbb{N}$ be an even square number. In every instance, the agents' costs are the same, namely $c_i=\frac{2}{n}$ for every agent $i$.

The instances differ in terms of the reward functions. To define them, consider the following
subadditive function $f$ over $n$ agents:

\[
f(S)=
\begin{cases}
3+\frac{2 \cdot |S|}{\sqrt{n}} & |S|\leq \frac{n}{2}\\
4  + \sqrt{n} & |S|= \frac{n}{2}+1 \\
5 + \sqrt{n} & |S| = \frac{n}{2}+2 \\
6 + \sqrt{n} & |S| \geq \frac{n}{2}+3 \\
\end{cases}
\]

Given a set $T$ of size $n/2+1$, let $f_T$ be the function where $f_T(S) = f(S) + \indicator{S=T}$. Accordingly, let $g_T$ be the associated principal's utility function.
The random instance consists of $f_{T^\star}$, where $T^\star$ is a uniformly drawn set of size $n/2 + 1$.

\subsubsection{Properties of the reward function $f_T$}\label{sec:subadditive-reward}

We state and prove properties of the reward functions $f_T$. In particular, we show that they are subadditive, and close to submodular functions, and even to symmetric ones; i.e., submodular functions that depend only on the cardinality of the set.\footnote{Since symmetric submodular functions are gross-substitutes \citep{gul1999walrasian}, these subadditive functions are even close to gross-substitutes functions.}

\begin{claim} \label{cl:f-sub}
For every $T$, the function $f_T$ is subadditive.
\end{claim}

\begin{proof}
Consider any disjoint sets $S_1,S_2 \subseteq A$. We show that $f_T(S_1)+f_T(S_2) \geq f_T(S_1 \cup S_2)$. Distinguish two cases.

\noindent {\bf Case 1: $|S_1|,|S_2|\leq \frac{n}{2}$.}
In this case $f_T(S_1)+f_T(S_2) = 6+\frac{2\cdot (|S_1|+ |S_2|)}{\sqrt{n}}$.
If $|S_1|+|S_2|\leq \frac{n}{2}$, then $f_T(S_1\cup S_2) \leq 3+\frac{2\cdot(|S_1|+|S_2|)}{\sqrt{n}} \leq 6+\frac{2\cdot(|S_1|+|S_2|)}{\sqrt{n}} =f_T(S_1)+f_T(S_2)$.
If $|S_1|+|S_2| > \frac{n}{2}$, then $f_T(S_1\cup S_2) \leq 6+\sqrt{n} \leq 6+\frac{2\cdot(|S_1|+|S_2|)}{\sqrt{n}}=f_T(S_1)+f_T(S_2)$.

\noindent {\bf Case 2: $|S_1|>\frac{n}{2}, |S_2|\geq 1$.}
In this case $f_T(S_1)+f_T(S_2) \geq 4+\sqrt{n}+3 \geq f_T(S_1 \cup S_2)$.
\end{proof}

\begin{observation}\label{obs:subadditive-close}
There is a symmetric submodular function $f'$ that fulfills
\[
f'(S) \leq f_T(S) \leq \left( 1 + \frac{3}{3 + \sqrt{n}} \right) f'(S)
\]
for all $S$ and $T$.
\end{observation}

\begin{proof}
Let $f'(S) = \min\{ 3 + \frac{2 \cdot \lvert S \rvert}{\sqrt{n}}, 3 + \sqrt{n} \}$. Note that $f'$, as the minimum between two submodular functions, is submodular. Observe that $f'(S) \leq f_T(S)$ for all $S \subseteq \agents$ with equality for $\lvert S \rvert \leq \frac{n}{2}$. For $\lvert S \rvert > \frac{n}{2}$, we have $f'(S) = 3 + \sqrt{n}$ and $f_T(S) \leq 6 + \sqrt{n}$.
\end{proof}

\subsubsection{Properties of the principal's utility function $g_T$}\label{sec:subadditive-principal-utility}

We next show that $T$ is the optimal contract for reward function $f_T$, and no other set gives a better than $O(\sqrt{n})$-approximation to $T$.
This implies that one needs to identify $T$ in order to get a better than $O(\sqrt{n})$-approximation.

\begin{lemma}\label{lem:onlyT}
We have that $g_T(T) \geq \frac{\sqrt{n}}{4}$ and $g_T(S) \leq 5$ for all $S \neq T$.
\end{lemma}

\begin{proof}
First note that for every $i \in T$, $f_T(i \mid T \setminus \{i\})=2$.
Thus, $g_T(T)=f_T(T)\left(1-\sum_{i\in T}\frac{c_i}{f_T(i \mid T \setminus \{i\})}\right) \geq \frac{\sqrt{n}}{4}$.
{Next, consider any $S \neq T$. We can distinguish the following cases.
\begin{itemize}
    \item If $|S|\leq 1$, then $g_T(S)\leq f_T(S) \leq  3+\frac{2}{\sqrt{n}}$.
    \item If $1 < |S| \leq \frac{n}{2}$, then $f_T(i \mid S \setminus \{i\}) = \frac{2}{\sqrt{n}}$, thus
    $$
    g_T(S) = f_T(S)\left(1-\sum_{i\in S}\frac{c_i}{f_T(i \mid S \setminus \{i\})}\right) = f_T(S)\left(1-\frac{1}{\sqrt{n}}|S|\right)\leq \begin{cases}
    5\cdot \left(1-\frac{|S|}{\sqrt{n}}\right) & |S|<\sqrt{n}\\
    0 & |S|\geq \sqrt{n}\\
    \end{cases}
    $$
    \item If $|S| \geq \frac{n}{2}+1$ and $S\neq T$, then
    $f_T(i \mid S \setminus \{i\}) \leq 1$ for all $i\in S$, thus
    $$g_T(S)=f_T(S)\left(1-\sum_{i\in S}\frac{c_i}{f_T(i \mid S \setminus \{i\})}\right) \leq f_T(S)\left(1-|S|\cdot \frac{2}{n}\right) \leq 0.$$
\end{itemize}
Hence for any $S \neq T$ it holds that $g_T(S) \leq 5$.
\end{proof}

\subsubsection{Limiting the power of demand queries}\label{sec:subadditive-demand-queries}

We now show that with each demand query one can distinguish at most $n^{29}$ sets $T^\star$. This together with Lemma~\ref{lem:onlyT} will derive our impossibility result.
\begin{lemma} \label{lem:size-dem}
For $n>4096$, for every vector of prices $p=(p_1,\ldots,p_n)$,
the set of $\{T^\star \mid D(f,p) \neq D(f_{T^\star},p)\}$ is at most of size $n^{29}$, where $D(f,p)$  (resp. $D(f_{T^\star},p)$) is the demand set\footnote{For simplicity of the proof, we assume that when there are multiple sets  in demand, the tie breaking is consistent across all $f_T$.} of function $f$ (resp. $f_{T^\star}$) with respect to prices $p$.
\end{lemma}
Let $S_p=\{i \mid p_i \leq 1/4\}$, and $B_p=\{i \mid p_i \geq 1/2\}$.

\begin{claim}
If $|B_p| \leq n/2 -3$, then for every $T$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:big}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the value of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$, then, {because $|A \setminus B_p| \geq n/2+3$ and $|T| = n/2+1$}, the set $\Delta:= A \setminus B_p \setminus T $ is of size at least $2$. Let $x,y$ be two arbitrary different elements in $\Delta$, {and note that for these $p(x) < 1/2$ and $p(y) < 1/2$}.
Now $f(T\cup \{x,y\}) - p(T\cup \{x,y\}) \geq 1+ f(T) -p(T) -p(x)-p(y) > f(T)-p(T)$, which contradicts that $T$ is the demand set.
\end{proof}

\begin{claim}
For $n>4096$, if $|S_p| \leq n/2 - 8$, then for every $T$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:small}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the values of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$, then the set $\Delta:= T \setminus S_p  $ is of size at least $9$. Let $X$ be  an arbitrary subset of  $\Delta$ of size $9$. It holds that
$$f(T\setminus X)-p(T \setminus X) = f(T)-2-\frac{{16}}{\sqrt{n}} - p(T) + p(X) \geq f(T)-p(T) +\frac{|X|}{{4}} -2-\frac{16}{\sqrt{n}}  >  f(T)-p(T),$$
which contradicts that $T$ is the demand set.
\end{proof}

\begin{claim}
If  $|S_p| > n/2 - 8$ and  $|B_p| > n/2 -3$, then for all $T \notin \{S \mid (|S| =n/2+1) \wedge (|S\setminus SP_p| \leq 14) \}$ {it holds that} $D(f_T,p)=D(f,p)$. \label{cl:mixed}
\end{claim}
\begin{proof}
Since $f_T$ and $f$ disagree only on the values of $T$, it is sufficient to show that $D(f_T,p) \neq T$.
Assume towards contradiction that $D(f_T,p) = T$,
it holds that the set $\Delta_1:= B_p \cap T $ is of size at least $5$ since $|B_p \cap T| \geq |T\setminus S_p| -|A \setminus B_p \setminus S_p| \geq 14-9 =5 $, and the set $\Delta_{{2}}:= S_p \setminus T $ is of size at least $6$ since $|S_p \setminus T| = |T \setminus S_p | -  |T| +|S_p| \geq 14 - 8  =6.$
Let $X$ be  an arbitrary subset of  $\Delta_1$ of size $5$ and let $Y$ be an arbitrary subset of $\Delta_2$ of size $5$. It holds that
$$f((T\setminus X) \cup Y)-p((T \setminus X) \cup Y) = f(T)-1 - p(T) + p(X) -p(Y) \geq f(T)-p(T) +\frac{|X|}{4} -1  >  f(T)-p(T),$$
which contradicts that $T$ is the demand set.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:size-dem}]

By combining Claim~\ref{cl:big} and Claim~\ref{cl:small},
{a demand query can only reveal information about $T$ if}
$|S_p| > n/2 - 8$ and  $|B_p| > n/2 -3$, and even then, by Claim~\ref{cl:mixed},
{a demand query}
cannot distinguish between $T$'s not in $\{S \mid (|S| =n/2+1) \wedge (|S\setminus S_p| \leq 14) \}$.
{Now,} the lemma follows since for every choice of $S_p$ of {size} greater than $n/2-8$, the set $\{S \mid (|S| =n/2+1) \wedge (|S\setminus S_p| \leq 14) \}$ is at most of size $n^{29}$.
(One can bound it by counting the options to select  a set $S\setminus S_p$ of size at most $14$ and then select a set  $S_p\setminus S$ which is of size at most $15$ since $|S_p\setminus S| = |S\setminus S_p| +|S_p|-|S| \leq 14 + n - |B_p| - (n/2+1) \leq 14 +n - (n/2-2)-(n/2+1)  = 15$.)
\end{proof}

\subsubsection{Putting it all together}\label{sec:subadditive-proof}

We are now ready to prove the theorem.

\begin{proof}[Proof of Theorem~\ref{thm:subadditive-demand}]
Consider any fixed deterministic algorithm $ALG$, and the random instances described in Section~\ref{sec:subadditive-instances}.
Let $S_{ALG}$ be the set that the algorithm computes when all demand and value queries are answered according to the function $f$. We claim that on the vast majority of functions $f_T$ the algorithm will also compute $S_{ALG}$.

To this end, let $\mathcal{T}_i$ be the family of all sets $T$ of size $\frac{n}{2}+1$ such that the first $i$ demand or value queries performed by the algorithm would have led to the same answers on $f_T$ as on $f$. Clearly
$\vert \mathcal{T}_0 \vert= \binom{n}{n/2+1}$.
By Lemma~\ref{lem:size-dem}
any demand query allows us to distinguish at most $n^{29}$ many sets from $f$ (and of course, any value query can distinguish at most one set). That is, $\lvert \mathcal{T}_{i+1} \rvert \geq \lvert \mathcal{T}_i \rvert - n^{29}$.

This implies that $\lvert \mathcal{T}_i \rvert \geq \binom{n}{n/2+1} - i \cdot n^{29}$.
Furthermore, by Lemma~\ref{lem:onlyT},  the approximation ratio of the algorithm that uses at most $i$ queries is no better than $\frac{20}{\sqrt{n}}$ whenever $T^\star \in \mathcal{T}_i$ and $T^\star \neq S_{ALG}$. This happens with probability of at least
$1- \frac{\lvert \mathcal{T}_i \rvert - 1}{\binom{n}{n/2+1}} $ since $T^\star$ is uniformly distributed in $\mathcal{T}_i$ and the algorithm can choose just one of them.
Overall, we get that the approximation of  an algorithm $ALG$ that uses at most $i$ demand and value queries is at most
\begin{eqnarray*}
E\left[\frac{g(S_{ALG})}{g(T^\star)}\right] &\leq & \Pr[T^\star \notin \mathcal{T}_i  \vee T^\star =S_{ALG}] \cdot 1  + (1-\Pr[T^\star \notin \mathcal{T}_i  \vee T^\star =S_{ALG}]) \cdot \frac{20}{\sqrt{n}} \\
& \leq  &
\frac{\binom{n}{n/2+1}-\lvert \mathcal{T}_i \rvert +1}{\binom{n}{n/2+1}} + \frac{\lvert \mathcal{T}_i \rvert -1}{\binom{n}{n/2+1}} \cdot \frac{20}{\sqrt{n}} \\
& \leq & \frac{20}{\sqrt{n}} + \frac{i\cdot n^{29}+1}{\binom{n}{n/2+1}} \leq O\left(\frac{1}{\sqrt{n}}\right),
\end{eqnarray*}
where the last inequality holds for every polynomial amount of queries.
\end{proof}

\subsection{Inapproximability Result for XOS}\label{sec:xos-upper}

We conclude by stating our inapproximability result for XOS reward functions. The proof follows the same structure as Theorem~\ref{thm:subadditive-demand}, so we focus on stating the family of XOS functions and defer the rest of the proof to Appendix~\ref{app:upper-xos}.

\begin{theorem}\label{thm:xos-upper}
For every randomized algorithm that performs only polynomially many value and demand queries, there is a subadditive function $f$ such that the approximation ratio is at least $1.136$ with high probability.
\end{theorem}
\begin{proof}
Let $n$ be an even number. Consider the following symmetric XOS function $f$ over $n$ agents:
$$
f(S)=
\begin{cases}
1+\frac{3 \cdot |S|}{n} & |S|\leq \frac{n}{2}\\
1/2 + \frac{4 \cdot |S|}{n} & |S| > \frac{n}{2} \\
\end{cases}
$$
Given a set $T$ of size $n/2+1$, let $f_T$ be the function where $f_T(S) = f(S) + \indicator{S=T} \cdot \frac{1}{n}$.
The costs of all actions are $\frac{5}{n(n+2)}$.

The rest of the proof follows exactly the same steps as in the proof of Theorem~\ref{thm:subadditive-demand}, just instead of using Claim~\ref{cl:f-sub}, Lemma~\ref{lem:onlyT} and Lemma~\ref{lem:size-dem}, it uses Claim~\ref{cl:f-xos}, Lemma~\ref{lem:onlyTXOS} and Lemma~\ref{lem:size-dem-xos} which are deferred to Appendix~\ref{app:upper-xos}.
\end{proof}

\section{Introduction}

Contract theory is a core problem in economic theory (c.f.~the 2006 ``Nobel Prize'' to Oliver Hart and Bengt Holmstr\"om), which seeks, using incentive mechanisms, to achieve desirable outcomes in the presence of unobservable actions.
It plays a major role in the design of markets for effort (or services), similar to the role that mechanism design and auction theory play in the design of markets for goods.
Applications of contract design range from multi-million dollar markets, such as influencer marketing on social media platforms \citep[e.g.,][]{Statista}, to contracts for social goods, such as government-run programs to encourage afforestation/prevent deforestation \citep[e.g.,][]{LiIL21, AshlagiLL22}.

At its heart is the hidden-action principal-agent problem \citep[e.g.,][]{Holmstrom79,GrossmanHart83}, in which a principal seeks to incentivize an agent to take a costly action, whose stochastic outcome determines a reward for the principal. A contract defines monetary transfers from the principal to the agent based on the observable outcome.
The principal's goal is to find the contract that maximizes her utility (expected reward minus transfer), when the agent chooses the action that maximizes his utility (expected transfer minus cost).

In its vanilla version, with a single principal and a single agent, the problem can be solved in polynomial time by solving one LP for each action \citep{GrossmanHart83}. While this approach can also be applied in more complex scenarios, its running time will usually be exponential in the (succinct) representation. Therefore, one has to understand the structure of optimal contracts in order to obtain computationally efficient algorithms for finding optimal contracts \cite[e.g.][]{BabaioffFNW12,DuttingRT21,DuttingEFK21}

A natural extension of the classic single-principal single-agent model, are settings where a principal seeks to incentivize a \emph{team} of agents \citep{Holmstrom82}. In such scenarios, the complexity arises from the complex combinatorial structure of dependencies between the agent actions, and is already compelling when each agent can either exert effort or not \citep{BabaioffFNW12}.
In this work, we provide computationally efficient algorithms and impossibilities for (approximating) the optimal contract in this multi-agent setting.

As in many economic models, the problem of optimally incentivizing teams of agents boils down to a clean and compelling combinatorial optimization problem.
The challenge is that, even in cases where the dependencies between the agent actions exhibit nice structure, this structure does \emph{not} transfer to the objective function.

\paragraph{Model -- Key Ingredients.}
To state and discuss our results, it will be useful to describe the key ingredients of the multi-agent hidden-action principal-agent problem \citep[c.f.][]{BabaioffFNW12} that we study in this paper.

In this model, a principal interacts with a set $A$ of $n$ agents. Agents have binary actions: They can either exert effort or not. Exerting effort comes with cost $c_i \in \mathbb{R}_{\geq 0}$ for agent $i$. Each subset of agents $S \subseteq \agents$ induces a probability distribution over possible outcomes $\omega \in \Omega$, and the principal associates a reward $r(\omega) \in \mathbb{R}_{\geq 0}$ with each possible outcome.
The reward function $f: 2^A \rightarrow \mathbb{R}_{\geq 0}$ associates with each set $S \subseteq \agents$ of agents that exert effort an expected reward.

Our focus in this work is on a particularly important class of contracts, so-called linear contracts, and the optimal contract design problem in that class.

A linear contract consists of a vector $\alpha \in [0,1]^n$; and specify that agent $i$ should be paid $\alpha_i \cdot r (\omega)$ for each outcome $\omega \in \Omega$. We say that a linear contract incentivizes a set of agents $S$ if for each $i \in S$ it holds that $\alpha_i \cdot f(S) - c_i \geq \alpha_i \cdot f(S\setminus\{i\})$ and for each $i \not\in S$ it holds that $\alpha_i \cdot f(S) \geq \alpha_i \cdot f(S \cup \{i\}) -c_i$.
The goal is to find a linear contract $\alpha$ and a set $S$ such that $S$ is incentivized by $\alpha$, and maximizes the principal's expected utility given by $g(S) = (1-\sum_{i \in \agents} \alpha_i) f(S)$.

Linear contracts are arguably the most important class of contracts in practice, and they also exhibit good properties analytically.
In particular, for the important special case of a binary outcome (e.g., a project that can succeed or fail), linear contracts are in fact optimal;
and for more general outcome spaces, they are known to be max-min optimal when only the expected reward of each set of agents is known
\citep{DuttingRT19,DuttingEFK21}.

\subsection{Our Contribution}

We study the computational complexity of computing optimal and near-optimal linear contracts for the multi-agent hidden-action principal-agent problem for different classes of ``complement-free'' reward functions \citep{LehmannLN06}.

As it turns out, moving from a single-agent to a multi-agent setting significantly complicates matters. Even for the simplest class of reward functions --- additive reward --- it is NP-hard to compute the optimal contract; but the problem admits
an FPTAS (see Appendix~\ref{app:additive}). As we progress in the hierarchy,
the problem becomes  significantly more challenging.

Our first main result concerns submodular, and in fact, the more general class of XOS reward functions (for definitions see Section~\ref{sec:preliminaries}). We show that for both of these classes there exist algorithms that provide constant-factor approximation to the optimal contract.

Our result relies on an uncoventional use of ``prices'' and (approximate) demand queries for selecting the set of agents that the principal should seek to incentivize, and exploits a novel scaling property for XOS functions and their marginals, which may be of independent interest.

\vspace{0.1in}
\noindent {\bf Main Result 1 (Theorem~\ref{thm:xos}):}
For any multi-agent setting with {\em submodular} reward function $f$, there exists a polynomial-time $O(1)$-approximation
to the optimal contract,  that uses a {\em value} oracle.
If $f$ is {\em XOS}, an $O(1)$-approximation can be achieved using a {\em demand} oracle.
\vspace{0.1in}

We complement this result by showing that, for the broader class of {\em subadditive} functions, the following impossibility applies:

\vspace{0.1in}
\noindent {\bf Main Result 2 (Theorem~\ref{thm:subadditive-demand}):}
For any polynomial-time algorithm, with demand or value oracles, there exists a multi-agent setting with {\em subdditive} reward function $f$, such that the algorithm achieves no better than $\Omega\left(\sqrt{n}\right)$-approximation to the optimal contract, where $n$ is the number of agents
\vspace{0.1in}

This impossibility result is particularly interesting in light of the fact that it applies to a subadditive function that is ``constant-factor close" to submodular:
It can be approximated by
a submodular function to within a factor of $2$. Yet, the gap between the optimal contract that can be found in polynomial time and the optimal contract jumps from constant to $\Omega(\sqrt{n})$.

So, on the one hand we show that---just like in pure combinatorial optimization and algorithmic mechanism design---submodularity, or more generally being XOS, enables efficient computation of near-optimal contracts.
On the other hand we show that---in stark contrast to these closely related domains, where usually being within a factor of $\beta$ of submodular or XOS
implies that the bounds only deteriorate by a factor of $O(\beta)$ \citep[e.g.,][]{BhawalkarR11,FeldmanGL15}---in our case the bound does not degrade gracefully with the closeness to submodularity.

Our positive result is ``tight" in an additional way: In Theorem~\ref{thm:xos-upper} we show that it is impossible to obtain a better than constant approximation for XOS functions (even with demand queries).

\subsection{Our Techniques}
In Section~\ref{sec:preliminaries}, we observe that the underlying optimization problem we need to solve is as follows. Given a cost $c_i \geq 0$ for each agent $i$ and a reward function $f: 2^A \to \mathbb{R}_{\geq 0}$, our goal is to maximize the function $g: 2^A \to \mathbb{R}$ defined by
\[
g(S) = \left( 1 - \sum_{i \in S} \frac{c_i}{f(i \mid S \setminus \{i\})} \right) f(S).
\]

The difficulty is that, even in cases where $f$ is highly structured
such as submodular, XOS, or subadditive (see definitions in Section~\ref{sec:preliminaries}),
this structure does not carry over to $g$.
For example, even in cases where $f$ is non-negative monotone
and submodular, the induced $g$
will usually not be monotone and take negative values. If $f$ is only XOS, $g$ may even not be subadditive.

\paragraph{Constant-factor approximations for submodular and XOS.}
Let $S^\star$ be a set that maximizes $g(S^\star)$.
Our goal is to find a set $S$ such that $g(S) \geq \mathrm{constant} \cdot g(S^\star)$.
For the purpose of conveying the intuition behind our approach,
assume in the following that $f(S^\star)$ is known to the algorithm
(but not $S^\star$ itself)
and the contribution of a single agent is negligible. In the technical sections, these assumptions will not be necessary.

A key ingredient in our proof is a pair of lemmas that draw connections between the value of the optimal solution and its marginals to the costs. Specifically, in Lemma~\ref{lem:sumci}, we show that $\sum_{i \in S^\star} \sqrt{c_i} \leq \sqrt{f(S^\star)}$. In Lemma~\ref{lem:stronger-condition}, we show that if for a set $S$ we have $f(i \mid S \setminus \{i\}) \geq \sqrt{2 c_i f(S)}$ for every $i \in S$, then $g(S) \geq \frac{1}{2} f(S)$.

These observations give rise to guiding the choice of our set $S$ by defining a ``price'' for each agent.
Namely, let $p_i = \frac{1}{2} \sqrt{c_i f(S^\star)}$ for each agent $i$ and consider the \emph{demand set} $T$, which is defined to maximize $f(T) - \sum_{i \in T}p_i$. We now have $f(T) \geq f(T) - \sum_{i \in T} p_i \geq f(S^\star) - \sum_{i \in S^\star} p_i \geq \frac{1}{2} f(S^\star)$ using the definition of a demand set and Lemma~\ref{lem:sumci}. By definition, the marginal contribution of every agent in the demand set must exceed its price, namely $f(i \mid T \setminus \{i\}) \geq p_i = \frac{1}{2} \sqrt{c_i f(S^\star)}$.  This condition looks almost like the one that is necessary to invoke Lemma~\ref{lem:stronger-condition}. However, note that we only have a lower bound on $f(T)$, no upper bound. Therefore possibly $f(T)$ is much larger than $f(S^\star)$.

To deal with this, we establish a novel scaling property of XOS functions, showing that one can scale down the value of any set $T$ to essentially any level, by removing some of its elements, while keeping the marginals of the remaining elements sufficiently high with respect to their original marginals. Namely, for every set $T$ and every $\Psi < f(T)$, one can compute a subset $U \subseteq T$ such that
$\frac{1}{2} \Psi \leq f(U) \le \Psi$ and $f(i \mid U \setminus \{ i \}) \geq \frac{1}{2} f(i \mid T \setminus \{ i \})$.
While this property is not too surprising for submodular functions, for XOS functions this is far from obvious, given the apparent lack of control over marginals, and may be of independent interest. Setting $\Psi = \frac{1}{32}  f(S^\star)$,
we can invoke Lemma~\ref{lem:stronger-condition} because with this choice
$f(i \mid U \setminus\{i\}) \geq \frac{1}{2} f(i \mid T \setminus \{i\}) \geq \frac{1}{2} p_i = \frac{1}{4} \sqrt{c_i f(S^\star)} \geq \sqrt{2 c_i f(U)}$
and conclude that
$g(U) \geq \frac{1}{2} f(U) \geq \frac{1}{128} f(S^\star) \geq \frac{1}{128} g(S^\star)$.

{\paragraph{Inapproximability results for subadditive and XOS.}

To show the impossibility result for subadditive reward functions $f$, we first construct a subadditive function $f$ on subsets $S \subseteq A$ of $n$ agents. It has the property that $g(S) = O(1)$ for $\lvert S \rvert < \sqrt{n}$ and $g(S) \leq 0$ if $\lvert S \rvert \geq \sqrt{n}$. That is, the optimal principal utility is constant and any attempt to incentivize more than $\sqrt{n}$ agents would result in a negative (or zero) utility.

We then slightly modify $f$ by choosing a random set $T^\star$ of size $\frac{n}{2}+1$, and increasing its value. Monotonicity and subadditivity of $f$ are preserved by this change. This change significantly increases the principal's utility from the set $T^\star$ to $g(T^\star) = \Omega(\sqrt{n})$. At the same time, it does not increase the utility from any other set, so that, not only is $T^\star$ the unique optimal set, but it is also the only one that approximates it well. The principal's problem thus boils down to finding $T^\star$.

It then remains to show that $T^\star$ cannot be found by a polynomial number of (demand or value) queries. We then use the fact that the modified function is almost identical to the original (symmetric) one to show that every (demand or value) query reveals information only on a small set of candidates for $T^\star$, and thus every algorithm that uses only a polynomial number of queries, cannot guess $T^\star$ with high enough probability, resulting in an $\Omega(\sqrt{n})$ approximation to the principal's optimal utility

Our proof providing a constant lower bound for XOS
follows the same approach, but the additional structure of XOS functions limits how big the gap between $g(T)$ and $g(T^\star)$ can be.

\subsection{Related Work}\label{sec:related-work}

\paragraph{Optimizing the effort of others.}
Our work is part of an emerging frontier in Algorithmic Game Theory  on optimizing the effort of others  (see, e.g., the STOC 2022 TheoryFest workshop with the same title). This includes work on algorithmic contract design \citep[e.g.,][]{DuttingRT19,DuttingRT21,DuttingEFK21}, strategic classification \citep[e.g.,][]{KleinbergR19,BechavodPWZ22}, optimal scoring rule design \citep[e.g.,][]{ChenY21,LiHSW22}, and delegation \citep[e.g.,][]{KleinbergK18,BechtelDP22}.

\paragraph{Combinatorial optimization and auctions.} A number of fundamental papers has explored combinatorial optimization problems with ``complement-free'' set functions. In a landmark paper, \cite{Feige09} gives constant-factor approximation algorithms for the welfare maximization problem in combinatorial auctions with submodular, XOS, and subadditive  bidders. An exciting line of work seeks to understand whether it is possible to match these bounds with truthful mechanisms, with the current state of the art being polyloglog approximations \citep{Dobzinski21,AssadiKS21}. Complement-free valuations also play a crucial role in combinatorial auctions with item bidding, where subadditive valuations enable constant-factor Price of Anarchy bounds  \citep{ChristodoulouKS16,BhawalkarR11,SyrgkanisT13,FeldmanFGL13}; and the prophet inequalities/posted-price literature, where constant-factor approximations are known for XOS and the state of the art for subadditive is a loglog approximation \citep{FeldmanGL15,DuttingKL20,DuttingFKL20}. There are also polynomial-time constant-factor approximation results for truthful revenue maximization with unit-demand bidders \citep{ChawlaHMS10}, additive bidders \citep{Yao15}, and XOS bidders \citep{CaiOZ22}.

\paragraph{Computational approaches to contracts.} A computational approach to contracts was pioneered in \citep{FeldmanCSS07,BabaioffFNW12} and  \citep{DuttingRT19}.

Most relevant for us is work on \emph{combinatorial contracts}, which can be divided into three categories, depending on whether it concerns exponentially large outcome spaces \citep{DuttingRT21}, taking sets of  actions \citep{DuttingEFK21}, or settings with multiple agents \citep{BabaioffFNW12,BabaioffFN09,BabaioffFN10,EmekF12}.
Out of these, the most closely related papers to our work are \citep{DuttingEFK21} and \citep{BabaioffFNW12,EmekF12}.

\cite{DuttingEFK21} study a single-principal single-agent setting, where the agent can take any subset of $n$ actions. The main result is a polynomial-time (in $n$) algorithm for gross-substitutes reward functions. They also show NP-hardness for general submodular reward functions (with value oracle access).
While both \cite{DuttingEFK21} and the present paper deal with a reward function that maps any subset of $n$ actions to some expected reward, the induced optimization problems are fundamentally different: In \cite{DuttingEFK21} a single agent chooses a subset of $n$ actions, leading to a single incentive-compatibility constraint.
Here, in contrast, each one of the $n$ agents makes a binary choice over actions (exert effort or not), thus an action profile corresponds to a subset of the $n$ agents, and the corresponding optimization problem has $n$ incentive-compatibility constraints.
It is an exciting open question whether techniques similar to the ones we develop in this paper can advance the state of the art for the multi-action problem.

\cite{BabaioffFNW12} and \cite{EmekF12} study the same
model studied here---$n$ agents with binary actions.
They assume that each agent succeeds in his individual task with a certain probability, depending on whether he exerts effort or not;
then a Boolean function maps individual successes and failures to a success or failure of the project.
\cite{BabaioffFNW12} show that for Boolean functions represented by
read-once networks the
optimal contract problem is \#P-complete, and give a polynomial-time algorithm for AND networks. \cite{EmekF12} show that for OR networks (a special case of submodular) the problem is NP-hard,
but admits an FPTAS.
Our work significantly expands the landscape of this model, by considering general submodular, XOS, and subadditive reward functions.

Finally, recent work has considered  settings exhibiting both hidden-action and hidden-type, through a computational lens \citep{AlonDT21,GuruganeshSW21,CastiglioniM022}.

\subsection{Organization}

We formally set up the model in Section~\ref{sec:preliminaries}. Our main positive result---the constant-factor approximation guarantees for submodular and XOS reward functions--
appear in Section~\ref{sec:sm-and-xos}. We prove the impossibility results for subadditve and XOS reward functions in Section~\ref{sec:beyond-submodular}. Our results for additive reward functions
appear in Appendix~\ref{app:additive}.

\section{Preliminaries}

\input{model}

\input{xos-new}

\input{beyond-submodular}

\bibliographystyle{abbrvnat}

\subsection{Auxiliary Lemma for XOS Functions}

For our main result on XOS reward functions we need the following lemma, which generalizes a well-known property of submodular functions to XOS functions.

\begin{lemma}\label{lem:xos-sum-of-marginals-extended}\label{lem:xos-sum-of-marginals}
For any XOS function $f$ and any sets $S\subseteq T$,
\[
\sum_{i \in S} f(i \mid T \setminus\{i\}) \leq f(S).
\]
\end{lemma}
\begin{proof}
Let $a$ be an additive supportive function for $f$ on $T$ so that $a(T) = f(T)$ and $a(T') \leq f(T')$ for all $T' \subseteq T$. Then, for any $i \in T$, it holds that
\[
f(i \mid T \setminus\{i\}) = f(T) - f(T \setminus\{i\}) \leq  a(T) - a(T \setminus\{i\}) = a(\{i\}).
\]
Summing over all $i \in S$ we obtain
\[
\sum_{i \in S} f(i \mid T \setminus\{i\}) \leq \sum_{i \in S} a(\{i\}) = a(S) \leq  f(S),
\]
as claimed.
\end{proof}

\section{Constant Factor for Submodular and XOS}\label{sec:sm-and-xos}

In this section, we present our main positive results: polynomial-time constant-factor approximation algorithms
for submodular and XOS multi-agent combinatorial contracts.

\begin{theorem}\label{thm:xos}
\begin{enumerate}
\item For submodular $f$ and $n$ agents, it is possible to compute an $O(1)$-approximation to the optimal contract in polynomial time using value queries.
\item For
XOS $f$ and $n$ agents,
it is possible to compute an $O(1)$-approximation to the optimal contract  in polynomial time using value and demand queries.
\end{enumerate}
\end{theorem}

Recall that we use $g:2^A\rightarrow\mathbb{R}$ to denote the  principal's utility as a function of the set of incentivized agents. I.e.,
    $g(S) := f(S) \left(1-\sum_{i\in S} \frac{c_i}{f(i\mid S\setminus\{i\})}\right)$.

Let $S^\star$ be the optimal set of agents, i.e., the set that maximizes $g$.

Below we present the full argument for submodular/XOS reward functions assuming value and demand oracle access to the reward function.
The result to submodular reward functions with only value oracle access requires only small modifications and relies on known  algorithms for computing approximate demand sets \citep{SviridenkoVW17,Harshaw19a}. We defer the details of this extension to Appendix~\ref{app:extension-to-submodular}.

\subsection{Decomposing the Benchmark}

Our first lemma provides a useful decomposition of the benchmark by showing that  $g(S^\star)$ is upper bounded by the sum of $f(S^{\star} \cap \agents')$, where $\agents' = \{ i \in \agents \mid \frac{c_i}{f(\{i\})} \leq \frac{1}{2} \}$, and $\max_{i \in A} g(\{i\})$ --- the best contract for incentivizing a single agent.

This may look innocent, but is not, because---as we already observed earlier---generally none of the nice structural properties of $f$ (such as non-negativity, monotonicity, submodularity or being XOS)  carry over to $g$.

An important consequence of the lemma is that, since it's easy to find the best contract for incentivizing a single agent, we can focus on the non-trivial task of finding a contract that approximates $f(S^\star \cap A')$.

\begin{lemma}
\label{lem:onebigagent}
If $f$ is XOS (or, more generally, subadditive),  then
\[
g(S^\star) \leq f(S^\star \cap \agents') + \max\{0,\max_{i \in \agents} g(\{i\})\}.
\]
\end{lemma}

\begin{proof}
If $g(S^\star) = 0$, then the claim is trivial.
Otherwise, we first prove that $|S^\star \setminus \agents'| \leq 1$.
This is since,
\[0 < g(S^\star) = f(S^\star)  \left(1- \sum_{i\in S^\star} \frac{c_i}{f(i\midS^\star\setminus\{i\})}\right) \leq  f(S^\star) \left(1- \sum_{i\in S^\star\setminusA'} \frac{c_i}{f(\{i\})}\right) \leq f(S^\star) \left(1-  \frac{|S^\star\setminusA'|}{2}\right),
\]
where the second inequality follows from subadditivity of $f$ which implies that $f(i \mid S^\star \setminus \{i\}) = f(S^\star) - f(S^\star \setminus \{i\}) \leq f(\{i\})$.
Since $f(S^\star)>0$, this implies that $ |S^\star\setminusA'| \leq 1$.

If $|S^\star \setminus \agents'| = 0$, the statement follows since  $g(S^\star) = g(S^\star\cap A') \leq f(S^\star\cap A')$.
Else, let $i^\star$ be the single item in $S^\star \setminus \agents'$. We have
\[
g(S^\star) \leq f(S^\star \cap \agents') + f(\{i^\star\}) \left( 1 - \frac{c_{i^\star}}{f(i^\star \mid S^\star \setminus \{i^\star\})} \right)  \leq f(S^\star \cap \agents') + \max_{i \in \agents} g(\{i\}).
\]
The first inequality follows from subadditivity of $f$, implying that
$f(S^\star) \leq f(S^\star \cap \agents') + f(\{i^\star\})$,
and by decreasing the payments. The second inequality follows again by subadditivity of $f$, implying that $f(i^\star \mid S^\star \setminus \{i^\star\}) \leq f(\{i^\star\})$.
This concludes the proof.
\end{proof}

\subsection{Relaxing the Problem}
We next present two crucial lemmas that draw connections between rewards, marginal rewards, and costs. This pair of lemmas relaxes the problem and motivates our approach for finding a good set of agents to incentivize in a contract via prices and demand queries.

\begin{lemma}
For all $S \subseteq S^\star$, we have \[
\sum_{i\in S} \sqrt{c_i}  \leq \sqrt{f(S)}.
\] \label{lem:sumci} \label{lem:stronger-sumci}
\end{lemma}
\begin{proof}
Note that $f(i \mid S^\star \setminus \{i\}) > 0$ for all $i \in S^\star$ with $c_i > 0$ because otherwise $g(S^\star) = -\infty$, whereas $g(\emptyset) = 0$, contradicting the optimality of $S^\star$.

Let's first consider the case where $f(S^\star) = 0$. In this case, we have $f(i \mid S^\star \setminus \{i\}) \leq f(\{i\}) \leq f(S^\star) = 0$ for all $i \in S^\star$. This means that $c_i = 0$ for all $i \in S^\star$, implying the statement.

So consider the case where $f(S^\star) > 0$. By optimality $g(S^\star) \geq 0$, so
\[
g(S^\star) = f(S^\star) \left(1-\sum_{i\in S^\star} \frac{c_i}{f(i\mid S^\star \setminus\{i\})}\right) \geq 0 \quad \Longrightarrow \quad \sum_{i\in S^\star} \frac{c_i}{f(i\mid S^\star \setminus\{i\})} \le 1,
\]
where we used that $f(S^\star) >0$ for the implication.

For $i \in S$ let $x_i = \sqrt{\frac{c_i}{f(i\mid S^\star \setminus\{i\})}}$
and $y_i = \sqrt{f(i\mid S^\star \setminus\{i\})}$. This is well-defined because $\frac{c_i}{f(i\mid S^\star \setminus\{i\})} \geq 0$ by our initial observation. The Cauchy-Schwarz inequality states
\[
\left(\sum_{i \in S} x_i y_i \right)^2 \leq \left(\sum_{i \in S} x_i^2 \right) \left(\sum_{i \in S} y_i^2 \right).
\]
Using this we obtain
\[
\left(\sum_{i \in S} \sqrt{c_i} \right)^2 \leq  \underbrace{\left(\sum_{i \in S}\frac{c_i}{f(i\mid S^\star \setminus\{i\})}\right)}_{\leq 1} \left(\sum_{i \in S} f(i\mid S^\star \setminus\{i\}) \right) \leq f(S),
\]
where the last inequality holds by Lemma~\ref{lem:xos-sum-of-marginals}. Taking the square root on both sides of the inequality establishes the claim.
\end{proof}

\begin{lemma}\label{lem:stronger-condition}
For any set $S$ that fulfills $f(S) > 0$ and
\[
f( i \mid S \setminus \{ i \}) \geq \sqrt{2 c_i f(S)} \quad \text{for all $i \in S$,}
\]
we have $g(S) \geq \frac{1}{2} f(S)$.
\end{lemma}

\begin{proof}
Consider any $i \in S$. If $c_i > 0$, note that we have to have $f( i \mid S \setminus \{ i \}) > 0$. So
\[
f( i \mid S \setminus \{ i \}) \geq \sqrt{2 c_i f(S)}
\]
is equivalent to
\[
\frac{c_i}{f( i \mid S \setminus \{ i \})} \leq \frac{1}{2} \frac{f( i \mid S \setminus \{ i \})}{f(S)}.
\]
For any $i \in S$ with $c_i = 0$, we defined $\frac{c_i}{f( i \mid S \setminus \{ i \})} = 0$, even when the denominator is zero; so also $\frac{c_i}{f( i \mid S \setminus \{ i \})} \leq \frac{1}{2} \frac{f( i \mid S \setminus \{ i \})}{f(S)}$ because $f( i \mid S \setminus \{ i \}) \geq 0$. Summing over all $i \in S$ we obtain
\[
\sum_{i \in S} \frac{c_i}{f( i \mid S \setminus \{ i \})} \leq \frac{1}{2} \frac{\sum_{i \in S} f( i \mid S \setminus \{ i \})}{f(S)} \leq \frac{1}{2},
\]
where the second inequality holds by  Lemma~\ref{lem:xos-sum-of-marginals}.
Therefore
\[
g(S) = \left( 1 - \sum_{i \in S} \frac{c_i}{f( i \mid S \setminus \{ i \})}\right) f(S) \geq \frac{1}{2} f(S),\]
as claimed.
\end{proof}

\subsection{A Scaling Property of XOS Functions and Their Marginals}

The other crucial ingredient in our argument for finding a contract is a novel scaling property of XOS functions and their marginals, which roughly says that we can scale down the reward $f(T)$ of any set $T$ to whatever level we wish, while also ensuring that the marginals of the elements that remain stay high (with respect to the original marginals).

This property is not too suprising for submodular $f$, and is indeed easy to obtain for this class of functions: Consider iteratively dropping elements from $T$ one by one to get down to the desired level. Then, by submodularity, the marginals of the items that remain can only go up.
For XOS $f$, however, this is far from obvious (given the apparent lack of control over marginals), and may be of independent interest.

\begin{lemma}
\label{lem:xosscaling}
Let $f:2^A\rightarrow \mathbb{R}_{\geq 0}$ be an XOS function. Given a set $T \subseteqA$, and parameters $\delta \in (0,1]$ and $0\leq \Psi < f(T)$, Algorithm~\ref{alg:scaling} runs in polynomial time with value oracle access to $f$ and finds a set $U \subseteq T$ such that
\begin{equation}
 (1-\delta)\Psi \leq f(U) \leq \Psi + \max_{i\in T} f(\{i\}), \label{eq:prop_val}
\end{equation}
and
\begin{equation}
    f(i \mid U \setminus \{i\}) \geq \delta f(i \mid T \setminus \{i\}) \qquad \text{for all $i \in U$}. \label{eq:prop_marg}
\end{equation}
\end{lemma}

\begin{algorithm}
\caption{Scaling sets for XOS}\label{alg:scaling}
\KwData{An XOS function $f:2^A \rightarrow \mathbb{R}_{\geq 0}$, a set $T$, parameters $0 \leq \Psi < f(T)$ and $\delta\in (0,1]$
}

\KwResult{A set $U \subseteq T$ satisfying Equations \eqref{eq:prop_val} and \eqref{eq:prop_marg}}

    Let $T_0$ be an inclusion-wise minimal subset of $T$ with $f(T_0) = f(T)$  \quad

    \Comment{I.e.,  $f(S)< f(T_0), \forall S \subsetneq T_0$}

    \For{ $t=1,\ldots,|T_0|$}{
    Let $i_t = \arg\min_{i \in T_{t-1}} \frac{f(i\mid T_{t-1} \setminus \{i\})}{f(i\mid T_0 \setminus \{i\})}$

    Let $T_{t} =T_{t-1} \setminus \{i_t\}$

    Let $\delta_t= \frac{f(i_t\mid T_{t})}{f(i_t\mid T_0 \setminus \{i_t\})}$
    }

    Let $j^\star = \min \{j \mid f(T_{j}) \leq \Psi \} $

    Let $k^\star = \min \{k \mid f(T_k) \leq (1-\delta) f(T_{j^\star-1}) \} $

    Let $t^\star = \arg\max_{t\in \{j^\star,\ldots,k^\star\}} \delta_t $

    \Return $U=T_{t^\star-1}$

\end{algorithm}

\begin{proof
It is easy to see that Algorithm~\ref{alg:scaling} can be implemented in polynomial time with value oracle access to $f$; in particular, $T_0$ can be obtained by iteratively dropping any element from $T$ whose removal does not decrease the value until reaching a point where no such element exists. So we focus on showing that it  finds a set $U$ that satisfies (\ref{eq:prop_val}) and (\ref{eq:prop_marg}).

We begin by arguing that the algorithm is well defined. First note that $f(i \mid T_0 \setminus \{i\}) > 0$ for all $i \in T_0$ because otherwise $T_0$ would not be inclusion-wise minimal. Furthermore, we have to argue that the indices $j^\star$ and $k^\star$ as defined in the algorithm exist and satisfy $1 \leq j^\star \leq k^\star \leq \lvert T_0 \rvert$. To this end observe that $f(T) = f(T_0) \geq f(T_1) \geq \ldots \geq f(T_{\lvert T_0 \rvert})$ and $T_{\lvert T_0 \rvert} = \emptyset$, so $f(T_{\lvert T_0 \rvert}) = 0$. Therefore there must be a smallest $j$ with $0 \leq j \leq \lvert T_0 \rvert$ such that $f(T_j)\leq  \Psi$. This is $j^\star$. Moreover, since $\Psi < f(T) = f(T_0)$, it must be that $j^\star \geq 1$. Hence there must also be a smallest $k$ with $j^*-1 \leq k \leq \lvert T_0 \rvert$ such that $f(T_k) \leq (1-\delta) f(T_{j^\star-1})$. This is $k^\star$.
Finally, since $\delta > 0$, and $f(T_{j^\star-1})>\Psi\geq 0$, this $k^\star$ must satisfy $k^\star \geq j^\star$.

It remains to show that $U = T_{t^\star-1}$ fulfills the respective properties.

By definition, it holds that
\[
f(T_{j^\star-1})  =  f(T_{k^\star}) + \sum_{t \in \{j^\star,\ldots,k^\star\}} f( i_t \mid T_{t} ) .
\]
By rearranging and replacing $f( i_t \mid T_{t} )$ by $ \delta_{t} \cdot f( i_t \mid T_{0} \setminus\{i_t\} )$ we get that
\begin{align*}
f(T_{j^\star-1})  -  f(T_{k^\star}) &=  \sum_{t \in \{j^\star,\ldots,k^\star\}}\delta_{t} \cdot f( i_t \mid T_{0}\setminus\{i_t\} ) \\
& \leq \sum_{t \in \{j^\star,\ldots,k^\star\}}\delta_{t^\star} \cdot f( i_t \mid T_{0}\setminus\{i_t\} ) \\
&\leq \delta_{t^\star} \cdot f(\{i_{j^\star},\ldots,i_{k^\star}\}) \\
&\leq \delta_{t^\star} \cdot f(\{i_{j^\star},\ldots,i_{\lvert T_0 \rvert}\}) =\delta_{t^\star} \cdot  f(T_{j^\star-1}),
\end{align*}
where the first inequality is by the definition of $t^\star$, the second inequality is by Lemma~\ref{lem:xos-sum-of-marginals}, and the third inequality is by monotonicity.
Thus,  for all $i \in U =  T_{t^\star-1}$,
\[
\frac{f(i\mid T_{t^\star-1} \setminus\{i\} )}{f(i\mid T_0 \setminus \{i\})} \geq \delta_{t^\star} \geq  \frac{f(T_{j^\star-1})  -  f(T_{k^\star}) }{ f(T_{j^\star-1})}
 =  1- \frac{ f(T_{k^\star})}{ f(T_{j^\star-1})} \geq 1- \frac{(1-\delta) f(T_{j^\star-1})}{ f(T_{j^\star-1})} = \delta,
 \]
where the first inequality holds by definition of $i_{t^\star}$ and $\delta_{t^\star}$. Therefore, in order to establish Equation~\eqref{eq:prop_marg}, it remains to show that $f(i \mid T_0 \setminus \{i\}) \geq f(i \mid T \setminus \{i\})$. Indeed, since $f(T_0) = f(T)$ and $T_0 \subseteq T$, monotonicity of $f$ implies that
\[
f(i \mid T_0 \setminus \{i\}) = f(T_0) - f(T_0 \setminus \{i\}) \geq f(T) - f(T \setminus \{i\}) = f(i \mid T \setminus \{i\}).
\]

To prove Equation~\eqref{eq:prop_val} observe that  $f(T_{t^\star-1}) \geq f(T_{k^\star-1}) \geq (1-\delta) f(T_{j^\star-1}) \geq (1-\delta) \Psi$, and that $f(T_{t^\star-1}) \leq f(T_{j^\star-1}) \leq f(T_{j^\star}) +\max_{i\in T} f(\{i\}) \leq \Psi+\max_{i\in T} f(\{i\})$.
\end{proof}

\subsection{Computing a Good Set via a Demand Oracle}

We next present a subroutine that formalizes the argument outlined in the introduction that if we knew the value of $f(S^\star \cap A')$, then by running a demand query at appropriately chosen prices and using the scaling property of XOS functions from the previous section we can find a contract that constant-factor approximates $f(S^\star \cap A')$.

The actual argument is a bit more complicated than what we sketched before as it has to deal with the fact that we don't know the value of $f(S^\star \cap A')$; and that we cannot simply ignore the contribution of individual agents.

\begin{algorithm}
\caption{Approximately optimal contract given an estimate of $f(S^\star {\cap A'})$}\label{alg:xos-contract-estimate}
\KwData{An XOS function $f:2^A \rightarrow \mathbb{R}_{\geq 0}$, costs $\{c_{i}\}_{i\in A}$, an estimate $\tilde{y} \geq 0$ of $f(S^\star \cap A')$}

\KwResult{A set $U \subseteq A'$}

            Let $\Psi=\frac{\tilde{y}}{32} - \max_{i \in A'} f(\{i\})$.

        For every $i\in A'$, let $p_{i} = \frac{1}{2} \cdot \sqrt{ c_i \cdot \tilde{y} }$ ($p_{i} =\infty$ for $i\in A\setminusA'$)

    Let $T $ be a demand set with prices $p_{i}$ over the set $A'$

    \eIf{$0<\Psi<f(T)$}{

    $U \leftarrow $  the output of Algorithm~\ref{alg:scaling} on $(f, T, \Psi, \delta= \frac{1}{2})$
    }
    {
    $U\leftarrow \emptyset$
    }

\Return{U}

\end{algorithm}

\begin{lemma}
Algorithm~\ref{alg:xos-contract-estimate} runs in polynomial time with access to a demand and value oracle to $f$.
If $\tilde{y} \leq f(S^\star \cap A' )$, then the set $U \subseteq A'$ that it returns satisfies
\[
g(U) \geq \max\left\{\frac{\tilde{y}}{128}  - \frac{\max_{i \in A'} f(\{i\})}{4},0\right\}.
\]
\label{lem:gu128}
\end{lemma}

\begin{proof}
Algorithm~\ref{alg:xos-contract-estimate}
runs in polynomial time with access to a demand and value oracle to $f$, because it issues a single demand query to $f$ and makes at most one call to Algorithm~\ref{alg:scaling} which runs in polynomial-time with value oracle access to $f$.

We next prove the lower bound on $g(U)$, under the assumption that $\tilde{y} \leq f(S^\star \cap A')$.
If $\Psi\leq 0$ then the algorithm returns the empty set, which satisfies the claim.
So consider the case $\Psi > 0$. In this case we have
\begin{eqnarray}
f(T) & \geq & f(T) - \sum_{i \in T} p_i  \nonumber \\
& \geq & f(S^\star \cap A') - \sum_{i \in S^\star \cap A'} p_i \nonumber \\
& = & f(S^\star \cap A') - \frac{\sqrt{\tilde{y}}}{2} \cdot \sum_{i \in S^\star \cap A'} \sqrt{c_i} \nonumber \\
&\geq &  f(S^\star \cap A' ) - \frac{1}{2} \sqrt{f(S^\star \cap A' ) \cdot  \tilde{y}}\nonumber \\
& \geq &  \frac{1}{2} \cdot f(S^\star \cap A') , \label{eq:ft}
\end{eqnarray}
where the first inequality holds since the prices are positive, the second inequality uses that $T$ is a demand set over the set $A'$, the third inequality is by Lemma~\ref{lem:stronger-sumci}, and the last inequality holds because $\tilde{y} \leq f(S^\star \cap A')$.

Furthermore, note that, as $T$ is a demand set, we have to have $f(i \mid T \setminus\{i\}) \geq p_i$ for all $i \in T$ (because otherwise it would be beneficial to remove $i$).

Now, since $\Psi = \tilde{y}/32 - \max_{i \in A'} f(\{i\}) > 0$, we must have $\tilde{y} > 0$ and hence $\tilde{y}/2 > \tilde{y}/32 \geq \Psi$. This shows
$$f(T)\stackrel{\eqref{eq:ft}}{\geq} \frac{1}{2}\cdot f(S^\star \cap A') \geq  \frac{\tilde{y}}{2}
> \Psi.$$
By Lemma~\ref{lem:xosscaling},
the set $U \subseteq T$ therefore fulfills $$f(U) \geq \left(1-\delta\right) \Psi = \frac{1}{64} \tilde{y} - \frac{1}{2} \max_{i \in T} f(\{i\}) \geq \frac{1}{64} \tilde{y} - \frac{1}{2} \max_{i \in A'} f(\{i\}).$$
Furthermore, $U$ fulfills
\begin{equation}
    f(U) \leq \Psi + \max_{i \in T} f(\{i\}) \leq  \frac{\tilde{y}}{32}\label{eq:fu-up}
\end{equation}
and  for all $i \in U$
\begin{equation}
f(i \mid U \setminus\{i\}) \geq \delta f(i \mid T \setminus\{i\}) = \frac{1}{2} \cdot  f(i \mid T \setminus\{i\}) \label{eq:fu-marg}.
\end{equation}
We conclude that, for all $i \in U$, we have
\begin{align*}
    f(i \mid U \setminus\{i\})
    \stackrel{\eqref{eq:fu-marg}}{\geq} \frac{1}{2} \cdot f(i \mid T \setminus\{i\})
    \geq \frac{1}{2}\cdot  p_i = \frac{1}{4}\cdot \sqrt{c_i \tilde{y}} = \sqrt{2 c_i \frac{\tilde{y}}{32}} \stackrel{\eqref{eq:fu-up}}{\geq} \sqrt{2 c_i f(U)}.
\end{align*}
So, Lemma~\ref{lem:stronger-condition} implies $g(U) \geq \frac{1}{2} f(U)$. In combination, we obtain
\[
g(U) \geq \frac{1}{2}f(U) \geq \frac{1}{2} \left( \frac{1}{64} \tilde{y} - \frac{1}{2} \max_{i \in A'} f(\{i\}) \right),
\]
as claimed.
\end{proof}

\subsection{Putting It All Together}

We are finally in a position to wrap up our argument. Below we show that Algorithm~\ref{alg:xos-contract} achieves a constant-factor approximation to $g(S^\star)$ for XOS reward function $f$, and runs in polynomial time with access to a demand and a value oracle to $f$.

The idea is simple: Try out all contracts that incentivize a single agent; and use the subroutine from the previous section with polynomially many guesses for the value of $f(S^\star \cap A')$ to obtain additional candidate sets.
Argue that for the right guess of $f(S^\star \cap A')$ the better of the best contract that incentivizes a single agent, and the candidate set $U$ from the subroutine for this guess yields the desired approximation.

\begin{algorithm}
\caption{Approximate optimal contract for XOS}\label{alg:xos-contract}
\KwData{An XOS function $f:2^A \rightarrow \mathbb{R}_{\geq 0}$, costs $\{c_{i}\}_{i\in A}$, parameter $\xi>1$}

    Let $\mathcal{C}=\{\{i\} \mid i\in A \} \cup \{\emptyset\}$

    Let $A' =  \{i \in A \mid \frac{c_i}{f(\{i\})} \leq \frac{1}{2}\} $

\If{$A'\neq \emptyset \wedge \max_{i\in A'}f(\{i\}) >0$}{
Let $x = \max_{i\in A'} f(\{i\})/2 $

\For{$ j =0,.. ,\lceil \log_{\xi} 2n \rceil $}
{
    Let $x_{j} = x \cdot \xi ^ j$

    $U^{(j)} \leftarrow $ the output of Algorithm~\ref{alg:xos-contract-estimate} on ($f,\{c_i\}_{i\in A},A',\tilde{y} = x_j$)

    $\mathcal{C} \leftarrow \mathcal{C} \cup \{U^{(j)}\}$
}
}
\Return{$\arg\max_{S \in \mathcal{C}} g(S)$}

\end{algorithm}

\begin{proof}[Proof of Theorem~\ref{thm:xos}]
We show that Algorithm~\ref{alg:xos-contract} achieves the claims in the theorem for XOS reward functions $f$, assuming that we have access to a demand and a value oracle to $f$. We present details on how to obtain the result for submodular reward functions $f$ when we only have value oracle access to $f$ in Appendix~\ref{app:extension-to-submodular}.

We begin by observing that, for any $\xi > 1$, Algorithm~\ref{alg:xos-contract} runs in polynomial time with access to a demand and a value oracle to $f$, because we make only polynomially many calls to Algorithm~\ref{alg:xos-contract-estimate}, which itself runs in polynomial time with demand/value oracle access to $f$.

We next show that Algorithm~\ref{alg:xos-contract} obtains an approximation guarantee of $1/(256\xi+2)$ which tends to $1/258$ as $\xi \rightarrow 1$.
To this end, we distinguish between two cases. The first case is that  $f(S^\star\cap A') \leq 128 \xi \cdot \max\{0,\max_{i\in A} g(\{i\})\}$. Then by Lemma~\ref{lem:onebigagent}
\[
g(S^\star) \leq f(S^\star \cap A') + \max\{0,\max_{i \in A} g(\{i\})\} \leq (128 \xi + 1) \cdot \max\{0,\max_{i \in A} g(\{i\})\}.
\]
So, the best single action (or the empty set) gives at least an approximation of $\frac{1}{128\xi+1}$, which completes the proof of the theorem for this case.

In the other case, we have $f(S^\star\cap A') > 128 \xi \cdot \max\{0,\max_{i\in A} g(\{i\})\}$. So, in particular, we need to have $A' \neq \emptyset$ and $\max_{i \in A'} f(\{i\}) > 0$. Furthermore, $g(\{i\}) \geq \frac{1}{2} f(\{i\})$ for all $i \in A'$, resulting in $\max_{i\in A} g(\{i\}) \geq x$. So, in combination in this case $f(S^\star\cap A') \geq x$. On the other hand, by subadditivity of $f$ and the definition of $x$, $f(S^\star \cap A') \leq \sum_{i \in S^\star \cap A'} f(\{i\}) \leq 2n \cdot x$. Therefore, there is a unique $j^\star \in \{0, 1, \ldots, \lceil\log_{\xi} 2n\rceil\}$ for which $x_j \leq f(S^\star \cap A') < \xi \cdot x_j$.

Now, since $ \frac{1}{\xi} \cdot f(S^\star \cap A') \leq x_j \leq f(S^\star \cap A')$,
\begin{eqnarray*}
g(U^{(j^\star)})    & \geq &  \frac{x_{j^\star}}{128} - \frac{\max_{i\in A'} f(\{i\})}{4}  \\
&\geq & \frac{f(S^\star\cap A')}{128\cdot \xi} - \frac{\max_{i\in A} g(\{i\})}{2}  \geq  f(S^\star\cap A')\cdot \left(\frac{1}{128\cdot \xi} - \frac{1}{256\cdot \xi} \right) \\  & \geq &
\frac{128\xi \cdot g(S^\star)}{128\xi+1}\frac{1}{256\cdot \xi} = \frac{g(S^\star)}{256\xi+2},
\end{eqnarray*}
where the first inequality is by Lemma~\ref{lem:gu128}, the second inequality is since for every $i\in A'$ it holds that $\frac{c_i}{f(\{i\})}\leq \frac{1}{2}$ and thus $g(\{i\}) = f(\{i\})(1-\frac{c_i}{f(\{i\})}) \geq f(\{i\})/2$, the third and fourth inequality both use that $f(S^\star\cap A') > 128 \xi \cdot \max\{0,\max_{i\in A} g(\{i\})\}$, and the the fourth inequality additionally uses Lemma~\ref{lem:onebigagent}.
This  gives an approximation of $\frac{1}{256\xi+2}$.
\end{proof}