Heterogeneous Beliefs and Multi-Population Learning in Network Games

Shuyue Hu, Harold Soh, Georgios PiliourasarXiv 2023 · DOI · arXiv

Researchers from the Shanghai AI Lab, NUS, and SUTD have recently explored a fundamental question in multi-agent systems: What happens when a crowd doesn't agree? Their study investigates how diversity in beliefs affects the way populations learn to play games against each other over time, moving beyond traditional models that assume all agents in a role share identical expectations.

The Problem: Beyond Homogeneity

In classical game theory and AI learning models, researchers often simplify systems by assuming "homogeneity"—the idea that every agent in a specific role (e.g., all "buyers" or all "sellers") shares the exact same belief about opponent behavior.

In reality, traders, drivers, and social agents hold diverse opinions. While previous work used "stochastic approximation" to observe average behavior, these tools could not precisely explain how the initial spread of opinions impacts the long-term destination of the system. This paper provides a mathematical framework to track how the entire distribution of beliefs evolves.

Methodology: A Fluid Dynamics Approach

The authors move away from tracking individual agents, instead treating the population's beliefs as a probability distribution:

  • The PDE Approach: They derive a system of Partial Differential Equations (PDEs), specifically "continuity equations" similar to those in fluid dynamics, to describe how the "mass" of beliefs flows over time.
  • Moment Closure Approximation: To solve these complex PDEs, the authors use "moment closure," focusing on the mean (average belief) and the variance (diversity of opinion) to analyze system stability.
  • Asymptotically Autonomous Systems: Using advanced dynamical systems theory, they prove that a complex, diverse population eventually settles into the same behavior as a uniform one.

Key Insights: Diversity as an Equilibrium Selector

The research yields two striking findings regarding the evolution of beliefs:

  1. Quadratic Homogenization: Beliefs always homogenize over time. The variance of beliefs across a population decays at a rate of $1/t^2$. Regardless of initial polarization, consistent learning from observations eventually leads to consensus.
  2. Diversity as a Feature: In coordination games like the "Stag Hunt," starting with a high variance of beliefs is actually beneficial. If a uniform population starts with the same "wrong" belief, they remain trapped in a mediocre outcome. However, a wide range of initial opinions allows "correct" beliefs to pull the entire group toward the most desirable, high-payoff equilibrium.
Evolution of mean beliefs and probabilities in a Stag Hunt game. Higher initial variance (magenta) leads the population to the high-payoff 'Stag' equilibrium, while low variance (blue) leads to the 'Rabbit' outcome.

Key Results and Convergence

The authors validated their proofs using two benchmarks: a 2-population Stag Hunt and a 5-population Asymmetric Matching Pennies game.

  • Basin of Attraction: In Stag Hunt simulations, increasing the initial variance of beliefs significantly expanded the "basin of attraction" for the optimal equilibrium. Essentially, more initial disagreement makes it easier for the group to eventually find the best collective solution.
  • Competitive Robustness: In competitive games, the system always converges to a unique Quantal Response Equilibrium (QRE), regardless of whether the population starts with consensus or a wild mix of opinions.
Basins of attraction for different initial variances. As the variance $\sigma^2$ increases, the blue region (representing the optimal (S,S) equilibrium) expands, showing that diversity aids coordination.

Limitations and Future Work

While the competitive results are general, the coordination results are currently limited to "star" network structures (one central population connected to several others). Proving these effects for arbitrary, complex networks remains an open challenge. Additionally, the paper assumes agents use Smooth Fictitious Play (SFP); other learning rules, such as certain types of Q-learning, might allow heterogeneity to persist indefinitely, representing a promising path for future research.

Reference: Hu, S., Soh, H., & Piliouras, G. (2023). Heterogeneous Beliefs and Multi-Population Learning in Network Games. arXiv:2301.04929v1 [cs.MA].

Summary updated

Abstract

The effect of population heterogeneity in multi-agent learning is practically relevant but remains far from being well-understood. Motivated by this, we introduce a model of multi-population learning that allows for heterogeneous beliefs within each population and where agents respond to their beliefs via smooth fictitious play (SFP).We show that the system state -- a probability distribution over beliefs -- evolves according to a system of partial differential equations akin to the continuity equations that commonly desccribe transport phenomena in physical systems. We establish the convergence of SFP to Quantal Response Equilibria in different classes of games capturing both network competition as well as network coordination. We also prove that the beliefs will eventually homogenize in all network games. Although the initial belief heterogeneity disappears in the limit, we show that it plays a crucial role for equilibrium selection in the case of coordination games as it helps select highly desirable equilibria. Contrary, in the case of network competition, the resulting limit behavior is independent of the initialization of beliefs, even when the underlying game has many distinct Nash equilibria.
BibTeX
@misc{hu2023heterogeneous,
  author = {Shuyue Hu and Harold Soh and Georgios Piliouras},
  title = {{Heterogeneous Beliefs and Multi-Population Learning in Network Games}},
  year = {2023},
  eprint = {2301.04929},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.04929},
}
Figure