Proof. The theorem is proved by reducing from the problem \(\textsf{GAP-Bounded-IS}_{\mu, \eta}\). For any desired constant approximation ratio \(c\), we reduce from the problem \(\textsf{GAP-Bounded-IS}_{\mu, \eta}\) with constants \(\mu=\frac{1}{2c}\) and \(k=k(\mu)\). In the following, we let \(\gamma=|V|\), \(\beta=|E|\), and we define the constant \(\delta=\frac{1}{8ck^2}\), and \(\epsilon = \delta/3\). Notice that since the maximum degree is \(k\), we have \(\beta\le \frac{\gamma k}{2}\).

3.1.0.1 Construction.

Given a graph \(G=(V,E)\), we construct an instance as follows. We first define the set of agents. For each edge \(e\in E\), there exists an agent \(b_{e}\). Additionally, we have one “efficient" agent \(b^*\). Then, we define two sets of tasks:

• For each vertex \(v\in V\), we have a task \(d_v\) with reward \(r_{d_v}=1\). The probabilities of success and costs are constructed as follows.

  • Let \(p_{b^*,d_v}=1\) and \(c_{b^*,d_v}=1/2\).

  • If node \(v\in e\), i.e., the edge \(e\) connects \(v\) to another node, then let \(p_{b_{e},d_v}=\delta\) and \(c_{b_{e},d_v}=0\).

  • Let \(p_{b,d_v}=0\) and \(c_{b,d_v}=0\) for all other agents \(b\).

• For each edge \(e\in E\), we define a task \(d_{e}\) with \(r_{d_{e}}=\delta/2\). The probabilities of success and costs are defined as follows.

  • For agent \(b_{e}\), let \(p_{b_{e}, d_{e}}=1\) and \(c_{b_{e}, d_{e}}=0\).

  • Let \(p_{b,d_{e}}=c_{b,d_{e}}=0\) for all other agents \(b\).

3.1.0.2 Key idea of the proof.

To prove the statement, we mainly show the following two key statements: (i) If there exists an independent set of size at least \(\eta |V|\), then there exists an EF contract with principal’s expected revenue at least \(\frac{1}{2} \eta\gamma\); (ii) If all independent sets have size at most \(\mu \eta \gamma\), then all \(\epsilon\)-EF contracts achieve principal’s expected revenue strictly less than \(\frac{1}{2c}\eta\gamma\).

