Answer: Polynomial-time solvable under the permitted succinct representation.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any instance (G(V, E), ~x(0)) and any round t ≥1, the opinions maintained by LIP-FJ satisfy kE[~x(t)] −~x⇤k1 e−(1−⌫(A)) Pt q=1(1−λ(q))k~x(0) −~x⇤k1 where ~x⇤is the stable state of the FJ model.
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\) with \(\sum_{t\in T}\mu_t=1\), initial opinions \(q_t\in[0,1]\), and a rational matrix \(A\) with \(A_{tu}\ge 0\), \(\sum_u A_{tu}=1-\beta_t\) for \(\beta_t>0\), and \(\mu_t A_{tu}=\mu_u A_{ut}\), consider a nonatomic population in which every type-\(t\) member uses these shared parameters. In round \(r\), a member samples a current opinion from type \(u\) with probability \(A_{tu}\), or uses \(q_t\) with probability \(\beta_t\), then updates using \(\lambda(r)=r/(r+1)\). Given \(\epsilon>0\), find an explicit round bound \(R(\epsilon)\) guaranteeing that the vector of expected typewise opinion means is within \(\epsilon\) in \(\ell_\infty\) distance of the unique type-level FJ fixed point \(\mathbf{x}^*=A\mathbf{x}^*+\boldsymbol{\beta}\odot\mathbf{q}\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Opinions are scalar, so \(m=1\). Let \(L\) be the total binary input length.
Each type has a rational initial opinion \(q_t\in[0,1]\). The rational matrix \(A\) satisfies \(A_{tu}\ge0\), \(\sum_u A_{tu}=1-\beta_t\), \(\beta_t\in(0,1]\), and \(\mu_tA_{tu}=\mu_uA_{ut}\). Same-type sampling is permitted.
Initially every type-\(t\) member has opinion \(q_t\). In each synchronous round \(r\ge1\), a member samples type \(u\) with probability \(A_{tu}\) and then samples an opinion from that type's preceding-round distribution, independently of her own history; with probability \(\beta_t\), the sampled value is \(q_t\).
Writing this sampled value as \(S\), her update is \(X(r)=\frac{r}{r+1}X(r-1)+\frac{1}{r+1}S\). Let \(y_t(r)\) be the expected opinion of a uniformly sampled type-\(t\) member, and let \(\mathbf{x}^*\) be the unique FJ fixed point satisfying \(x_t^*=\sum_u A_{tu}x_u^*+\beta_tq_t\).
Given rational \(\epsilon>0\), the computational problem is to produce an explicit integer bound \(R(\epsilon)\ge0\) such that \(\|\mathbf{y}(r)-\mathbf{x}^*\|_\infty\le\epsilon\) for every integer \(r\ge R(\epsilon)\). Bounds may be represented succinctly by finite expressions using binary rationals, arithmetic, rational powers, and ceilings; minimality is not required.
Is computing such an explicit round bound polynomial-time in \(m,\tau,L\), or is this computational problem NP-hard?
For finite societies with symmetric interaction weights and positive anchoring weights, a quantitative convergence-in-expectation bound is known; the specified averaging schedule gives an upper round bound exponential in the inverse minimum anchoring weight. [Fotakis, Palyvos-Giannas, and Skoulakis](https://www.ijcai.org/Proceedings/16/Papers/047.pdf).
Later work analyzes different limited-information update rules and the expectation of the opinion error norm, rather than the norm of expected opinions. No result explicitly treating the nonatomic problem specified here was identified. [Opinion Dynamics with Limited Information](https://link.springer.com/article/10.1007/s00453-023-01157-5).
Computing a valid round bound is polynomial-time under the permitted succinct representation. Let \(b=\min_{t\in T}\beta_t\). One valid output is
\(R(\epsilon)=\begin{cases}0,&\epsilon\ge 1,\\[2pt]\left\lceil 2\epsilon^{-1/b}\right\rceil-2,&0<\epsilon<1.\end{cases}\)
The numerical value of this bound can be enormous, but its expression has polynomial encoding length. The proof below does not require detailed balance or computation of the fixed point.
Write \(\mathbf q=(q_t)_{t\in T}\), \(B=\operatorname{diag}(\beta_t)\), and define \(\|\mathbf v\|_\infty=\max_{t\in T}|v_t|\). Because the support is finite and every anchoring weight is positive, \(0<b\le 1\).
Every individual opinion remains in \([0,1]\): initially this holds by assumption, and each subsequent sampled value and update is a convex combination of values in this interval. Thus all expectations are well-defined.
For every vector \(\mathbf v\), nonnegativity and the row-sum assumptions give
\(\displaystyle |(A\mathbf v)_t|\le\sum_u A_{tu}|v_u|\le(1-\beta_t)\|\mathbf v\|_\infty\le(1-b)\|\mathbf v\|_\infty.\)
Consequently, the induced matrix norm satisfies \(\|A\|_\infty\le 1-b<1\). The series
\(\displaystyle \mathbf x^*=\sum_{k=0}^{\infty}A^kB\mathbf q\)
therefore converges and satisfies \(\mathbf x^*=A\mathbf x^*+B\mathbf q\). If two vectors satisfy this equation, their difference \(\mathbf d\) satisfies \(\|\mathbf d\|_\infty\le(1-b)\|\mathbf d\|_\infty\), forcing \(\mathbf d=\mathbf 0\). Hence the fixed point is unique.
Moreover, \(F(\mathbf z)=A\mathbf z+B\mathbf q\) maps \([0,1]^\tau\) into itself: each coordinate is nonnegative and at most \((1-\beta_t)+\beta_t=1\). Its iterates from \(\mathbf 0\) are the partial sums of the displayed series. Their limit therefore belongs to \([0,1]^\tau\), giving
\(\|\mathbf q-\mathbf x^*\|_\infty\le 1.\)
For a type-\(t\) member, let \(S_t(r)\) denote her sampled value in round \(r\). By the specified sampling rule,
\(\displaystyle \mathbb E[S_t(r)]=\sum_u A_{tu}y_u(r-1)+\beta_tq_t.\)
This includes the term with \(u=t\); same-type sampling causes no exception. Taking expectations in the update yields
\(\displaystyle \mathbf y(r)=\frac{rI+A}{r+1}\mathbf y(r-1)+\frac{B\mathbf q}{r+1},\qquad \mathbf y(0)=\mathbf q.\)
Define \(\mathbf e(r)=\mathbf y(r)-\mathbf x^*\). Subtracting the fixed-point equation gives
\(\displaystyle \mathbf e(r)=\frac{rI+A}{r+1}\mathbf e(r-1).\)
The matrix \((rI+A)/(r+1)\) is nonnegative, and its type-\(t\) row sum is
\(\displaystyle \frac{r+1-\beta_t}{r+1}=1-\frac{\beta_t}{r+1}\le 1-\frac{b}{r+1}.\)
Applying the same row-sum norm inequality as above and iterating, we obtain
\(\displaystyle \|\mathbf e(r)\|_\infty\le\prod_{k=1}^{r}\left(1-\frac{b}{k+1}\right)\|\mathbf e(0)\|_\infty\le\prod_{k=1}^{r}\left(1-\frac{b}{k+1}\right).\)
The corresponding finite-agent expectation recurrence appears in Section 3 of [Fotakis, Palyvos-Giannas, and Skoulakis](https://www.ijcai.org/Proceedings/16/Papers/047.pdf). Here it follows directly from the specified type-distribution sampling rule.
For \(0\le z<1\), the elementary inequality \(\log(1-z)\le-z\) follows from \(\log(1-z)=-\int_0^z(1-u)^{-1}\,du\). Therefore, for \(r\ge1\),
\(\displaystyle \prod_{k=1}^{r}\left(1-\frac{b}{k+1}\right)\le\exp\left(-b\sum_{k=1}^{r}\frac1{k+1}\right).\)
Since the function \(x\mapsto 1/x\) decreases on the positive real numbers,
\(\displaystyle \sum_{k=1}^{r}\frac1{k+1}=\sum_{j=2}^{r+1}\frac1j\ge\int_2^{r+2}\frac{dx}{x}=\log\frac{r+2}{2}.\)
Combining these inequalities proves
\(\displaystyle \|\mathbf y(r)-\mathbf x^*\|_\infty\le\left(\frac{2}{r+2}\right)^b.\)
This also holds at \(r=0\), because its right-hand side is \(1\).
If \(\epsilon\ge1\), boundedness immediately makes \(R(\epsilon)=0\) valid. Otherwise, \(2\epsilon^{-1/b}>2\), so the proposed \(R(\epsilon)\) is a nonnegative integer. For every integer \(r\ge R(\epsilon)\),
\(\displaystyle r+2\ge\left\lceil2\epsilon^{-1/b}\right\rceil\ge2\epsilon^{-1/b},\)
and hence
\(\displaystyle \|\mathbf y(r)-\mathbf x^*\|_\infty\le\left(\frac2{r+2}\right)^b\le\epsilon.\)
This proves the required guarantee for every subsequent round.
The algorithm performs only the following operations:
Exact rational sums, comparisons, and reciprocals take polynomial time in the total binary input length \(L\). Their intermediate encoding lengths are polynomial: a common denominator for any row sum can be chosen as the product of that row’s input denominators, whose binary length is bounded by their total encoding length.
The output contains only polynomial-length rational constants, one rational-power operation, one ceiling, and arithmetic. The algorithm outputs this expression without evaluating or expanding the resulting integer. That is precisely the succinct representation permitted in the question.
Thus the stated computational problem is polynomial-time solvable in \(\tau\) and \(L\), with \(m=1\). A large numerical round bound does not imply hardness of producing its succinct expression.
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the task. The round bound is valid for every subsequent round, and its permitted succinct expression can be produced in polynomial time. No major or minor mathematical issues were found.
The definition \(b=\min_{t\in T}\beta_t\) is valid because the support is finite and nonempty. Positivity of every anchoring weight gives \(0<b\le1\). The proof uses the stated hypotheses without introducing additional assumptions.
The boundedness argument is correct: a sampled value belongs to \([0,1]\), either because it is an initial opinion or because its distribution comes from the preceding round. The update coefficients are nonnegative and sum to \(1\), so induction preserves \([0,1]\). All expectations therefore exist.
The displayed row-sum estimate correctly establishes \(\|A\|_\infty\le1-b<1\). Consequently, the matrix series defining \(\mathbf{x}^*\) converges. Substitution into the fixed-point equation is justified by this convergence.
The uniqueness argument is valid, including the endpoint \(b=1\): the inequality \(\|\mathbf d\|_\infty\le(1-b)\|\mathbf d\|_\infty\) forces \(\mathbf d=\mathbf0\).
The map \(F\) preserves \([0,1]^\tau\), as each coordinate is nonnegative and bounded above by the sum of its interaction and anchoring weights. Its iterates from \(\mathbf0\) are indeed partial sums of the displayed series. Their limit belongs to the closed cube, establishing \(\|\mathbf q-\mathbf{x}^*\|_\infty\le1\).
The sampling rule directly gives the claimed formula for \(\mathbb E[S_t(r)]\). Same-type sampling contributes the ordinary term \(A_{tt}y_t(r-1)\); it requires no exception.
Linearity of expectation gives the stated vector recurrence. Subtracting the fixed-point equation cancels the constant term correctly and yields
\(\mathbf e(r)=(rI+A)\mathbf e(r-1)/(r+1)\).
The cited finite-agent analogue does appear in Section 3 of [Fotakis, Palyvos-Giannas, and Skoulakis](https://www.ijcai.org/Proceedings/16/Papers/047.pdf). The prover derives the recurrence directly for the specified model, so no external theorem or transfer of finite-agent hypotheses is needed.
The matrix \((rI+A)/(r+1)\) is nonnegative. Its row sum is exactly \(1-\beta_t/(r+1)\), so its induced infinity norm is at most \(1-b/(r+1)\).
Iterating this inequality gives the claimed product bound. The initial-error factor is at most \(1\) by the already established fixed-point range. All factors are positive for the stated range \(r\ge1\).
The logarithmic inequality is applied within its domain: \(0<b/(k+1)\le1/2<1\).
The harmonic-sum comparison has the correct direction and endpoints. Since \(1/x\) decreases, the integral over each interval from \(j\) to \(j+1\) is at most \(1/j\). Thus the displayed comparison with the integral from \(2\) to \(r+2\) is valid.
Combining the estimates gives exactly
\(\|\mathbf y(r)-\mathbf{x}^*\|_\infty\le(2/(r+2))^b\).
At \(r=0\), the right-hand side is \(1\), so the separately stated base-case check is correct.
For \(\epsilon\ge1\), boundedness validates \(R(\epsilon)=0\), including equality at \(\epsilon=1\).
For \(0<\epsilon<1\), positivity of \(b\) gives \(2\epsilon^{-1/b}>2\). Hence the proposed ceiling expression minus \(2\) is a nonnegative integer. For every integer \(r\ge R(\epsilon)\), the displayed threshold inequality holds, and raising the positive reciprocal bound to the positive power \(b\) gives the required error at most \(\epsilon\).
This establishes the requested guarantee for all subsequent rounds, rather than only at the threshold.
Recovering the anchoring weights from row sums, finding their minimum, comparing \(\epsilon\) with \(1\), and constructing the output expression all require polynomial time in the binary input length.
The denominator-length justification is valid: the binary length of a product of input denominators is bounded by their summed binary lengths. Numerators and reciprocals likewise have polynomial encoding length.
The output uses precisely the permitted operations, including one rational power and one ceiling. The algorithm constructs the expression without evaluating its potentially enormous integer value. Therefore its running time and output length are polynomial under the task’s specified representation.
No repair or additional clarification is needed. The unused detailed-balance and mass assumptions do not create a gap; the argument proves the required guarantee under weaker hypotheses.
⟨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.