Answer: \(\mathrm{NP}\)-complete, already for \(m=2\)
Theorem 9 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf ρ∗> f(1) g(1), the dynamics on G diverges if and only if G is well-partitioned.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite opinion set \(S\), \(\tau\) role types with positive rational masses \(\mu_r\), beliefs \(b_r\), rational role interaction matrix \(K\), costs \(f_r,g_r\), and pressure \(\rho\), decide whether there are masses \(y_{r,a}\ge 0\) with \(\sum_{a\in S}y_{r,a}=\mu_r\), positive total mass on at least two opinions, and every used opinion a best response. For each role \(r\), define \(C_r(a;y)=f_r(d(a,b_r))+\rho g_r(1)\sum_s K_{rs}\sum_{a'\ne a}y_{s,a'}\); require \(C_r(a;y)\le C_r(a';y)\) for every \(a'\in S\) whenever \(y_{r,a}>0\).
Let \(S\) be a common opinion set of size \(m\ge2\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_r\) a binary rational; \(\tau\) is the support size, not the number of possible types. Require \(\sum_r\mu_r=1\).
Each type has a belief \(b_r\in S\); define \(d(a,b)=0\) for equal opinions and \(d(a,b)=1\) otherwise. Costs satisfy \(f_r(0)=g_r(0)=0\), with binary rational values \(f_r(1)\ge0\) and \(g_r(1)>0\); only these endpoint values are needed.
The interaction matrix \(K\) is symmetric, nonnegative, and binary rational. Its graph on types, with edges between distinct types when \(K_{rs}>0\), is connected, and every row has positive sum. Diagonal entries describe interaction within a type and may be positive.
Pressure is a fixed binary rational \(\rho>\max_r f_r(1)/g_r(1)\). Let \(L\) be the total binary input length.
An allocation consists of real masses \(y_{r,a}\ge0\) with \(\sum_{a\in S}y_{r,a}=\mu_r\). Define \(C_r(a;y)=f_r(d(a,b_r))+\rho g_r(1)\sum_{s=1}^{\tau}K_{rs}\sum_{a'\in S\setminus\{a\}}y_{s,a'}\).
It is an equilibrium if \(y_{r,a}>0\) implies \(C_r(a;y)\le C_r(a';y)\) for every \(a'\in S\); ties are allowed. Individuals are nonatomic, so deviations leave aggregate masses fixed. It is nonconsensus if \(\sum_r y_{r,a}>0\) for at least two opinions.
Is deciding whether a nonconsensus equilibrium exists solvable in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Discrete: above pressure \(f(1)/g(1)\), a connected undirected graph admits some belief instance with a nonconsensus stationary profile exactly when it admits a partition into at least two nonempty classes where each vertex has at least as many neighbors in its own class as in any other. [Characterization](https://www.ijcai.org/proceedings/2017/0512.pdf).
Recognizing a connected graph admitting a nonconsensus stable binary majority configuration was subsequently proved \(\mathrm{NP}\)-complete. [Discrete complexity result](https://www.ijcai.org/proceedings/2018/0007.pdf).
No result settling this exact mass decision problem was located.
The decision problem is \(\mathrm{NP}\)-complete, already for \(m=2\)\), with all types having the same belief and with fixed pressure \(\rho=1\). Thus a polynomial-time algorithm in \(m,\tau,L\)\) exists only if \(\mathrm{P}=\mathrm{NP}\).
The proof is a direct reduction from \(\mathrm{CLIQUE}\). It handles fractional allocations explicitly, rather than transferring the [discrete stable-configuration result](https://www.ijcai.org/proceedings/2018/0007.pdf).
Take opinions \(S=\{A,B\}\)\), and suppose every type believes \(A\)\). Set \(\rho=g_r(1)=1\)\). Write
\(z_r=y_{r,A},\qquad y_{r,B}=\mu_r-z_r,\qquad w_r=\sum_s K_{rs}\mu_s.\)\)
Choose thresholds \(t_r\)\) and define \(f_r(1)=h_r=w_r-2t_r\)\), ensuring below that \(0\le h_r<1\)\). Then
\(C_r(A)=w_r-(Kz)_r,\qquad C_r(B)=h_r+(Kz)_r,\)\)
so
\(C_r(B)-C_r(A)=2((Kz)_r-t_r).\)\)
Consequently, the equilibrium conditions are exactly
\[z_r>0\Longrightarrow (Kz)_r\ge t_r,\qquad z_r<\mu_r\Longrightarrow (Kz)_r\le t_r.\tag{1}\]\)
In particular, a type using both opinions must satisfy \((Kz)_r=t_r\)\). These conditions include all ties.
Let \(G\)\) be a finite simple graph, with adjacency matrix \(M\)\) and clique number \(\omega\)\). For every probability vector \(x\)\),
\[x^{\mathsf T}Mx\le 1-\frac1\omega.\tag{2}\]\)
Here is a self-contained proof. If nonadjacent vertices \(i,j\)\) both have positive mass, hold the other coordinates fixed and put
\(c_i=\sum_{\ell\notin\{i,j\}}M_{i\ell}x_\ell,\qquad c_j=\sum_{\ell\notin\{i,j\}}M_{j\ell}x_\ell.\)\)
Because the graph has no loops and \(M_{ij}=0\)\), the objective has the form
\(x^{\mathsf T}Mx=\text{constant}+2x_ic_i+2x_jc_j.\)\)
Moving all of \(x_i+x_j\)\) to the coordinate with larger \(c\)\) does not decrease the objective and removes one vertex from its support. Repeating this operation produces a probability vector supported on a clique, of some size \(r\le\omega\)\). On that clique,
\(x^{\mathsf T}Mx=1-\sum_i x_i^2\le 1-\frac1r\le 1-\frac1\omega,\)\)
where the first inequality follows from \(\sum_i x_i^2\ge 1/r\)\). Since the operations never decreased the objective, this proves (2).
The standard \(\mathrm{NP}\)-complete problem \(\mathrm{CLIQUE}\) asks whether a simple graph \(G\)\), on \(n\)\) vertices, has a clique of size at least \(k\)\). We restrict to \(3\le k\le n\)\); omitted cases are polynomial-time decidable, so this restriction preserves hardness.
Let \(M\)\) be the adjacency matrix of \(G\)\). We construct one type for each vertex and two auxiliary types \(p,q\)\). Thus \(\tau=n+2\)\).
Let \(N\)\) be the smallest power of two satisfying \(N\ge n+2\)\), and set
\(u=\frac1N,\qquad \alpha=\frac14,\qquad \theta=\frac u4.\)\)
Assign masses
\(\mu_v=u\quad(v\in V(G)),\qquad \mu_q=u,\qquad \mu_p=1-(n+1)u.\)\)
They are positive, sum to one, and satisfy \(\mu_p\ge u\)\).
Choose a power of two \(D>k^2\)\), of magnitude polynomial in \(k\)\), and define
\(\beta=\frac{\left\lceil Dk/(k-1)\right\rceil}{D},\qquad B=\theta\beta.\)\)
The rounding error is smaller than \(1/D<1/k^2\)\). Since
\(\frac{k-1}{k-2}-\frac{k}{k-1}=\frac1{(k-1)(k-2)},\)\)
we obtain
\[\frac{k}{k-1}\le\beta<\frac{k-1}{k-2}\le2,\qquad 0<B<\frac u2.\tag{3}\]\)
Define the symmetric interaction matrix by
\(K_{vw}=\alpha M_{vw},\qquad K_{qv}=K_{vq}=\alpha,\qquad K_{pq}=K_{qp}=\alpha,\qquad K_{pp}=\alpha,\)\)
with every remaining entry zero. Its graph is connected because \(q\)\) is adjacent to every other type. Every row has positive sum.
Set thresholds
\(t_p=0,\qquad t_q=\alpha B,\qquad t_v=\alpha\theta\quad(v\in V(G)).\)\)
Every type believes \(A\)\). Set \(\rho=g_r(1)=1\)\) and \(f_r(1)=h_r=w_r-2t_r\)\), as in Section 1.
We verify the cost restrictions. For a vertex type,
\(h_v=\alpha u\left(\deg_G(v)+\frac12\right)>0.\)\)
For the auxiliary types,
\(h_q=\alpha(1-u-2B)>0,\qquad h_p=\alpha(\mu_p+u)>0.\)\)
The positivity of \(h_q\)\) follows from \(2B<u\)\) and \(u\le1/8\)\). Moreover, every entry of \(K\)\) is at most \(\alpha\)\), so
\(h_r\le w_r=\sum_sK_{rs}\mu_s\le\alpha=\frac14<1.\)\)
Thus all costs are nonnegative, and the strict pressure condition holds:
\(\rho=1>\max_r f_r(1)/g_r(1).\)\)
All constructed numbers are dyadic rationals with polynomial binary encoding length. The construction therefore has polynomial input length and takes polynomial time.
We now prove that every nonconsensus equilibrium has \(z_p=z_q=0\)\).
First, if \(z_p>0\)\), then
\((Kz)_p=\alpha(z_p+z_q)>0=t_p.\)\)
By (1), this forces \(z_p=\mu_p\)\). Consequently,
\((Kz)_q=\alpha\left(\mu_p+\sum_vz_v\right)\ge\alpha u>\alpha B=t_q,\)\)
so \(z_q=\mu_q=u\)\). Every vertex type then satisfies
\((Kz)_v=\alpha\left((Mz_V)_v+u\right)\ge\alpha u>\alpha\theta=t_v,\)\)
forcing \(z_v=\mu_v\)\). The allocation is therefore consensus on \(A\)\).
Second, if \(z_p=0\)\), its positive mass on \(B\)\) requires
\((Kz)_p=\alpha z_q\le t_p=0,\)\)
hence \(z_q=0\)\).
Thus any nonconsensus equilibrium has \(z_p=z_q=0\)\), and its vertex vector \(z_V\)\) has positive total
\(T=\sum_vz_v>0.\)\)
Type \(q\)\), which uses only \(B\)\), imposes
\(\alpha T=(Kz)_q\le t_q=\alpha B,\)\)
so \(T\le B<u\)\). Hence every vertex has \(z_v<\mu_v=u\)\). Applying (1) gives
\((Mz_V)_v\le\theta,\qquad z_v>0\Longrightarrow(Mz_V)_v=\theta.\)\)
Conversely, any vector satisfying
\[z_V\ge0,\qquad 0<T=\sum_vz_v\le B,\qquad Mz_V\le\theta\mathbf1,\qquad z_v>0\Longrightarrow(Mz_V)_v=\theta\tag{4}\]\)
extends, by setting \(z_p=z_q=0\)\), to a nonconsensus equilibrium. Indeed, (1) holds at every vertex, at \(q\)\) by \(T\le B\)\), and at \(p\)\) with equality. There is positive mass on \(A\)\) because \(T>0\)\), and positive mass on \(B\)\) at both auxiliary types.
Therefore (4) exactly characterizes nonconsensus equilibria of the constructed instance.
Suppose a nonconsensus equilibrium exists. By (4),
\(z_V^{\mathsf T}Mz_V=\sum_vz_v(Mz_V)_v=\theta T.\)\)
Normalize \(x=z_V/T\)\). Then \(x\)\) is a probability vector, and
\(x^{\mathsf T}Mx=\frac{\theta}{T}\ge\frac{\theta}{B}=\frac1\beta.\)\)
If \(\omega(G)\le k-1\)\), the bound (2) and the strict inequality in (3) give
\(x^{\mathsf T}Mx\le1-\frac1{\omega(G)}\le\frac{k-2}{k-1}<\frac1\beta,\)\)
a contradiction. Thus \(G\)\) has a clique of size at least \(k\)\).
Suppose \(G\)\) has a maximum clique \(Q\)\) of size \(\omega\ge k\)\). Define
\(z_v=\frac{\theta}{\omega-1}\quad(v\in Q),\qquad z_v=0\quad(v\notin Q).\)\)
For \(v\in Q\)\), we have \((Mz_V)_v=\theta\)\). Every vertex outside \(Q\)\) has at most \(\omega-1\)\) neighbors in \(Q\)\); otherwise it would extend \(Q\)\) to a larger clique. Thus \((Mz_V)_v\le\theta\)\) outside \(Q\)\).
Finally,
\(0<T=\theta\frac{\omega}{\omega-1}\le\theta\frac{k}{k-1}\le\theta\beta=B.\)\)
All conditions in (4) hold, producing a nonconsensus equilibrium.
This proves the required polynomial-time reduction and establishes \(\mathrm{NP}\)-hardness.
For any other prescribed positive rational pressure \(\rho\)\), replace \(f_r(1)\)\) by \(\rho h_r\)\), retaining \(g_r(1)=1\)\). The cost comparisons scale by \(\rho\)\), and \(\rho>\rho h_r\)\), so the same proof applies.
Consider an arbitrary instance. Define rational normalized utilities
\(U_{r,a}(y)=\sum_sK_{rs}y_{s,a}+\frac{f_r(1)}{\rho g_r(1)}\mathbf1_{\{a=b_r\}}.\)\)
For a fixed type, minimizing costs is equivalent to maximizing these utilities.
Suppose a nonconsensus equilibrium exists, and let \(T_r=\{a:y_{r,a}>0\}\)\) be its support at type \(r\)\). Consider the rational linear program with variables \(y,\delta\)\), maximizing \(\delta\)\), subject to
The given equilibrium makes \(\delta>0\)\) feasible. The feasible region is bounded, and its rational coefficients have polynomial encoding length. An optimal vertex therefore has polynomial encoding length: choose independent tight constraints defining that vertex, clear denominators, and apply Cramer’s rule and determinant bounds.
This yields a polynomial-length rational equilibrium certificate. Its positive support includes at least two opinions, since \(\bigcup_rT_r\)\) does. Exact rational arithmetic verifies the allocation constraints, nonconsensus, and every required cost comparison in polynomial time.
Hence the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The argument establishes \(\mathrm{NP}\)-completeness for the stated continuous mass problem. The reduction satisfies the input restrictions, explicitly excludes unintended fractional equilibria, and proves both directions of the equivalence. The certificate argument also holds. I found no substantive mathematical gaps.
With every belief equal to \(A\), and with \(\rho=g_r(1)=1\), the stated costs are correct:
\[ C_r(A)=w_r-(Kz)_r,\qquad C_r(B)=h_r+(Kz)_r. \]
Substituting \(h_r=w_r-2t_r\) gives the claimed difference. Consequently:
These implications are also sufficient. Thus (1) correctly handles pure allocations, fractional allocations, and ties. It uses the stipulated nonatomic interpretation.
The proof of (2) is valid.
For nonadjacent positive coordinates \(i,j\), the absence of loops and of an edge between them eliminates quadratic terms involving only these coordinates. Holding their sum fixed therefore makes the objective linear in their redistribution. Moving their combined mass to the coordinate with the larger coefficient cannot decrease the objective.
Each operation strictly reduces the support size. The process terminates with support forming a clique. For a resulting support of size \(r\), the objective equals \(1-\sum_i x_i^2\), and the stated bound \(\sum_i x_i^2\ge 1/r\) applies.
Because the objective never decreases during these operations, the resulting upper bound also bounds the original vector. The inequality direction is correct.
The reduction applies this lemma to graphs with \(n\ge3\), so the clique number is positive and division by it is defined.
Restricting \(\mathrm{CLIQUE}\) to \(3\le k\le n\) preserves its standard \(\mathrm{NP}\)-hardness. Instances outside this range are decidable directly and can be mapped to fixed restricted yes-instances or no-instances. No substantive reduction gap arises from omitting those cases.
The mass assignments satisfy every support requirement:
\[ \sum_r\mu_r=nu+u+1-(n+1)u=1. \]
Since \(N\ge n+2\),
\[ \mu_p=\frac{N-n-1}{N}\ge\frac1N=u>0. \]
All vertex masses and \(\mu_q\) are also positive. Thus the support size is exactly \(n+2\).
Because \(n\ge3\), the smallest qualifying power of two satisfies \(N\ge8\), justifying \(u\le1/8\).
The ceiling definition gives
\[ 0\le\beta-\frac{k}{k-1}<\frac1D<\frac1{k^2}. \]
For \(k\ge3\),
\[ \frac1{k^2}<\frac1{(k-1)(k-2)}. \]
Together with the displayed difference between the two target fractions, this proves the strict upper bound on \(\beta\). In particular, \(\beta<2\), so \(B<u/2\).
The strict inequality required later in the soundness argument is therefore justified, including when the ceiling introduces no rounding error.
The specified matrix is symmetric and nonnegative. Type \(q\) is adjacent to every vertex type and to \(p\), so the graph on distinct types is connected. Every row has a positive entry.
The diagonal entry at \(p\) is permitted by the task and is used explicitly in the equilibrium analysis.
The endpoint calculations are correct:
\[ h_v=\alpha u\left(\deg_G(v)+\frac12\right), \]
\[ h_q=\alpha(1-u-2B),\qquad h_p=\alpha(\mu_p+u). \]
All are positive. For \(h_q\), the stated inequalities give
\[ 1-u-2B>1-2u>0. \]
Since all thresholds are nonnegative and every matrix entry is at most \(\alpha\),
\[ h_r\le w_r\le\alpha\sum_s\mu_s=\alpha=\frac14. \]
Thus \(f_r(1)\ge0\), \(g_r(1)=1>0\), and the strict pressure condition holds.
The numbers in the reduction are dyadic rationals of polynomial encoding length. Suitable powers \(N\) and \(D\) have polynomial magnitude, and the ceiling defining \(\beta\) is computable using integer arithmetic.
There are \(n+2\) types and quadratically many matrix entries. The construction is polynomial in the source input size.
This is the critical step excluding spurious fractional solutions, and it is correct.
If \(z_p>0\), then \((Kz)_p>t_p\). Condition (1) consequently prevents \(z_p<\mu_p\), forcing \(z_p=\mu_p\).
The inequalities \(\mu_p\ge u>B\) then force \(z_q=\mu_q\). With \(z_q=u>\theta\), every vertex type is forced to use only \(A\). Thus any equilibrium with \(z_p>0\) is consensus on \(A\).
If \(z_p=0\), type \(p\) has positive mass on \(B\). Its equilibrium inequality gives \(\alpha z_q\le0\), hence \(z_q=0\).
Therefore every nonconsensus equilibrium has \(z_p=z_q=0\). Its vertex total \(T\) must be positive; otherwise the allocation would be consensus on \(B\).
Type \(q\)'s inequality yields \(T\le B<u\). Since \(0\le z_v\le T\), every vertex has \(z_v<\mu_v\). Condition (1) then yields precisely the inequalities and support equalities in (4).
The converse is also verified correctly. A vector satisfying (4) automatically satisfies \(z_v<u\), extends to valid type masses, and satisfies the equilibrium conditions at all types. Positive \(T\) supplies opinion \(A\), while the auxiliary types supply opinion \(B\).
Thus (4) is an exact characterization, not merely a necessary condition.
The support equalities in (4) justify
\[ z_V^{\mathsf T}Mz_V=\theta T. \]
Zero coordinates contribute nothing, so no equality is needed outside the positive support.
Normalization is legitimate because \(T>0\). It gives
\[ x^{\mathsf T}Mx=\frac{\theta}{T}\ge\frac1\beta. \]
If the clique number is at most \(k-1\), the quadratic-form bound gives an upper bound of \((k-2)/(k-1)\). The strict rounding bound implies
\[ \frac{k-2}{k-1}<\frac1\beta. \]
This is a contradiction. Soundness is established.
The use of a maximum clique is sufficient and correctly stated. An outside vertex adjacent to every clique vertex would produce a larger clique; therefore every outside vertex has at most \(\omega-1\) neighbors in the clique.
The proposed vector consequently satisfies equality on its positive support and the required inequality elsewhere.
Its total mass satisfies
\[ T=\theta\frac{\omega}{\omega-1} \le\theta\frac{k}{k-1} \le B. \]
The denominator is positive because \(\omega\ge k\ge3\). All conditions in (4) hold.
Choosing a maximum clique here is an existential construction for completeness; the reduction itself does not need to compute one.
Both directions establish the claimed polynomial reduction and \(\mathrm{NP}\)-hardness.
The subsequent extension to any prescribed positive rational pressure also checks out: scaling \(f_r(1)\) by \(\rho\) scales the cost differences by \(\rho\), and \(h_r<1\) preserves the strict pressure inequality.
The normalized utilities correctly represent cost minimization. For a fixed type, the opinion-independent part of its cost can be removed, and division by \(\rho g_r(1)>0\) preserves comparisons.
For the support sets taken from an existing equilibrium:
The feasible region is bounded: allocation coordinates are bounded by their type masses, and \(\delta\) is bounded by the supported coordinates. It is also closed and nonempty, so the maximum is attained. Its optimum is positive.
The polynomial bit-length argument for an optimal vertex is valid. The numbers of variables and constraints are polynomial in \(m,\tau,L\), and all coefficients have polynomial bit length. Selecting independent tight constraints and applying determinant bounds yields polynomial-size rational coordinates.
Positive optimal \(\delta\) preserves every chosen support coordinate. Hence the certificate retains at least two opinions and satisfies all equilibrium comparisons.
Exact rational verification takes polynomial time. Membership in \(\mathrm{NP}\) follows.
The proof resolves the assigned continuous decision problem. Its hardness argument does not rely on importing the discrete result, and its treatment of fractional allocations is complete. No additional mathematical clarification or repair is required.
⟨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.