Intuitively, to achieve a high revenue, the principal should assign as many tasks as possible to the efficient agent \(b^*\), with a contract at least \(\frac{1}{2}\). Therefore, if there exists an independent set of size at least \(\eta |V|\), we can construct an EF contract that assigns at least \(\eta |V|\) tasks to \(b^*\), yielding a revenue of \(\frac{1}{2} \eta\gamma\). Otherwise, if all independent sets have size at most \(\mu \eta |V|\), the key for proving the upper bound on revenue is to show that the number of tasks assigned to agent \(b^*\) is at most \(\mu\eta\gamma\), even if we allow \(\epsilon\)-EF constraints, where \(\epsilon>0\) is a small constant and \(\epsilon<\frac{\delta}{2}\). This is shown by contradiction: There must be tasks \(d_v\) and \(d_{v'}\) assigned to \(b^*\), where \((v,v')=e \in E\), and the contract on each of these tasks is at least \(\frac{1}{2}\) by the effort constraints. Hence, agent \(b_{e}\) would get \(\delta\) performing tasks \(d_v\) and \(d_v'\). Thus, it must be the case that the payment to agent \(b_{e}\) from \(d_{e}\) (the only other task with positive success probability) is \(\delta\), which is impossible since \(r_{d_{e}}=\frac{\delta}{2}\) and violates the EF constraint by at least \(\frac{\delta}{2} > \epsilon\).

3.1.0.3 Sufficiency.

Assume that there is an independent set \(I\) such that \(|I|\ge \eta \gamma\). Consider the set of tasks \(\{d_v\}_{v\in V}\). We assign all the tasks \(d_v\) with \(v\in I\) to agent \(b^*\) and we set contract \(\alpha_{d_{v}} = \frac{1}{2}\) for every \(v\in I\). The effort constraints for agent \(b^*\) are therefore satisfied. We assign every remaining task \(d_v\), where \(v\in V\setminus I\), to any agent \(b_{e^*}\) with \(v \in e^*\). We set the contract for these tasks \(d_v\) to \(\alpha_{d_v} = 0\). Note that this will not increase the utility of agent \(b_{e^*}\), but it will increase the principal’s revenue by at most \((\gamma - |I|)\delta\).

Next, we consider the set of tasks \(\{d_{e}\}_{e\in E}\). For any edge \(e\in E\), note that at most one of its nodes \(v\in e\) belongs to the set \(I\). If such a node \(v\in e\cap I\) exists, then agent \(b_{e}\) would receive utility \(\frac{1}{2}\delta\) by switching to the set of tasks \(I\) assigned to \(b^*\). Hence, we assign the task \(d_{e}\) to this agent \(b_{e}\) by setting contract \(\alpha_{d_{e}}=1\), which leads to satisfying EF constraints. Otherwise, i.e., if \(e\cap I=\emptyset\), the corresponding agent \(b_{e}\) gets utility \(0\) by switching to agent \(b^*\)’s assigned set \(I\). Hence, we can assign the task \(d_{e}\) to agent \(b^*\) by setting contract \(\alpha_{d_{e}} = 0\). Note that this will not change agents’ utilities, and the EF constraints continue to hold. The principal gets revenue \(0\) for this set of tasks.

Hence, we conclude that the principal’s revenue is \[\frac{1}{2}|I| + (\gamma - |I|)\delta \ge \frac{1}{2}\eta \gamma.\]

3.1.0.4 Necessity.

Assume that all the independent sets have size at most \(\gamma \eta \mu\). Consider an allocation \(S\) and contracts \(\alpha\). Let \(S_{b^*}\) be the set of tasks assigned to \(b^*\) and \(V^*\) be the subset of nodes in \(V\) whose corresponding tasks are assigned to agent \(b^*\), i.e., \(V^* = \{v \in V\mid d_v \in S_{b^*} \}\). By the effort constraints, it must be the case that \(\alpha_{d_v} \ge \frac{1}{2}\) for all \(v\in V^*\).

We first show that the size \(|V^*| \le \gamma \eta \mu\). The following argument is by contradiction. Suppose \(|V^*| > \gamma \eta \mu\). By assumption, we have that \(V^*\) is not an independent set. Therefore, there must exist some edge \(e = (v_1, v_2)\) such that both nodes \(v_1, v_2 \in V^*\). This implies that both tasks \(d_{v_1}\) and \(d_{v_2}\) are assigned to agent \(b^*\). Hence, by the EF constraints, if an agent \(b_{e}\) switches to work on the set of tasks \(S_{b^*}\), it would receive payments at least \[\begin{align} \label{eq:cont1} \alpha_{d_{v_1}}p_{b_{e}, d_{v_1}} r_{d_{v_1}} + \alpha_{d_{v_2}}p_{b_{e}, d_{v_2}} r_{d_{v_2}} \ge \delta. \end{align}\tag{3}\] Hence, the payment to agent \(b_{e}\) is at least \(\delta\). However, since we are restricted to linear contracts, the payments to agent \(b_{e}\) is upperbounded by \(\delta/2\). Indeed, the only task outside \(S_{b^*}\) from which \(b_e\) can obtain positive utility is \(d_e\), whose payment is at most \(\delta/2\). Hence, the EF constraint is violated by at least \(\delta/2>\epsilon\) by Equation 3 , reaching a contradiction.

Thus, we can restrict to allocations in which \(|V^*|\le \gamma \eta \mu\). In this case, the principal’s revenue is at most \[\frac{1}{2}|V^*| + \delta(\gamma - |V^*|)+ \frac{\delta}{2}\beta \le \frac{1}{2} \eta \mu \gamma + \delta (\gamma+ \frac{\gamma k}{2})< \frac{1}{2c} \eta \gamma\] where in the first inequality we use \(\beta\le \frac{\gamma k}{2}\), and the strict inequality follows from \(\mu=1/(2c)\), \(\delta=1/(8ck^2)\), \(k\ge 1\), and \(\eta\ge 1/k\). This concludes the proof. ◻

Proof of 6. We present the proof for computing optimal EF contracts, \(\epsilon\)-EF contracts and EF1 contracts separately.

4.1.0.1 Computing optimal EF contracts.

Notice that if the number of tasks \(m\) is a constant, there are at most \(O(n^m)\) different allocations of tasks. To prove the result, it is sufficient to show that given an allocation \(S_1, S_2, \dots, S_n\), Program (2 ) is a linear program. By introducing additional variables \(t_{i,k}\) for all \(i \in \mathcal{N}, k\in \mathcal{M}\), we have the Program (2 ) become \[\begin{align} \label{OPT95EF95LP95add95var} \max_{\{\alpha_k\}_{k\in \mathcal{M}}} \quad & {\rm Rev}(S,\alpha) \\ \text{subject to} \qquad & \alpha_j p_{i, j }r_j - c_{i,j} \geq 0, \quad \forall i \in \mathcal{N}, j\in S_i. \nonumber\\ & \sum_{k \in S_i} \alpha_k p_{i, k }r_k - c_{i,k} \geq \sum_{k \in S_j} t_{i,k}, \quad \forall j \neq i. \nonumber \\ &t_{i, k} \ge \alpha_k p_{i, k} r_k - c_{i, k}, \quad \forall i \in \mathcal{N}, k\in \mathcal{M}. \nonumber \\ &t_{i, k} \ge 0, \quad \forall i \in \mathcal{N}, k\in \mathcal{M}. \nonumber \end{align}\tag{4}\] which is a linear program with polynomial number of variables and constraints. This concludes the proof.

4.1.0.2 Computing optimal \(\epsilon\)-EF contracts.

Following the proof for EF contracts, we can find the optimal \(\epsilon\)-EF contracts by first enumerating the allocation of tasks, and then formulating a linear program.

4.1.0.3 Computing optimal EF1 contracts.

The proof for EF1 contracts is more involved. We first note that given an allocation \(S_1, S_2, \dots, S_n\), there are at most a constant number of agents assigned a non-empty set of tasks. The number of such allocations is at most \(O(n^m)\). Hence, as in the proof of 6, we can enumerate over all the allocations.

Hence, in the following we fix an allocation \(S_1, S_2, \dots, S_n\). Consider the EF1 constraint relative to a pair of agents \((i, j)\), which guarantees that agent \(i\) prefers \(S_i\) over \(S_j\) up to one item. Note that if we directly enumerate all the possible removable tasks \(k_{i,j}\) (as in Definition 4) for all pairs of agents \((i,j)\), there would be an exponential number of possible sets of constraints, i.e., combinations of removal tasks. Our main result is that we actually only need to enumerate a polynomial number of possible sets of constraints. Then, for each allocation and combination of removal tasks, we solve a linear program.

For pair \((i, j)\), consider the following four cases:

(i) \(|S_i|>0\) and \(|S_j|=0\)

(ii) \(|S_i|=0\) and \(|S_j|=0\)

(iii) \(|S_i|>0\) and \(|S_j|>0\)

(iv) \(|S_i|=0\) and \(|S_j|>0\)

(i) Since the effort constraints give agent \(i\) weakly nonnegative utility from every assigned task, the EF1 constraints are satisfied.

(ii) Since both sides of EF1 constraints are \(0\), the EF1 constraints are satisfied.

(iii) There are at most \(|S_j|\) different possible EF1 constraints, which are obtained by enumerating all tasks \(k_{i,j}\in S_j\). Since there are at most \(m\) agents such that \(|S_i|>0\), we get that the total number of possible sets of EF1 constraints related to an agent \(j\) is \(O(m^m)\). Moreover, there are at most \(m\) such \(S_j\), and hence the total number of possible sets is \(O((m^m)^m)\).

(iv) Suppose the set of agents that are assigned the empty set is \(A\). First, note that there are at most \(n\) agents that are assigned empty sets of tasks. Hence, we cannot directly enumerate all the removable tasks \(k_{i,j}\) for each agent \(i\). However, the EF1 constraints of pairs \((i,j)\) imply that \[\label{aps95ef1950removeal} 0 \geq \sum_{k \in S_j\backslash\{k_{i,j}\}} \max\{\alpha_k p_{i, k} r_k - c_{i, k},0\}, \quad \forall j \neq i, \exists k_{i,j} \in S_j\tag{5}\] which implies that for task \(k\in S_j\setminus \{k_{i,j}\}\), the contract must be at most \[\alpha_k \le \tau_{i,k}\] This means that if the removable task is \(k_{i,j}\), as long as \(\alpha_k \le \tau_{i,k}\) holds for all tasks \(k\in S_j\setminus \{k_{i,j}\}\), the agent pair \((i,j)\) is EF1. Equivalently, an empty agent can have positive utility for at most one task in the compared bundle. Moreover, in this case, the contract \(\alpha_{k_{i,j}}\) of the removable task \(k_{i,j}\) has no restriction. In other words, there exists at most one task in \(S_j\), from which agent \(i\) can get positive utility.

Given an EF1 contract, suppose the set of removable tasks from \(S_j\) is \(\{k_{i,j}\}_{i\in A}\) for the set of agents \(A\). Note that \(\{k_{i,j}\}_{i\in A}\) is a multiset. By the above discussion, it determines the upper bounds (i.e., the break-even shares) for all contracts \(\alpha_k\) of all tasks \(k\in S_{j}\), which is also a sufficient condition for EF1 constraints to hold for all agents \(i\in A\) regarding set \(S_j\). Hence, instead of enumerating removable tasks for all agents \(i\in A\) regarding set \(S_j\), we can equivalently enumerate the upper bounds for contracts of all tasks in \(S_j\).

The algorithm for case (iv) works as in Algorithm 1.

For each task \(k \in S_j\), we calculate the break-even share \(\tau_{i,k}\) for agent \(i\in A\). Dispose \(\tau_{i,k}\) if \(\tau_{i,k}> 1\). To ease exposition, assume all break-even shares \(\tau_{i,k}\) are at most \(1\). Then, for each task \(k\), we sort all agents according to their break-even shares from low to high. Additionally, we add one virtual threshold value \(\omega=1\) to serve as an upper bound on contracts. Denote this list as \(l_k\). Now, we have \(|S_j|\) such lists. To determine the upper bounds for contract \(\alpha_k\) of task \(k\in S_j\), we can iterate over the threshold values in list \(l_k\) and use them as candidate upper bounds.

Suppose in one iteration, we obtain indexes \(\{i_k\}_{k\in S_j}\) for all the lists. Then, given an allocation of sets \(S_1, S_2, \dots, S_n\), which can be obtained by enumeration, we form a linear program \[\begin{align} \label{ef195tmp} \max_{\{\alpha_k\}_{k\in \mathcal{M}}} \quad & {\rm Rev}(S,\alpha) \\ \text{subject to} \qquad & \text{(\ref{effort-constraints})} \nonumber\\ & \text{ EF1 constraints from case (iii) } \nonumber\\ & \text{ Upper bounds \alpha_k \le l_k [i_k]for all the tasks} \nonumber \end{align}\tag{6}\]

However, not every enumeration of upper bounds is desired, as some of them may lead to a solution of (6 ) that is not EF1. To see this, consider an agent \(a \in A\) and two tasks \(k, k' \in S_j\). The indexes of agent \(i\) in lists \(l_k, l_{k'}\) are \(a_k, a_{k'}\), respectively. Suppose in one enumeration, we have enumerated indexes \(i_k > a_k\) and \(i_{k'}>a_{k'}\). By solving (6 ), it may lead to one undesired solution where \(\tau_{l_k [a_k],k} < \alpha_{k} \le \tau_{l_k [i_k],k}\) and \(\tau_{l_{k'} [a_{k'}],k'} < \alpha_{k'} \le \tau_{l_{k'} [i_{k'}],k'}\). This solution is not EF1 for agent \(a\), as it gives agent \(a\) a positive utility from exerting efforts on set \(S_j\).

To rule out the above undesired enumerated upper bounds, we need to check the feasibility of enumerated upper bounds as follows: If there do not exist two lists \(l_k, l_{k'}\) where \(k, k' \in S_j\) such that there is an agent \(a\in A\) appearing in both lists \(l_k[1, \dots, i_k-1]\) and \(l_{k'} [1, \dots, i_{k'}-1]\) for two enumerated index \(i_k, i_{k'}\), the enumeration of upper bounds is feasible.

Finally, we show that there are at most a polynomial number of possible sets of constraints in case (iv). Note that there are at most \(O(n^{|S_j|})\) possible sets of upper bounds for the set \(S_j\). Since there are at most \(m\) tasks, the total number of possible sets of upper bounds is \(O(n^m)\).

In summary of the above four cases, given a task allocation, we need to solve at most \(O(m^{m^2} n^m)\) different programs (6 ). For each task allocation, EF1 constraints, and upper bounds, we check if the enumerated upper bounds are feasible. If it is the case, we proceed to solve an LP: For each program (6 ), by introducing additional variables \(t_{i,k}\) for all \(i \in \mathcal{N}, k\in \mathcal{M}\) and rewriting EF1 contracts as in (4 ), we obtain a linear program with a polynomial number of variables and constraints. Finally, since the number of allocations of tasks is at most \(O(n^m)\), we have that the complexity of computing EF1 contracts is polynomial. This concludes the proof. ◻

Proof. Property (i) follows from the feasibility check in Line [alg295line8ir]. The second property follows from standard dynamic programming arguments that the algorithm keeps track of all possible utility profiles. ◻

Proof of 9. We will use the template of the \(\epsilon\)-EF dynamic programming approach designed in the previous section, enhanced with an initial guessing step and an adaptive grid. The pseudocode of our algorithm is in Algorithm 3.

Denote the optimal solution of Program (2 ) as \(\alpha^*= (\alpha_1^*, \alpha_2^*, \dots, \alpha_m^*)\), and its corresponding fair allocations of tasks as \(S^*= (S_1^*, S_2^*, \dots, S_n^*)\). Given the desired approximation \(\epsilon>0\) for the principal’s revenue, if \(m=1\), every full allocation is EF1 because the unique task can be removed from any compared nonempty bundle, so the problem reduces to choosing the revenue-maximizing effort-feasible assignment. Hence, we assume \(m\ge 2\) and set errors \(\nu= \min\{\epsilon, \frac{1}{6m}\}\) and \(\delta=\frac{\nu}{m}\).

4.2.0.3 Characterize the range of utilities.

Since, given an optimal allocation \(S^*\), the optimal contract is a solution to an LP, standard arguments imply that the utility of each agent is \(0\) or at least \(2^{-f(I)}\), where \(f(I)\) is a polynomial function of the instance size [61].

4.2.0.4 Guessing step.

We consider the following set of approximate agents’ utilities: \[\mathcal{G}= \{0\} \cup \{ m 2^{-i}\}_{i \in \{0,1,\ldots, f(I)+\log(m)\}}.\] Then, we enumerate over all the tuples \((U_i)_{i \in \mathcal{N}}\in \mathcal{G}^{n}\) which include a guess of the utility for each agent. Notice that there exists a guess \((U_i)_{i \in \mathcal{N}}\) such that: \[\begin{align} \label{eq:guess} \sum_{k \in S^*_i} \alpha_k^* p_{i, k }r_k - c_{i,k} \in [U_i/2,U_i] \quad \forall i \in \mathcal{N}. \end{align}\tag{8}\]

In the following, we focus on the execution of Algorithm 3 when the guess is correct and hence we assume that Equation 8 holds.

4.2.0.5 Adaptive grid.

Once we fix the utility profile \((U_i)_{i \in \mathcal{N}}\), we can define an adaptive grid for the dynamic programming as a function of the guesses.

We define a set of possible discrete contracts as follows. Consider a task \(j\in \mathcal{M}\) and an agent \(i\in \mathcal{N}\). Let \(\underline{\alpha}_{i,j}\) be the maximum \(\alpha\) in the set \[\begin{align} \label{def:barAlpha} \{\alpha\in [0,1]:\alpha p_{i,j} r_j-c_{i,j} \le U_i\}. \end{align}\tag{9}\] and let \(\underline{\alpha}_j= \min_i \underline{\alpha}_{i,j}\). Then, we define the set \[\begin{align}\label{eq:disc95contracts} &\mathcal{D}_{i,j}= \begin{cases} \{ \tau_{i,j}+\delta k (\underline{\alpha}_j-\tau_{i,j})\}_{k \in \{0,1,\ldots,1/\delta\}} \quad \quad \textrm{if }\underline{\alpha}_j\ge \tau_{i,j}\\ \mathcal{D}_{i,j}= \emptyset\textrm{otherwise} \end{cases} \end{align}\tag{10}\] Notice that for each \(j\in \mathcal{M}\), at least one of the sets \(\{\mathcal{D}_{i,j}\}_{i \in \mathcal{N}}\) is not empty thanks to Assumption 1. Finally, we set the possible contracts for a task \(j \in \mathcal{M}\) as \[\begin{align} \label{eq:disc95contract95EF1} \mathcal{D}_j=\cup_{i\in \mathcal{N}} \mathcal{D}_{i,j}. \end{align}\tag{11}\]

Now, we define the set of possible discretized utilities with a normalized uniform grid. In particular, for each agent \(i\), we define the discretized utilities as \[\begin{align} \label{eq:disc95utilities95EF1} \mathcal{U}_i=\{\delta k U_i\}_{k \in \{0,1,\ldots,1/\delta\} } \quad\forall i \in \mathcal{N} \end{align}\tag{12}\] Finally, we use a uniform grid over the principal’s expected revenue: \[\begin{align} \label{eq:discretization95principal95EF1} &\mathcal{H}=\{0,\delta, \ldots, 1\} \end{align}\tag{13}\]

Now, we are left to define the approximate utility functions \(\hat{U}_{i,j}(\cdot)\), \(\hat{U}^P(\cdot,\cdot)\). We let

\[\label{eq:disc95utility95EF1} \begin{align} &\hat{U}_{i,j}(\hat{\alpha}_j)= \lceil \hat{\alpha}_j p_{i,j} r_j-c_{i,j}\rceil_{\mathcal{U}_i} \quad \forall i \in \mathcal{N}, j \in \mathcal{M}, \hat{\alpha}_{j}\in \mathcal{D}_j\\ &\hat{U}^P(\hat{\alpha}_j,i)=\lceil (1-\hat{\alpha}_j) p_{i,j} r_j\rceil_{\mathcal{H}}\quad \forall i \in \mathcal{N}, j \in \mathcal{M}, \hat{\alpha}_{j}\in \mathcal{D}_j \end{align}\tag{14}\] It is easy to see that \(\lceil \hat{\alpha}_j p_{i,j} r_j-c_{i,j}\rceil_{\mathcal{U}_i}\) are well-defined thanks to the definition of \(\mathcal{D}_j\). Moreover, it holds \[\begin{align} \label{eq:good95apx95EF1} \hat{U}_{i,j}(\hat{\alpha}_j)\in [\max \{\hat{\alpha}_j p_{i,j} r_j-c_{i,j}, 0\},\max \{\hat{\alpha}_j p_{i,j} r_j-c_{i,j}, 0\} + \delta U_i] \quad \forall i \in \mathcal{N}, j \in \mathcal{M}, \hat{\alpha}_{j}\in \mathcal{D}_j \end{align}\tag{15}\]

4.2.0.6 Existence of a good solution with discretized contracts.

We start showing that there exists a discretized contract that is almost EF and almost optimal. Consider the contract \(\bar \alpha\) obtained by setting \(\bar \alpha_j = \lceil \alpha^*_j\rceil_{\mathcal{D}_j}\) for each \(j \in \mathcal{M}\). First of all, we have to show that such \(\bar \alpha\) is well-defined. To do that, we have to guarantee that \(\mathcal{D}_j\) includes at least one contract greater than \(\alpha^*_j\) for each \(j \in \mathcal{M}\).

Now, we show that \((S^*,\bar \alpha)\) is almost optimal and almost EF. Formally:

4.2.0.7 Find a good solution with discretized contracts.

Our algorithm enumerates over all the possible utilities \((U_i)_{i \in \mathcal{N}}\). For each guess, the algorithm runs Algorithm 2, and stores the set of EF1 contracts returned by it. Then, it outputs the contract that maximizes the principal’s expected revenue. Let’s denote this contract with \((\tilde{S}, \tilde{\alpha})\).

Now, by 7, Algorithm 3 finds a set \(\mathcal{C}\) which includes an allocation \(\hat{S}\) and a contract \(\hat{\alpha}\) that induce the same discrete utility profile as \((\bar \alpha, S^*)\). Formally, we have that \[\begin{align} &\sum_{i \in \mathcal{N}} \sum_{j \in S_i^*} \hat{U}^P( \bar \alpha_j,i)= \sum_{i \in \mathcal{N}} \sum_{j \in \hat{S}_i} \hat{U}^P(\hat{\alpha}_j,i)\\ &\sum_{k \in S_j^*} \hat{U}_{i,k}(\bar\alpha_k) = \sum_{k \in \hat{S}_j} \hat{U}_{i,k}(\hat{\alpha}_k), \quad \forall i,j\in \mathcal{N}\\ & \hat{\alpha}_j p_{i,j} r_j-c_{i,j} \ge 0, \quad \forall i \in \mathcal{N}, j \in \hat{S}_i. \end{align}\] The final step is to show that \((\tilde{S}, \tilde{\alpha})\) has principal’s expected revenue at least \(\rm{OPT\text{-}EF}-2\nu\), while by construction it is EF1 and satisfies the effort constraints. To do so, it is sufficient to show that \((\hat{S}, \hat{\alpha})\) is EF1 and \(2\nu\)-optimal, since such a contract belongs to \(\mathcal{C}\).

Hence, we are left to show that the contract \((\hat{S}, \hat{\alpha})\) is indeed EF1.

We conclude the proof by noticing that the algorithm runs in polynomial time. Indeed, Algorithm 3 clearly runs in polynomial time excluding the calls to Algorithm 2. Moreover, it is easy to see that each call to Algorithm 2 runs in polynomial time since the possible vectors of agents’ cumulative utilities and the principal’s cumulative expected revenue have polynomial size (agent \(i\) utility belongs to \(\{0,\delta U_i, \ldots,m U_i\}\), while the principal’s expected revenue belongs to \(\{0,\delta, \ldots,m\}\) ). ◻

Proof. In this proof, we prove the upper bound and lower bound for the PoF separately.

5.3.0.1 The upper bound \(O(n^2)\).

Let \(i^*\) be the agent that maximizes \(\sum_{j \in \mathcal{M}}\max\{p_{i,j}r_j-c_{i,j}, 0\}\). Note that this maximum value is at least \(\frac{{\rm OPT}}{n}\), where we recall that \({\rm OPT}\) is the optimal principal’s expected revenue without fairness concerns. Set the contract for each task as \(\alpha_j=\tau_{i^*,j}\) if \(p_{i^*,j}r_j-c_{i^*,j} \geq 0\); otherwise, set \(\alpha_j = \min_{i \in \mathcal{P}_j} \tau_{i,j}\) where \(\mathcal{P}_j=\{i \in \mathcal{N}\mid p_{i,j}r_j-c_{i,j} \geq 0\}\). We recall that this set is not empty thanks to Assumption 1.

Now, we construct the contract using a round-robin algorithm, where agents take turns to select one of the remaining tasks. In particular, we start with agent \(i^*\), followed by the other agents in an arbitrary order. Let \(\hat{S}\) be the set of remaining tasks. In each turn, each agent \(i\) chooses one of the remaining tasks in \(\arg\max_{j \in \hat{S}} \alpha_{j} p_{i,j} r_{j}-c_{i,j}\) with the following additional constraints:

• the agent selects the tasks by breaking ties to maximize the principal’s revenue;

• the agent does not select a task if no remaining task satisfies her effort constraint.

It is straightforward to see that the modifications do not affect the conclusion that the allocation given by the round-robin algorithm is EF1. Moreover, contracts are set in order to guarantee that for any task there exists an agent that can be incentivized to exert effort. Hence, our modified round-robin algorithm can ensure that the resulting allocation is a full allocation.

Now, we provide a lower bound on the principal’s expected revenue. To do that, it is sufficient to focus on agent \(i^*\). Since agent \(i^*\) has zero utility for all tasks by construction, and in each round, the tie-breaking rule assigns to \(i^*\) the task that provides the principal’s maximum revenue (among the remaining ones), it is easy to see that the principal has revenue at least \[\frac{1}{n} \sum_{j \in \mathcal{M}}\max\{p_{i^*,j}r_j-c_{i^*,j}, 0\} \ge \frac{1}{n^2}{\rm OPT},\] implying \(\rm{OPT\text{-}EF1}\geq \frac{1}{n^2}\cdot {\rm OPT}\).

5.3.0.2 The lower bound of PoF \(\Omega(\sqrt{n})\).

Let \(m=n\) with \(n \ge 9\). Also, let \(r= {\lfloor {\sqrt{n}} \rfloor} \ge 3\). The rewards are \(1\) for all the tasks. Next, we define the success probabilities and costs for each agent.

• For agent \(i \in \{1, 2, \dots, r-1\}\), let the probabilities and costs be \(p_{i, (i-1)r +k } = 1\), \(c_{i, (i-1)r +k } = \frac{r-1}{r}\) for \(k = 1, 2, \dots, r\), while for all other tasks \(j\), let \(p_{i, j } = 0\), \(c_{i, j } = 1\).

• For agent \(i=r\), let \(p_{i, j} = 1\), \(c_{i, j } = \frac{n-r(r-1)-1}{n-r(r-1)}\) for tasks \(j \in \{ r(r-1)+1, r(r-1)+2, \dots, n\}\), while for all other tasks \(j\), let \(p_{i, j} = 0\), \(c_{i, j} = 1\).

• For agent \(i\in \{r+1, \dots, n\}\), let \(p_{i, j} = \frac{2}{n}\), \(c_{i, j } = \frac{1}{n}\) for all the task \(j \in \mathcal{M}\).

Note that assigning one task to any agent \(i \in \{ r+1,\dots, n\}\) yields revenue at most \(\frac{1}{n}\) to the principal. To obtain the maximum revenue without fairness, the principal assigns to each agent \(i\in \{1, 2, \dots, r-1\}\) tasks \(j \in \{(i-1)r+1, \dots, ir\}\) and sets the contract \(\alpha_j = \frac{r-1}{r}>\frac{1}{n}\). The principal’s revenue from each of these contracts is \(\frac{1}{r}\). Moreover, the principal assigns task \(j\in \{r(r-1)+1, \dots, n\}\) to agent \(r\) with contract \(\alpha_j = \frac{n-r(r-1)-1}{n-r(r-1)}\). The revenue from each of these tasks is \(\frac{1}{n-r(r-1)} > \frac{1}{n}\). This leads to a cumulative principal’s revenue of \((r-1) \cdot r\cdot \frac{1}{r} + (n-r(r-1))\cdot \frac{1}{(n-r(r-1))} = r\).

Next, we provide an upper bound for the revenue achievable with EF1 contracts. Note that by construction, agent \(i \in \{1, 2, \dots, r-1\}\) can only be assigned tasks \(j \in \{(i-1)r+1, \dots, ir \}\), and agent \(i=r\) can only be assigned tasks \(j\in \{r(r-1)+1, \dots, n\}\).

We claim that if there exists one agent \(i \in \{1, 2, \dots, r\}\) assigned at least two tasks, while there is one agent \(i' \in \{r+1, \dots, n\}\) assigned no tasks, then agent \(i'\) will envy agent \(i\). Note that by construction, the minimum contract to incentivize agent \(i'\) is \(\frac{1}{2}\). Then, the claim holds because the minimum contract that incentivizes agent \(i \in \{1, 2, \dots, r-1\}\) and agent \(i=r\) is greater than that for agent \(i \in \{r+1,r+2, \dots, n\}\), i.e., \(\frac{r-1}{r} > \frac{1}{2}\) and \(\frac{n-r(r-1)-1}{n-r(r-1)}\ge \frac{r-1}{r} > \frac{1}{2}\) by \(n > 9\).

Recall that there are \(n\) tasks. As long as there are at least two tasks assigned to one agent in \(\{1, 2, \dots, r\}\), each agent in \(\{r+1, \dots, n\}\) must be assigned at least one task. Note that the maximum revenue from assigning task \(j\in \{r(r-1)+1, \dots, n\}\) to agent \(i=r\) is \(\frac{1}{n-r(r-1)} < \frac{1}{r}\) since \(r = {\lfloor {\sqrt{n}} \rfloor}\) implies \(n-r(r-1) \ge r\). Hence, the revenue of EF1 contracts in this case is at most \((n-r)\cdot \frac{1}{n} + (\frac{1}{r})\cdot(r)<2\), which is exactly the welfare extracted by assigning one task to each agent in \(\{r+1, \dots, n\}\) while the remaining tasks are assigned to agents in \(\{1, 2, \dots, r\}\).

Moreover, if all the agents in \(\{1, 2, \dots, r\}\) are assigned at most one task, then the revenue of EF1 contracts is also at most the welfare \((n-r)\cdot \frac{1}{n} + (\frac{1}{r})\cdot(r)<2\). This is because assigning more tasks to agents in \(\{r+1, \dots, n\}\) will lead to lower welfare, as \(\frac{1}{r}\ge\frac{1}{n-r(r-1)}>\frac{1}{n}\), i.e., the maximum welfare extracted from an agent in \(\{r+1, \dots, n\}\) completing one task is less than that from an agent in \(\{1, 2, \dots, r\}\).

In summary, the optimal revenue from EF1 contracts is at most \(2\), which leads to a retained fraction of at most \(\frac{2}{r} = \frac{2}{ {\lfloor {\sqrt{n}} \rfloor} }\). This concludes the proof. ◻

Proof. One possible EF contract is constructed as follows: for every task \(j\), among the set of agents \(\mathcal{M}_j = \{i \mid p_{i,j}r_j -c_{i,j} \ge 0\}\), assign task \(j\) to the agent \(i^* \in \mathcal{M}_j\) where \(i^* =\mathop{\mathrm{arg\,min}}_i \tau_{i,j}\) and set the contract \(\alpha_j = \tau_{i^*,j}\). The resulting allocation is EF and satisfies the effort constraints. ◻

Proof. Suppose that in an envy-free contract \((S,\alpha)\), task \(j\) is unallocated. Among the set of agents \(\mathcal{M}_j = \{i \mid p_{i,j}r_j -c_{i,j} \ge 0\}\), assign task \(j\) to the agent \(i^* \in \mathcal{M}_j\) where \(i^* =\mathop{\mathrm{arg\,min}}_i \tau_{i,j}\) and set the contract \(\alpha_j = \tau_{i^*,j}\). Apply the same operation to every other unallocated task. These modifications preserve the effort and EF constraints while increasing the principal’s revenue. ◻

Proof. Our proof is by a reduction from the partition problem: given a set of \(\ell\) integers \(n_1, n_2, \dots, n_{\ell}\), find a subset of integers \(\mathcal{S}\) such that \(\sum_{j\in \mathcal{S}} n_j = \sum_{j\in [\ell]} n_j/2\).

9.1.0.1 Construction.

We construct an instance where there are \(3\) agents, i.e., \(n=3\). Given a set of integers \(n_1, n_2, \dots, n_{\ell}\), we define the instance as follows. There exists a task \(j^*\) whose reward is \(r_{j^*}=1\). The agents’ success probabilities for task \(j^*\) are \(p_{1,j^*}=1\), \(p_{2,j^*}=p_{3,j^*}=\frac{1}{10}\), and their costs are \(c_{1,j^*}=\frac{1}{2}\), \(c_{2,j^*}=c_{3,j^*}=0\). Let \(M=10 \sum_{j \in [\ell]}n_j\). For each \(n_j\), we define a task \(j\) with reward \(r_j = n_j/M\). Additionally, we define the agents’ success probabilities as \(p_{1,j}=0\), \(p_{2,j}=p_{3,j}=1\) and costs as \(c_{1,j}=c_{2,j}=c_{3,j}=0\).

9.1.0.2 Sufficiency.

We show that if there exists a partition, then the principal’s revenue is at least \(\frac{1}{2}\).

Suppose that there is a set of indexes \(\mathcal{S}\) such that \(\sum_{j\in \mathcal{S}} n_j=\sum_{j \in [\ell]} n_j/2\). Consider the following contract. Assign task \(j^*\) to agent \(1\) with contracts as \(\alpha_{j^*}=\frac{1}{2}\). Moreover, assign all the tasks in \(\mathcal{S}\) to agent \(2\), and all the other tasks to agent \(3\). We set the contracts \(\alpha_j=1\) to all the tasks \(j\in [\ell]\).

We are left to show that the allocation satisfies the effort constraints and guarantees revenue at least \(\frac{1}{2}\). First, the allocation is envy-free. Indeed, by the construction above, agent \(1\) receives utility \(0\). Due to \(p_{1,j}=0\) for all \(j\in [\ell]\), agent \(1\) receives utility \(0\) switching to the tasks assigned to one of the other agents. Agent \(2\) receives utility \[\sum_{j\in \mathcal{S}} r_j p_{2,j} - c_{2,j} = \sum_{j\in \mathcal{S}} \frac{n_j}{M}=\frac{1}{20}.\] Switching to the tasks assigned to agent \(1\), agent \(2\) gets utility \(\alpha_{j^*}r_{j^*}p_{2, j^*} = \frac{1}{20}\). In addition, switching to the task assigned to agent \(3\), agent \(2\) gets utility \(\sum_{j \in [\ell]\setminus \mathcal{S}} \alpha_{j}r_{j}p_{2, j} - c_{2, j} = \frac{1}{20}\) since \(\mathcal{S}\) is a partition. Hence, the agent \(2\) does not envy other agents. A similar argument applies to agent \(3\).

We conclude noticing that the principal gets positive revenue only from task \(j^*\) and in particular \(\frac{1}{2}\).

9.1.0.3 Necessity.

We prove that if there is no partition, the principal’s revenue is at most \(\frac{1}{5}\).

We prove the result by contradiction. Assume that the principal’s revenue is strictly greater than \(\frac{1}{5}\). Notice that if agent \(1\) is not assigned the task \(j^*\), the principal’s revenue is at most: \[r_{j^*}p_{2,j^*} + \sum_{j\in [\ell]} r_{j}p_{2,j} = \frac{1}{10} + \sum_{j\in [\ell]} \frac{n_j}{M} = \frac{1}{5},\] which is obtained, for instance, by assigning all the tasks to agent \(2\).

Hence, task \(j^*\) must be assigned to agent \(1\) since by assumption the principal’s revenue is strictly greater than \(\frac{1}{5}\). This directly implies that the payment for task \(j^*\) is at least \(\alpha_{j^*}\ge \frac{1}{2}\) by the effort constraint of agent \(1\).

Now, we analyze the EF constraints of agent \(2\) and \(3\). Since agent \(2\) does not envy agent \(1\), the set of tasks \(S_2\subseteq[\ell]\) assigned to agent \(2\) must guarantee utility: \[\sum_{j \in S_2} \alpha_j r_j p_{2,j} = \sum_{j \in S_2} \alpha_j \frac{n_j}{M}\ge \alpha_{j^*}r_{j^*}p_{2, j^*} \ge 1/20.\] where the first inequality is by the EF constraints with respect to agent \(1\), and the second inequality is by \(\alpha_{j^*}\ge \frac{1}{2}\). Therefore, we have that \[\sum_{j \in S_2} \frac{n_j}{10 \sum_{j\in [\ell]}n_j} =\sum_{j \in S_2} \frac{n_j}{M} \ge \sum_{j \in S_2} \alpha_{j}\frac{n_j}{M}\ge \frac{1}{20}\] which further implies that \[\sum_{j \in S_2} n_j\ge \frac{1}{2} \sum_{j\in[\ell]} n_j.\] By similar arguments, we have that for the set of tasks \(S_3\subseteq [\ell]\) assigned to agent \(3\) guarantees: \[\sum_{j \in S_3} n_j\ge \frac{1}{2} \sum_{j\in [\ell]} n_j.\]

Hence, it must be the case that \(\sum_{j \in S_2} n_j = \sum_{j \in S_3} n_j= \frac{1}{2} \sum_{j\in [\ell]} n_j\), which implies that \(S_2\) defines a partition, leading to a contradiction.

We conclude the proof by noting that any algorithm guaranteeing a revenue fraction strictly larger than \(\frac{1}{5}/\frac{1}{2}=\frac{2}{5}\) would distinguish the two cases; equivalently, no approximation ratio strictly smaller than \(\frac{5}{2}\) is possible. ◻

Proof of 5. We prove the results by reducing from the partition problem: given a set of \(\ell\) integers \(n_1, n_2, \dots, n_{\ell}\), find a subset of integers \(\mathcal{S}\) such that \(\sum_{j\in \mathcal{S}} n_j = \sum_{j\in [\ell]} n_j/2\).

9.2.0.1 Construction.

There are two agents \(n=2\) and \(m=\ell+2\) tasks. There is a task \(j^*\) with reward \(r_{j^*}=1\). The success probabilities for task \(j^*\) are \(p_{1,j^*}=1\), \(p_{2,j^*}=\frac{1}{10}\), and the related costs are \(c_{1,j^*}=\frac{1}{2}\), \(c_{2,j^*}=0\). Moreover, there is one task \(\bar{j}\) with reward \(r_{\bar{j}} =1\). The success probabilities relative to task \(\bar j\) are \(p_{1,\bar{j}} = \frac{1}{10}, p_{2,\bar{j}} = 0\), and the costs are \(c_{1,\bar{j}} = c_{2,\bar{j}} = 0\).

Additionally, let \(T=\sum_{j\in S} n_j\) and \(M=5 T\). Then, for each \(n_j\in \mathcal{S}\), we add a task \(j\) with reward \(r_j = \frac{n_j}{M}\). The success probabilities relative to this task are \(p_{1,j}=1\), \(p_{2,j}=\frac{1}{2}\), and the costs are \(c_{1,j}=c_{2,j}=0\).

9.2.0.2 Sufficiency.

Suppose there exists a solution \(\mathcal{S}_1,\mathcal{S}_2\) to the partition problem, i.e., \(\mathcal{S}_1\cup \mathcal{S}_2 = \mathcal{S}\) and \(\sum_{j \in S_1} n_j = \sum_{j \in S_2} n_j = \frac{T}{2}\). We can construct the following contracts:

• \(\alpha_{j^*} = \frac{1}{2}\)

• \(\alpha_j = 0\) for \(j\in \mathcal{S}_1\)

• \(\alpha_j = 1\) for \(j \in \mathcal{S}_2\)

• \(\alpha_{\bar{j}}=1\)

The tasks assigned to agent \(1\) are \(G_1 = \mathcal{S}_1\cup \{j^*, \bar{j}\}\), and the tasks assigned to agent \(2\) are \(G_2 = \mathcal{S}_2\). First, by construction, the contracts satisfy the effort constraints. Next, we verify that the allocations are EF. For agent \(1\), the EF constraints are satisfied, i.e., \[\begin{align} \sum_{j\in S_1} r_j \alpha_j p_{1,j} + (r_{j^*} \alpha_{j^*}p_{1, j^*} - c_{1,j^*}) + r_{\bar{j}} \alpha_{\bar{j}} p_{1, \bar{j}}&= 0 + \frac{1}{10} \ge \sum_{j\in S_2} r_j \alpha_j p_{1,j}= \sum_{j\in S_2} \frac{n_j}{M} = \frac{\frac{1}{2}T}{5T} = \frac{1}{10} \end{align}\] The EF constraints for agent \(2\) are also satisfied, \[\begin{align} &\sum_{j\in S_2} r_j \alpha_j p_{2,j} = \frac{1}{2} \sum_{j\in S_2} \frac{n_j}{M}=\frac{1}{20} \ge \sum_{j\in S_1} r_j \alpha_j p_{2,j} + (r_{j^*} \alpha_{j^*}p_{2, j^*} - c_{2,j^*}) + r_{\bar{j}} \alpha_{\bar{j}} p_{2, \bar{j}} = \frac{1}{20} \end{align}\] Hence, we have that the principal’s revenue is \[(1-\alpha_{j^*})r_{j^*}p_{1,j^*} + \sum_{j\in S_1} (1-\alpha_j) r_j p_{1, j}= \frac{1}{2} + \sum_{j\in S_1} \frac{n_j}{M} = \frac{1}{2} + \frac{1}{10}.\]

9.2.0.3 Necessity.

Next, we show that if the partition problem is not satisfiable, then the optimal revenue is strictly smaller than \(\frac{1}{2} + \frac{1}{10}\). Now, we assume that there does not exist an equal partition.

We first notice that \(j^*\) must be assigned to agent \(1\) in the optimal solution. Otherwise, the principal’s revenue is at most \(\sum_{j \in \mathcal{S}} r_j p_{1,j} + r_{j^*} p_{2, j^*} + r_{\bar{j}} p_{1, \bar{j}} = \frac{1}{5} + \frac{1}{10} + \frac{1}{10} = \frac{2}{5}\).

Moreover, since agent \(2\) has probability \(0\) on task \(\bar{j}\), the optimal contract assigns \(\bar{j}\) to agent \(1\), which will not cause envy from agent \(2\) but will improve the principal’s revenue.

We have the following observation for the optimal solution.

Hence, by Observation 13, we have the binding EF constraints as \[\sum_{j\in \mathcal{S}_1} r_j \alpha_j p_{1,j} + (r_{j^*} \alpha_{j^*}p_{1, j^*} - c_{1,j^*}) + r_{\bar{j}} \alpha_{\bar{j}} p_{1, \bar{j}} = \sum_{j\in \mathcal{S}_2} r_j \alpha_j p_{1,j}\] \[\sum_{j\in \mathcal{S}_2} r_j \alpha_j p_{2,j} =\sum_{j\in \mathcal{S}_1} r_j \alpha_j p_{2,j} + r_{j^*} \alpha_{j^*}p_{2, j^*}\] We show that in the optimal contracts, \(\alpha_j = 0\) for all \(j\in \mathcal{S}_1\). Suppose this is not true. Then, given the optimal solution, we can construct a new solution with \(\alpha_j'=0\) for all \(j\in \mathcal{S}_1\) and for all \(j\in \mathcal{S}_2\), let \(\alpha_j' = \alpha_j - \Delta_j\) for some \(\Delta_j \ge 0\) such that the EF constraints of agent \(2\) is still binding, \[\label{33333} \sum_{j\in \mathcal{S}_2} r_j \alpha_j' p_{2,j} = r_{j^*} \alpha_{j^*}p_{2, j^*}\tag{19}\] which implies that \(\sum_{j\in \mathcal{S}_2} r_j\Delta_jp_{2,j} = \sum_{j\in \mathcal{S}_1} r_j\alpha_j p_{2,j}\). Due to \(p_{1,j} = 2p_{2,j}\) for all \(j \in S\), the EF for agent \(1\) is still binding, \[\label{44444} (r_{j^*} \alpha_{j^*}p_{1, j^*} - c_{1,j^*}) + r_{\bar{j}} \alpha_{\bar{j}} p_{1, \bar{j}} = \sum_{j\in \mathcal{S}_2} r_j \alpha_j' p_{1,j}\tag{20}\] This will lead to better principal’s expected revenue, which is a contradiction. Hence, in the optimal contracts, \(\alpha_j = 0\) for all \(j\in \mathcal{S}_1\).

To maximize the principal’s revenue, since all the utilities in \(\mathcal{S}_1\) will be extracted by the principal (\(\alpha_j = 0\) for \(j\in \mathcal{S}_1\)), it will be optimal to maximize the principal’s revenue from tasks \(j^*\) and \(\bar{j}\), and minimize the payments in \(\mathcal{S}_2\) to agents \(2\).

Recall that \(\alpha_{j^*}\ge \frac{1}{2}\) by the effort constraint of agent \(1\). By (19 ) and (20 ), we have the relation for \(\alpha_{j^*}\) and \(\alpha_{\bar{j}}\) in the optimal solution as \[\frac{4}{5}\alpha_{j^*} + \alpha_{\bar{j}}\frac{1}{10}=\frac{1}{2}\] Hence, to maximize the principal’s revenue from tasks \(j^*\) and \(\bar{j}\), i.e., \[(1-\alpha_{j^*})r_{j^*}p_{1, j^*} + (1-\alpha_{\bar{j}})r_{\bar{j}}p_{1, \bar{j}}\] we can set \(\alpha_{j^*}=\frac{1}{2}\) and \(\alpha_{\bar{j}}=1\), which indeed also minimizes the payments to agent \(2\) according to (19 ) and \(\alpha_{j^*} \ge \frac{1}{2}\). Hence, the optimal solution would have \(\alpha_{j^*}=\frac{1}{2}\) and \(\alpha_{\bar{j}}=1\), which implies that by (19 ), \[\sum_{j\in \mathcal{S}_2} r_j \alpha_j p_{2,j} = \frac{1}{20}\] By our previous arguments, to maximize the principal’s expected revenue, we finally need to maximize the revenue \[\sum_{j\in \mathcal{S}_1} (1-\alpha_j) r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} (1-\alpha_j) r_j p_{2,j} = \sum_{j\in \mathcal{S}_1} r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} r_j p_{2,j} - \frac{1}{20}\] which is equivalent to maximizing \(\sum_{j\in \mathcal{S}_1} r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} r_j p_{2,j}\) while ensuring \(\sum_{j \in \mathcal{S}_2} r_j p_{2,j} - \frac{1}{20}\ge 0\) due to that the principal revenue from agent \(2\) is nonnegative.

Note that if \(\sum_{j\in \mathcal{S}_2} r_jp_{2,j} =\frac{1}{20}\), it implies \(\sum_{j\in \mathcal{S}_2} n_j = \frac{1}{2}T\), i.e., an equal partition. Hence, we must have \[\sum_{j\in \mathcal{S}_2} r_jp_{2,j} >\frac{1}{20}\] which due to \(p_{1, j} > p_{2, j}\), implies that \[\sum_{j\in \mathcal{S}_1} (1-\alpha_j) r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} (1-\alpha_j) r_j p_{2,j} = \sum_{j\in \mathcal{S}_1} r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} r_j p_{2,j} - \frac{1}{20} <\frac{1}{10}.\] Hence, the total revenue will be \[(1-\alpha_{j^*})r_{j^*}p_{1, j^*} + (1-\alpha_{\bar{j}})r_{\bar{j}}p_{1, \bar{j}} + \sum_{j\in \mathcal{S}_1} (1-\alpha_j) r_j p_{1, j} + \sum_{j \in \mathcal{S}_2} (1-\alpha_j) r_j p_{2,j} < \frac{1}{2} + \frac{1}{10}.\] ◻

