Answer: \(\mathrm{NP}\)-hard even when \(|a_{st}|\leq1\), \(a_{tt}=0\), and \(1/\epsilon=4\tau^3\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOPT-CS-WGG is NP-complete, and assum- ing P ̸= NP, there is no polynomial time O(n1/2−ϵ)- approximation algorithm for it where n is the number of ver- tices and ϵ is any positive constant. There is no polynomial time O(n1−ϵ)-approximation algorithm for this problem un- less NP = ZPP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a symmetric rational interaction matrix \(a\), and \(\epsilon>0\), treat each type as an atomless population of mass \(\mu_t\). For a coalition with type-mass profile \(q\), define per-capita value \(\phi(q)=\sum_{s<t}a_{st}q_sq_t+\frac12\sum_t a_{tt}q_t^2\), corresponding to pair weights scaled by \(1/N\) in an \(N\)-agent realization. Output a finite rational decomposition into coalition profiles, with residual mass assigned to infinitesimal singleton coalitions, whose welfare is within \(\epsilon\) of the supremum over measurable partitions; measure complexity in \(|T|\), input bit length \(L\), and \(1/\epsilon\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; there is no separate ground-set parameter \(m\).
Each type is an atomless population. Input also includes a symmetric matrix \(a\in\mathbb Q^{\tau\times\tau}\), with unrestricted signs and diagonal entries, and a binary rational \(\epsilon>0\); \(L\) is the total input bit length.
A coalition's profile \(q\) records its absolute type masses, and its contribution to welfare is \(\phi(q)=\sum_{s<t}a_{st}q_sq_t+\tfrac12\sum_t a_{tt}q_t^2\).
Types may be split freely among disjoint measurable coalitions, with no bound on their number or additional feasibility constraints. Welfare is the sum of \(\phi(q)\) over the at most countably many positive-mass coalitions; zero-mass coalitions contribute zero.
Let \(\mathrm{OPT}\) be the supremum of this welfare over measurable partitions. The computational problem is to output finitely many nonzero rational profiles \(q^1,\ldots,q^k\ge0\) satisfying \(\sum_i q^i_t\le\mu_t\) for every type and \(\sum_i\phi(q^i)\ge\mathrm{OPT}-\epsilon\); residual mass is partitioned into singleton coalitions of value zero.
Is this additive approximation problem solvable in time polynomial in \(\tau\), \(L\), and \(1/\epsilon\), or is it \(\mathrm{NP}\)-hard even when \(1/\epsilon\) is polynomially bounded in the remaining input length?
For finite agents, deciding whether a partition's total internal signed edge weight can reach a rational threshold is \(\mathrm{NP}\)-complete, including on planar graphs. [Verified source](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/bkkz_aaai2013.pdf).
No result settling this exact atomless additive approximation problem was identified in the literature search.
The problem is \(\mathrm{NP}\)-hard even when all diagonal entries are zero, all coefficients have absolute value at most one, and \(1/\epsilon=4\tau^3\). Consequently, an algorithm polynomial in \(\tau\), \(L\), and \(1/\epsilon\) would imply \(\mathrm{P}=\mathrm{NP}\).
The essential fact is that, with zero diagonal entries, splitting types cannot improve the optimal welfare.
Assume \(a_{tt}=0\) for every type \(t\). Let \((q^i)_{i\in I}\) be any finite or countable family of positive-mass coalition profiles satisfying \(\sum_{i\in I}q^i_t\leq\mu_t\). Its welfare is
\[ W=\sum_{i\in I}\sum_{s<t}a_{st}q^i_sq^i_t. \]
This sum is absolutely convergent. Indeed, for each pair of types,
\[ \sum_{i\in I}q^i_sq^i_t \leq \left(\sum_{i\in I}q^i_s\right) \left(\sum_{i\in I}q^i_t\right) \leq\mu_s\mu_t, \]
and therefore
\[ \sum_{i\in I}\left|\phi(q^i)\right| \leq\sum_{s<t}|a_{st}|\mu_s\mu_t<\infty. \]
For each type \(t\), independently choose a label \(X_t\). Assign probability \(q^i_t/\mu_t\) to coalition label \(i\in I\). Assign the remaining probability to a private label \(r_t\), distinct from every coalition label and every other private label.
Group whole type populations according to their chosen labels. This produces a measurable partition with at most \(\tau\) coalitions. Its welfare is
\[ F(X)=\sum_{s<t}a_{st}\mu_s\mu_t\,\mathbf{1}_{\{X_s=X_t\}}. \]
For distinct types \(s,t\), independence and the private-label construction give
\[ \Pr(X_s=X_t) =\sum_{i\in I}\frac{q^i_s}{\mu_s}\frac{q^i_t}{\mu_t}. \]
Consequently,
\[ \mathbb{E}[F(X)] =\sum_{s<t}a_{st}\sum_{i\in I}q^i_sq^i_t =W. \]
Let \(\mathcal{P}(T)\) denote the finite set of partitions of the type set. Every realization of \(X\) induces a member of \(\mathcal{P}(T)\), so its welfare is at most
\[ M=\max_{P\in\mathcal{P}(T)} \sum_{B\in P}\sum_{\substack{s<t\\s,t\in B}} a_{st}\mu_s\mu_t. \]
Thus \(W=\mathbb{E}[F(X)]\leq M\). Conversely, every partition of whole types is a permissible measurable partition. We have proved the exact identity
\[ \boxed{\mathrm{OPT}=M.} \]
In particular, the supremum is attained by at most \(\tau\) rational profiles when the input masses are rational. This argument covers both countably many positive-mass coalitions and residual singleton mass.
We reduce from the standard \(\mathrm{NP}\)-complete Independent Set decision problem: given a simple graph \(G=(V,E)\) with \(n\geq1\) vertices and an integer \(K\), decide whether its independence number \(\alpha(G)\) satisfies \(\alpha(G)\geq K\). Independent Set is also the starting point of the finite-agent hardness reduction in Theorem 3 of [Bachrach, Kohli, Kolmogorov, and Zadimoghaddam](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/bkkz_aaai2013.pdf).
Let \(\tau\) be the smallest power of two satisfying \(\tau\geq n+1\). Then \(n+1\leq\tau<2(n+1)\).
Create one type for each vertex, one additional hub type \(h\), and \(\tau-n-1\) dummy types. Every type has mass \(\mu_t=1/\tau\). Define the symmetric matrix by
\[ a_{hv}=\frac1\tau\quad(v\in V),\qquad a_{uv}=-1\quad(\{u,v\}\in E), \]
with every other entry, including all diagonal entries, equal to zero. Set
\[ \epsilon=\frac{1}{4\tau^3}. \]
All masses, coefficients, and the accuracy parameter are dyadic rationals. Every type has positive mass, and \(|a_{st}|\leq1\).
We now prove
\[ \boxed{\mathrm{OPT}=\frac{\alpha(G)}{\tau^3}.} \]
By the rounding lemma, it suffices to consider partitions of whole types.
For such a partition, let \(S\subseteq V\) be the vertices sharing the hub’s coalition, and let \(e(S)\) be the number of graph edges induced by \(S\). The hub coalition has welfare
\[ \frac{|S|}{\tau^3}-\frac{e(S)}{\tau^2} =\frac{|S|-\tau e(S)}{\tau^3}. \]
Every other coalition has nonpositive welfare, since its only possible nonzero interactions are negative graph edges.
If \(S\) is independent, the total welfare is at most \(|S|/\tau^3\leq\alpha(G)/\tau^3\).
If \(S\) is not independent, then \(e(S)\geq1\), and hence
\[ |S|-\tau e(S)\leq n-\tau\leq-1. \]
The total welfare is then negative, so it is again at most \(\alpha(G)/\tau^3\). This proves the upper bound for every partition.
For the matching lower bound, place the hub together with a maximum independent set, and put every remaining type in its own coalition. There are exactly \(\alpha(G)\) positive hub interactions and no internal negative interactions. The resulting welfare is \(\alpha(G)/\tau^3\), proving the identity.
Suppose an algorithm satisfies the requested guarantee. Run it on the constructed instance and compute the exact rational welfare \(W\) of its output.
Feasibility and the approximation guarantee imply
\[ \frac{\alpha(G)-1/4}{\tau^3} \leq W \leq \frac{\alpha(G)}{\tau^3}. \]
Compare \(W\) with the rational threshold
\[ R=\frac{K-1/2}{\tau^3}. \]
If \(\alpha(G)\geq K\), then
\[ W\geq\frac{K-1/4}{\tau^3}>R. \]
If \(\alpha(G)<K\), integrality gives \(\alpha(G)\leq K-1\), so
\[ W\leq\frac{K-1}{\tau^3}<R. \]
Thus a single call to the approximation algorithm decides Independent Set.
The construction has \(\tau<2(n+1)\), input length \(L=O(\tau^2\log\tau)\), and \(1/\epsilon=4\tau^3\). Its encoding and construction time are polynomial in the graph input size. Moreover, the input length excluding \(\epsilon\) is at least \(\tau\), so \(1/\epsilon\) is polynomially bounded in that remaining length.
If the approximation algorithm ran in polynomial time, its output would also have polynomial bit length. Exact evaluation of its finitely many rational profiles and comparison with \(R\) would therefore take polynomial time.
This completes the reduction and settles the stated question.
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the assigned problem. The rounding lemma is valid, the reduction establishes the claimed exact optimum, and the additive error is small enough to distinguish the Independent Set decision cases. I found no mathematical or complexity-theoretic gaps.
The prover establishes hardness on a restricted family of valid inputs: zero diagonal entries, coefficients of absolute value at most one, equal positive rational masses, and inverse accuracy polynomially bounded in the remaining input length. Hardness on this family suffices for the unrestricted problem.
The proof does not claim membership in \(\mathrm{NP}\) for the continuous approximation problem. Its conclusion is the requested \(\mathrm{NP}\)-hardness.
Absolute convergence. For each distinct pair of types, nonnegativity of the profiles gives
\[
\sum_i q_s^i q_t^i
\leq
\left(\sum_i q_s^i\right)\left(\sum_i q_t^i\right)
\leq \mu_s\mu_t.
\]
The first inequality holds for finite or countable index sets: the product on the right includes every term on the left and only additional nonnegative terms. Summing over the finitely many type pairs proves the asserted absolute convergence. Arbitrary signs of the coefficients cause no difficulty.
Random labels. Each label distribution is well-defined because \(\mu_t>0\) and \(\sum_i q_t^i\leq\mu_t\). There are finitely many types, so the independent choices are well-defined even when the label set is countable.
The private labels are essential and correctly specified. For distinct types, they cannot produce a matching label. Consequently, the stated matching probability includes exactly the shared coalition labels.
Expected welfare. The formula for \(F(X)\) is correct because each type is assigned wholly to one coalition and all diagonal entries vanish. Independence gives the stated expectation, equal to the original welfare. The finite sum over type pairs and the established convergence justify the calculation.
Comparison with whole-type partitions. Every realization groups the finite type set into at most \(\tau\) blocks. Its welfare is therefore at most the finite maximum \(M\), giving \(W\leq M\).
Conversely, every whole-type partition is permitted by the task. Any measurable partition has at most countably many positive-mass coalitions, whose profiles satisfy the lemma’s mass constraints; its zero-mass coalitions contribute nothing. Thus the lemma applies to the full optimization domain, and the conclusion \(\mathrm{OPT}=M\) follows.
The claim of attainment by rational profiles also follows: each block profile has coordinates either zero or the corresponding rational input mass.
Finding: Correct, including countable families and residual singleton mass.
The source problem is stated precisely: Independent Set on a simple graph with an integer decision threshold. Restricting to at least one vertex does not affect its standard \(\mathrm{NP}\)-completeness. The historical observation that Theorem 3 of the cited paper starts from Independent Set is accurate; the prover supplies its own reduction and does not rely on transferring the paper’s finite-agent result to the atomless setting. See the [cited paper, Theorem 3](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/bkkz_aaai2013.pdf).
Construction. The smallest power of two satisfying \(\tau\geq n+1\) obeys
\[
n+1\leq\tau<2(n+1).
\]
There are exactly \(\tau\) types. Their masses are positive and sum to one. All constructed numbers are dyadic rationals, the matrix is symmetric, and its diagonal entries are zero. Dummy types have no nonzero interactions and hence do not affect welfare.
Hub-coalition calculation. Each hub–vertex pair contributes \(1/\tau^3\), while each internal graph edge contributes \(-1/\tau^2\). Therefore the asserted welfare
\[
\frac{|S|-\tau e(S)}{\tau^3}
\]
has the correct factors and signs.
Other coalitions. Outside the hub coalition, every nonzero interaction is a negative graph-edge interaction. Their combined welfare is therefore nonpositive.
Upper bound.
\[
|S|-\tau e(S)\leq n-\tau\leq-1.
\]
The total welfare is negative and hence below \(\alpha(G)/\tau^3\).
These cases exhaust all whole-type partitions. The rounding lemma extends the upper bound to every permissible atomless partition.
Lower bound. Grouping the hub with a maximum independent set and leaving all remaining types in separate coalitions produces exactly the asserted positive interactions and no negative internal interactions.
Thus the identity
\[
\mathrm{OPT}=\frac{\alpha(G)}{\tau^3}
\]
is established.
Finding: Correct.
For any output satisfying the task’s guarantee, the lower bound is
\[
W\geq\frac{\alpha(G)-1/4}{\tau^3}.
\]
The upper bound \(W\leq\alpha(G)/\tau^3\) follows directly from the rounding lemma applied to the feasible output profiles.
The proposed threshold
\[
R=\frac{K-1/2}{\tau^3}
\]
strictly separates the cases:
Equality with the comparison threshold cannot occur for a guaranteed output. Arbitrary integer thresholds, including those outside the nontrivial range, do not invalidate these implications.
Finding: Correct.
The dense matrix and rational parameters admit the claimed encoding bound \(L=O(\tau^2\log\tau)\). Since \(\tau<2(n+1)\), construction time and output-instance length are polynomial in the source input size.
The inverse accuracy is \(4\tau^3\). The remaining input explicitly lists \(\tau\) positive masses, so its length is at least \(\tau\); the required polynomial bound on inverse accuracy follows.
Under the assumed polynomial running time, the algorithm’s explicitly written output has polynomial total bit length. Exact evaluation requires polynomially many rational arithmetic operations, with polynomially bounded intermediate bit lengths. The threshold comparison likewise takes polynomial time, including the encoding length of \(K\).
Finding: Correct.
The proof establishes the claimed hardness of the exact atomless additive approximation problem. The decisive progress is the valid rounding lemma, which connects arbitrary splitting to a finite whole-type optimum without assuming that finite-agent hardness automatically carries over.
No additional lemma, clarification, or repair is needed.
⟨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.