Answer: \(F\) exists for every input and is exactly computable in polynomial time; \(P_N(c)=F\) for every admissible \(N\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet {Rt}t≥m+1 be a memory consensus pro- cess (p0, . . . , pm) on a (strongly connected) graph G with initial states Ri = si, for i = 0, . . . , m. Let µ be the sta- tionary distribution of G. Then for any colour c ∈X, the winning probability is given by P(c wins|R0 = s0, . . . , Rm = sm) = = m X i=0 1 −p0 −· · · −pi−1 σ X sm−i(vj)=c µ(vj) where σ = p0 + 2p1 + 3p2 + · · · + (n + 1)pn.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite role set \(R\), colour set \(C\), irreducible rational row-stochastic matrix \(Q\), memory probabilities \(p_0,\ldots,p_m\), target colour \(c\), and rational society distribution \(\mu\) over types \((r,h)\in R\times C^{m+1}\), compute \(\lim_{N\to\infty}\Pr_N(c\text{ reaches stable consensus})\). For each valid \(N\), instantiate \(N\mu_{r,h}\) agents of each type; each role-\(r\) agent selects role \(s\) according to \(Q_{rs}\), then samples an agent uniformly from that role, and follows the stated memory protocol.
Let \(R,C\) be nonempty finite sets, \(c\in C\), \(m\geq1\), and \(Q\) an irreducible rational row-stochastic matrix indexed by \(R\). Let \(p_0,\ldots,p_m\) be positive binary rationals summing to \(1\).
A society is given by its support: the list of the \(\tau\) types \((r,h)\in R\times C^{m+1}\) with positive mass, each mass \(\mu_{r,h}\) a binary rational; masses sum to \(1\), and every role has positive total mass. Here \(\tau\) is the support size, not the number of possible types.
For each positive integer \(N\) such that every \(N\mu_{r,h}\) is integral, instantiate that many agents of type \((r,h)\), with fixed role \(r\) and initial colours \(X_a(j)=h_j\) for \(0\leq j\leq m\).
At each round \(t\geq m\), every role-\(r\) agent independently draws a lag \(i\) with probability \(p_i\), a role \(s\) with probability \(Q_{rs}\), and an agent \(b\) uniformly from role \(s\), then sets \(X_a(t+1)=X_b(t-i)\). Updates are synchronous; draws are independent across agents and rounds, and sampling may select the updating agent itself.
Stable consensus on \(c\) means all agents have colour \(c\) throughout the current and preceding \(m\) rounds. Let \(P_N(c)\) be the probability of eventually reaching this state, and define \(F=\lim_{N\to\infty,\;N\mu\text{ integral}}P_N(c)\).
Does \(F\) exist for every such input, and is its exact computation polynomial-time solvable or NP-hard? State running times in \(m,\tau,|R|,|C|\) and the total input bit length \(L\).
For finite strongly connected weighted agent graphs with positive lag probabilities and \(m\geq1\), stable consensus occurs almost surely, and an exact stationary-distribution expression gives each colour’s winning probability. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/17342/17149)
No separate result for the distribution-input limit specified here was identified in the literature search.
The limit \(F\) exists for every input and is exactly computable in polynomial time. In fact, \(P_N(c)\) is the same for every admissible population size \(N\).
Let \(d=|R|\), and define the mass of role \(r\) and its initial colour frequencies by
\(\displaystyle \rho_r=\sum_{h:(r,h)\text{ is supported}}\mu_{r,h},\qquad f_{r,j}(c)=\frac{1}{\rho_r}\sum_{h:(r,h)\text{ is supported}}\mu_{r,h}\mathbf 1_{\{h_j=c\}}.\)
Every \(\rho_r\) is positive by hypothesis. Let \(\nu\) be the unique stationary distribution of \(Q\):
\(\displaystyle \nu Q=\nu,\qquad \sum_{r\in R}\nu_r=1.\)
Define
\(\displaystyle a_k=\sum_{i=k}^{m}p_i\quad(0\leq k\leq m),\qquad Z=\sum_{k=0}^{m}a_k=\sum_{i=0}^{m}(i+1)p_i.\)
Then the exact answer is
\(\displaystyle \boxed{F=P_N(c)=\frac{1}{Z}\sum_{r\in R}\nu_r\sum_{k=0}^{m}a_k f_{r,m-k}(c)}.\)
The index reversal matters: \(a_0/Z\) weights the most recent initial round, whose index is \(m\).
Fix an admissible \(N\), and let \(n_r=N\rho_r\). These are positive integers because they are sums of the integral type counts.
The agent-to-agent sampling matrix is
\(\displaystyle H_{ab}=\frac{Q_{rs}}{n_s},\)
where agents \(a,b\) have roles \(r,s\), respectively. It is row-stochastic, since
\(\displaystyle \sum_bH_{ab}=\sum_{s\in R}n_s\frac{Q_{rs}}{n_s}=1.\)
Its positive-edge graph is strongly connected. Indeed, any positive-probability role walk lifts to an agent walk by choosing an agent in each intermediate role. Irreducibility of \(Q\) supplies such a walk between distinct roles. It also supplies a positive-length closed walk through each role, which permits connecting two agents in the same role. For the single-role case, \(Q=(1)\), and every agent samples every other agent with positive probability.
We use the finite-population result supplied in the question: a memory consensus process on a finite strongly connected weighted agent graph reaches stable consensus almost surely when \(m\geq1\) and all lag probabilities are positive. These hypotheses have now all been verified. See Proposition 4 and Corollary 1 of [*The Influence of Memory in Multi-Agent Consensus*](https://ojs.aaai.org/index.php/AAAI/article/download/17342/17149).
Consequently, this population eventually reaches stable consensus on some colour with probability one.
For each role \(r\) and time \(t\), let
\(\displaystyle z_r(t)=\frac{1}{n_r}\sum_{a:\,\operatorname{role}(a)=r}\mathbf 1_{\{X_a(t)=c\}}.\)
Let \(\mathcal F_t\) contain the initial histories and all draws used through time \(t\). For \(t\geq m\), the sampling rule gives
\(\displaystyle \mathbb E[z_r(t+1)\mid\mathcal F_t]=\sum_{i=0}^{m}p_i\sum_{s\in R}Q_{rs}z_s(t-i).\)
To justify this identity, a role-\(r\) agent chooses lag \(i\) and role \(s\) with probability \(p_iQ_{rs}\). Conditional on those choices, its probability of copying colour \(c\) is precisely \(z_s(t-i)\). Averaging over agents preserves this expectation.
Set
\(\displaystyle y(t)=\sum_{r\in R}\nu_rz_r(t).\)
Using \(\nu Q=\nu\), we obtain
\(\displaystyle \mathbb E[y(t+1)\mid\mathcal F_t]=\sum_{i=0}^{m}p_i y(t-i).\)
Now define, for \(t\geq m\),
\(\displaystyle M_t=\frac{1}{Z}\sum_{k=0}^{m}a_k y(t-k).\)
The identities
\(\displaystyle a_0=1,\qquad a_i=p_i+a_{i+1}\ (0\leq i<m),\qquad a_m=p_m\)
show that \(M_t\) is a martingale. Explicitly,
\(\displaystyle \begin{aligned} Z\,\mathbb E[M_{t+1}\mid\mathcal F_t] &=\sum_{i=0}^{m}p_i y(t-i)+\sum_{k=1}^{m}a_k y(t+1-k)\\ &=\sum_{i=0}^{m-1}(p_i+a_{i+1})y(t-i)+p_m y(t-m)\\ &=\sum_{i=0}^{m}a_i y(t-i) =ZM_t. \end{aligned} \)
Moreover, \(0\leq M_t\leq1\), because \(0\leq y(t)\leq1\), all \(a_k\) are positive, and their sum is \(Z\).
Let \(W\) denote the eventual consensus colour, which exists almost surely by Section 1. Once stable consensus has occurred, all the indicators appearing in \(M_t\) equal \(\mathbf 1_{\{W=c\}}\). Thus
\(\displaystyle M_t\longrightarrow\mathbf 1_{\{W=c\}}\qquad\text{almost surely}.\)
Bounded convergence and the martingale expectation identity imply
\(\displaystyle P_N(c)=\mathbb E[\mathbf 1_{\{W=c\}}]=\lim_{t\to\infty}\mathbb E[M_t]=M_m.\)
This argument requires no estimate of the consensus time.
For an initial time \(j\), the number of role-\(r\) agents having colour \(c\) is
\(\displaystyle \sum_{h:(r,h)\text{ is supported}}N\mu_{r,h}\mathbf 1_{\{h_j=c\}}.\)
Therefore,
\(\displaystyle z_r(j)=\frac{\sum_hN\mu_{r,h}\mathbf 1_{\{h_j=c\}}}{N\rho_r}=f_{r,j}(c).\)
Substituting this into \(M_m\) gives the boxed formula. Every quantity in that formula is determined by the input and is independent of \(N\).
Finally, admissible population sizes are unbounded: every positive multiple of a common denominator of the masses is admissible. Since \(P_N(c)\) is constant on this set, its specified limit exists and equals that constant.
The algorithm computes \(\nu\), the tail sums \(a_k\), and the quantities
\(\displaystyle \rho_r,\qquad T_r=\sum_{h:(r,h)\text{ is supported}}\mu_{r,h}\sum_{k=0}^{m}a_k\mathbf 1_{\{h_{m-k}=c\}}.\)
It then returns
\(\displaystyle F=\frac{1}{Z}\sum_{r\in R}\frac{\nu_rT_r}{\rho_r}.\)
Gaussian elimination and a scan of the support require
\(\displaystyle O\!\left(d^3+(m+1)\tau+m\right)\)
exact rational arithmetic operations. Here is also an explicit polynomial bound on bit complexity.
Let \(D\) be the product of the denominators of all numerical input entries. Its bit length is \(O(L)\). Write
\(\displaystyle Q_{rs}=\frac{A_{rs}}D,\qquad p_i=\frac{P_i}D,\qquad \mu_{r,h}=\frac{U_{r,h}}D.\)
All these integer numerators lie between zero and \(D\).
To compute \(\nu\), take any \(d-1\) equations of
\(\displaystyle (A^{\mathsf T}-DI)\nu^{\mathsf T}=0\)
and append the equation \(\sum_r\nu_r=1\). The resulting integer coefficient matrix \(B\) is nonsingular. Indeed, irreducibility gives rank \(d-1\) for \(Q^{\mathsf T}-I\). Its row relations form a one-dimensional space generated by the all-ones vector, since the rows sum to zero. Hence any \(d-1\) rows are independent. Their common nullspace is the stationary line, on which normalization determines a unique vector.
Cramer’s rule gives a common-denominator representation
\(\displaystyle \nu_r=\frac{b_r}{b},\qquad b=\det B\ne0.\)
The determinants have \(O(d(L+\log(d+1)))\) bits by Hadamard’s inequality. Computing these \(d+1\) determinants by fraction-free elimination takes \(O(d^4)\) integer operations on operands of this bit length. This is a conservative implementation; it suffices for the claimed classification.
Define integers
\(\displaystyle U_r=\sum_hU_{r,h},\qquad A_k'=\sum_{i=k}^{m}P_i,\qquad V=\sum_{i=0}^{m}(i+1)P_i, \)
and
\(\displaystyle S_r=\sum_hU_{r,h}\sum_{k=0}^{m}A_k'\mathbf 1_{\{h_{m-k}=c\}}.\)
Then
\(\displaystyle F=\sum_{r\in R}\frac{b_rS_r}{b\,U_rV}.\)
Every \(U_r\) is positive. Using the common denominator
\(\displaystyle bV\prod_{r\in R}U_r\)
allows exact evaluation without uncontrolled growth of intermediate rational denominators.
We have \(U_r\leq D\), \(V\leq(m+1)D\), and \(S_r\leq U_rV\). Consequently, all required operands and the final numerator and denominator have
\(\displaystyle O\!\left(d\bigl(L+\log(d+m+2)\bigr)\right)\)
bits.
Using schoolbook integer arithmetic, a valid overall bit-operation bound is
\(\displaystyle O\!\left( L+ \bigl[d^4+(m+1)\tau+m+1\bigr] \bigl[d(L+\log(d+m+2))\bigr]^2 \right). \)
For the specified colour \(c\), the algorithm does not iterate over \(C\); colour-label encoding and any explicit list of \(C\) are accounted for in \(L\). It scans the listed \(\tau\) histories, without enumerating \(C^{m+1}\) or instantiating agents.
Thus exact computation of \(F\) is polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The finite-population argument, cancellation of population size, and polynomial bit complexity bound are correct. I found no substantive gaps or required repairs.
Every role mass \(\rho_r\) is positive by the input assumptions, so every frequency \(f_{r,j}(c)\) is well-defined and belongs to \([0,1]\).
The existence and uniqueness of the stationary probability vector \(\nu\) follow from finiteness and irreducibility of the row-stochastic matrix \(Q\). Aperiodicity is not required for this statement.
The definitions of \(a_k\) and \(Z\) are consistent. In particular, \(a_0=1\), every \(a_k>0\), and summing the tail sums counts \(p_i\) exactly \(i+1\) times. Thus the stated identity \(Z=\sum_{i=0}^{m}(i+1)p_i\) is correct, and division by \(Z\) is valid.
For every admissible \(N\), the role count \(n_r=N\rho_r\) is a positive integer: it is the sum of the integral counts of supported types belonging to that role.
The sampling matrix \(H_{ab}=Q_{rs}/n_s\) correctly describes the agent selected after choosing its role. Its row-stochasticity calculation is correct.
The strong-connectivity argument covers both distinct roles and distinct agents within one role. Positive-length closed role walks allow the latter connections. The single-role case is separately and correctly handled by \(Q=(1)\). Self-sampling is permitted by the task, so self-loops introduce no mismatch.
The prover states the needed finite-population result and checks its hypotheses: a finite strongly connected weighted graph, positive lag probabilities, and \(m\geq1\).
The cited source supports this application. Its memory protocol permits arbitrary fixed initial histories and self-loops; Proposition 4 and Corollary 1 provide the asserted convergence result through the associated memory graph. Thus the citation is applicable to the process written here. [*The Influence of Memory in Multi-Agent Consensus*](https://ojs.aaai.org/index.php/AAAI/article/download/17342/17149)
The invoked stable-consensus conclusion matches the task’s requirement that all agents share the colour throughout the current and preceding \(m\) rounds. Such a state is absorbing under the stated copying rule.
The identity
\(\mathbb E[z_r(t+1)\mid\mathcal F_t]=\sum_{i=0}^{m}p_i\sum_sQ_{rs}z_s(t-i)\)
correctly conditions on the lag and sampled role, then uses uniform sampling within that role.
All histories referenced are available when \(t\geq m\). The inclusion of the updating agent among possible sampled agents causes no problem because the sampled colour is from a time already contained in \(\mathcal F_t\).
Multiplication by \(\nu_r\) and summation over roles correctly uses \(\nu Q=\nu\), yielding the stated scalar recurrence for \(y(t)\). No independence between the role frequencies is assumed or needed.
The displayed reindexing is correct. The shifted-history terms contribute \(a_{i+1}y(t-i)\) for \(0\leq i<m\), while the oldest term has coefficient \(p_m=a_m\). Consequently, every coefficient becomes the required \(a_i\).
The process \(M_t\) is adapted and bounded between zero and one. Its expectation is constant for integer times \(t\geq m\).
Almost-sure stable consensus implies that, after absorption, every history entry used by \(M_t\) has the eventual winning colour. Hence the asserted almost-sure limit is correct.
Bounded convergence applies because the uniform bound is deterministic. The equality \(\mathbb E[M_m]=M_m\) is also justified: the initial histories and type counts are fixed. The identification \(P_N(c)=M_m\) therefore follows without an expected-consensus-time assumption.
The initial-frequency calculation cancels \(N\) exactly, leaving \(f_{r,j}(c)\). Substitution into \(M_m\) gives the boxed formula with the correct reversed index \(m-k\).
Every term is independent of \(N\). Moreover, multiples of a common denominator of the masses provide an unbounded collection of admissible population sizes. Constancy on that collection proves the requested limit exists.
The common integer denominator \(D\) has \(O(L)\) bits, and the scaled input numerators have magnitude at most \(D\).
The argument for selecting any \(d-1\) stationary equations is valid. The phrase “the rows sum to zero” is correctly read as saying that the sum of the row vectors of \(A^{\mathsf T}-DI\) is zero, rather than that every individual row has zero sum. Together with rank \(d-1\), this identifies the sole row relation and justifies independence of any \(d-1\) rows.
Appending normalization makes \(B\) nonsingular. The case \(d=1\) also works: no stationary equation is retained, and normalization alone determines \(\nu\).
Cramer’s rule and the stated Hadamard bound give the claimed determinant bit lengths. Fraction-free determinant computation supplies the conservative polynomial implementation described. A negative determinant denominator affects neither the representation nor the magnitude bounds.
Substitution of the integer-scaled quantities into the probability formula gives exactly
\(F=\sum_r b_rS_r/(bU_rV)\).
The factors of \(D\) cancel correctly.
The inequalities \(U_r\leq D\), \(V\leq(m+1)D\), and \(S_r\leq U_rV\) are valid. The proposed common denominator consequently has the stated polynomial bit length. Summing the corresponding numerators does not exceed that asymptotic bound.
The rational-operation count \(O(d^3+(m+1)\tau+m)\) and the more conservative integer implementation using \(O(d^4)\) determinant operations are compatible descriptions of different implementations.
The displayed schoolbook bit-operation bound is polynomial in the requested parameters and \(L\). It also accommodates denominator preparation, integer scaling, and exact evaluation. Colour comparisons and input parsing are covered by the input encoding length; there is no enumeration of \(C^{m+1}\).
Both requested conclusions are established: existence for every valid input and polynomial-time exact computation. The stronger claim that all admissible finite populations have the same winning probability is also established.
No repair is required. The singleton-colour case, absent queried colour in the histories, initially stable consensus, periodic irreducible role matrices, and single-role populations introduce no exceptions to the argument.
⟨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.