Answer: Computing an exact global maximizing assignment is \(\mathrm{NP}\)-hard already for \(m=1\) and \(K=2\); the rational-threshold decision problem is \(\mathrm{NP}\)-complete.
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven any community member matrix s (T) at the initial moment, CDP can ultimately find a stable community membership matrix s (T + 1), which is a pure Nash equilibrium w.r.t. DGSWM, and is also the solution of CDSWM.
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>0\) summing to \(1\), fixed opinions \(x_t\), susceptibilities \(\lambda_t\), type-to-type influence rates \(w_{tu}\), a threshold \(\psi\), and \(K\) communities, define \(D_{tu}=\psi-|x_t-x_u|\), \(B_{tu}=\max\{D_{tu},0\}\), and \(Y_{tu}=(\lambda_tD_{tu}-B_{tu})w_{tu}+(\lambda_uD_{ut}-B_{ut})w_{ut}\). Choose shares \(q_{tk}\geq0\), with \(\sum_{k=1}^K q_{tk}=1\), to globally maximize \(\Phi(q)=\frac12\sum_{t,u\in T}\mu_t\mu_uY_{tu}\sum_{k=1}^Kq_{tk}q_{uk}\), and return a maximizing assignment.
A society is given by its support: the list of the \(\tau=|T|\) types with positive mass, each mass a binary rational \(\mu_t>0\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a fixed rational opinion \(x_t\in[0,1]\) and susceptibility \(\lambda_t>1\). Influence rates \(w_{tu}\geq0\) are rational, \(w_{tt}=0\), and the directed graph with arcs where \(w_{tu}>0\) is strongly connected. The rational confidence threshold satisfies \(0<\psi<1\); the number of available community labels \(K\geq1\) is an input integer.
Define \(D_{tu}=\psi-|x_t-x_u|\), \(B_{tu}=\max\{D_{tu},0\}\), and \(Y_{tu}=(\lambda_tD_{tu}-B_{tu})w_{tu}+(\lambda_uD_{ut}-B_{ut})w_{ut}\). Negative values of \(D_{tu}\) are retained.
An assignment consists of real shares \(q_{tk}\geq0\) satisfying \(\sum_{k=1}^{K}q_{tk}=1\); \(\mu_tq_{tk}\) is the mass of type \(t\) in community \(k\). Empty communities are allowed. The objective is \(\Phi(q)=\frac12\sum_{t,u\in T}\mu_t\mu_uY_{tu}\sum_{k=1}^{K}q_{tk}q_{uk}\).
Let \(L\) be the total binary input length and \(m=1\) the opinion dimension; state running times in \(m,\tau,K,L\).
Is computing an exact global maximizing assignment for \(\Phi\) solvable in polynomial time in \(m,\tau,K,L\), or is it NP-hard?
For finite agents with indivisible memberships, sequential best responses are claimed to reach a pure Nash equilibrium that also globally maximizes welfare; the stated runtime depends on an unbounded expected iteration count. [Zhang et al.](https://ojs.aaai.org/index.php/AAAI/article/download/41312/45273)
No complexity classification for this exact mass optimization problem was located.
Computing an exact global maximizing assignment is \(\mathrm{NP}\)-hard, already when \(m=1\), \(K=2\), every susceptibility is \(\lambda_t=2\), and \(\psi=3/4\). This remains true with positive dyadic masses and symmetric influence rates whose graph is strongly connected.
The corresponding decision problem—whether the maximum is at least a given rational threshold—is \(\mathrm{NP}\)-complete. Consequently, an algorithm polynomial in \(m,\tau,K,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
For \(K=1\), the assignment is forced. The hardness concerns the nontrivial case \(K=2\).
The definition gives \(Y_{tu}=Y_{ut}\) and \(Y_{tt}=0\). Put \(c_{tu}=\mu_t\mu_uY_{tu}\). Fixing any ordering of the types, the objective becomes
\(\displaystyle \Phi(q)=\sum_{t<u}c_{tu}\sum_{k=1}^{K}q_{tk}q_{uk}.\)
A pure assignment is a label map \(s:T\to\{1,\ldots,K\}\), represented by \(q_{tk}=\mathbf{1}\{s(t)=k\}\). Its objective is
\(\displaystyle \Phi(s)=\sum_{t<u}c_{tu}\mathbf{1}\{s(t)=s(u)\}.\)
Lemma. The maximum over all real-share assignments equals the maximum over pure assignments.
Proof. Given any feasible \(q\), independently choose a label \(S_t\) for each type, with \(\Pr(S_t=k)=q_{tk}\). For distinct types,
\(\displaystyle \Pr(S_t=S_u)=\sum_{k=1}^{K}q_{tk}q_{uk}.\)
Linearity of expectation therefore gives \(\mathbb{E}[\Phi(S)]=\Phi(q)\). At least one pure assignment has value at least this expectation. Since pure assignments themselves are feasible, the two maxima coincide. This also proves that a global maximum exists. \(\square\)
The absence of diagonal terms is essential: independence is used only for distinct types.
We reduce from unweighted Max-Cut. Its decision problem asks whether a simple undirected graph has a cut containing at least a specified number of edges. This problem is \(\mathrm{NP}\)-complete by [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975%2876%2990059-1).
We can require the source graph to be connected. Indeed, if a graph has \(d\) connected components, choose one representative from each and add \(d-1\) edges joining consecutive representatives. The resulting graph \(G'\) satisfies
\(\displaystyle \operatorname{MaxCut}(G')=\operatorname{MaxCut}(G)+d-1.\)
The upper bound follows because only \(d-1\) edges were added. For the lower bound, take a maximum cut in each component. Complementing a component’s two sides preserves its internal cut size. Choose these complements successively so that every added edge crosses the cut. Adjusting the decision threshold by \(d-1\) proves the claimed restriction.
Henceforth let the source graph be connected, with vertices \(\{1,\ldots,n\}\), edge set \(E\), and \(r=|E|\). We may restrict to \(n\geq2\), since smaller instances are trivial. Set \(H=r+1\).
For each source vertex \(i\), introduce three types \(a_i,b_i,d_i\), with opinions
\(x_{a_i}=0,\qquad x_{b_i}=1/2,\qquad x_{d_i}=1.\)
Set \(K=2\), \(\psi=3/4\), and \(\lambda_t=2\) for every type. Thus \(m=1\) and \(\tau=3n\).
To ensure that the masses are dyadic, enumerate the types as \(t_1,\ldots,t_\tau\), and let \(Q\) be the smallest power of two at least \(\tau\). Define
\(\displaystyle \mu_{t_j}=1/Q\quad(j<\tau),\qquad \mu_{t_\tau}=(Q-\tau+1)/Q.\)
All masses are positive, and their sum is one.
Define symmetric influence rates as follows:
For either internal pair, the opinion distance is \(1/2\). Therefore \(D=1/4\), \(B=1/4\), and \(\lambda D-B=1/4\). Symmetry of the rates gives
\(\displaystyle Y_{tu}=w_{tu}/2,\qquad c_{tu}=H.\)
For a pair encoding a source edge, the opinion distance is \(1\). Thus \(D=-1/4\), \(B=0\), and \(\lambda D-B=-1/2\). Consequently,
\(\displaystyle Y_{tu}=-w_{tu},\qquad c_{tu}=-1.\)
All other coefficients vanish. For a pure assignment, the objective is exactly
\(\displaystyle \Phi(s)= H\sum_{i=1}^{n} \bigl( \mathbf{1}\{s(a_i)=s(b_i)\} +\mathbf{1}\{s(b_i)=s(d_i)\} \bigr) -\sum_{\substack{\{i,j\}\in E\\i<j}} \mathbf{1}\{s(a_i)=s(d_j)\}. \)
Each triple is connected by its two internal influence edges. Each source edge connects its two corresponding triples. Since the source graph is connected, the undirected influence graph is connected. Every influence edge occurs in both directions, so the directed graph is strongly connected.
The construction uses only rational, nonnegative rates and has zero diagonal. Also, \(Q<2\tau\), and every nonzero rate has numerator and denominator of \(O(\log n)\) bits: after substituting the masses, its numerator is at most \(2HQ^2\), and its denominator is at most \(Q^2\). A dense encoding therefore has length \(O(n^2\log n)\), and the construction takes polynomial time.
Call an assignment coherent if \(s(a_i)=s(b_i)=s(d_i)\) for every source vertex.
Lemma. Every globally maximizing pure assignment is coherent.
Proof. Assigning every type the same label gives value \(2nH-r\).
An incoherent assignment loses at least one of the \(2n\) positive contributions of size \(H\). All remaining terms are nonpositive, so its value is at most \((2n-1)H\). But
\(\displaystyle (2nH-r)-(2n-1)H=H-r=1>0.\)
Thus an incoherent assignment cannot maximize the objective. \(\square\)
For a coherent assignment, let \(z_i\in\{1,2\}\) be the common label of its triple. If \(C(z)\) is the number of source edges crossing these two labels, then
\(\displaystyle \Phi(s)=2nH-\bigl(r-C(z)\bigr)=2nH-r+C(z). \)
Every cut yields such a coherent assignment. Combining this fact with the preceding lemma and Section 1 proves
\(\displaystyle \boxed{\max_q\Phi(q)=2nH-r+\operatorname{MaxCut}(G).}\)
Hence, for any integer cut threshold \(b\),
\(\displaystyle \operatorname{MaxCut}(G)\geq b \quad\Longleftrightarrow\quad \max_q\Phi(q)\geq 2nH-r+b. \)
This is a polynomial-time many-one reduction proving decision hardness.
There is no ambiguity caused by a solver returning fractional shares. In this construction, every maximizing real-share assignment is pure and coherent.
To prove this, independently round a maximizing \(q\) as in Section 1. Its expected value equals the global maximum, and every pure outcome has value at most that maximum. Therefore every outcome of positive probability must be maximizing, hence coherent.
In particular, adjacent types within a triple have equal random labels with probability one. Two independent label distributions can have this property only when both are concentrated on the same single label: any distinct labels in their supports would otherwise occur together with positive probability. Applying this to both internal pairs proves the assertion.
Reading the triple labels from an exact maximizing assignment consequently recovers a maximum cut. This establishes hardness of the requested assignment computation itself.
For an arbitrary valid instance, Section 1 ensures that a pure assignment witnesses any attainable threshold. Its certificate consists of \(\tau\) labels, requiring \(O(\tau\log(K+1))\) bits. Its objective can be evaluated exactly using polynomially many rational arithmetic operations, with polynomial bit complexity.
Thus the rational-threshold decision problem belongs to \(\mathrm{NP}\), and the reduction proves it is \(\mathrm{NP}\)-complete.
For an explicit exact upper bound, put \(K_0=\min\{K,\tau\}\). A pure assignment occupies at most \(\tau\) labels, and relabeling preserves its value. Enumerating all \(K_0^\tau\) label maps and evaluating each yields a running time of
\(\displaystyle O\!\left(K_0^\tau\,\tau^2\,\operatorname{poly}(m,L)+\tau K\right),\qquad m=1.\)
The final \(\tau K\) term accounts for writing a dense share matrix; it can be omitted when the output is given as one label per type.
The hardness holds with \(m=1\) and \(K=2\) fixed. Therefore allowing polynomial dependence on these parameters does not remove it.
[Zhang et al., Theorems 1–3](https://ojs.aaai.org/index.php/AAAI/article/download/41312/45273) give the potential-game formulation, claim that the resulting equilibrium solves global welfare maximization, and express runtime using an expected iteration count. The potential property supports termination of strict improvement moves in a finite game; it does not imply global maximization.
Here is an explicit counterexample satisfying the finite-agent assumptions.
Take six agents in two triples, with opinions \(0,1/2,1\) in each triple. Set \(K=2\), \(\psi=3/4\), and every susceptibility to \(2\). Give each of the four internal adjacent pairs symmetric influence rate \(4\), and give the pair connecting the opinion-\(0\) agent of the first triple to the opinion-\(1\) agent of the second triple symmetric rate \(1\). All other rates are zero.
The influence graph is strongly connected. The four internal coefficients are \(Y=2\), and the connecting coefficient is \(Y=-1\).
Place all agents in community \(1\). Under the paper’s modified utility \(u_t^\star=\sum_{u\ne t}Y_{tu}\mathbf{1}\{s(t)=s(u)\}\):
Moving alone to the empty second community gives utility \(0\). Thus this assignment is a strict pure Nash equilibrium, even when both labels are available.
Its potential is \(4\cdot2-1=7\). Placing the two whole triples in different communities gives potential \(4\cdot2=8\). The equilibrium therefore fails to maximize welfare.
⟨structured verdict parsed — rendered above⟩
The reduction is correct and resolves the intended complexity question: computing an exact maximizing assignment is \(\mathrm{NP}\)-hard, even with \(m=1\) and \(K=2\). No mathematical error or blocking gap appears in the argument. One minor clarification concerns the encoding assumed for susceptibilities in the general decision-complexity claim.
The construction respects support-size encoding: it explicitly lists \(\tau=3n\) positive-mass types. It does not enumerate an implicitly larger space of possible types.
All parameters in the hardness construction are rational, including the fixed susceptibilities \(\lambda_t=2\). Thus the hardness conclusion does not depend on any ambiguity about susceptibility encoding.
Minor issue: the claim of membership in \(\mathrm{NP}\) for arbitrary valid instances assumes that susceptibilities have binary-rational encodings. The task expressly specifies rationality for opinions and influence rates but does not expressly specify it for susceptibilities. The natural intended interpretation supports the claim, but the write-up should state that interpretation.
Minimum clarification: explicitly assume that each \(\lambda_t\) is a binary-encoded rational included in \(L\).
Symmetry \(Y_{tu}=Y_{ut}\) follows directly from the definition, and \(Y_{tt}=0\) follows from \(w_{tt}=0\). Consequently, replacing the half-weighted ordered-pair sum by the unordered-pair sum is correct.
Independent rounding gives, for distinct types,
\[
\Pr(S_t=S_u)=\sum_{k=1}^{K}q_{tk}q_{uk}.
\]
This identity and linearity of expectation remain valid when coefficients are negative.
The rounded distribution has finitely many outcomes, so at least one outcome has objective value at least its expectation. Every feasible fractional assignment is therefore dominated by some pure assignment. Since pure assignments are feasible and there are finitely many of them, the two maxima coincide and a global maximum exists.
Assessment: correct and complete. The absence of diagonal terms is appropriately identified.
The cited source establishes the NP-completeness of unweighted Max-Cut. The source problem used in the reduction has the required form. See [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591).
Joining representatives of different connected components by a chain preserves simplicity and creates exactly \(d-1\) additional edges. These edges can all cross a cut by successively complementing component cuts, without changing their internal cut sizes. Hence
\[
\operatorname{MaxCut}(G')=\operatorname{MaxCut}(G)+d-1
\]
is justified in both directions.
Restricting to \(n\geq2\) removes only trivial cases. For the connected source graphs subsequently used, \(r\geq1\).
Assessment: correct; the stated source theorem and the connectedness restriction suffice.
The mass construction is valid. Since \(Q\geq\tau\), every numerator is positive, and
\[
\frac{\tau-1}{Q}+\frac{Q-\tau+1}{Q}=1.
\]
All masses are dyadic.
For an internal pair, the distance is \(1/2\), giving
\[
D=B=\frac14,\qquad \lambda D-B=\frac14.
\]
Equal rates in the two directions therefore give \(Y_{tu}=w_{tu}/2\). Substituting the specified rate yields \(c_{tu}=H\).
For a source-edge pair, the distance is \(1\), giving
\[
D=-\frac14,\qquad B=0,\qquad \lambda D-B=-\frac12.
\]
Thus \(Y_{tu}=-w_{tu}\), and the specified rate yields \(c_{tu}=-1\). Retaining negative confidence differences is essential here and agrees with the task.
Internal pairs and source-edge pairs cannot coincide. Each source edge introduces exactly one negative unordered pair, and all unspecified coefficients vanish. The displayed pure objective consequently has the correct signs and multiplicities.
Each triple is connected internally, and each source edge connects its corresponding triples. Bidirectional influence edges turn this connected undirected graph into a strongly connected directed graph.
Finally, \(Q<2\tau\), \(r\leq n(n-1)/2\), and \(H=r+1\). The stated numerator and denominator bounds give \(O(\log n)\) bits per nonzero rate. The dense input-length bound \(O(n^2\log n)\) and polynomial construction time follow.
Assessment: all input requirements and calculations check out.
An incoherent triple necessarily loses at least one internal positive contribution. Since every other contribution outside the internal rewards is nonpositive,
\[
\Phi(s)\leq(2n-1)H
\]
holds for every incoherent pure assignment.
The all-equal assignment has value \(2nH-r\), exceeding that bound by \(H-r=1\). Thus every maximizing pure assignment is coherent.
In a coherent assignment, a negative source-edge contribution occurs exactly when its endpoint triples share a label. Therefore
\[
\Phi(s)=2nH-r+C(z).
\]
Every source cut has a coherent representative. Combining this correspondence with Section 1 establishes the claimed optimum identity and both directions of the threshold reduction.
Assessment: correct and complete.
Independently rounding a maximizing fractional assignment produces a finite distribution whose expectation equals the global maximum. Since every outcome has value at most that maximum, every positive-probability outcome must attain it.
Such outcomes must be coherent. Hence both internal pairs in every triple receive equal labels with probability one. For independent finite label distributions, this forces both distributions to concentrate on the same label: any unequal pair of supported labels would occur with positive probability.
Applying the argument to both internal pairs makes every row of the maximizing assignment pure and every triple coherent. Its labels therefore recover a maximum source cut.
Assessment: correct. This establishes hardness of producing the requested assignment, including when a solver is permitted to return fractional shares.
Under binary-rational parameter encoding, Section 1 supplies a pure certificate for every yes-instance. The certificate length \(O(\tau\log(K+1))\) is polynomial in the input length.
Exact evaluation involves polynomially many rational operations. Each coefficient uses a bounded number of input rational operations, and summing polynomially many such coefficients has polynomial bit complexity. Thus the membership claim is sound under the encoding clarification identified above.
The label bound \(K_0=\min\{K,\tau\}\) is valid because a pure assignment uses at most \(\tau\) labels and relabeling preserves its value. Enumerating \(K_0^\tau\) maps therefore includes a representative of an optimum. The stated runtime
\[
O\!\left(K_0^\tau\tau^2\operatorname{poly}(m,L)+\tau K\right),\qquad m=1,
\]
is a valid upper bound, with the final term accounting for dense output.
For \(K=1\), the assignment is indeed forced. Fixed \(m=1\) and \(K=2\) in the reduction rule out a general polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
The cited paper uses the modified utility and potential stated by the prover; its Theorem 2 claims global welfare optimality, while Theorem 3 expresses runtime through an expected iteration count. The attribution is accurate. See [Zhang et al.](https://ojs.aaai.org/index.php/AAAI/article/download/41312/45273).
The counterexample has four internal coefficients equal to \(2\) and one connecting coefficient equal to \(-1\). Its influence graph is strongly connected.
At the all-equal assignment, the six utilities are \(1,1,2,2,4,4\). Switching alone to the empty label gives utility \(0\), so every possible unilateral switch strictly lowers utility. The assignment is therefore a strict Nash equilibrium when both labels are available.
Its potential is \(7\), whereas separating the two intact triples gives \(8\). This correctly disproves the asserted implication from equilibrium to global welfare maximization.
Strict improvement moves terminate in a finite potential game because each move strictly increases the potential over a finite set of profiles. The prover correctly limits that statement to strict improvements.
Actionable feedback: state the binary-rational encoding assumption for susceptibilities before the general NP-membership claim. No mathematical repair is required, and no issue blocks the hardness conclusion.
⟨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.