In a perfectly rational world, a group of people sharing information should eventually reach a consensus on the truth. This is the essence of the "Agreement Theorem": if two Bayesian agents share their beliefs, they cannot "agree to disagree." However, as Natalie Collina, Aaron Roth, and others point out in Tractable Agreement Protocols, this theoretical ideal assumes agents possess infinite computational power and a perfect map of the social network.
In reality, social learning is a computational minefield. Recent research has shifted from modeling "perfect" Bayesian agents to discovering how simple, bounded-rationality heuristics can achieve the same optimal results without the impossible math.
The Complexity Wall of Bayesian Rationality
Why is being "perfectly rational" so hard? In a social network, you don't just observe the world; you observe your neighbors, who are also observing their neighbors. To update your beliefs correctly, you must perform "inverse reasoning": you have to figure out what private information led your neighbor to their current opinion.
Jan Hązła, Elchanan Mossel, and M. Amin Rahimian proved in Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard that this task is computationally intractable. Even approximating these beliefs is NP-hard. The difficulty stems from two main factors:
- Information Bottlenecks: Agents often only see discrete actions (like a "buy" or "sell" decision) rather than the continuous internal probabilities of their neighbors.
- Data Incest: This is the problem of redundant information. If you and I both listen to the same third person, and then I listen to you, I might accidentally count that third person’s information twice. To avoid this, a Bayesian agent needs a global map of the network and a full history of every interaction—requirements that are impossible in large-scale systems.
Heuristics as a Bridge to Truth
If perfect rationality is impossible, how do groups ever learn? The answer lies in "non-Bayesian" social learning—simple rules of thumb that mimic rational outcomes.
Pooya Molavi in On Non-Bayesian Social Learning and Alireza Tahbaz-Salehi in Non-Bayesian Social Learning, Second Version demonstrate that agents can reach the truth using a simple update rule: combine your own local Bayesian reasoning with a weighted average of your neighbors' opinions. As long as the network is strongly connected and the truth is "collectively distinguishable," the group will eventually reach a consensus, even if no single person has enough information to find the truth on their own.
Learning Without Recall
One of the most powerful frameworks for this "bounded rationality" is Learning without Recall. In this model, agents don't try to remember the entire history of the network or map out its topology. Instead, they treat their neighbors' current beliefs as a sufficient proxy for the information those neighbors have gathered.
In Bayesian Learning without Recall, Mohammad Amin Rahimian and Ali Jadbabaie show that this "memoryless" approach can still lead to exponential learning speeds in specific structures like circles and trees. By replacing their own prior beliefs with their neighbors' estimates, agents bypass the need to filter out redundant information manually. This provides a mathematical explanation for how real-world groups can be efficient despite individual cognitive limits.
When Efficiency is Guaranteed
While general social learning is hard, certain conditions make it surprisingly easy. Elchanan Mossel and Omer Tamuz have identified several "tractable" scenarios:
- Gaussian Estimators: When signals are Gaussian, Bayesian learning becomes a matter of simple linear algebra. In Efficient Bayesian Learning in Social Networks with Gaussian Estimators, they show that agents can reach optimal consensus quickly while preserving the privacy of their raw data.
- Egalitarian Networks: In Strategic Learning and the Topology of Social Networks, Allan Sly and colleagues show that networks where no single individual is too influential ("egalitarian" structures) are much more likely to aggregate information correctly than "non-egalitarian" ones, where a few misinformed but highly visible leaders can lead the whole group astray.
By moving away from the requirement of perfect global knowledge, this research direction shows that collective intelligence is not about individual brilliance, but about the efficiency of the local rules we use to talk to our neighbors.