Answer: Polynomial-time solvable. Every admissible input has unique consensus, with limiting profile \((q,\ldots,q)\), where \(q=\theta+\varepsilon(1-\theta)\).
Theorem 4.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe graph-based Bayesian learning system has a globally unique, stable fixed point X∗. This fixed point is a consensus state, i.e., x∗ 1 = x∗ 2 = · · · = x∗ N = x∗.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a nonatomic community with finite type support \(T\), rational masses \(\mu_t>0\), common \(\theta\) and \(\varepsilon\), initial beliefs by type, and a primitive type-level influence matrix compatible with \(\mu\), does the induced Tabu/Tagg process converge to a unique consensus, and what is the limiting belief profile?
A nonatomic society is given by its support \(T\): the list of its \(\tau\) positive-mass types, with binary rational masses \(\mu_t>0\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(m=2\) is the signal alphabet size, and \(L\) is the total input bit length.
Inputs include binary rationals \(0\leq\theta<1\), \(0<\varepsilon\leq1\), initial Beta parameters \(\alpha_t(0),\beta_t(0)>0\), and a nonnegative rational matrix \(W\). Require \(\tau\geq2\), \(W\mathbf1=\mathbf1\), \(\mu^{\mathsf T}W=\mu^{\mathsf T}\), primitivity, and \(W_{tt}<1\) for every type.
A true failure has probability \(\theta\); failures are always reported accurately, while successes are reported as failures with probability \(\varepsilon\). Write \(q=\theta+\varepsilon(1-\theta)\).
Use unbiased attention and deterministic mass updates: at each integer time \(k\geq0\), \(T_{\mathrm{abu}}\) gives \(\alpha'_t=\alpha_t(k)+q\), \(\beta'_t=\beta_t(k)+1-q\); then \(T_{\mathrm{agg}}\) gives \(\alpha_t(k+1)=\sum_uW_{tu}\alpha'_u\), \(\beta_t(k+1)=\sum_uW_{tu}\beta'_u\).
The belief profile is \(x_t(k)=\alpha_t(k)/(\alpha_t(k)+\beta_t(k))\). Unique consensus means that all coordinates converge to one common value determined by \((\theta,\varepsilon,W,\mu)\), independently of the positive initial Beta parameters.
Is deciding whether this process has a unique consensus, and computing its limiting belief profile when it does, polynomial-time solvable in \(m,\tau,L\), or NP-hard?
For finite agents, the Distrust Fixed-Point Theorem asserts a unique stable consensus of expected beliefs at \(\theta+\varepsilon(1-\theta)\). [Published result](https://ojs.aaai.org/index.php/AAAI/article/download/41318/45279).
No result settling exactly the mass dynamics specified above was located in the literature search.
Result
The problem is polynomial-time solvable. Every input satisfying the stated hypotheses has unique consensus, with limiting profile \((q,\ldots,q)\), where \(q=\theta+\varepsilon(1-\theta)\).
The proof below uses only nonnegativity and row stochasticity of \(W\). Thus the additional assumptions concerning stationarity, primitivity, and diagonal entries are compatible with the result but unnecessary for this conclusion.
Exact evolution of the masses
Write \(\alpha(k)\) and \(\beta(k)\) for the column vectors of Beta parameters, and let \(\mathbf 1\) be the all-ones vector. The specified update gives
\(\alpha(k+1)=W\alpha(k)+qW\mathbf 1=W\alpha(k)+q\mathbf 1\),
\(\beta(k+1)=W\beta(k)+(1-q)W\mathbf 1=W\beta(k)+(1-q)\mathbf 1\).
Here the second equality in each line uses \(W\mathbf 1=\mathbf 1\). Consequently, for every integer \(k\geq0\),
\(\alpha(k)=W^k\alpha(0)+kq\mathbf 1,\qquad \beta(k)=W^k\beta(0)+k(1-q)\mathbf 1.\)
To verify these formulas, they hold at \(k=0\), with \(W^0=I\). If they hold at \(k\), substituting into the recurrence and using \(W\mathbf 1=\mathbf 1\) proves them at \(k+1\).
Set \(s(0)=\alpha(0)+\beta(0)\). Adding the two formulas yields
\(\alpha(k)+\beta(k)=W^ks(0)+k\mathbf 1.\)
A uniform convergence bound
Every power \(W^k\) is nonnegative and row stochastic. Indeed, this holds for \(W^0=I\), and multiplication by \(W\) preserves nonnegativity and gives \(W^{k+1}\mathbf 1=W^k\mathbf 1=\mathbf 1\).
Therefore each coordinate of \(W^kv\), for any real vector \(v\), is a convex combination of the coordinates of \(v\). In particular,
\(\left|(W^kv)_t\right|\leq\max_u|v_u|.\)
Define the finite constants
\(s_{\min}=\min_t s_t(0)>0,\qquad C=\max_t|\alpha_t(0)-qs_t(0)|.\)
The same convex-combination property gives \((W^ks(0))_t\geq s_{\min}\), so every belief denominator is strictly positive. Using the exact evolution,
\(x_t(k)-q=\dfrac{(W^k\alpha(0))_t+kq-q\bigl((W^ks(0))_t+k\bigr)}{(W^ks(0))_t+k}=\dfrac{(W^k(\alpha(0)-qs(0)))_t}{(W^ks(0))_t+k}.\)
It follows that
\(\max_t|x_t(k)-q|\leq\dfrac{C}{k+s_{\min}}\longrightarrow0.\)
Thus all coordinates converge to \(q\), for every choice of positive initial Beta parameters. The limiting profile is independent of those parameters. Moreover, any proposed common limiting value must equal \(q\), because each coordinate has just been proved to converge to \(q\). This establishes unique consensus in the precise sense requested.
The endpoint \(\varepsilon=1\), for which \(q=1\), is included: the denominator still grows by one per step, and the same bound applies.
Exact computation and bit complexity
On the promised input class, the decision algorithm always answers “yes.” To compute the limiting profile, calculate \(q\) exactly and output \(\tau\) copies.
For an explicit rational calculation, write \(\theta=a/b\) and \(\varepsilon=c/d\), with positive denominators. Then
\(q=\dfrac{ad+c(b-a)}{bd}.\)
The numerator and denominator have bit lengths bounded by \(O(L)\): their construction uses a constant number of additions, subtractions, and multiplications of integers whose bit lengths are bounded by the input length. These operations, and an optional greatest-common-divisor reduction, take polynomial time in \(L\).
Writing the explicit profile takes \(O(\tau L)\) bits. Hence both deciding unique consensus and computing its exact limiting profile take time polynomial in \(m,\tau,L\), with \(m=2\). No simulation or finite-agent theorem is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: every admissible input has unique consensus, and the exact limiting profile is computable in polynomial time. No mathematical gaps or false steps were found.
\[
\alpha(k)=W^k\alpha(0)+kq\mathbf 1,\qquad
\beta(k)=W^k\beta(0)+k(1-q)\mathbf 1
\]
are correct. The prover checks the base case \(k=0\) and supplies the induction step using \(W\mathbf 1=\mathbf 1\). Adding them correctly gives
\[
\alpha(k)+\beta(k)=W^ks(0)+k\mathbf 1.
\]
\[
|(W^kv)_t|\leq\max_u|v_u|,
\qquad
(W^ks(0))_t\geq s_{\min}>0.
\]
The second bound ensures that every belief denominator is positive, including at \(k=0\). These conclusions require no convergence theorem for \(W^k\).
\[
(W^k(\alpha(0)-qs(0)))_t.
\]
Its absolute value is bounded by \(C\), while the denominator is at least \(k+s_{\min}\). Thus
\[
\max_t|x_t(k)-q|\leq\frac{C}{k+s_{\min}}
\]
holds for every integer \(k\geq0\). For every fixed positive initialization, \(C\) is finite and \(s_{\min}>0\), so the bound tends to zero.
\[
q=\frac{ad+c(b-a)}{bd}
\]
is algebraically correct. A constant number of integer additions, subtractions, and multiplications produces a numerator and denominator of bit length \(O(L)\). Exact arithmetic and optional greatest-common-divisor reduction take polynomial time in \(L\).
No additional 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.