Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a coalition C ⊆A and a partition P ∈P(C), a coalition structure containing P can be pruned from the search space if there exists another partition P ′ ∈P(C) such that UBP ≤ LBP ′ and ∀p′ ∈P ′ at least one of the following is true: 1. ∃p ∈P : p′ = p 2. ∃p ∈P : p′ ⊂p and Tp ⊇T ¯ C 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational population masses \(\mu_t\), and rational formulas assigning each coalition block’s per-capita value from its mass, type mix, and specified aggregate moments of the full partition, find a finite mass partition with total value within \(\varepsilon\) of the supremum. Require the formulas to allow mixed externalities and satisfy the paper’s typed competition and complementation conditions.
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
A finite mass partition is an indexed family \(P=(x^1,\ldots,x^k)\), with arbitrary finite \(k\geq1\), where \(x^j\in\mathbb R_{\geq0}^{\tau}\setminus\{0\}\) and \(\sum_jx^j=\mu\); identical block vectors are allowed. Write \(s_j=\sum_tx_t^j\), \(q_j=x^j/s_j\), and \(S(x)=\{t:x_t>0\}\).
The input specifies \(m\geq0\) aggregate moments \(M_\ell(P)=\sum_js_jg_\ell(s_j,q_j)\) and a per-capita value formula \(f(s,q,M)\). Each formula is an explicit expression using binary rational constants and arithmetic operations, with every denominator promised nonzero on its feasible domain.
Block value is \(v(x^j,P)=s_jf(s_j,q_j,M(P))\), and total value is \(V(P)=\sum_jv(x^j,P)\). Values may have either sign; promise \(\sup_PV(P)<\infty\).
Typed competition requires that replacing another block \(y\) by any finite collection of positive-mass vectors summing to \(y\) cannot decrease \(v(x,P)\) whenever \(S(x)\cap S(y)\neq\varnothing\).
Typed complementation requires that merging any nonempty collection of other blocks whose combined type support is disjoint from \(S(x)\) cannot decrease \(v(x,P)\). Both requirements hold for every feasible partition, leaving the observed block and all unaffected blocks fixed; mixed externalities are permitted but not required.
Given binary rational \(0<\varepsilon<1\), the computational problem is to find a finite partition with rational block vectors satisfying \(V(P)\geq\sup_QV(Q)-\varepsilon\). Let \(L\) be the total input bit length, including formulas, masses, and \(\varepsilon\).
Is this additive approximation problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For discrete typed societies, a sufficient dominance pruning criterion supports exact branch-and-bound optimization; it supplies no polynomial-time guarantee ([source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2010/pdf/01%20Full%20Papers/03_03_FP_0581.pdf)).
No result settling the precisely specified continuous problem was located in the literature search.
The additive approximation problem is \(\mathrm{NP}\)-hard, already when \(m=0\), all type masses are equal, values are nonnegative, and \(\varepsilon=1/4\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The proof constructs instances whose optimal value equals the maximum-cut size of an input graph. Both typed externality requirements hold with equality.
For a simple unweighted graph \(G=(\{1,\ldots,n\},E)\), define its maximum-cut size by
\(C(G)=\max_{b\in\{-1,1\}^{n}}\sum_{\{i,j\}\in E}(1-b_i b_j)/2.\)
Each summand is one exactly when the endpoints lie on opposite sides of the cut. Thus \(C(G)\) is an integer. Deciding whether \(C(G)\geq K\), for an integer threshold \(K\), is \(\mathrm{NP}\)-complete. This is the unweighted “Simple Max Cut” problem established in [Garey, Johnson and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975(76)90059-1).
We may pad the graph with isolated vertices so that \(n\geq2\) is a power of two. This preserves \(C(G)\) and increases the vertex count by at most a factor of two.
Construct a society with two types per vertex:
\(T=\{(i,+),(i,-):1\leq i\leq n\},\qquad \tau=2n,\qquad \mu_{i,+}=\mu_{i,-}=1/(2n).\)
The masses are positive, sum to one, and are dyadic rationals. Set \(m=0\) and \(\varepsilon=1/4\).
For any composition vector \(q\), define
\(z_i(q)=n(q_{i,+}-q_{i,-}),\qquad r_i(q)=\dfrac{2z_i(q)}{1+z_i(q)^2}.\)
Take the per-capita formula to be
\(f(s,q)=F_G(q):=\sum_{\{i,j\}\in E}\dfrac{1-r_i(q)r_j(q)}{2}.\)
These definitions are shorthand for an explicit arithmetic expression: substitute the expression for each \(r_i\), and write every square as a multiplication. Each edge then contributes a constant number of arithmetic operations. The construction has polynomial encoding length and can be performed in polynomial time.
For every real \(z\), the denominator \(1+z^2\) is positive. Furthermore,
\(1-\dfrac{2z}{1+z^2}=\dfrac{(z-1)^2}{1+z^2}\geq0,\qquad 1+\dfrac{2z}{1+z^2}=\dfrac{(z+1)^2}{1+z^2}\geq0.\)
Hence \(r_i(q)\in[-1,1]\) for every feasible composition \(q\). Every edge contribution to \(F_G(q)\) lies in \([0,1]\), so
\(0\leq F_G(q)\leq |E|.\)
For any feasible finite partition \(P\), its block masses satisfy \(\sum_j s_j=1\). Therefore
\(0\leq V(P)=\sum_j s_jF_G(q_j)\leq |E|.\)
In particular, the promised finite supremum holds.
Because \(m=0\), an observed block \(x\) has value
\(v(x,P)=s_xF_G(x/s_x),\)
which depends only on \(x\). Refining another block, or merging any collection of other blocks, leaves this value unchanged.
Thus typed competition and typed complementation both hold for every feasible partition and every operation specified in the question. Their support restrictions are immaterial here because equality holds even without those restrictions.
Fix any feasible composition \(q\). Independently choose random signs \(B_i\in\{-1,1\}\) with
\(\Pr(B_i=1)=(1+r_i(q))/2,\qquad \Pr(B_i=-1)=(1-r_i(q))/2.\)
These are valid probabilities because \(r_i(q)\in[-1,1]\). They give \(\mathbb E[B_i]=r_i(q)\). Since the graph is simple, each edge joins distinct vertices; independence therefore gives
\(\mathbb E[B_iB_j]=r_i(q)r_j(q)\quad\text{for every }\{i,j\}\in E.\)
By linearity of expectation, the expected cut size is
\(\mathbb E\!\left[\sum_{\{i,j\}\in E}\dfrac{1-B_iB_j}{2}\right] =\sum_{\{i,j\}\in E}\dfrac{1-r_i(q)r_j(q)}{2} =F_G(q).\)
Every realized cut has size at most \(C(G)\). Its expectation consequently satisfies \(F_G(q)\leq C(G)\).
Apply this bound separately to every block of any feasible finite partition, including partitions with real block vectors and arbitrarily many blocks:
\(V(P)=\sum_j s_jF_G(q_j)\leq\sum_j s_jC(G)=C(G).\)
Thus \(\sup_P V(P)\leq C(G)\).
Let \(b\in\{-1,1\}^{n}\) describe a maximum cut. Define
\(q^b_{i,+}=\dfrac{1+b_i}{2n},\qquad q^b_{i,-}=\dfrac{1-b_i}{2n}.\)
For each vertex, exactly one of these two coordinates equals \(1/n\), and the other equals zero. Thus \(q^b\) is a composition vector. Moreover,
\(z_i(q^b)=b_i,\qquad r_i(q^b)=\dfrac{2b_i}{1+b_i^2}=b_i,\)
so \(F_G(q^b)=C(G)\). Reversing all signs preserves every product \(b_i b_j\), hence \(F_G(q^{-b})=C(G)\) as well.
Now form two blocks
\(x^1=q^b/2,\qquad x^2=q^{-b}/2.\)
Both have mass \(1/2\). For every type,
\(x^1_{i,+}+x^2_{i,+}=1/(2n)=\mu_{i,+},\qquad x^1_{i,-}+x^2_{i,-}=1/(2n)=\mu_{i,-}.\)
They therefore form a feasible rational partition. Its value is
\(V((x^1,x^2))=\tfrac12 C(G)+\tfrac12 C(G)=C(G).\)
Together with the upper bound, this proves the exact identity
\(\sup_P V(P)=C(G).\)
The supremum is attained by two rational blocks.
Suppose an algorithm returns a rational partition \(P\) meeting the required approximation guarantee. On the constructed instance,
\(C(G)-\tfrac14\leq V(P)\leq C(G).\)
Because \(C(G)\) is an integer, these inequalities imply
\(\lceil V(P)\rceil=C(G).\)
The value \(V(P)\) can be evaluated exactly in time polynomial in the graph size and the returned partition’s encoding length. Indeed, computing block masses and compositions uses rational additions and divisions. Each edge contribution then uses a fixed number of arithmetic operations. When adding the resulting rational terms, a common denominator can be taken as their product; its bit length is at most the sum of their denominator bit lengths. All intermediate integers therefore have polynomial bit length.
Consequently, exact evaluation followed by an integer ceiling recovers \(C(G)\). Comparing it with \(K\) decides the source \(\mathrm{NP}\)-complete problem.
If the approximation algorithm ran in polynomial time, its explicit output would also have polynomial length, so this entire reduction would run in polynomial time.
The precisely specified approximation problem is \(\mathrm{NP}\)-hard. The reduction uses \(m=0\) and fixed accuracy \(\varepsilon=1/4\), verifies both typed externality conditions, and bounds every feasible real partition. It therefore applies without restricting the allowed number of blocks.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated problem: additive approximation is \(\mathrm{NP}\)-hard, even with \(m=0\), equal masses, nonnegative values, and fixed \(\varepsilon=1/4\). No major or minor mathematical gaps were found.
\[
C(G)-1/4\leq V(P)\leq C(G).
\]
Since \(C(G)\) is an integer, \(\lceil V(P)\rceil=C(G)\). This also covers the zero-optimum case.
None. The argument supplies both a valid polynomial construction and polynomial postprocessing of every acceptable output. 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.