text:
\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}

redpajama_set_name: RedPajamaArXiv


Head of Iraq's National Railway Company Taleb al-Husseini said talks have been held in that regard given the importance of Iraq's railway network being connected to that of Syria before being linked to Iran's railroad network.
The remaining 32-kilometre stretch of railroad was completed during a recent trip to Iraq by Iranian President Hassan Rouhani and the following visit to Iran by Iraqi Prime Minister Adil Abdul-Mahdi. The two sides also agreed on how and when the railway should be inaugurated. Based on the agreement reached, the railroad from Khorramshahr will be connected to Iraq's national railway network, making it possible to make major trade exchanges and transport passengers from Iran all the way to other parts of the Middle East.


It has only been a few months since Robert Downey Jr. last put on his most famous suit by gracing the big screen in Marvel's mega-franchise Avengers Assemble, and just one year on; he's back! As the synopsis and the new trailer released this morning suggest, this seems to be Tony Stark's most personal challenge yet (don't count on him giving his Avengers pals a quick call for help in this one), setting up a film which should be more along the lines of the original Iron Man and deliberately steering away from Iron Man 2; the overcrowded nature of which didn't know whether it wanted to be an Iron Man sequel or an Avengers prequel - sounds good to me!
What do you think? Check out the new trailer below and leave your thoughts in the comments section.
Iron Man 3 is set for release in cinemas across the UK on April 26th 2013.
Are you looking forward to Tony Stark's third installment, or is this iron starting to rust? Will it be a blockbuster or lacklustre? Leave your comments below!