Proof. We prove the results by reducing from partition: Given a set \(S\) of integers \(\{n_j\}\), find a subset of elements such that their sum equals \(\frac{\sum_{j\in S} n_j}{2}\).

9.3.0.1 Construction

There are three agents, i.e., \(n=3\). Let \(C=10\). Define two tasks \(j^*\) and \(\hat{j}\) with reward \(r_{j^*} = r_{\hat{j}}=1\). The success probabilities are \(p_{1,j^*}=p_{1,\hat{j}}=1\) and \(p_{2,j^*}=p_{3,j^*}=p_{2,\hat{j}}=p_{3,\hat{j}}=\frac{1}{C}\), and the costs are \(c_{1,j^*} = c_{1,\hat{j}}=\frac{1}{2}\) and \(c_{2,j^*}=c_{3,j^*}=c_{2,\hat{j}}=c_{3,\hat{j}}=0\).

Let \(M=C \sum_{j\in S}n_j\). For each \(n_j\), we define a task \(j\) with reward \(r_j = \frac{n_j}{M}\). The success probabilities are \(p_{1,j}=0\), \(p_{2,j}=p_{3,j}=1\). The costs are \(c_{1,j}=0\), \(c_{2,j}=c_{3,j}=0\).

9.3.0.2 Sufficiency.

