d4-journals-geb-2012-0082 (d4-journals-geb-2012-0082)

Given finite states and signals, rational masses (\mu_t)_{t\in T}, and rational type data specifying priors, signal likelihoods, self-reliance weights, and interactions \(a_{tu}\), decide whether the role-based continuum update makes the population learn the true state. Each type \(t\) has a belief distribution \(B_{t,k}\) after \(k\) rounds; for every (\varepsilon>0), does (\sum_t \mu_t B_{t,k}(\{b:b(\theta^*)\ge 1-\varepsilon\})\to 1 as \(k\to\infty\)?

A society is given by its support: the list of the \(\tau\) types \(T\) with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=|\Theta|\) states, a specified true state \(\theta^*\), and nonempty finite signal sets \(S_t\); write \(q=\sum_t|S_t|\).
Each type has a rational prior \(p_t\in\Delta(\Theta)\), strictly positive rational likelihoods \(\ell_t(s\mid\theta)\) summing to one over \(S_t\) for every state, rational self-reliance \(\alpha_t>0\), and rational interaction densities \(a_{tu}\ge0\), satisfying \(\alpha_t+\sum_u\mu_u a_{tu}=1\). The graph with edges \(u\to t\) when \(a_{tu}>0\) is strongly connected; some \(p_t(\theta^*)>0\); and for every \(\theta\ne\theta^*\), some \(t,s\) satisfy \(\ell_t(s\mid\theta)\ne\ell_t(s\mid\theta^*)\).
The within-type belief distribution starts at \(B_{t,0}=\delta_{p_t}\). Let \(\bar b_{u,k}=\int b\,dB_{u,k}(b)\), and let \(\operatorname{BU}_t(b;s)\) denote the Bayesian posterior using likelihood \(\ell_t\). Define \(B_{t,k+1}\) as the law of \(\alpha_t\operatorname{BU}_t(b;s)+\sum_u\mu_u a_{tu}\bar b_{u,k}\), where \(b\sim B_{t,k}\) and independently \(s\sim\ell_t(\cdot\mid\theta^*)\). This deterministic recursion represents fresh private signals independent over time and averaging previous beliefs across each role, including the recipient's role when its interaction density is positive.
Population learning means that for every \(\varepsilon>0\), \(\sum_t\mu_t B_{t,k}(\{b\in\Delta(\Theta):b(\theta^*)\ge1-\varepsilon\})\to1\) as \(k\to\infty\). Let \(L\) be the total binary input length.

Is deciding population learning for these inputs in \(\mathrm P\), with running time polynomial in \(m,\tau,q,L\), or is it \(\mathrm{NP}\)-hard?

