Problem settings: we have $n$ agents and a set $\mathcal{S}$ of possible world-states, where the size of $\mathcal{S}$ is exponential with respect to $n$. Each agent $j$ has a utility function $u_j\colon \mathcal{S}\to\mathbb{R}_{\geq 0}$ that describes its satisfaction level from a given state. The functions are not explicitly given, but can be accessed through the following two oracles:
- A value oracle: given $S$ and $j$ returns $u_j(S)$.
- An $\alpha$-SUM oracle (for some given $\alpha\in(0,1)$): for any set of non-negative constants $a_1,\ldots, a_n$, it finds a state that approximately maximizes the following expression: \begin{align*} \sum_{j=1}^n a_j \cdot u_j(S) \end{align*} That is, it returns a state $S'$ such that: \begin{align*} \sum_{j=1}^n a_j \cdot u_j(S') \geq (1-\alpha)\cdot \max_{S\in\mathcal{S}} \sum_{j=1}^n a_j \cdot u_j(S) \end{align*}
Goal: our goal is to find a probability distribution over the set $S$ (i.e., some function $p\colon \mathcal{S}\to[0,1]$ such that $\sum_{S\in \mathcal{S}}p(S) =1$), that would satisfy some desired properties (described below) regarding the expected utilities of the agents (i.e., $E_j(p) = \sum_{S\in \mathcal{S}}p(S) \cdot u_j(S)$ for each $1\leq j \leq n$).
Specificaly, in the first step, we want to maximize the minimum value; however, we know that it is NP-hard and so we aim to approximate it. The problem can be modeled as the following LP that has an exponential number of variables ($p(S)$ for any $S \in \mathcal{S}$ and $z$): \begin{align} & \max\quad z \quad s.t. \tag{P1}\\ & (1) \quad \sum_{S \in \mathcal{S}}p(S)=1 \nonumber \\ & (2) \quad \sum_{S \in\mathcal{S}}p(S)\cdot u_j(S) \geq z && j = 1,\ldots, n \nonumber\\ & (6) \quad p(S)\geq 0 && \forall S \in \mathcal{S}\nonumber \end{align}
Its dual has a specific structure that allows us to use the ellipsoid method in order to find a feaible solution to the primal with objective value that $(1-\alpha)$-approximates the optimal value (e.g., as described here or in Section "Dual-based algorithm" of this article). \begin{align} & \min \quad q_0\quad s.t.\tag{D1}\\ & (1) \quad q_0 -\sum_{j=1}^n u_j(S) v_{j} \geq 0 && \forall S \in \mathcal{S} \nonumber\\ & (2) \quad \sum_{j=1}^n v_{j} = 1 && j = 1,\ldots, n \nonumber \\ & (3) \quad v_{j} \geq 0 && j = 1,\ldots, n \nonumber \end{align} The variables are $q_0$ and $v_{j}$ for $1\leq j\leq n$.
The hard part: Denote the approximation we found for the primal P1 as $z_1$. Our second goal is to find (or to approximate) the maximum value, $z$, that can be added to $z_1$ such that the sum of any two expected utilities will be at least $z_1 + z$ (while each expected utility will be at least $z_1$). This can be modelled as the following LP (the variables are $p(S)$ for any $S \in \mathcal{S}$ and $z$ and $z_1$ is constant): \begin{align} & \max\quad z \quad s.t. \tag{P2}\\ & (1) \quad \sum_{S \in \mathcal{S}}p(S)=1 \nonumber \\ & (2) \quad y_{1} - \sum_{j=1}^n m_{1,j}\geq z_1 && \nonumber \\ & (3) \quad 2 y_2 - \sum_{j=1}^{n} m_{2,j} \geq z_1 + z \nonumber \\ & (4) \quad m_{\ell,j} \geq y_{\ell} - \sum_{S \in\mathcal{S}}p(S)\cdot u_j(S) && \ell = 1,2 \quad j = 1,\ldots, n \nonumber \\ & (5) \quad m_{\ell,j} \geq 0 && \ell = 1,2\quad j = 1,\ldots, n \nonumber\\ & (6) \quad p(S)\geq 0 && \forall S \in \mathcal{S}\nonumber \end{align} The reason we use these constraints (instead of a constraint for each pair of agents) is that we aim to extend this process up to $n$ (that is, given an approximation $z_2$ to this program, we then want to find the maximum value, $z$, the can be added to $z_1+z_2$ such that the sum of any three expected utilities will be at least $z_1+z_2+z$ -while keeping the previous constraints-; and so on), so a direct approach will eventually result in a program that have an exponential number of variables and constraints.
The dual of this program can be modeled as follows (the variables are $q_0$, $v_{\ell,j}$ and $q_{\ell}$ for $\ell=1,2$ and $1\leq j\leq n$): \begin{align} & \min \quad q_0- z_1\cdot q_{1} - z_1\cdot q_2 \quad s.t.\tag{D2}\\ & (1) \quad q_0 -\sum_{j=1}^n u_j(S) \sum_{\ell=1}^2 v_{\ell,j} \geq 0 && \forall S \in \mathcal{S} \nonumber\\ & (2) \quad q_2=1 \nonumber \\ & (3) \quad -\ell q_{\ell} + \sum_{j=1}^n v_{\ell,j} = 0 && \ell = 1,2 \nonumber \\ & (4) \quad q_{\ell} - v_{\ell,j} \geq 0 && \ell = 1,2 \quad j = 1,\ldots, n \nonumber \\ & (5) \quad v_{\ell,j} \geq 0 && \ell = 1,2 \quad j = 1,\ldots, n \nonumber \\ & (6) \quad q_{\ell} \geq 0 && \ell = 1,2 \nonumber \end{align}
Unfortunately, this dual has a different structure and so we cannot use the same technique. All our attempts to approximate P2 have failed. Notice that the solution that we find for P1 (and D1) gives us a lower bound on the optimal value (maybe it can help..)
My question is: is there any way to approximate P2 in polynomial time, such that the approximation error is polynomial in $\alpha$?
-- Recall that $\alpha$ is the error in the given $\alpha$-SUM oracle (described above).
-- Note that a feasible primal solution has an exponential size (as we need to describe the value of each variable), but since the primal has only polynomially many constraints, it has a solution in which only a polynomial number of variables are nonzer, so we can consider its sparse form (i.e., a list of the variables with positive values, along with their values).