Suppose there is a set of indexes \(S^*\) such that \(\sum_{j\in S^*} n_j=\frac{\sum_{j\in S} n_j}{2}\). Assign both tasks \(j^*, \hat{j}\) to agent \(1\) with \(\alpha_{j^*}=\alpha_{\hat{j}}=1/2\). Moreover, assign all the tasks in \(S^*\) to agent \(2\), and all the other tasks in \(S\setminus S^*\) to agent \(3\). Set all the contracts \(\alpha_j=1\) to all tasks \(j\in S\).

Next, we verify that the allocation is EF1. Indeed, agent \(1\) gets \(0\) utility from the allocated tasks, and if switching to the sets of tasks of agent \(2\) or \(3\), it gets utility \(0\).

Also, agent \(2\) does not envy agent \(3\), and it gets the same utility if switching to the set of tasks assigned to agent \(3\). By simple calculation, we have that agent \(2\) gets utility \(\sum_{j\in S^*} \frac{n_j}{M}=\frac{1}{20}\). By removing the task \(j^*\) or \(\hat{j}\) from the set assigned to agent \(1\), agent \(2\) gets utility \(\frac{1}{20}\) from the remaining task. Hence, the EF1 constraints are satisfied. A similar argument also holds for agent \(3\).

Hence, the principal’s revenue (only obtained from tasks \(j^*, \hat{j}\)) is \(1\).

