Answer: Polynomial-time solvable: the problem belongs to \(\mathrm{P}\), with running time \((m+\tau+L+1)^{O(1)}\) bit operations.
Proposition 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate$\optval$ is NP-complete even if one assumes that $\cal G$ is a 2-OCF game, and that $\wmax = 3$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), per-agent endowments \(w_\theta\), aggregate resource caps \(b_\theta\le\mu_\theta w_\theta\), explicitly listed finite contribution levels and singleton/pair values, and a threshold \(V\), choose nonnegative masses \(z_{\theta,r}\) and \(x_e^{r,s}\) of singleton and pair coalitions to maximize \(\sum_{\theta,r}v_\theta(r)z_{\theta,r}+\sum_{e,r,s}v_e(r,s)x_e^{r,s}\), subject for every type \(\theta\) to \(\sum_r z_{\theta,r}+\sum_{e\ni\theta,r,s}x_e^{r,s}\le\mu_\theta\) and \(\sum_r rz_{\theta,r}+\sum_{e\ni\theta,r,s}\rho_{\theta e}(r,s)x_e^{r,s}\le b_\theta\), where \(\rho_{\theta e}\) is that type’s contribution in pair \(e\); decide whether the optimum is at least \(V\), with coalitions of support greater than \(2\) having value zero.
A society is given by its support: the list of \(\tau\) types \(\Theta\) with positive binary rational masses \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a positive rational per-agent endowment \(w_\theta\) and a rational resource cap \(0\le b_\theta\le\mu_\theta w_\theta\).
The input explicitly lists \(m\) coalition configurations. Configuration \(j\) has support \(S_j\subseteq\Theta\) of size one or two, positive rational contributions \(a_{\theta j}\le w_\theta\) for \(\theta\in S_j\), and a nonnegative rational value \(v_j\); set \(a_{\theta j}=0\) otherwise. Pair configurations involve distinct types. Unlisted configurations and coalitions with support larger than two have value zero; the empty coalition has value zero.
Choose real configuration masses \(y_j\ge0\). Their total value is \(\sum_{j=1}^m v_jy_j\), and feasibility means \(\sum_{j:\theta\in S_j}y_j\le\mu_\theta\) and \(\sum_{j=1}^m a_{\theta j}y_j\le b_\theta\) for every \(\theta\). Unused mass and resources are allowed; these aggregate constraints completely define feasibility.
Given a binary rational threshold \(V\), the decision problem asks whether the maximum feasible value is at least \(V\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous coalition-value decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Discrete optimal overlapping coalition-value decision is \(\mathrm{NP}\)-complete even with coalition support at most two and maximum agent endowment three. [Source](https://arxiv.org/pdf/1407.0420)
Continuous linear bottleneck games admit polynomial-time optimal coalition-value computation; their bottleneck value functions and resource-only feasibility differ from the explicitly tabulated, mass-constrained problem above. [Source](https://arxiv.org/pdf/1407.0420)
The stated continuous coalition-value decision problem is in \(\mathrm{P}\). It can be decided exactly in \((m+\tau+L+1)^{O(1)}\) bit operations.
The proof uses precisely the given aggregate feasibility constraints; no additional condition on individual agents is imposed.
Define the matrices \(M,A\in\mathbb{Q}^{\tau\times m}\) by \(M_{\theta j}=1\) when \(\theta\in S_j\), and \(M_{\theta j}=0\) otherwise, and by \(A_{\theta j}=a_{\theta j}\). Let \(v=(v_1,\ldots,v_m)\).
The feasible set is exactly
\(P=\{y\in\mathbb{R}^{m}:y\ge 0,\ My\le\mu,\ Ay\le b\}.\)
This is a polytope defined by rational linear inequalities. It is nonempty because \(y=0\) satisfies every constraint.
For each configuration \(j\), choose a type \(\theta\in S_j\). Nonnegativity and the mass constraint for that type imply
\(0\le y_j\le\sum_{k:\theta\in S_k}y_k\le\mu_\theta\le 1.\)
Thus \(P\subseteq[0,1]^m\). Since \(P\) is also closed, it is compact. Consequently, the continuous linear objective \(v^\mathsf{T}y\) attains its maximum on \(P\).
If \(m=0\), the maximum is \(0\), and the answer is yes exactly when \(V\le 0\). Henceforth assume \(m>0\).
Construct the following system:
It has \(m\) real variables and \(m+2\tau+1\) inequalities.
If this system is feasible, its solution belongs to \(P\) and has value at least \(V\), so the decision answer is yes. Conversely, if the maximum feasible value is at least \(V\), a maximizer exists by Section 1 and satisfies the entire system.
Therefore, the decision problem is exactly equivalent to feasibility of this rational linear system.
We apply the standard polynomial-time linear programming feasibility theorem: feasibility of an explicitly represented system of linear inequalities with binary integer coefficients can be decided in time polynomial in its total encoding length. The theorem applies even when the feasible set has empty interior. See [MIT’s notes on the ellipsoid method, Section 3.12](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Here is an explicit check that our rational system meets its encoding requirements.
Let \(D\) be the product of the positive denominators of all numerical input entries. Their total binary length is at most \(L\), so \(\log_2 D=O(L)\). Multiplying each inequality by \(D>0\) preserves feasibility and gives integer coefficients. Every resulting coefficient has \(O(L+1)\) bits: its numerator originally has at most \(L\) bits, and multiplication by \(D\) adds only \(O(L)\) bits.
A dense representation of the resulting system therefore has encoding length
\(B=O\bigl((m+2\tau+1)(m+1)(L+1)\bigr).\)
The system can be constructed in polynomial time in \(m,\tau,L\). Applying integer linear feasibility then takes \(B^{O(1)}\) bit operations, hence
\(T(m,\tau,L)=(m+\tau+L+1)^{O(1)}.\)
This is an exact decision algorithm, including the case where the optimum equals \(V\). It does not rely on floating-point approximation.
The cited paper proves \(\mathrm{NP}\)-completeness for discrete overlapping coalition-value computation even with support at most two and maximum endowment three ([Proposition 3.4](https://arxiv.org/pdf/1407.0420)). That theorem concerns a different feasible set.
Here, configuration masses are arbitrary nonnegative real numbers, their values are linear in those masses, and the stated aggregate inequalities completely determine feasibility. These premises give the polynomial-size linear system above. Neither an integrality restriction nor an additional coalition-realization requirement may be imported from the discrete model.
The support-size restriction makes the capacity matrices sparse: each configuration column has at most two nonzero entries in each matrix. Polynomial-time solvability already follows from explicit representation and linearity. No result about bottleneck value functions is needed.
Thus the problem is polynomial-time solvable; under polynomial-time many-one reductions, it could also be \(\mathrm{NP}\)-hard only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover resolves the stated decision problem correctly. The reduction preserves exactly the specified feasibility conditions, and the encoding bounds justify polynomial bit complexity. No major or minor issues were found.
The matrices \(M,A\in\mathbb{Q}^{\tau\times m}\) correctly encode the mass and resource constraints. Thus
\(P=\{y\in\mathbb{R}^m:y\ge0,\ My\le\mu,\ Ay\le b\}\)
is exactly the task’s feasible set. No extra realization or integrality assumption is introduced.
Nonemptiness follows from \(y=0\), since all masses and resource caps are nonnegative.
Every configuration has nonempty support. For each \(j\), choosing \(\theta\in S_j\) gives
\(0\le y_j\le\sum_{k:\theta\in S_k}y_k\le\mu_\theta\le1\).
Each inequality is justified respectively by nonnegativity, inclusion of \(j\) in the sum, the mass constraint, and normalization of the positive masses.
The finite system of non-strict linear inequalities defines a closed set. Together with the coordinate bounds, this establishes compactness. The linear objective is continuous, so its maximum exists.
The case \(m=0\) is handled correctly: the objective is identically zero, including when the threshold is negative or zero.
The constructed system has \(m\) real variables and \(m+2\tau+1\) inequalities, as claimed.
The added inequality
\(-\sum_jv_jy_j\le-V\)
is exactly equivalent to the required value condition
\(\sum_jv_jy_j\ge V\).
Both implications are valid:
Consequently, the reduction handles equality at the threshold exactly.
The invoked theorem is appropriately stated: feasibility of an explicitly encoded system with binary integer coefficients is decidable in polynomial time in its encoding length. Here “integer” concerns the coefficients; the variables remain real.
The cited [MIT notes, Section 3.12](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) explicitly cover general integer-data linear feasibility, including the treatment of sets without full dimension and polynomially bounded numerical precision. Thus zero resource caps or a threshold attained only on a face do not invalidate the application.
The denominator-clearing calculation is correct:
The dense encoding bound
\(B=O((m+2\tau+1)(m+1)(L+1))\)
correctly accounts for coefficients and right-hand sides. Constructing this representation requires polynomially many operations on polynomial-length integers.
Applying the stated feasibility theorem therefore yields the claimed bound
\(T(m,\tau,L)=(m+\tau+L+1)^{O(1)}\).
Because the support and configurations are explicitly listed, their counts are also bounded by the input length. This establishes membership in \(\mathrm{P}\).
The description of [Proposition 3.4](https://arxiv.org/pdf/1407.0420) matches the cited discrete hardness result. The prover correctly distinguishes that model from the present real-variable, aggregate-constraint formulation.
The sparsity observation is accurate: every configuration column has at most two nonzero entries in each capacity matrix. The proof does not require sparsity or invoke a bottleneck-game theorem.
The concluding qualification concerning \(\mathrm{NP}\)-hardness and \(\mathrm{P}=\mathrm{NP}\) is correct.
None. The argument settles the assigned problem as written.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.