Coal Processing | Osborn South AfricaThe preparation of ROM coal commences the moment it is received from the mine . be applied as primary or secondary crushers in applications processing soft,.company primary and secondary coal processing,Coal Processing - Osborn South AfricaHorizontal Shaft Impact Crushers. Impact crushers may be applied as primary or secondary crushers in applications processing soft, low abrasion materials.
Primary Crushers; Jaw Crusher; Gyratory Crusher; Secondary and Tertiary , Crushing . Keywords: Mineral beneficiation, mineral processing, coal preparation, coal . Copper Mountain Mining Corporation is installing a secondary crusher at its.
CHP Plants; Coal Transformation; Electricity Plants; Energy Industry Own Use . Primary solid biofuels and charcoal are defined as any plant matter used directly as . Since charcoal is a secondary product, its treatment is slightly different than that . by the inputs of primary solid biofuels into the charcoal production process.
II – Processing of Primary and Secondary Fuels: Perspective on Petroleum . A petroleum refinery is a highly organized processing plant, which consists of many . derived by thermal or electrochemical means from fossil fuels such as coal,.
This Revision Bite helps you to understand why a business is set up and how . For example, metals and coal have to be mined, oil drilled from the ground, rubber . Secondary production: this is the manufacturing and assembly process.
Horizontal Shaft Impact Crushers. Impact crushers may be applied as primary or secondary crushers in applications processing soft, low abrasion materials.
Client:Huainan Mining Group Coal Preparation Co., Ltd . Primary and secondary separation of HM bath for lump coal and primary and secondary separation of.
Tug Valley Coal Processing Company began operation of the preparation ... for both the primary (rear brakes) and the secondary (front brakes) air systems.
Aug 16, 2012 . Secondary production involves recycling aluminum scrap to form new products, . Primary processing includes processing raw materials and.
Aug 17, 2016 . . company profile of a grinding mill, company primary and secondary coal processing, company is into grinding machines wheel and ceramics,.
Examples include coal, crude oil, natural gas, solar power, nuclear power . primary energy source employing a transformation or conversion process. Thus oil . Both electricity and heat can be obtained as primary and secondary energies. 2.2.2.2 .. demand, pricing policies, business environment, viability of alternative.
The energy intensity of primary materials processing is exceeded only by the . Long considered smokestack industries, PMPI companies handle much of their . The coke production process (i.e., the carbonization of coal) is inherently dirty, and ... and reducing the secondary packaging (the plastic web that holds the cans.
Energy Agency (IEA) in co-operation with the Statistical Office of the European. Communities . bringing this manual to completion include: Larry Metzroth (coal, electricity, . Pekka Loesoenen from Eurostat also contributed to the preparation of the manual. . What are Primary and Secondary Energy Commodities? 18. 4.
Theoretically, the secondary separation density can be manipulated by .. The primary product in a coal processing plant is the high-value product - thus any.


" Kripya is prakriya-draft ka badhava va maang website, niji bil aadi dwara karein. Draft - tinyurl.com/RtrMilawatRoktham Varna apko aur apki party ko vote nahin karenge. Kripya smstoneta.com jaise public sms server banayein jismein logon ki SMS dwara raay unke voter ID ke saath sabhi ko dikhe"
" Please promote/demand tinyurl.com/RtrMilawatRoktham RTR anti-adulteration officer draft via website, private member bill etc. Or will not vote for you/your party. Also, set up a public sms server like smstoneta.com so that SMS-opinions of all citizens, along with their voter IDs, can be seen without login by all " .
If you have received the internet link to this status via SMS from your voter, then it is order to you, to order CM to print the following DRAFT in Gazette.
= District Anti Adulteration Officer , and he appears in person or via a lawyer with affidavit before the DC (or officer he deputes), the DC (or officer he deputes) would accept his application to become DAAO after taking filing fee same as deposit amount for MP election.
3. (procedure for Talati ( = village officer = patwari = lekhpal) or Talati's clerks) If a citizen comes in person to Talati's office, pays Rs 3 fee , and approves at most five persons for the DAAO position, the Talati would enter his approvals in the computer and would him a receipt with his voter-id#, date/time and the persons he approved.
9 (procedure for CM ) As long as a DAAO has approvals of more than 34% citizens , CM need not replace him. But if a DAAO's approval goes below 34%, the CM can replace him with the officer of his choice.


THE NEXT wave brings endless possibilities… Warm, sultry and inviting; introducing FREE WAVE for her and him, the newest fragrances in the already best-selling HOLLISTER WAVE collection.
THE GIRL: Friendship is everything to her. She celebrates her life with excitement and embraces all to the fullest. Modern and sparkling, the Free Wave girl is not afraid to dare and smile. She surfs, dances and lives each day as a new discovery.


eXtreme flying kite Fly For Freedom! NON PULLUTION!
"Stunt Kite" Thank you for visit the extreme-kite website, we hope you come back often "Stunt Kite"
Buying our kites and accessories.
Copyright 2019 Weloveshopping.com All rights reserved.


text:
ANOC chief expects hijab ban to be lifted
November 06 2014 15:05:00
BANGKOK - Agence France-Presse
The Qatar women's basketball team refused to play in their Asian Games group match against Mongolia on Wednesday after being refused permission to wear the hijab. REUTERS Photo
Basketball's lifting of a controversial ban on headgear including religious scarves is only a "matter of time," a senior Olympic official said Thursday following a row at the Asian Games.
Sheikh Ahmad al-Fahad al-Sabah, president of the Association of National Olympic Committees, said he had been assured by talks with FIBA secretary general Patrick Baumann that the Islamic hijab headscarf and other headgear would soon be allowed on the court.
The basketball body's ban on headgear more than 5 centimeters (2 inches) wide caused controversy at the September-October Asian Games when Qatar's women's team forfeited their matches after being told they could not wear hijabs.
"It's more related to culture than to religion and if [the headgear is] secure, as FIFA has done it and other federations, I expect basketball will do it," Sheikh Ahmad told reporters at an ANOC meeting in Bangkok.
"We have discussed it, they have their opinion, we have our opinion. We found a road map, they already announced that some club events will start it, after this they will evaluate it.
"I think will be only a matter of time and (when) the mechanism has been decided," added the sheikh, who is also president of the Olympic Council of Asia, the body behind the Asian Games.
FIBA's ban on headgear has already been relaxed at the national level and the body has said tests could be carried out at international competitions next year.
FIBA has denied any "religious connotation" to its rule, which is aimed at improving safety. The approach conflicts with other sports including football, which ended a similar ban earlier this year.
FIBA's stance earlier ran into trouble in July when two Sikh players from India were reportedly forced to remove their turbans at the Asia Cup in China and had to tie their hair with elastic bands.
In August, reports also said that India's Anmol Singh was ordered to take off his patka head-covering at the FIBA Asia U18 Championship in Doha.

redpajama_set_name: RedPajamaCommonCrawl


The Minolta LS-150 Luminance Meter (successor to the LS-100) is a highly accurate luminance meter that uses a newly designed sensor with a spectral response that more closely matches the V(λ) spectral luminous efficiency function of the human eye to provide measurement results that correlate well with visual evaluation. The LS-150 is compact, ergonomic, and extremely portable running off AA batteries.
The LS-150 series uses a single lens reflex (SLR) optics system that provides users with several important capabilities. The SLR allows highly accurate targeting of light sources. Very small areas, even down to 1.3mm (when close-lens is used), can be measured accurately. Measurement areas at distances both long and short show up consistently in the viewfinder. This flexibility allows even those who have never used the instrument to gather precise measurement results.
The value of the measured luminance is easy to read on the clear backlit LCD screen and also on the bright viewfinder. With this capability, the instrument allows the user to never have to move the instrument from the eye while still perfectly controlling the measured object. The automatic mode sets the measurement time according to the brightness of the target. When measuring light sources that are particularly bright a neutral density eyepiece filter makes the job safe and comfortable. In all measuring tasks, our uniquely designed pistol-type grip provides for a secure hold on the instrument.
When measuring low luminance, the LS-150 comes through with a range that begins at 0.001cd/m². Color-correction and calibration functions built into the instrument give users the ability to choose a standard luminance and have differences corrected according to any light sources that are specified. The LS-150 included utility software allows the instrument to be controlled from a PC via USB 2.0. Repeated interval measurements can be conducted a specific number of times at specific intervals, measurement data can be displayed on graphs or lists, and data can be exported to spreadsheet applications. Optional close-up lenses allows for measurement of extremely small areas. Also, the optional illuminance adapter enables illuminance measurement as well.


text:
® Brown & Michaels, PC
Patent Prosecution Trademark Prosecution Copyright Prosecution IP Enforcement/Disputes IP Business Consulting IP Licensing & Commercialization IP Analyses & Opinions
IP Overview
Patent Info
Staff Directory About Us Contact Us News
About Brown & Michaels, PC
Brown & Michaels' is located in Ithaca, the "centrally isolated" home of Cornell University and Ithaca College in central New York State. We are a New York Professional Corporation.
It's no longer necessary to deal with impersonal law firms located in Washington DC or New York City, just because you are dealing with patent, trademark or copyright issues. While it might once have been important for patent attorneys to be physically close to the Patent Office, electronic filing systems, the fax machine, express mail, and e-mail have made it possible for a patent law firm far from the crowds of the major cities to serve a nation- and world-wide clientele as well as, or better than, the expensive big city firms. Inventors, companies, and institutions of all shapes and sizes are coming to realize the many advantages of working with a non-urban, intellectual property firm.
High quality -- both process & results are important
Experience in new technologies such as biotechnology, computer hardware/software and telecommunications.
Low overhead means you don't help finance expensive office space.
Emphasis on high quality and client satisfaction, not on billable hours or our prestige.
Inventor involvement in every step of the process.
Fast, convenient communications via email or fax.
Founded in 1980, our firm engages in an intellectual property practice which includes patents, trademarks and copyrights. We have advised inventors, institutions and companies in fields ranging from high-tech computer hardware and software, or the latest developments in biotechnology, communications, or sophisticated electronic systems, to improvements in household appliances. Our clients are located around the United States and around the world - we are perfectly comfortable working by phone, fax and e-mail with clients who will never physically be in our offices. We have represented many individual inventors and small companies, as well as large corporations such as BorgWarner Morse TEC, IBM, Smith Corona and Lucent Technologies, and educational institutions such as Cornell University and Boyce Thompson Institute for Plant Research.
Our inventors have received patents on chemical processing systems, test equipment, musical instruments, vaccines and medical diagnostics, energy systems, furniture, games, tools - you name it. We can do trademark/trade name searches quickly and accurately by computer, and have registered many marks for our clients.
New York State court rules require the following disclaimer: "Prior results cannot and do not guarantee or predict a similar outcome with respect to any future matter, including yours, in which a lawyer or law firm may be retained."
Our patent attorneys and patent agent are all registered and qualified to practice in the Patent and Trademark Office. To send an e-mail to one of the group, you can click on their name, below, and click on "Linkedin" to see their Linkedin profile.
Would you like to add a "virtual business card" to your contacts list for our firm or for any of our staff? Most e-mail programs support the vCard standard. Just click on "vCard" after an entry on this page, select your e-mail program to open the vCard if necessary, and a business card entry will automatically be created.
Michael F. Brown is a 1974 graduate of Cornell University College of Engineering, with a degree in Industrial Engineering (Data Processing). After working as a computer systems analyst and programmer for a number of years, he attended Cornell University Law School, passing the Patent Bar to become a Patent Agent while still a student. With Ralph R. Barnard (now retired), he founded our firm in 1980 as "Barnard and Brown". Mr. Brown was admitted to the New York State Bar in 1981, and is also admitted to practice in the US District Court for the Eastern District of New York. He has prosecuted many patent applications in a wide variety of fields, from animal vaccines to computer software, avionics and automotive products, household appliances to radio communications. Mr. Brown was selected to the New York Super Lawyers list each year from 2011 to 2016 as well as in 2007, and has received a "Distinguished" peer review rating from Martindale-Hubble. An Extra Class amateur radio operator and a licensed pilot, he has a strong practical background in electronics, computers and communications technologies. Mr. Brown is a 45-year veteran Scouter, a recipient of the Silver Beaver award from the Baden-Powell Council, Boy Scouts of America, and wrote the 1985 and 2008 editions of the Radio Merit Badge book for the BSA. He has been a member of the Ithaca Rotary Club for many years, and has been a guest speaker on "Weird and Wonderful Patents" and "Intellectual Property on the Internet" at over 50 Rotary Clubs, libraries, BOCES and other organizations around New York State. Mr. Brown retired on July 1, 2017.
Christopher A. Michaels is a graduate of Bucknell University, with a degree in Biochemistry. While working with our firm as a Patent Agent and Business Manager, he earned a degree in law from Syracuse University and has been the managing partner and CEO since 1994. He earned an MBA from The Wharton School at the University of Pennsylvania. He has worked as an executive for technology companies through multiple product development, financing and manufacturing rounds. He also consults for early stage technology companies providing strategic business development, strengthening the company's intellectual property position, assessing competitive landscapes, supporting product pipeline partnership licensing, and assessing future technology licensing opportunities. He is admitted as an attorney in New York and also to the Federal District Court for the Northern District of New York. Mr. Michaels has been working with our firm since 1989 and primarily practices in the areas of patent, copyright, trademark, trade secret, computer law and business law, with a special concentration in the rapidly developing area of Biotechnology. He has published articles on "Obviousness-style Double Patenting Isn't So Obvious", in the the Patent Journal, "The Utility Requirement in Biotechnology Patenting" in the Journal of the Patent Office Society, and on "Grant Applications as Publications", in the Journal of the Association of University Technology Managers. He has edited several books on trademark and patent practice.* Linkedin
Garth E. Coviello Since 2008, Garth Coviello has lived and worked in central NY while assisting clients with patent, trademark, and copyright matters. In this time, Garth has prepared or prosecuted hundreds of U.S. and international patent applications related to LED lighting, electrical connectors, medical devices, surgical devices, turbines, power systems, refrigeration, radar, semiconductors, nanotechnology, machine tooling, software, and computer systems, among other technologies. Garth's technical education includes an undergraduate degree from St. Lawrence University in physics and biology, and a master's degree from Binghamton University in philosophy with an emphasis on artificial intelligence, computer science, and systems science. Garth's technical experience also includes several years, prior to law school, engineering electrical connectors and robotic, automated manufacturing systems. In addition to patent preparation and prosecution, Garth counsels clients regarding matters such as licensing agreements, intellectual property infringement, patent validity, patentability, and trademark registerability. Garth enjoys working with clients ranging from entrepreneurs to national-scale and international-scale companies, catering to each client's specific expectations and needs to provide strong intellectual property protection and a high value at a reasonable cost.*
*Shareholder in Brown & Michaels, PC, a New York Professional Corporation.
Patent Agent
Lynda Wood is a registered Patent Agent and a graduate of Cornell University with a degree in Biological Sciences, specializing in Genetics. Lynda has worked at Brown & Michaels, PC since 2001 and in this time has prepared and prosecuted hundreds of cases in various fields including biotechnology, computers and automotive technologies. Lynda has also managed patent portfolios for Fortune 100 and 500 companies. Lynda has worked with clients and foreign agents on prosecution of their cases in the US and overseas as well as PCT practice. Lynda also has experience in preparing and filing design applications. Linkedin
Lorenzo Luna is a graduate of University of L'Aquila, Italy, with a degree in Computer Science. Lorenzo joined Brown & Michaels, PC in 2020 as a Technical Specialist, lending his expertise and analytical abilities to assist the firm with patent prosecution in the areas of computer software and elsewhere. Lorenzo is currently training at Brown & Michaels, PC to become a registered Patent Agent. Lorenzo also works on maintaining and improving this website.
A complete Staff Directory with e-mail addresses and phone extensions is available on this web site.
We look forward to being able to work with you for your intellectual property needs. If you have any questions, feel free to contact us by e-mail, phone, or at the postal address below.
Last updated: Tue, 16 Feb 2021
Planning to visit our office? Here's where we are in Ithaca. Click to open Google Maps.
400 M & T Bank Building
118 North Tioga Street
bpm@bpmlegal.com
Subject Patents Trademarks Copyright Glossary Other Select the subject of your question
Note: Sending a message does not establish attorney-client privilege
Owl logo and phrase "our knowledge protects yours" are registered service marks of Brown & Michaels, PC.
Notice: This website is "ATTORNEY ADVERTISING" under the rules of the New York State Court System which became effective February 1, 2007.
Privacy policy - All pages on this site are © Copyright 1996-2020 Brown & Michaels, PC


In Singapore, companies have the prerogative to fire at will, but what if you think you were unfairly dismissed?
Are there avenues of redress you can refer to in the event you feel victimised and shouldn't have lost your job?
Did you know that unfair dismissals, compensation and reinstatement are actually covered in the Employment Act?
What does the Employment Act say about unfair dismissals?
Under the Employment Act, an employee may be dismissed on the grounds of misconduct inconsistent with the fulfillment of the express or implied conditions of his service.
However, the employer should only do this after "due enquiry".
Usually this will amount to the holding of an inquiry, where the employee is given a chance to present his case.
The person(s) hearing the inquiry should not have any bias or personal interest in the case.
What should dismissed employees do to appeal against unfair dismissals?
An employee who considers himself dismissed without just cause may appeal in writing to the Minister for Manpower to be reinstated in his employment.
If the employee is a union member, the union can file the appeal to the Minister on the member's behalf, under the Industrial Relations Act.
The appeal must be submitted within one month from the date of dismissal.
The Ministry will inquire into the case and hear from both parties.
If the Minister is satisfied that the employee was dismissed without just cause, he may direct the employer to reinstate the employee and backpay wages for the period after the dismissal.
Alternatively, he may order the employer to pay an amount of wages as compensation, without reinstatement.
For a manager or executive meeting the first criteria: if you are dismissed with the necessary notice or salary-in-lieu, you must have served your employer for at least 12 months before you can appeal.
If your employer has given notice and terminates you according to your contract, the onus is on you to show proof that the dismissal is unfair.
The reasons your employer gave for the dismissal or termination.
Why you think you have been unfairly dismissed or terminated (you can cite specific incidents to support your appeal).
Whether your employer has given you notice of dismissal or termination.
Relevant documents related to your appeal, such as employment contract, letter of termination or warning letters.
This article was contributed by a lawyer to highlight the extent of coverage of the Employment Act with respect to unfair dismissals.
You are contradicting yourself. If an employer has to first of all conduct an inquiry before firing an employee, you don't call that "Employers can fire at will"!
You think MOM really bothers? They will just wayang through the procedures and still side with the employer!
A colleague told my department head that I committed an irresponsible act , and my employer, without questioning me, fired me but gave me one month's notice pay.
I brought the matter to MOM, who then arranged for me and my employer to meet up to try to settle the case amicably. A major shouting match erupted when my employer's representative repeated the accusations about my "irresponsible" attitude. I rebutted them by showing a few letters of compliments written by some customers.
The meeting ended in a deadlock and both sides were asked to present their case. I submitted my defence three days later, but my employer submitted their case two months later! Not only that, they even hired a lawyer to write 6-page letter for them and invented many other "offences" which I was said to have committed.
I rebutted them with a 7-page letter, successfully exposing their contradictions and lies in their letter.
The exchange of letters went on for nearly a year and the MOM suddenly stopped contacting me. I called up the officer in charge of the case and was told that it was still pending. But after receiving no reply for a few more months, I went to see my MP, who wrote a letter to MOM. One month passed, no reply. I went to see my MP again and he wrote another letter. Still no reply from MOM.
Two months later the then Manpower Minister Lee Boon Yang visited my constituency and I raised the matter with him during the dialogue session, asking him how long does MOM take to investigate cases of unfair dismissal. He answered normally a few weeks, and when I told him my case has dragged on for more than a year, the minister expressed surprise and said he will look into it. After the dialogue session, I tried to hand the letter to the minister personally but was stopped by his bodyguard. I could only hand the letter to my MP the following day.
This time the MOM finally replied. Relief for me? You bet! In their reply letter, the MOM turned around and accused me of making a false allegation against my employer by saying "Our investigation showed that you were contractually terminated and not dismissed "AS ALLEGED BY YOU". But they tried to play the nice guy by saying they have negotiated with my employer to pay me another month's salary-in-lieu but "without admitting that the termination was unlawful"!
I was furious by the accusation and "compensation" and questioned the MOM's sense of responsibility. The MOM later responded by saying the minister has found my employer justified in the termination and would not intervene.
I wrote to the Prime Minister (Goh Chok Tong then) but the letter did not reach him. It was redirected to MOM who replied that since I was contractually terminated and there was no such avenue for contractual termination to seek redress. I rebutted by saying, if the was no such avenue, then the MOM should not have taken up the case in the first place.
The MOM replied that in some cases of contractual termination, the employee can still seek redress if he feels he was unfairly terminated.
Ah ha! This means the MOM has indirectly admitted that they made a false accusation against me by saying "Our investigation showed that you were contractually terminated and not dismissed as ALLEGED BY YOU".
This loophole caught the PM office clerk and MOM off-guard, then what happened? Both sides never replied to me anymore!
By the way, I still have all the letters with me.
Wow! I just read about your case and i am not surprised that end of the day, MOM will often took Employer sides. The world is really unfair but nevertheless thank you for sharing your stories.


Many famous golfers have played at Wallasey over the years, Bobby Jones, James Braid and Henry Cotton came for the 1930 Open when qualifying embraced one round at Hoylake and one at Wallasey.
The 1936 Open qualifying again included Cotton as well as Gene Sarazen, Tommy Armour and a young eighteen year old amateur called Bobby Locke.
1956 saw Peter Thompson's third successive Open victory, for which, despite being the defending Open champion, he still had to qualify at Wallasey, along with previous Open champions Henry Cotton, Gene Sarazen, Max Faulkner and Bobby Locke. Together with Sam Snead, Peter Alliss, Dai Rees and Gary Player, then a twenty year old.