9.3.0.3 Necessity.

We show that if there exists a contract with utility strictly greater than \(\frac{1}{5} + \frac{1}{2}\), then there exists a partition.

First, notice that if at most one of the tasks \(j^*, \hat{j}\) is assigned to agent \(1\), the principal’s revenue is at most: \[r_{j^*} p_{1, j^*} - c_{1,j^*}+ r_{\hat{j}}p_{2,\hat{j}} + \sum_{j\in S} r_j p_{2,j} = \frac{1}{2}+ \frac{1}{10}+ \sum_{j\in S} \frac{n_j}{M} =\frac{1}{5}+ \frac{1}{2}.\] Hence, in order to achieve optimal utility, both tasks \(j^*\) and \(\hat{j}\) are assigned to agent \(1\) and the contracts are set \(\alpha_{j^*} , \alpha_{\hat{j}} \ge 1/2\).

Since agent \(2\) envies agent \(1\) up to at most one task (EF1), it must be the case that \(S_2\) (the set of tasks assigned to agent \(2\)) guarantees that \[\sum_{j \in S_2} \alpha_j r_j p_{2,j} = \sum_{j \in S_2} \alpha_j \frac{n_j}{M}\ge \alpha_{j^*} r_{j^*} p_{2,j^*} \ge \frac{1}{20}.\] which further implies \[\sum_{j \in S_2} \frac{n_j}{10 \sum_{j \in S}n_j}= \sum_{j \in S_2} \frac{n_j}{M}\ge \frac{1}{20}\] and \[\sum_{j \in S_2} n_j\ge \frac{1}{2} \sum_{j \in S} n_j.\] Similar results hold for agent \(3\), \[\sum_{j \in S_3} n_j\ge \frac{1}{2} \sum_{j \in S} n_j.\] The above together implies the existence of a partition. Thus any guarantee with revenue fraction strictly larger than \(\frac{7}{10}\) would distinguish the two cases; equivalently, no approximation ratio strictly smaller than \(\frac{10}{7}\) is possible. ◻