For finite agents, strong connectivity, positive self-reliance, some positive prior on the truth, and collective distinguishability guarantee almost-sure learning; this is a convergence result, not a polynomial-time decision theorem. [Finite-agent convergence](https://arxiv.org/pdf/1103.4395).
A subsequent finite-agent treatment assumes strictly positive likelihoods and establishes the same learning guarantee. [Expanded treatment](https://economics.sas.upenn.edu/sites/default/files/filevault/11-025.pdf). The search located no complexity classification for the exact distribution recursion defined here.

Result

The problem is in \(\mathrm P\). Every input satisfying the stated assumptions exhibits population learning.

We prove this directly for the distribution recursion, extending the [finite-agent learning guarantee](https://arxiv.org/pdf/1103.4395) to the model in the question.

1. Notation and positivity of belief in the truth

Set \( C_{tu}=\mu_u a_{tu},\qquad W_{tu}=\alpha_t\mathbf 1_{\{t=u\}}+C_{tu}. \)

The normalization assumption makes \(W\) row-stochastic. Strong connectivity and positive masses make \(W\) irreducible.

Write \( r_t(s)=\ell_t(s\mid\theta^*),\qquad M_t(b;s)=\sum_{\theta\in\Theta}b(\theta)\ell_t(s\mid\theta). \)

We also use \(M_t(\,\cdot\,;s)\) as a linear functional on vectors that need not be probability distributions. All Bayesian denominators are positive because all likelihoods are strictly positive.

There is a finite time \(K\) after which every belief in every distribution’s support assigns positive probability to the truth. To see this, choose a type whose initial belief assigns positive probability to \(\theta^*\). Its positive self-reliance preserves this property under every signal. If type \(u\) has positive mean belief in the truth and \(C_{tu}>0\), then every updated belief of type \(t\) has truth coordinate at least \(C_{tu}\bar b_{u,k}(\theta^*)>0\). Strong connectivity propagates positivity to all types along paths; we can take \(K=\tau-1\).

Each distribution has finite support at each finite time, by induction from the initial point masses and finite signal sets. Consequently, for \(k\ge K\), the quantities \( g_{t,k}=\int\log b(\theta^*)\,dB_{t,k}(b) \)
are finite.

2. A logarithmic potential forces accurate predictions

Choose a stationary probability vector \(\pi\) for \(W\), so that \(\pi W=\pi\). Every coordinate \(\pi_t\) is positive.

For completeness, existence follows by taking an accumulation point of the Cesàro averages of any probability row vector under \(W\). Their difference from their images under \(W\) tends to zero. Positivity follows from irreducibility: if \(\pi_i>0\), then for every \(j\) some power satisfies \((W^d)_{ij}>0\), and hence \(\pi_j=(\pi W^d)_j>0\).

Define \( H_k=\sum_t\pi_tg_{t,k}\le0. \)

For \(b\sim B_{t,k}\), the truth coordinate after signal \(s\) is \( b^+(\theta^*)= \alpha_t b(\theta^*)\frac{r_t(s)}{M_t(b;s)} +\sum_u C_{tu}\bar b_{u,k}(\theta^*). \)

Concavity of the logarithm, followed by averaging over \(b\) and the independent signal, gives \( g_{t,k+1}\ge \alpha_tg_{t,k} +\alpha_t\mathbb E_{B_{t,k}}D\!\left(r_t\Vert M_t(b;\cdot)\right) +\sum_u C_{tu}\log\bar b_{u,k}(\theta^*), \)
where \( D(r\Vert z)=\sum_s r(s)\log\frac{r(s)}{z(s)} \)
is relative entropy.

Jensen’s inequality also gives \(\log\bar b_{u,k}(\theta^*)\ge g_{u,k}\). Multiplying by \(\pi_t\), summing over types, and using stationarity therefore yields \( H_{k+1}-H_k\ge \sum_t\pi_t\alpha_t\, \mathbb E_{B_{t,k}}D\!\left(r_t\Vert M_t(b;\cdot)\right). \)

Relative entropy is nonnegative, and \(H_k\le0\). Telescoping shows that \( \sum_{k=K}^{\infty}\sum_t\pi_t\alpha_t\, \mathbb E_{B_{t,k}}D\!\left(r_t\Vert M_t(b;\cdot)\right) \le-H_K<\infty. \)

Because every \(\pi_t\alpha_t>0\), each type’s expected relative entropy tends to zero.

We explicitly convert this into prediction convergence. For strictly positive probability vectors \(r,z\), let \(d=z-r\) and \(h(v)=D(r\Vert r+vd)\). Then \( h(0)=h'(0)=0,\qquad h''(v)=\sum_s\frac{r(s)d(s)^2}{(r(s)+vd(s))^2} \ge \bigl(\min_s r(s)\bigr)\sum_s d(s)^2. \)

The inequality uses that every coordinate of the interpolated probability vector is at most one. Integrating twice gives \( D(r\Vert z)\ge \frac{\min_s r(s)}2\sum_s(z(s)-r(s))^2. \)

Since each signal set is finite, Cauchy–Schwarz now implies, for every type, \[ e_{t,k}:= \mathbb E_{B_{t,k}}\sum_{s\in S_t} |M_t(b;s)-r_t(s)| \longrightarrow0. \tag{1} \]

3. Averaged Bayesian updating becomes asymptotically neutral

Define the averaged Bayesian posterior \( y_{t,k}= \sum_{s\in S_t}r_t(s)\, \mathbb E_{B_{t,k}}\operatorname{BU}_t(b;s). \)

Using \(\sum_s\ell_t(s\mid\theta)=1\), we obtain \( y_{t,k}(\theta)-\bar b_{t,k}(\theta) = \sum_s\mathbb E\!\left[ b(\theta)\ell_t(s\mid\theta) \left(\frac{r_t(s)}{M_t(b;s)}-1\right) \right]. \)

Taking the sum of absolute values over states gives \[ \|y_{t,k}-\bar b_{t,k}\|_1 \le \sum_s\mathbb E \left[ \left|\frac{r_t(s)}{M_t(b;s)}-1\right|M_t(b;s) \right] =e_{t,k}\longrightarrow0. \tag{2} \]

Thus averaging Bayesian updates over the true signal distribution changes the mean belief by a vanishing amount.

4. Consecutive prediction accuracy eliminates locally distinguishable states

Fix a type \(t\) and a signal \(s\). Temporarily suppress the type index, and set \( z_k=\sum_u C_{tu}\bar b_{u,k},\qquad F_{k,s}(b)=\alpha_t\operatorname{BU}_t(b;s)+z_k. \)

The distribution \(B_{t,k+1}\) is the mixture of the laws of \(F_{k,s'}(b)\), with weights \(r(s')\). By (1) at time \(k+1\), \( r(s)\,\mathbb E_{B_{t,k}} |M(F_{k,s}(b);s)-r(s)| \le e_{t,k+1}\longrightarrow0. \)

Since \(r(s)>0\), this implies \[ \mathbb E M(F_{k,s}(b);s)\longrightarrow r(s). \tag{3} \]

Also, (1) implies \(M(\bar b_{t,k+1};s)\to r(s)\). The mean recursion and linearity give \( \bar b_{t,k+1}=\alpha_t y_{t,k}+z_k, \)
and \( \mathbb E M(F_{k,s}(b);s) =\alpha_t\mathbb E M(\operatorname{BU}_t(b;s);s)+M(z_k;s). \)

Subtracting these identities and using (3) yields \( \mathbb E M(\operatorname{BU}_t(b;s);s)-M(y_{t,k};s) \longrightarrow0. \)

By (1) and (2), \(M(y_{t,k};s)\to r(s)\). Hence \[ \mathbb E\frac{\sum_\theta b(\theta)\ell_t(s\mid\theta)^2}{M_t(b;s)} \longrightarrow r_t(s). \tag{4} \]

Let \( A_s(b)=\sum_\theta b(\theta)\ell_t(s\mid\theta)^2. \)

Because likelihoods lie in \((0,1]\), we have \(0\le A_s(b)\le M_t(b;s)\). Therefore \( \left|A_s(b)-r_t(s)\frac{A_s(b)}{M_t(b;s)}\right| \le |M_t(b;s)-r_t(s)|. \)

Combining (1) and (4) gives \(\mathbb E A_s(b)\to r_t(s)^2\). Consequently, \[ \begin{aligned} \sum_\theta\bar b_{t,k}(\theta) \bigl(\ell_t(s\mid\theta)-r_t(s)\bigr)^2 &=\mathbb E A_s(b) -2r_t(s)M_t(\bar b_{t,k};s)+r_t(s)^2\\ &\longrightarrow0. \end{aligned} \tag{5} \]

Every summand on the left is nonnegative. Thus, whenever \(\ell_t(s\mid\theta)\ne\ell_t(s\mid\theta^*)\), equation (5) forces \[ \bar b_{t,k}(\theta)\longrightarrow0. \tag{6} \]

This eliminates every state locally distinguishable by type \(t\), including cases where a mixture of false states initially predicts its signals correctly.

5. Strong connectivity gives population learning

Fix \(\theta\ne\theta^*\). Collective distinguishability supplies a type \(t\) and signal \(s\) satisfying the inequality in (6), so \(\bar b_{t,k}(\theta)\to0\).

For every edge \(u\to t\), the update implies \( 0\le C_{tu}\bar b_{u,k}(\theta) \le\bar b_{t,k+1}(\theta). \)

Since \(C_{tu}>0\), elimination at type \(t\) implies elimination at type \(u\). Every type has a directed path to \(t\); applying this implication backwards along that path proves \( \bar b_{u,k}(\theta)\longrightarrow0 \qquad\text{for every type }u. \)

There are finitely many false states. Therefore \( \bar b_{t,k}(\theta^*)\longrightarrow1 \qquad\text{for every type }t. \)

For every \(\varepsilon>0\), Markov’s inequality gives \( B_{t,k}\bigl(\{b:b(\theta^*)<1-\varepsilon\}\bigr) \le\frac{1-\bar b_{t,k}(\theta^*)}{\varepsilon}. \)

Multiplying by the masses and summing proves the required population-learning condition.

6. Decision complexity

On the stipulated input class, the algorithm simply answers yes: the preceding proof establishes learning for every admissible input.

If validity must also be checked, all stated conditions are polynomial-time checkable. These checks require exact rational arithmetic, strong-connectivity testing on \(\tau\) vertices, and likelihood comparisons across at most \(mq\) entries. Their bit complexity is polynomial in \(m,\tau,q,L\).

Thus deciding asymptotic population learning is in \(\mathrm P\). The proof does not assert a polynomial bound on the number of updates needed to approach learning.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes population learning for every admissible input to the specified distribution recursion, and the polynomial-time decision conclusion follows. I found no mathematical errors or gaps requiring clarification.

• Stochastic matrix and positivity of truth beliefs

The normalization gives \(\sum_u W_{tu}=1\), and all entries are nonnegative. Since \(\mu_u>0\), the positive entries of \(C\) correspond exactly to the stated interaction edges. The matrix’s usual directed graph reverses the stated edge orientation, but reversal preserves strong connectivity, so \(W\) is irreducible.

Positive truth probability persists under every Bayesian update because likelihoods and self-reliance are positive. A positive interaction coefficient from a type with positive mean truth probability makes every recipient belief’s truth coordinate positive. Persistence and propagation along paths justify \(K=\tau-1\), including the case \(\tau=1\).

Finite support at each finite time follows from the finite signal sets. Consequently, once truth coordinates are positive throughout the support, every \(g_{t,k}\) is finite. No uniform lower bound over all subsequent times is needed.

• Stationary weights and logarithmic potential

The supplied Cesàro argument establishes a stationary probability vector. Its positivity follows from irreducibility exactly as written.

The logarithmic concavity inequality uses weights \(\alpha_t\) and \(C_{tu}\), which sum to one. All logarithm arguments are positive for \(k\ge K\). Independence of the fresh signal and current belief justifies the relative-entropy term.

Both \(r_t\) and \(M_t(b;\cdot)\) are strictly positive probability vectors: positivity follows from the likelihood assumptions, and normalization follows from summing likelihoods over signals. Thus relative entropy is well-defined and nonnegative.

Jensen’s inequality and stationarity correctly yield the displayed potential increment. Telescoping is valid because \(H_k\le0\) and \(H_K\) is finite. Since every coefficient \(\pi_t\alpha_t\) is positive, each type’s expected relative entropy tends to zero.

• Conversion to prediction convergence

The derivative calculation is correct. In particular, \(h'(0)=0\) uses \(\sum_s(z(s)-r(s))=0\). Each coordinate of the interpolated probability vector is at most one, so the displayed lower bound on \(h''\) has the correct direction and constant.

Integrating twice gives the stated quadratic bound. Cauchy–Schwarz over the finite signal set, together with the vanishing expected relative entropy, establishes equation (1). The constants may depend on the fixed input; no uniform rate is needed for the convergence claim.

• Asymptotic neutrality of averaged Bayesian updating

The expression for \(y_{t,k}(\theta)-\bar b_{t,k}(\theta)\) correctly uses likelihood normalization. Applying the triangle inequality and summing over states produces \(M_t(b;s)\), which cancels the positive denominator.

Thus the bound by \(e_{t,k}\), and hence equation (2), is valid.

• Elimination of locally distinguishable false states

The mixture representation of \(B_{t,k+1}\) is correct. Its prediction error includes the nonnegative contribution from update signal \(s\) and prediction coordinate \(s\), giving the displayed bound by \(e_{t,k+1}\). Since \(r_t(s)>0\), equation (3) follows.

Subtracting the conditional-update prediction from the mean-update prediction cancels \(M(z_k;s)\). Division by the fixed positive \(\alpha_t\) is legitimate. Equations (1) and (2), with linearity of \(M_t\), then justify equation (4).

The posterior prediction in equation (4) has the stated numerator involving squared likelihoods. The bound \(A_s(b)\le M_t(b;s)\) follows from likelihoods lying in \((0,1]\), and the subsequent displayed error inequality is correct. These statements establish \(\mathbb E A_s(b)\to r_t(s)^2\).

The expansion in equation (5) is exact, including its constant term because beliefs sum to one. All summands are nonnegative. A strictly positive squared likelihood difference therefore forces the corresponding mean belief to vanish, proving equation (6). This step adequately handles false-state mixtures that initially produce accurate predictions.

• Propagation and population learning

The inequality
\[ 0\le C_{tu}\bar b_{u,k}(\theta)\le\bar b_{t,k+1}(\theta) \]
follows directly from nonnegativity of the Bayesian contribution and all interaction terms.

Elimination propagates backwards along interaction edges. Strong connectivity supplies a directed path from every type to the distinguishing type, so this direction of propagation reaches every type. The time shift does not affect convergence.

Collective distinguishability supplies a starting type for each false state. Finiteness of the state set then gives mean truth probability tending to one for every type. Markov’s inequality bounds exactly the complement of the learning event. Summing with the population masses proves the required definition of population learning.

• Decision complexity and scope

On the stipulated admissible input class, answering yes is correct. The optional validity checks are polynomial-time: rational normalization, positivity, likelihood comparisons, and strong connectivity can all be checked with polynomial bit complexity.

The conclusion concerns deciding asymptotic learning. It does not require a polynomial convergence rate or an efficient representation of intermediate belief distributions. The prover explicitly preserves this distinction.

No additional clarification is necessary. The cited finite-agent results are contextual; the argument establishes the distribution-recursion result independently.

⟨structured verdict parsed — rendered above⟩