Maximizing Truth Learning in a Social Network is NP-hard

I think there is a defensible, though deliberately narrow, continuous mirror: a high-multiplicity population of repeated social-network communities.

Let a community template be \(H_t=(G_t,q,p)\), where \(G_t\) is a finite directed graph with \(r_t\) vertex roles, and all communities use either Bayesian or majority aggregation. A society is a rational distribution \(\mu\) over finitely many community templates. A mass \(\mu_t\) means that fraction of the population’s communities has template \(H_t\). The corresponding agent type is \((t,v)\): an agent’s complete type records its community template, vertex role, incoming and outgoing role relations, signal accuracy, prior, and aggregation rule. Copy identities are irrelevant.

For each template \(t\), let \(\lambda_{t,\sigma}\) be the mass of its communities assigned decision ordering \(\sigma\in\Sigma_{r_t}\), with
\[ \lambda_{t,\sigma}\ge 0 \qquad\text{and}\qquad \sum_{\sigma\in\Sigma_{r_t}}\lambda_{t,\sigma}=1. \]
The continuous population problem is
\[ \operatorname{LR}^{\rho}_{\infty}(\mu,\lambda) = \frac{1}{\sum_t\mu_t r_t} \sum_t\mu_t \sum_{\sigma\in\Sigma_{r_t}} \lambda_{t,\sigma} L(H_t,\sigma,\rho), \]
where \(L(H_t,\sigma,\rho)\) is exactly the paper’s cumulative learning rate for one copy of \(H_t\) under aggregation rule \(\rho\). The task is to maximize this quantity, or decide whether it reaches a specified threshold.

This is genuinely a population-continuous object. If \(\mu_t=a_t/D\) and \(\lambda_{t,\sigma}=b_{t,\sigma}/B\), it is realized by taking many copies of each community and assigning the appropriate number of copies to each ordering. As the number of copies \(K\to\infty\), the population has \(n=\Theta(K)\) agents but only \(\tau=\sum_t r_t\) role types. Local communities remain finite, so private signals, Bayesian posteriors, majority ties, and herding retain exactly the semantics of the paper. The global ordering is simply the concatenation of the chosen orderings inside the disconnected communities.

My lead anchor is Theorem 5.1, proved in this paper: “Opt Network Learning with the Bayesian inference rule \(\mu=\mu_B\) is APX-hard.” The corresponding continuous problem is Bayesian Opt-CNL\(_\infty\), the optimization problem just defined with \(\rho=\mu_B\). The reduction is exact on the singleton-template slice: given the paper’s network \(N=(G,q,p)\), set \(\mu_{t_0}=1\) for the single template \(H_{t_0}=N\). Since randomizing over orderings cannot improve a linear expectation, an optimal \(\lambda_{t_0}\) is deterministic, and
\[ \max_{\lambda}\operatorname{LR}^{B}_{\infty}(\mu,\lambda) = \max_{\sigma\in\Sigma_n}\frac{L(N,\sigma,\mu_B)}{n}. \]
Thus an approximation algorithm for Bayesian Opt-CNL\(_\infty\) would approximate the paper’s Opt Network Learning problem. The APX-hardness transfers directly. The paper’s fixed-\(p\) strengthening, Theorem 3.10 and Corollary 5.2, also survives on this same slice.

This is a Class B mirror: the reduction’s combinatorics live in the topology of \(G\) and in the ordering of its roles, not in the number of named agents. Repeating the network many times does not dissolve that hardness; it merely turns the finite population into a high-multiplicity population of exchangeable role types.

A second, independently worthwhile anchor is Theorem 4.1, also proved here: “Network Learning with the majority vote rule \(\mu=\mu_M\) is NP-hard.” The continuous problem Majority-CNL\(_\infty\) uses exactly the same instance and solution space, but replaces Bayesian aggregation by the paper’s majority rule. It asks whether
\[ \max_{\lambda}\operatorname{LR}^{M}_{\infty}(\mu,\lambda) \ge 1-\varepsilon. \]
Again, the singleton-template restriction is exactly the paper’s Network Learning decision problem, so Theorem 4.1 transfers. This is not merely a Bayesian-inference artefact: the same continuous high-multiplicity population remains hard when agents are boundedly rational and use majority dynamics. That is particularly plausible for repeated groups of voters, users of a platform, classrooms, trading desks, or sensor clusters, where each group has the same local communication pattern but many copies of the group exist.

The authors should recognize this as their problem’s continuous analogue because none of the substantive ingredients has been replaced: the graph topology, private noisy measurements, hidden binary truth, local visibility, aggregation rule, sequential ordering, and average prediction accuracy are all retained. Only named copies of structurally identical agents are replaced by population mass. A finite instantiation with \(K\) copies is also a literal high-multiplicity version of the original model, not an arbitrary fractional relaxation.

The scope is intentionally limited. This mirrors Opt Network Learning and Network Learning under the Bayesian and majority rules. It does not claim to continuize the paper’s cited asymptotic truth-learning theory, general Bayesian-network inference, or every possible graphon or mean-field formulation.

The weak point is that this is a repeated-community mirror rather than a fully atomless graphon model in which population mass changes the information available to each individual. The mass \(\mu\) affects the aggregate objective, while the hard local ordering problem survives inside each community. A referee could therefore say that the continuous aspect is conservative and that the type catalogue may still be as large as the original hard graph. I accept that objection. I would not claim, without further work, that simply replacing a finite graph by a continuum interaction kernel preserves the paper’s semantics: if an agent observes a positive mass of predecessors, private signals may average away and herding may disappear.

But that limitation does not defeat the narrower positive claim. The repeated-network regime is a sensible high-multiplicity society, its continuous problem is precise, and the paper’s strongest computational results transfer exactly. Further questions are whether a genuinely mass-sensitive typed interaction kernel preserves these hardness reductions, whether boundedly many network-role types admit efficient algorithms, and how many finite copies are needed to round a continuous ordering distribution while preserving the learning-rate gap.