Proof. We prove the results by reducing from partition: Given a set of integers \(\{n_1, \dots, n_{\ell}\}\), find a subset of elements such that their sum equals \(\frac{\sum_{j \in [ \ell ]} n_j}{2}\).

9.3.0.4 Construction

There are three agents, i.e., \(n=3\). Define two tasks \(j^*\) and \(\hat{j}\) with reward \(r_{j^*} = r_{\hat{j}}=1\). The success probabilities are \(p_{1,j^*}=p_{1,\hat{j}}=1\) and \(p_{2,j^*}=p_{3,j^*} = \frac{1}{10}, p_{2,\hat{j}}=p_{3,\hat{j}}=2\epsilon\), and the costs are \(c_{1,j^*} = c_{1,\hat{j}}=\frac{1}{2}\) and \(c_{2,j^*}=c_{3,j^*}=c_{2,\hat{j}}=c_{3,\hat{j}}=0\).

Let \(M=10 \sum_{j\in [\ell]}n_j\). For each \(n_j\), we define a task \(j\) with reward \(r_j = \frac{n_j}{M}\). The success probabilities are \(p_{1,j}=0\), \(p_{2,j}=p_{3,j}=1\). The costs are \(c_{1,j}=0\), \(c_{2,j}=c_{3,j}=0\).

9.3.0.5 Sufficiency.

We show that if there exists a partition, then the principal’s revenue is at least \(1\).

Suppose that there is a set of indexes \(\mathcal{S}\) such that \(\sum_{j\in \mathcal{S}} n_j=\sum_{j \in [\ell]} n_j/2\). Consider the following contract. Assign task \(j^*\) and \(\hat{j}\) to agent \(1\) with contracts as \(\alpha_{j^*}=\alpha_{\hat{j}}=\frac{1}{2}\). Moreover, assign all the tasks in \(\mathcal{S}\) to agent \(2\), and all the other tasks to agent \(3\). We set the contracts \(\alpha_j=1\) to all the tasks \(j\in [\ell]\).

We are left to show that the allocation satisfies the effort constraints and guarantees revenue at least \(1\). First, the allocation is \(\epsilon\)-EF. Indeed, by the construction above, agent \(1\) receives utility \(0\). Due to \(p_{1,j}=0\) for all \(j\in [\ell]\), agent \(1\) receives utility \(0\) switching to the tasks assigned to one of the other agents. Agent \(2\) receives utility \[\sum_{j\in \mathcal{S}} r_j p_{2,j} - c_{2,j} = \sum_{j\in \mathcal{S}} \frac{n_j}{M}=\frac{1}{20}.\] Switching to the tasks assigned to agent \(1\), agent \(2\) gets utility \[\alpha_{j^*}r_{j^*}p_{2, j^*} + \alpha_{\hat{j}}r_{\hat{j}}p_{2, \hat{j}} = \frac{1}{20} + \epsilon,\] which implies it is \(\epsilon\)-EF. In addition, switching to the task assigned to agent \(3\), agent \(2\) gets utility \[\sum_{j \in [\ell]\setminus \mathcal{S}} \alpha_{j}r_{j}p_{2, j} - c_{2, j} = \frac{1}{20}\] because \(\mathcal{S}\) is a partition. Hence, the agent \(2\) does not envy other agents. A similar argument applies to agent \(3\).

We conclude noticing that the principal gets positive revenue only from task \(j^*, \hat{j}\) and in particular \(1\).

9.3.0.6 Necessity.

We show that if there exists a contract with utility strictly greater than \(\frac{7}{10}\), then there exists a partition.

First, notice that if at most one of the tasks \(j^*, \hat{j}\) is assigned to agent \(1\), the principal’s revenue is at most: \[r_{\hat{j}} p_{1, \hat{j}} - c_{1,\hat{j}}+ r_{j^*}p_{2,j^*} + \sum_{j\in [\ell]} r_j p_{2,j} = \frac{1}{2}+ \frac{1}{10}+ \sum_{j\in [\ell]} \frac{n_j}{M} =\frac{7}{10}.\] Hence, in order to achieve optimal utility, both tasks \(j^*\) and \(\hat{j}\) are assigned to agent \(1\) and the contracts are set \(\alpha_{j^*} , \alpha_{\hat{j}} \ge 1/2\).

