Answer: \(\mathrm{NP}\)-hard, even with \(\tau=1\), zero unary rewards, and pair rewards in \(\{0,1\}\).
定理4 (Theorem 4) — class: hardness
Given rational type masses \(\mu_t\) summing to \(1\), finite action sets \(D_t\), rational unary rewards \(r_t(d)\), symmetric rational role-pair rewards \(\psi_{tu}(d,e)\), and rational \(\epsilon>0\), find a finite rational representation of coalition action masses \(z^j_{td}\) and residual singleton masses \(z^0_{td}\), with \(\sum_{j\ge 0,d} z^j_{td}=\mu_t\), whose welfare is within \(\epsilon\) of the supremum over feasible partitions and pure action assignments of a unit-mass population. The welfare is the integrated unary reward plus half the integrated pair reward for pairs in the same coalition, with singleton interactions zero.
A society is given by its support: the list of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. The population is atomless, and each type's mass may be split freely.
Each type has an explicitly listed nonempty finite action set \(D_t\), with \(m=\max_t|D_t|\). Unary rewards \(r_t(d)\) and pair rewards \(\psi_{tu}(d,e)=\psi_{ut}(e,d)\) are explicitly given finite rationals, possibly negative; each type has some action with nonnegative unary reward. Pair rewards include interactions between distinct individuals of the same type.
A feasible assignment consists of finitely or countably many measurable positive-mass coalitions and residual individuals forming singleton coalitions, with each individual choosing one pure action. Write \(z^j_{td}\geq0\) for type-action mass in coalition \(j\geq1\), and \(z^0_{td}\geq0\) for residual singleton mass; require \(\sum_{j\geq0}\sum_{d\in D_t}z^j_{td}=\mu_t\). Benchmark masses may be real. Zero-mass coalitions contribute no pair reward and may be replaced by singletons.
The welfare is \(W(z)=\sum_{t,d}r_t(d)\sum_{j\geq0}z^j_{td}+\frac12\sum_{j\geq1}\sum_{t,u}\sum_{d\in D_t,e\in D_u}\psi_{tu}(d,e)z^j_{td}z^j_{ue}\); singleton interactions are zero. Let \(W^\star\) be its supremum over feasible assignments.
Given also a binary rational \(\epsilon>0\), output finitely many rational coalition masses and rational residual singleton masses satisfying feasibility and \(W(z)\geq W^\star-\epsilon\). Let \(L\) be the total binary input length, including \(\epsilon\).
Is this additive-accuracy search problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite agents, coalition structure generation with unary and binary DCOP rewards has an NP-complete welfare-threshold decision problem, even when all rewards are nonnegative. This discrete result does not classify the atomless search problem stated above.
The search problem is \(\mathrm{NP}\)-hard, even when \(\tau=1\), every unary reward is zero, and every pair reward belongs to \(\{0,1\}\). A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
The proof gives a polynomial-time reduction from the clique decision problem to one call to the additive-accuracy search problem.
Let \(G=(V,E)\) be a simple undirected graph with \(V=\{1,\ldots,n\}\), and let \(\omega(G)\) denote its maximum clique size.
Construct a society with one type of mass \(\mu_1=1\), action set \(D_1=V\), and unary rewards \(r_1(i)=0\). Define the symmetric pair rewards by
\(\psi_{11}(i,j)=1\) when \(\{i,j\}\in E\), and \(\psi_{11}(i,j)=0\) otherwise.
These data satisfy every input requirement. In particular, rewards between individuals of the same type are permitted, and all unary rewards are nonnegative. Here \(\tau=1\) and \(m=n\).
Write \(z_i^j=z_{1i}^j\). Because each edge is counted twice in the ordered pair sum, the welfare is
\(W(z)=\sum_{j\geq1}\sum_{\{i,\ell\}\in E}z_i^jz_\ell^j\).
For any feasible assignment, including one with countably many positive-mass coalitions, define the total action masses
\(x_i=\sum_{j\geq0}z_i^j\).
Feasibility gives \(x_i\geq0\) and \(\sum_i x_i=1\). For each edge, nonnegativity implies
\(\sum_{j\geq1}z_i^jz_\ell^j\leq\bigl(\sum_{j\geq0}z_i^j\bigr)\bigl(\sum_{j\geq0}z_\ell^j\bigr)=x_ix_\ell\).
For countably many coalitions, this inequality follows first for finite partial sums and then by monotone convergence. Consequently,
\(W(z)\leq F_G(x)\), where \(F_G(x)=\sum_{\{i,\ell\}\in E}x_ix_\ell\).
Conversely, any nonnegative vector \(x\) with \(\sum_i x_i=1\) is realizable by one coalition containing the entire population, with action masses \(x_i\). This uses the stipulated freedom to split the atomless type mass. Its welfare equals \(F_G(x)\). Thus
\(W^\star=\max\{F_G(x):x_i\geq0,\ \sum_i x_i=1\}\).
The maximum exists because the simplex is compact and \(F_G\) is continuous.
We prove the identity
\(\max\{F_G(x):x_i\geq0,\ \sum_i x_i=1\}=\frac12\bigl(1-\frac1{\omega(G)}\bigr)\).
This is the [Motzkin–Straus identity](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0008414X00039493); the following argument proves the needed form directly.
Suppose two positive coordinates \(x_i,x_\ell\) correspond to nonadjacent vertices. Holding all other coordinates fixed, write
\(F_G(x)=C+a x_i+b x_\ell\),
where \(a=\sum_{v:\{i,v\}\in E}x_v\) and \(b=\sum_{v:\{\ell,v\}\in E}x_v\). Neither coefficient depends on \(x_i,x_\ell\), since the graph has no loops and these vertices are nonadjacent.
Move their combined mass to \(i\) if \(a\geq b\), and to \(\ell\) otherwise. Feasibility is preserved, welfare does not decrease, and the number of positive coordinates decreases. Repeating produces a vector \(y\) supported on a clique of size \(s\leq\omega(G)\), with \(F_G(y)\geq F_G(x)\).
On that clique,
\(F_G(y)=\frac12(1-\sum_v y_v^2)\).
Cauchy–Schwarz gives \(\sum_v y_v^2\geq1/s\), hence
\(F_G(x)\leq F_G(y)\leq\frac12(1-1/s)\leq\frac12(1-1/\omega(G))\).
Uniform mass on a maximum clique attains equality. Therefore
\(W^\star=f(\omega(G))\), where \(f(q)=\frac12(1-1/q)\).
In particular, this optimum is attained by one coalition with rational action masses.
The clique decision problem asks whether \(\omega(G)\geq k\) and is \(\mathrm{NP}\)-complete. [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf) establishes this result. We may restrict to \(n\geq2\) and \(2\leq k\leq n\), since the remaining cases are directly decidable.
Let \(h=\lceil\log_2 n\rceil\), and supply the constructed society with the dyadic accuracy
\(\epsilon=2^{-(2h+2)}\leq1/(4n^2)\).
Suppose a polynomial-time algorithm returns a feasible rational assignment of welfare \(V\) satisfying
\(W^\star-\epsilon\leq V\leq W^\star\).
The gap between consecutive relevant optimum values is
\(f(k)-f(k-1)=1/(2k(k-1))\geq1/(2n(n-1))>\epsilon\).
It follows that:
Thus the exact rational comparison \(V>f(k-1)\) decides whether \(G\) contains a clique of size at least \(k\).
The society’s explicitly listed reward table has polynomial size, and \(\epsilon\) has \(O(\log n)\) bits. A polynomial-time search algorithm necessarily produces an output of polynomial length. Its welfare can therefore be evaluated and compared with \(f(k-1)\) using exact rational arithmetic in polynomial time.
This establishes the claimed \(\mathrm{NP}\)-hardness directly for the atomless search problem, including its real-valued benchmark and countably many allowed coalitions.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated task correctly: the additive-accuracy search problem is \(\mathrm{NP}\)-hard, even with one supported type, zero unary rewards, and pair rewards in \(\{0,1\}\). No major or minor mathematical issues were found.
The construction satisfies every input requirement:
Interactions between distinct individuals of the same type are expressly allowed by the task, so using graph vertices as actions introduces no forbidden interaction.
The welfare formula is correct: each undirected edge contributes two equal terms to the ordered pair sum, and the factor \(1/2\) cancels this duplication.
For every feasible assignment, the total action masses \(x_i\) are nonnegative and sum to \(1\), including residual singleton mass.
The inequality
\(\sum_{j\geq1}z_i^jz_\ell^j\leq x_ix_\ell\)
is valid because all masses are nonnegative. The stated finite-partial-sum argument also covers countably many coalitions. Summing over the finitely many edges therefore gives the claimed upper bound on welfare.
Conversely, the task permits arbitrary real action masses summing to \(1\) within one coalition containing the entire population. Thus every simplex vector is feasible and realizes the corresponding quadratic objective.
Consequently, the equality between \(W^\star\) and the simplex maximum is justified. Compactness and continuity establish attainment, so there is no unresolved distinction between supremum and maximum.
The proof supplies a complete argument for the needed identity; it does not depend on an unproved invocation of Motzkin–Straus. Its statement also agrees with the [original paper](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0008414X00039493).
Every mass-transfer step is valid:
The process terminates after finitely many transfers. Its final support is a nonempty clique, so \(1\leq s\leq\omega(G)\).
The objective formula on that support, the Cauchy–Schwarz bound, and the comparison using \(s\leq\omega(G)\) are all correct. Uniform mass on a maximum clique gives the asserted equality.
The edgeless case is covered: \(\omega(G)=1\), and both the optimum and the stated formula equal zero. The attaining masses are rational, as claimed.
The invoked external complexity result is precisely that CLIQUE, with an explicitly represented finite graph and an integer threshold, is \(\mathrm{NP}\)-complete. This is the standard result attributed to [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf). The restriction to \(n\geq2\) and \(2\leq k\leq n\) is legitimate because the excluded cases are directly decidable.
The accuracy calculation is correct:
\(\epsilon=2^{-(2h+2)}\leq1/(4n^2)\), where \(h=\lceil\log_2n\rceil\).
The consecutive-value gap is also correct:
\(f(k)-f(k-1)=1/(2k(k-1))\geq1/(2n(n-1))>\epsilon\).
Both decision implications follow. A no-instance always produces welfare at most \(f(k-1)\); a yes-instance always produces welfare strictly greater than that threshold. This works for every output satisfying the search specification, independently of which approximate assignment the algorithm selects.
The upper bound \(V\leq W^\star\) follows from feasibility and the definition of the supremum.
The explicit reward table has polynomial size, and the chosen accuracy has binary length \(O(\log n)\). Hence the constructed parameters \(m,\tau,L\) are polynomially bounded in the source-instance length.
A polynomial-time algorithm producing an explicit finite rational assignment has polynomial output length. Its welfare involves polynomially many rational products and sums; exact evaluation and threshold comparison have polynomial bit complexity.
The argument therefore establishes the claimed one-call polynomial-time reduction to the search problem. It addresses the atomless benchmark directly and does not rely on the discrete coalition-generation result.
No additional lemma, clarification, or correction is required. The proof establishes hardness and the implication that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\); it does not claim an unconditional separation.
⟨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.