Answer: Both exact decision and additive value approximation are \(\mathrm{NP}\)-hard for every fixed rational \(\gamma\ge2\), including approximation when \(1/\varepsilon\) is polynomially bounded in \(L\).
Proposition 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf a domain satisfies the aforementioned prop- erties, an efficient technique can be used to compute a tight bound- ing function. In particular, given a node CSi: M (CSi) = f −(CSi) + f + (CSi) is an admissible bound for the subtree rooted at CSi: M (CSi) ≥max{f(CSi)∣CSj ∈ST(CSi)} PROOF. Consider that, for the subtree rooted at CSi, the max- imum of an anti-monotonic function f −will be achieved at CSi (Property 2), i.e., f −(CSi) ≥max {f −(CSj)∣CSj ∈ST(CSi)}. On the other hand, the maximum of a monotonic function f + will be reached at one of the leaves.
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\ge 0\) with \(\sum_{t\in T}\mu_t=1\), a type compatibility graph \(H=(T,E_H)\), rational interaction weights \(w_{tu}\), \(\alpha>0\), and fixed \(\gamma\ge 2\), maximize the sum of coalition payoffs over finite mass partitions \(x^1,\ldots,x^k\in\mathbb{R}_{\ge0}^{T}\), where \(\sum_j x_t^j=\mu_t\), each \(\operatorname{supp}(x^j)\) is connected in \(H\), and each payoff is \(F(x^j)=\frac12\sum_t w_{tt}(x_t^j)^2+\sum_{\{t,u\}\in E_H}w_{tu}x_t^jx_u^j-\alpha(\sum_t x_t^j)^\gamma\). Determine the exact optimum or return an additive-\(\varepsilon\) approximation.
A society is given by its support: the list of the \(\tau\) types \(T\) with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Input also includes a connected simple undirected compatibility graph \(H=(T,E_H)\), signed rational weights \(w_{tt}\) and \(w_{tu}=w_{ut}\) for \(\{t,u\}\in E_H\), and a positive rational \(\alpha\). Fix a rational constant \(\gamma\ge2\).
A feasible mass partition consists of any finite number \(k\ge1\) of nonzero vectors \(x^j\in\mathbb R_{\ge0}^{T}\), with \(\sum_{j=1}^k x_t^j=\mu_t\), such that each induced graph \(H[\{t:x_t^j>0\}]\) is connected; singleton supports are permitted. Types may split among coalitions, and no bound on \(k\) is imposed.
The payoff is \(F(x)=\frac12\sum_t w_{tt}x_t^2+\sum_{\{t,u\}\in E_H}w_{tu}x_tx_u-\alpha(\sum_t x_t)^\gamma\); nonedges contribute nothing. Define \(V^*=\sup\{\sum_{j=1}^kF(x^j): (x^1,\ldots,x^k)\text{ is feasible}\}\).
Exact value computation is understood through the decision problem \(V^*\ge b\), for a binary rational threshold \(b\). Additive approximation means computing a rational \(z\) with \(|z-V^*|\le\varepsilon\), for a binary rational \(0<\varepsilon<1\). Let \(m=|E_H|\) and let \(L\) be the total input bit length, including the threshold or accuracy input.
Is deciding \(V^*\ge b\) in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it NP-hard?
Is additive-\(\varepsilon\) value approximation possible in time polynomial in \(m,\tau,L,1/\varepsilon\), or is it NP-hard even when \(1/\varepsilon\) is polynomially bounded in \(L\)?
For discrete connected-coalition partitions, an objective decomposing into a part increasing under coalition mergers and a part decreasing under mergers admits an efficiently evaluable subtree upper bound, combining the decreasing part at the current partition with the increasing part at a computable coarsening. This supports exact branch and bound without establishing polynomial-time optimization ([verified discrete result](https://iris.univr.it/retrieve/e14ff6e3-ab38-0209-e053-6605fe0ad24c/2017tist.pdf)).
No result settling this precise continuous mass-partition problem was identified in the literature search.
For every fixed rational \(\gamma\ge2\), both problems are \(\mathrm{NP}\)-hard:
The hardness holds when \(H\) is complete, all masses are equal, and every weight has absolute value less than \(1\). Thus the proposed polynomial-time algorithms cannot exist unless \(\mathrm P=\mathrm{NP}\).
First, the possibility of using arbitrarily many coalitions must be handled explicitly.
Let \(r\in\mathbb R_{\ge0}^{T}\) be any residual mass vector. For a positive integer \(N\), split each positive coordinate \(r_t\) into \(N\) singleton coalitions, each with vector \((r_t/N)e_t\). These coalitions are feasible because singleton supports are permitted. Their total payoff is
\( D_N(r)=\frac{1}{2N}\sum_t w_{tt}r_t^2-\frac{\alpha}{N^{\gamma-1}}\sum_t r_t^\gamma. \)
Because \(\gamma\ge2\), both terms tend to zero as \(N\) tends to infinity.
Consequently:
These statements concern a supremum; they do not require its attainment.
The supremum is also finite. Let \(B\) be the largest absolute value of an input weight. For a coalition of total mass \(s\), its quadratic contribution is at most \(Bs^2/2\), so \(F(x)\le Bs^2/2\). Coalition masses sum to \(1\), hence every partition has value at most \(B/2\).
Let \(G\) be a simple graph on vertex set \(\{1,\ldots,n\}\), with clique number \(\omega(G)\). Define
\( A_G(p)=\sum_{\{i,j\}\in E(G)}p_ip_j \)
for \(p\ge0\) satisfying \(\sum_i p_i=1\). We prove
\( \max_{p\ge0,\ \sum_i p_i=1}A_G(p)=\frac12\left(1-\frac1{\omega(G)}\right). \)
Proof. Suppose two nonadjacent vertices \(a,b\) both have positive coordinates. Write
\( U_a=\sum_{v:\{a,v\}\in E(G)}p_v,\qquad U_b=\sum_{v:\{b,v\}\in E(G)}p_v. \)
Because \(a,b\) are nonadjacent, neither quantity depends on \(p_a\) or \(p_b\). The part of \(A_G(p)\) involving these coordinates is \(p_aU_a+p_bU_b\).
If \(U_a\ge U_b\), replace \((p_a,p_b)\) by \((p_a+p_b,0)\). This increases the objective by \(p_b(U_a-U_b)\ge0\). If \(U_b>U_a\), merge into \(b\) instead. Each operation decreases the support size.
After finitely many operations, the support is a clique, of some size \(r\le\omega(G)\). On that support,
\( A_G(p)=\frac12\left(1-\sum_i p_i^2\right) \le\frac12\left(1-\frac1r\right) \le\frac12\left(1-\frac1{\omega(G)}\right), \)
where \(\sum_i p_i^2\ge1/r\) follows from Cauchy–Schwarz. Since the operations never decreased the objective, this bounds the original vector as well.
Conversely, assigning mass \(1/\omega(G)\) to each vertex of a maximum clique attains the stated bound. This proves the characterization.
We reduce from CLIQUE: given \(G\) and an integer \(K\), decide whether \(\omega(G)\ge K\). Its \(\mathrm{NP}\)-completeness is the standard result of [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may restrict to \(2\le K\le |V(G)|\): instances outside this range are immediately decidable and can be mapped to fixed yes- or no-instances.
Pad \(G\) with isolated vertices until its vertex count \(n\) is a power of two. This at most doubles its size and preserves its clique number. The padding ensures that the masses and the thresholds below are dyadic rationals.
For each positive integer \(r\), define
\( a_r=\frac12\left(1-\frac1r\right). \)
Set
\( c=\frac{a_K+a_{K-1}}2,\qquad \delta=\frac{a_K-a_{K-1}}2=\frac1{4K(K-1)},\qquad \alpha=\frac{\delta}{2}. \)
Construct the society as follows:
\( w_{ij}= \begin{cases} 1-2c,&\{i,j\}\in E(G),\\ -2c,&\{i,j\}\notin E(G). \end{cases} \)
The source graph \(G\) encodes the weights; the compatibility graph \(H\) is complete. Thus every nonempty coalition support is connected.
Writing \(s=\sum_i x_i\), direct expansion gives
\( \frac12\sum_i w_{ii}x_i^2+\sum_{i<j}w_{ij}x_ix_j =\sum_{\{i,j\}\in E(G)}x_ix_j-cs^2. \)
Therefore the constructed payoff is
\( F(x)=\sum_{\{i,j\}\in E(G)}x_ix_j-cs^2-\alpha s^\gamma. \)
All constructed data are rational. Since \(0<c<1/2\), every weight has absolute value less than \(1\).
Suppose \(\omega(G)\le K-1\). Consider any nonzero coalition \(x\), and normalize it by \(p=x/s\), where \(s=\sum_i x_i>0\).
The characterization in Section 2 gives
\( \sum_{\{i,j\}\in E(G)}x_ix_j =s^2A_G(p) \le a_{K-1}s^2. \)
Since \(c-a_{K-1}=\delta\),
\( F(x)\le-\delta s^2-\alpha s^\gamma<0. \)
This inequality holds for every coalition vector, including arbitrary real vectors produced by splitting types. Every finite feasible partition therefore has negative total payoff, implying \(V^*\le0\).
Section 1 proves \(V^*\ge0\). Hence
\( \omega(G)\le K-1\quad\Longrightarrow\quad V^*=0. \)
In these instances the supremum is not attained, which is why arbitrarily fine splitting matters.
Suppose \(\omega(G)\ge K\), and choose a clique \(C\) with exactly \(K\) vertices. Define one coalition by
\( x_i= \begin{cases} 1/n,&i\in C,\\ 0,&i\notin C. \end{cases} \)
This vector satisfies \(x\le\mu\), and its support is connected in \(H\). Its total mass is \(s=K/n\le1\). Uniformity on the clique gives
\( \sum_{\{i,j\}\in E(G)}x_ix_j =\frac{K(K-1)}{2n^2} =a_Ks^2. \)
Since \(a_K-c=\delta\),
\( F(x)=\delta s^2-\alpha s^\gamma. \)
For \(0<s\le1\) and \(\gamma\ge2\), we have \(s^\gamma\le s^2\). Using \(\alpha=\delta/2\), it follows that
\( F(x)\ge\frac{\delta}{2}s^2 =\frac{K}{8(K-1)n^2} \ge\frac1{8n^2}. \)
By Section 1, the remaining masses can be partitioned into singleton coalitions whose total payoff tends to zero. Therefore
\( \omega(G)\ge K\quad\Longrightarrow\quad V^*\ge\frac1{8n^2}. \)
Together, Sections 4 and 5 establish the gap
\( \omega(G)<K\ \Longrightarrow\ V^*=0, \qquad \omega(G)\ge K\ \Longrightarrow\ V^*\ge\frac1{8n^2}. \)
Choose the rational threshold
\( b=\frac1{16n^2}. \)
The established gap proves the exact equivalence
\( \omega(G)\ge K\quad\Longleftrightarrow\quad V^*\ge b. \)
The construction has \(\tau=n\) and \(m=n(n-1)/2\). Every rational parameter has bit length \(O(\log n)\), and the entire instance can be constructed in polynomial time.
This is a polynomial-time many-one reduction from CLIQUE. Thus deciding \(V^*\ge b\) is \(\mathrm{NP}\)-hard for every fixed rational \(\gamma\ge2\).
For the same society, request accuracy
\( \varepsilon=\frac1{64n^2}. \)
Suppose an algorithm returns a rational \(z\) satisfying \(|z-V^*|\le\varepsilon\).
In a no-instance,
\( z\le\frac1{64n^2}<b. \)
In a yes-instance,
\( z\ge\frac1{8n^2}-\frac1{64n^2} =\frac7{64n^2}>b. \)
Comparing \(z\) with \(b\) therefore decides CLIQUE using one approximation call.
The explicit input lists \(n\) positive masses, so its total bit length satisfies \(L\ge n\). Consequently,
\( \frac1\varepsilon=64n^2\le64L^2. \)
Thus additive approximation is \(\mathrm{NP}\)-hard even when inverse accuracy is polynomially bounded in \(L\). An algorithm polynomial in \(m,\tau,L,1/\varepsilon\) would imply \(\mathrm P=\mathrm{NP}\).
The reduction proves both requested hardness results without imposing any bound on coalition count or forbidding type splitting. It makes no assertion of membership of the exact decision problem in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves both requested hardness results. I found no major or minor mathematical issues.
Splitting each positive residual coordinate into \(N\) singleton coalitions gives exactly
\(D_N(r)=\frac{1}{2N}\sum_t w_{tt}r_t^2-\frac{\alpha}{N^{\gamma-1}}\sum_t r_t^\gamma\).
Each partition is finite and feasible, and both terms converge to zero for every fixed \(\gamma\ge2\), including \(\gamma=2\).
Consequently, \(V^*\ge0\), even if every finite partition has negative value. Likewise, adjoining these residual coalitions to a permitted vector \(x\le\mu\) gives partition values converging to \(F(x)\), establishing \(V^*\ge F(x)\). When the residual is zero, the single coalition already supplies this inequality. No attainment assumption is used.
The finiteness bound is also valid: the quadratic contribution is at most \(Bs^2/2\), the penalty is nonpositive, and coalition masses satisfy \(\sum_j s_j^2\le(\sum_j s_j)^2=1\). Thus \(0\le V^*\le B/2\).
For nonadjacent positive coordinates \(a,b\), the quantities \(U_a,U_b\) are independent of both coordinates. Moving their combined mass to the coordinate with larger \(U\) therefore changes the objective by the stated nonnegative amount.
Every operation preserves nonnegativity and total mass while strictly reducing support size. Termination yields a nonempty clique support. On a support of size \(r\), Cauchy–Schwarz applies and gives \(\sum_i p_i^2\ge1/r\). Since \(r\le\omega(G)\), the resulting upper bound is correct. Uniform mass on a maximum clique attains it.
All graphs used in the reduction have at least two vertices, so the characterization encounters no empty-graph denominator issue.
The cited source theorem is that CLIQUE, with an input simple graph and variable integer target size, is \(\mathrm{NP}\)-complete. This is the problem used here. See [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Restricting to \(2\le K\le |V(G)|\) removes only immediately decidable cases. Isolated-vertex padding preserves the clique number for these nonempty graphs and increases the vertex count by less than a factor of two.
The parameter calculation is correct:
\(\delta=1/[4K(K-1)]\) and \(\alpha=1/[8K(K-1)]>0\).
The complete compatibility graph is connected, and every nonempty support induces a connected graph. The positive masses sum to one.
The asserted strict weight bounds hold, including at \(K=2\): \(0<c<1/2\), so \(|-2c|<1\) and \(|1-2c|<1\).
Padding makes the masses and the eventual threshold and accuracy dyadic. The other parameters need only be rationals encoded in binary, as the task permits. Their numerators and denominators have \(O(\log n)\) bits, and the explicit complete graph and weights require only polynomial output size.
Substituting the weights yields exactly
\(\sum_{\{i,j\}\in E(G)}x_ix_j-cs^2-\alpha s^\gamma\).
The diagonal and off-diagonal coefficients have the required factors.
Every nonzero coalition has \(s>0\), so \(p=x/s\) is a valid simplex vector. If \(\omega(G)\le K-1\), the characterization gives
\(F(x)\le-\delta s^2-\alpha s^\gamma<0\).
This applies to arbitrary real coalition vectors, regardless of splitting.
Every finite feasible partition therefore has negative value. Its supremum is at most zero; the splitting argument establishes the reverse inequality. Hence \(V^*=0\). The observation that this supremum is unattained is justified.
A clique of size at least \(K\) contains one of exactly \(K\) vertices. The proposed coalition respects every coordinate capacity and has connected support.
Its edge contribution is \(K(K-1)/(2n^2)=a_Ks^2\), with \(s=K/n\in(0,1]\). Since \(\gamma\ge2\), \(s^\gamma\le s^2\). Thus
\(F(x)\ge\delta s^2/2=K/[8(K-1)n^2]\ge1/(8n^2)\).
The residual-splitting argument transfers this coalition payoff to a lower bound on the supremum. It requires neither an attained optimum nor a bounded number of coalitions.
The threshold \(b=1/(16n^2)\) lies strictly between the no-instance value zero and the yes-instance lower bound \(1/(8n^2)\). Therefore the stated equivalence with CLIQUE holds in both directions.
The construction is polynomial in the source input size, with \(\tau=n\) and \(m=n(n-1)/2\). This proves the requested exact-decision hardness for each fixed rational \(\gamma\ge2\).
For \(\varepsilon=1/(64n^2)\), every permitted approximation satisfies \(z\le1/(64n^2)<b\) in a no-instance and \(z\ge7/(64n^2)>b\) in a yes-instance. The comparison works for every rational output satisfying the approximation guarantee.
The explicit mass list ensures \(L\ge n\), so \(1/\varepsilon=64n^2\le64L^2\). A running time polynomial in \(m,\tau,L,1/\varepsilon\) would therefore yield a polynomial-time CLIQUE algorithm.
The approximation hardness is established through the explicitly stated single-call reduction. The output correctly avoids claiming membership of the exact decision problem in \(\mathrm{NP}\).
No repair or additional clarification is needed. Both hardness claims hold under the intended continuous model, including unrestricted finite coalition counts and real-valued type splitting.
⟨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.