Since agent \(2\) envies agent \(1\) up to \(\epsilon\), it must be the case that \(S_2\) (the set of tasks assigned to agent \(2\)) guarantees that \[\sum_{j \in S_2} \alpha_j r_j p_{2,j} = \sum_{j \in S_2} \alpha_j \frac{n_j}{M}\ge \alpha_{j^*} r_{j^*} p_{2,j^*} + \alpha_{\hat{j}} r_{\hat{j}} p_{2,\hat{j}} -\epsilon\ge \frac{1}{20} .\] which further implies \[\sum_{j \in S_2} \frac{n_j}{10 \sum_{j \in \{1, 2, \dots, \ell\}}n_j}= \sum_{j \in S_2} \frac{n_j}{M}\ge \frac{1}{20}\] and \[\sum_{j \in S_2} n_j\ge \frac{1}{2} \sum_{j \in [\ell]} n_j.\] Similar results hold for agent \(3\), \[\sum_{j \in S_3} n_j\ge \frac{1}{2} \sum_{j \in [\ell]} n_j.\] The above together implies the existence of a partition. Thus any guarantee with revenue fraction strictly larger than \(\frac{7}{10}\) would distinguish the two cases; equivalently, no approximation ratio strictly smaller than \(\frac{10}{7}\) is possible. ◻

Proof. We prove a subroutine guarantee with internal parameter \(\xi>0\): Algorithm 4 returns a \(3\xi\)-EF contract with revenue at least \(\rm{OPT\text{-}EF}-2\xi\). Invoking the subroutine with \(\xi=\epsilon/3\) gives an \(\epsilon\)-EF contract with revenue at least \(\rm{OPT\text{-}EF}-2\epsilon/3\ge \rm{OPT\text{-}EF}-\epsilon\), proving the theorem. Let denote an optimal solution to Program (2 ) with \(\alpha^*= (\alpha_1^*, \alpha_2^*, \dots, \alpha_m^*)\), and its corresponding fair allocations of tasks \(S^*= (S_1^*, S_2^*, \dots, S_n^*)\).

The proof proceeds as follows. We build a discretized instance of the problem, we solve it with dynamic programming, and we show that one of the solutions returned by Algorithm 2 is approximately EF and approximately optimal.

10.1.0.1 Discretized instance.

We start building the discretized instance. Given an internal parameter \(\xi>0\), we define \(\delta=\frac{\xi}{m}\). We discretize the set of contracts, agents’ utilities, and the principal’s expected revenue with a grid of step \(\delta\). Formally, we define \[\label{eq:discretization95epsilon95EF} \begin{align} &\mathcal{D}_j= \{0,\delta, \ldots, 1\} \quad \forall j \in \mathcal{M}\\ &\mathcal{U}_{i}=\{0,\delta, \ldots, 1\} \quad \forall i \in \mathcal{N}\\ &\mathcal{H}=\{0,\delta, \ldots, 1\}\\ \end{align}\tag{21}\]

In the following since all sets \(\mathcal{D}_j\) and \(\mathcal{U}_i\) are the same for \(i\in \mathcal{N}\) and \(j\in \mathcal{M}\), we will refer to these sets simply with \(\mathcal{D}\) and \(\mathcal{U}\), respectively. Finally, we define \[\label{eq:disc95utility95EF} \begin{align} &\hat{U}_{i,j}(\hat{\alpha}_j)= \lceil \hat{\alpha}_j p_{i,j} r_j-c_{i,j}\rceil_{\mathcal{U}} \quad \forall i \in \mathcal{N}, j \in \mathcal{M}, \hat{\alpha}_{j}\in \mathcal{D}\\ &\hat{U}^P(\hat{\alpha}_j,i)=\lceil (1-\hat{\alpha}_j) p_{i,j} r_j\rceil_{\mathcal{H}}\quad \forall i \in \mathcal{N}, j \in \mathcal{M}, \hat{\alpha}_{j}\in \mathcal{D} \end{align}\tag{22}\]

10.1.0.2 Existence of a good solution with discretized contracts

Consider the contract \(\bar \alpha\) obtained setting \(\bar \alpha_i= \lceil \alpha^*_i\rceil_{\mathcal{D}}\). We show that \((S^*,\bar \alpha)\) is almost optimal and almost EF. Formally: \[\label{discreteize95withinsec4295eps} \begin{align} \sum_{k \in S^*_i}\bar{\alpha}_k p_{i, k }r_k - c_{i,k} &\ge \sum_{k \in S^*_i}\alpha_k^* p_{i, k }r_k - c_{i,k}\\ & \ge \sum_{k \in S^*_j} \max\{ \alpha_k^* p_{i, k }r_k - c_{i,k}, 0\}\\ & \ge \sum_{k \in S^*_j} \max\{ (\bar{\alpha}_k -\delta) p_{i, k }r_k - c_{i,k}, 0\} \\ & \ge \sum_{k \in S^*_j} \max\{ \bar{\alpha}_k p_{i, k }r_k - c_{i,k}, 0\} -\xi\quad \quad \forall i,j \in \mathcal{N} \end{align}\tag{23}\] where the second inequality is due to \((\alpha^*, S^*)\) satisfying the EF constraints. Moreover, the effort constraints for the tasks continue to hold as we round up the contracts.

Finally, we get that the principal’s revenue under the new (approximate) contracts \((\bar{\alpha}, S^*)\) is at least \(\rm{OPT\text{-}EF}-\xi\), which is \[\label{opt95approximation} \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-\bar{\alpha}_k) p_{i,k}r_k \ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-{\alpha}_k^* -\delta) p_{i,k}r_k \ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-{\alpha}_k^* ) p_{i,k}r_k -\xi = \rm{OPT\text{-}EF}-\xi.\tag{24}\]

10.1.0.3 Find a good solution with discretized contracts.

The pseudocode of our algorithm is in Algorithm 4. Our algorithm enumerates over all the possible pairs \((S,\alpha) \in \mathcal{C}\) returned by Algorithm 2, and outputs the \(3\xi\)-EF contract that maximizes the principal’s expected revenue. Denote this contract by \((\tilde{S}, \tilde{\alpha})\).

By Proposition 7, Algorithm 2 finds a set \(\mathcal{C}\) which includes an allocation \(\hat{S}\) and a contract \(\hat{\alpha}\) that induce the same discretized utility profile as \((\bar \alpha,S^*)\). Formally, we have that \[\begin{align} &\sum_{i \in \mathcal{N}} \sum_{j \in S_i^*} \hat{U}^P( \bar \alpha_j,i)= \sum_{i \in \mathcal{N}} \sum_{j \in \hat{S}_i} \hat{U}^P(\hat{\alpha}_j,i)\\ &\sum_{k \in S_j^*} \hat{U}_{i,k}(\bar\alpha_k) = \sum_{k \in \hat{S}_j} \hat{U}_{i,k}(\hat{\alpha}_k) \forall i,j\in \mathcal{N}\\ & \hat{\alpha}_j p_{i,j} r_j-c_{i,j} \ge 0 \quad \forall i \in \mathcal{N}, j \in \hat{S}_i. \end{align}\]

The last step of the proof shows that \((\tilde{S}, \tilde{\alpha})\) achieves principal’s expected revenue at least \(\rm{OPT\text{-}EF}-2\xi\). Indeed, this contract is \(3\xi\)-EF by construction, while all the contracts in \(\mathcal{C}\) satisfy the effort constraints. To do so, it is sufficient to show that \((\hat{S}, \hat{\alpha})\) is \(3\xi\)-EF and \(2\xi\)-optimal, since this contract belongs to \(\mathcal{C}\).

We start by showing that the contract is approximately EF. Take two agents \(i\) and \(j\). Then \[\begin{align} \sum_{k \in \hat{S}_i} \hat{\alpha}_k p_{i,k} r_k - c_{i,k} & \ge \sum_{k \in \hat{S}_i} (\hat{U}_{i,k}(\hat{\alpha}_k) -\delta) \\ &\ge \sum_{k \in \hat{S}_i} \hat{U}_{i,k}(\hat{\alpha}_k) -\xi \\ &= \sum_{k \in S^*_i} \hat{U}_{i,k}(\bar \alpha_k) -\xi\\ & \ge \sum_{k \in S^*_i}\bar{\alpha}_k p_{i, k }r_k - c_{i,k} -\xi\\ & \ge \sum_{k \in S^*_j} \max\{ \bar{\alpha}_k p_{i, k }r_k - c_{i,k}, 0\} -2\xi\\ & \ge \sum_{k \in S^*_j} \hat{U}_{i,k}(\bar \alpha) -3\xi\\ &= \sum_{k \in \hat{S}_j} \hat{U}_{i,k}(\hat{\alpha}) -3\xi\\ & \ge \sum_{k \in \hat{S}_j} \max\{ 0, \hat{\alpha}_k p_{i,k} r_k - c_{i,k} \}- 3\xi. \end{align}\] where the second and fourth inequalities are by the definition of \(\hat{U}_{i,k}\), the fifth inequality is by (23 ) and the equalities are by Proposition 7. Moreover, it is \(2\xi\)-optimal since \[\begin{align} \sum_{i \in \mathcal{N}} \sum_{k \in \hat{S}_i} (1-\hat{\alpha}_k) p_{i,k}r_k &\ge \sum_{i \in \mathcal{N}} \sum_{k \in \hat{S}_i} U^P(\hat{\alpha}_{k},i)- \xi\\ & = \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} U^P(\bar \alpha_{k},i) -\xi\\ & \ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-\bar{\alpha}_k) p_{i,k}r_k - \xi\\ & \ge \rm{OPT\text{-}EF}-2\xi. \end{align}\] where the last inequality is by (24 ).

We conclude the proof by noting that the algorithm runs in polynomial time. Indeed, Algorithm 4 clearly runs in polynomial time excluding the calls to Algorithm 2. Moreover, it is easy to see that each call to Algorithm 2 runs in polynomial time since the possible vectors of agents’ cumulative utilities and the principal’s cumulative expected revenue have polynomial size (i.e., each utility belongs to \(\{0,\delta, \ldots,m\}\)). ◻

Proof. First, we prove that \[\begin{align} \label{eq:initialEF1} \max\{\bar{\alpha}_j p_{i, j }r_j - c_{i,j},0\}\le \max\{{\alpha}^*_j p_{i, j }r_j - c_{i,j},0\} + \delta U_i \quad \forall i \in \mathcal{N}, j \in \mathcal{M}. \end{align}\tag{25}\]

