In classical economic theory, a group of perfectly rational agents should eventually reach a consensus. If two people share a common goal and exchange their beliefs, Robert Aumann’s famous "Agreement Theorem" suggests they cannot "agree to disagree." However, this theoretical ideal assumes that agents possess infinite computational power to process every signal they receive.
Recent research demonstrates that for agents in a social network, the "math" of being perfectly rational is not just difficult—it is often fundamentally intractable.
The Complexity of Being Rational
The core of the problem lies in how a Bayesian agent updates their beliefs based on the actions of others. To be truly rational, an agent cannot simply take a neighbor’s opinion at face value. They must account for the fact that the neighbor’s opinion was influenced by their own neighbors, some of whom might be shared.
Hazla et al. proved that determining what to believe in such a network is PSPACE-hard. This places rational social learning in the same complexity class as the most difficult problems solvable with limited memory, suggesting that the Bayesian ideal is physically impossible for real-world agents to achieve. Even when agents are willing to settle for a "good enough" estimate, Hazla et al. showed that distinguishing between extreme certainty and complete uncertainty remains NP-hard.
The Recursive Trap and Data Incest
Why is this so hard? A rational agent must recursively account for the reasoning of every other agent in the network. As Rahimian notes, perfect Bayesian rationality requires knowing the entire global network topology and performing complex inferences to filter out "historical echoes."
Without this global knowledge, agents fall victim to "data incest"—the over-amplification of information as it circles through the network. To avoid this, Rahimian explored the Bayesian Without Recall (BWR) model, where agents act rationally but "forget" the past at each step. While this simplifies the math, the authors found it often leads to a failure of learning because agents cannot distinguish new evidence from recycled information.
When Consensus Becomes Tractable
Despite these hard limits, consensus is not always impossible. The complexity of the problem depends heavily on the nature of the information and the structure of the network:
- Simple Voting: Mossel et al. showed that if agents are merely voting on a binary decision, they can reach a correct unanimous decision using a surprisingly simple $O(nt)$ algorithm.
- Gaussian Signals: When agents exchange continuous estimates (like temperature or price) and the noise follows a Gaussian distribution, Mossel et al. proved that Bayesian learning becomes computationally efficient, reducible to simple linear algebra.
- Specific Topologies: In highly structured environments like directed circles or rooted trees, Rahimian and Rahimian demonstrated that memoryless update rules can achieve exponentially fast learning.
Toward Realistic Models of Learning
The gap between elegant mathematical theorems and PSPACE-hard reality has led researchers to seek more "tractable" versions of rationality. Collina et al. proposed Tractable Agreement Protocols to bridge the gap between Aumann’s theory and practical AI or human interactions.
Similarly, Molavi et al. argued for non-Bayesian update rules. They showed that agents can still reach a consensus and learn the truth using simple heuristics, even if they don't know the full reliability of their neighbors. These findings suggest that while perfect rationality is a computational dead end, collective intelligence can still emerge through boundedly rational behavior.
Key Foundational Work
Non-Bayesian social learning (2012) — contributed 1 concept elements to this direction.
Making Consensus Tractable (2013) — contributed 1 concept elements to this direction.