Consider an agent \(i\) and a task \(j\). We consider three cases:

(i) \(\underline{\alpha}_j\ge \tau_{i,j}\) and \({\alpha}^*_j<\tau_{i,j}\)

(ii) \(\underline{\alpha}_j\ge \tau_{i,j}\) and \({\alpha}^*_j \ge \tau_{i,j}\)

(iii) \(\underline{\alpha}_j< \tau_{i,j}\).

(i) If \(\underline{\alpha}_j\ge \tau_{i,j}\) and \({\alpha}^*_j< \tau_{i,j}\), then both \(\max\{\bar{\alpha}_j p_{i, j }r_j - c_{i,j},0\}\) and \(\max\{{\alpha}^*_j p_{i, j }r_j - c_{i,j},0\}\) are \(0\), as \(\bar \alpha_j = \lceil \alpha^*_j\rceil_{\mathcal{D}_j} \le \tau_{i,j}\) by that the set \(\mathcal{D}_{i,j}\) starts from \(\tau_{i,j}\).

(ii) If \(\underline{\alpha}_j\ge c_i/(r_j p_{i,j})\) and \({\alpha}^*_j\ge c_i/(r_j p_{i,j})\), then \[\begin{align} \max\{\bar{\alpha}_j p_{i, j }r_j - c_{i,j},0\}&= \bar{\alpha}_j p_{i, j }r_j - c_{i,j} \\ & \le ({\alpha}^*_j+ \delta (\underline{\alpha}_{j} - \tau_{i,j})) p_{i, j }r_j -c_{i,j} \\ & \le {\alpha}^*_j p_{i, j }r_j+ \delta (\underline{\alpha}_{j} p_{i, j }r_j - c_{i,j}) -c_{i,j} \\ & \le {\alpha}^*_j p_{i, j }r_j-c_{i,j} + \delta U_i \\ &=\max\{{\alpha}^*_j p_{i, j }r_j - c_{i,j},0\} + \delta U_i, \end{align}\] where the last inequality follows from the definition of \(\underline{\alpha}_{i,j}\) in Equation 9 and \(\underline{\alpha}_j \le \underline{\alpha}_{i,j}\).

(iii) If \(\underline{\alpha}_j< c_i/(r_j p_{i,j})\), then \(\max\{\bar{\alpha}_j p_{i, j }r_j - c_{i,j},0\}\) and \(\max\{{\alpha}^*_j p_{i, j }r_j - c_{i,j},0\}\) are \(0\), as \(\bar \alpha_j = \lceil \alpha^*_j\rceil_{\mathcal{D}_j} \le \underline{\alpha}_j\) by Lemma 1 and the definition of \(\underline{\alpha}_j\). This concludes the proof of Equation 25 .

Then, we use Equation 25 to prove Equation ?? . Consider two agents \(i\) and \(j\). It holds: \[\begin{align} \sum_{k \in S^*_i}\bar{\alpha}_k p_{i, k }r_k - c_{i,k} &\ge \sum_{k \in S^*_i}\alpha_k^* p_{i, k }r_k - c_{i,k}\\ & \ge \sum_{k \in S^*_j} \max\{ \alpha_k^* p_{i, k }r_k - c_{i,k}, 0\}\\ & \ge \sum_{k \in S^*_j} (\max \{\bar\alpha_{k} p_{i,k}r_k -c_{i,k},0\}-\delta U_i)\\ & \ge \sum_{k \in S^*_j} \max \{\bar\alpha_{k} p_{i,k}r_k -c_{i,k},0\}-\nu U_i \quad\forall i,j \in \mathcal{N}, \end{align}\] where the third inequality is by Equation 25 . Moreover, the effort constraints for the tasks continue to hold as we round up the contracts.

Finally, we get that the principal’s revenue under the new approximate contracts \((\bar{\alpha}, S^*)\) is at least \(\rm{OPT\text{-}EF}-\nu\), which is \[\begin{align} \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-\bar{\alpha}_k) p_{i,k}r_k \ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-{\alpha}_k^* -\delta) p_{i,k}r_k \ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-{\alpha}_k^* ) p_{i,k}r_k -\nu = \rm{OPT\text{-}EF}-\nu. \end{align}\] ◻

Proof. It holds \[\begin{align} \sum_{i \in \mathcal{N}} \sum_{k \in \hat{S}_i} (1-\hat{\alpha}_k) p_{i,k}r_k &\ge \sum_{i \in \mathcal{N}} \sum_{k \in \hat{S}_i} ( \hat{U}^P(\hat{\alpha}_{k},i)- \delta)\\ &\ge \sum_{i \in \mathcal{N}} \sum_{k \in \hat{S}_i} \hat{U}^P(\hat{\alpha}_{k},i)- \nu\\ & = \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} \hat{U}^P(\bar \alpha_{k},i) -\nu\\ &\ge \sum_{i \in \mathcal{N}} \sum_{k \in S^*_i} (1-\bar{\alpha}_k) p_{i,k}r_k -\nu \\ & \ge \rm{OPT\text{-}EF}-2\nu. \end{align}\] where the last inequality follows from Equation ?? . ◻

Proof. Consider a \(j\in \mathcal{M}\). We show that \(\alpha^*_j\le \underline{\alpha}_{j}\). This is sufficient to show that \(\bar \alpha_j\) is well-defined by the definition of \(\mathcal{D}_j\).

We consider two cases: \(\underline{\alpha}_j=1\) and \(\underline \alpha_j<1\).

If \(\underline{\alpha}_{j}=1\), it immediately implies \(\alpha^*_j\le \underline{\alpha}_{j}\). Hence, in the following arguments, we focus on the second case \(\underline{\alpha}_{j}<1\).

Suppose by contradiction that \(\alpha^*_{j} > \underline{\alpha}_{j}\). Let \(i\) be such that \(\underline{\alpha}_j=\underline{\alpha}_{i,j}\). Then, by definition, \[\begin{align} \label{eq:useDefAlpha} \underline{\alpha}_j= \frac{c_{i,j}+U_i}{q_{i,j}}, \end{align}\tag{26}\] where we use \(\underline{\alpha}_{j}<1\). Furthermore, suppose that \(i'\) is the agent such that \(j \in S^*_{i'}\). Then, it holds: \[\begin{align} U_i &\ge \sum_{k \in S^*_{i}}\alpha^*_k p_{i, k }r_k - c_{i,k}\\ & \ge \sum_{k \in S^*_{i'}}\max \{\alpha^*_k p_{i, k }r_k - c_{i,k},0\}\\ &\ge \alpha_j^* p_{i, j }r_j - c_{i,j} \\ &> \underline{\alpha}_{j} p_{i, j }r_j - c_{i,j}\\ &= \frac{U_{i}+c_{i,j}}{p_{i,j}r_j} p_{i, j }r_j -c_{i,j}\\ & \ge U_{i}, \end{align}\] where the first inequality is by Equation 8 , the second inequality is by EF and the equality follows from Equation 26 . Hence, we reach a contradiction. ◻

Proof. If \(W=0\), assign the task to any effort-feasible agent using share \(\tau_i\). This gives revenue \(0\) and is \(\delta\)-EF. Hence, assume \(W>0\).

Start from an agent \(a\) maximizing \(W_i\). We sort the agents according to their break-even shares so that \(\tau_1 \ge\tau_2 \ge \dots\ge \tau_n\). We can simply ignore those agents \(i\) with \(\tau_i >1\) as they will never be assigned the task by effort constraints. To ease exposition, we assume \(\tau_1 \le 1\).

Start from the agent \(a\) and set \(\alpha=\tau_a\). Note that any agent \(i<a\) gains non-positive utility at \(\alpha=\tau_a\), implying the satisfaction of effort constraints and \(\delta\)-EF constraints. Hence, the contract is \(\delta\)-EF exactly when every agent \(i>a\) values it by at most \(\delta\); for agents with \(q_i>0\) with \(i>a\), this condition is \[0\ge \max\{0, q_i \tau_a -c_i\} -\delta\] which, by \(q_i \tau_i -c_i =0\), implies that \[q_i(\tau_a-\tau_i)_+\le \delta \quad\text{for all such }i.\] If there exists some agent \(i>a\) such that the above condition fails, move to considering this agent \(i\) and check the feasible conditions if it is assigned the task and has contract \(\alpha = \tau_i\). Finally, the process terminates at some agent \(b\) for which the break-even-share contract is \(\delta\)-EF.

If the process terminates at \(b = a\), then the revenue is \(W\).

If \(b \neq a\), then \(b>a\). It must be that agent \(b\) violated the above \(\delta\)-EF condition for all its immediate predecessor agents along the path. Let the path be \(a \to \cdots\to i \to j \to b\). By construction, we know that agent \(b\) violates the \(\delta\)-EF constraints when the contract is \(\alpha = \tau_j\), i.e., \[0 < \max\{q_b \tau_j - c_b, 0\} -\delta = q_b \tau_j - c_b - \delta,\] Moreover, since \(\tau_i\ge \tau_j\), we also have that \[0 < q_b \tau_i - c_b - \delta.\] Hence, when the contract is \(\alpha = \tau_a\) and the task is assigned to agent \(a\), we have \[0 < q_b\tau_a -c_b -\delta\] which, by \(q_b\tau_b-c_b =0\), implies that \[q_b(\tau_a-\tau_b)>\delta.\] Therefore, \[\frac{W}{W_b} = \frac{q_a(1-\tau_a)}{q_b(1-\tau_b)} < \frac{q_a(1-\tau_a)(\tau_a-\tau_b)}{\delta(1-\tau_b)}.\] Let \(x=(\tau_a-\tau_b)/(1-\tau_b)\). Since \(\tau_b<\tau_a\le 1\), we have \(x\in[0,1]\), and the last expression equals \[\frac{q_a x(1-x)(1-\tau_b)}{\delta} \le \frac{1}{4\delta},\] using \(q_a\le 1\) and \(x(1-x)\le 1/4\). Thus \(W_b\ge 4\delta W\), as required. ◻