The Best of Both Worlds in Network Population Games: Reaching Consensus and Convergence to Equilibrium

Shuyue Hu, Harold Soh, Georgios Piliouras

In the world of multi-agent systems (MAS), researchers usually obsess over two distinct types of stability. The first is consensus: how do individuals in a group come to agree on a single belief or behavior? The second is equilibrium: how do different groups interact so that no one has an incentive to change their strategy?

Historically, these have been studied in isolation. A new paper from researchers at the Shanghai AI Lab, NUS, and SUTD bridges this gap. They demonstrate that these two "worlds" are actually two sides of the same coin, governed by the same learning dynamics.

TL;DR

This paper proves that Smooth Fictitious Play (SFP)—a classic game-theoretic learning rule—guarantees both internal consensus within populations and convergence to a global equilibrium across networks. Crucially, it reveals that the level of initial disagreement (variance) within a group acts as a "hidden hand" that selects which equilibrium the system eventually settles into.

What Problem Does This Paper Address?

Most multi-agent learning research assumes "homogeneous" populations, where every agent in a group starts with the same belief. In reality, populations are messy and disordered.

The authors identify a conceptual split:

  1. Intra-population stability (Consensus): Internal cohesion within a group.
  2. Inter-population stability (Equilibrium): Alignment between different groups based on their incentives.

The challenge is twofold: Does a decentralized system of disordered agents naturally reach a consensus even when they are playing competitive (zero-sum) games? And how does the process of reaching that consensus affect the final "Nash-like" outcome of the game?

Methods

The authors model the system as a Network Population Game. Imagine a graph where each vertex is a massive population of agents, and edges represent games played between those populations.

To analyze this, they move away from standard discrete-time simulations and employ Continuity Equations—a tool borrowed from physics used to describe the flow of mass or energy.

  • The Algorithm: They use Smooth Fictitious Play (SFP). In SFP, agents maintain beliefs about what their neighbors will do based on historical averages and respond with a "smoothed" best response (using a logit choice rule).
  • The Innovation: By using partial differential equations (PDEs), they track the evolution of the entire distribution of beliefs over time, rather than just the average belief. This allows them to prove how the "spread" or variance of opinions changes.

Datasets and Benchmarks

As a theoretical and algorithmic paper, it evaluates its findings on two classic game-theoretic benchmarks rather than standard external datasets:

  • 2-Population Stag Hunt: A coordination game used to study "equilibrium selection" (choosing between a safe, low-reward "Hare" strategy or a risky, high-reward "Stag" strategy).
  • 5-Population Asymmetric Matching Pennies: A competitive, zero-sum game played on a line network to test convergence in adversarial settings.

Key Insights and Ideas

  • Consensus is Inevitable: The authors prove that in any network population game using SFP, the variance of beliefs within a population decays to zero at a quadratic rate ($1/t^2$). This means consensus happens regardless of whether the game is cooperative or competitive.
Variance and Distance to (H,H) Equilibrium
  • Variance as a Selection Tool: This is the "aha" moment. In games with multiple equilibria (like Stag Hunt), the initial variance of beliefs determines the outcome.
  • If everyone starts with similar beliefs (low variance), they tend to settle into the "risk-dominant" (safe) equilibrium.
  • If there is high initial disagreement (high variance), the population is more likely to "explore" and settle into the "payoff-dominant" (optimal) equilibrium.
  • The Stability Umbrella: The paper successfully frames consensus as "micro-stability" and equilibrium as "macro-stability," providing a unified mathematical framework for both.

Key Results

  • Convergence Proofs: The authors provide formal proofs that SFP converges to a Quantal Response Equilibrium (QRE)—a version of Nash equilibrium that accounts for bounded rationality—in both weighted zero-sum networks and star-structured potential games.
  • Quadratic Decay: They mathematically demonstrate that internal disagreement vanishes quickly ($Var \propto t^{-2}$), ensuring that the "mean-field" approximation (treating a population as a single agent) is valid in the long run.
Predicted vs Empirical Beliefs and Convergence to (S,S)
  • Equilibrium Selection: In simulations of the Stag Hunt, they showed that by simply increasing the initial variance of beliefs from 0 to 0.1, the "region of attraction" for the optimal (Stag, Stag) equilibrium expanded significantly. The empirical distributions closely matched their theoretical predictions, confirming the dual convergence to both consensus and equilibrium.

Limitations and Future Work

While the paper provides a robust theoretical foundation, there are a few areas for expansion:

  • Network Topology: The convergence proofs for potential games are currently limited to "star" structures. Extending this to arbitrary, complex graphs is a logical next step.
  • Observation Assumptions: The model assumes agents can observe the "average play" of neighboring populations. In massive, real-world systems, agents might only see a small, noisy sample of their neighbors' actions.
  • Beyond SFP: The authors suggest that their "continuity equation" approach could be applied to other learning rules, such as Reinforcement Learning (Q-learning) or Replicator Dynamics, to see if the consensus-equilibrium link holds there as well.

For engineers and researchers in MAS, this paper serves as a reminder that diversity of opinion (variance) isn't just a hurdle to overcome—it might be the very mechanism that allows a system to find the best possible solution.

Summary updated

Abstract

Reaching consensus and convergence to equilibrium are two major challenges of multi-agent systems. Although each has attracted significant attention, relatively few studies address both challenges at the same time. This paper examines the connection between the notions of consensus and equilibrium in a multi-agent system where multiple interacting sub-populations coexist. We argue that consensus can be seen as an intricate component of intra-population stability, whereas equilibrium can be seen as encoding inter-population stability. We show that smooth fictitious play, a well-known learning model in game theory, can achieve both consensus and convergence to equilibrium in diverse multi-agent settings. Moreover, we show that the consensus formation process plays a crucial role in the seminal thorny problem of equilibrium selection in multi-agent learning.
BibTeX
@inproceedings{hu2023best,
  author = {Shuyue Hu and Harold Soh and Georgios Piliouras},
  title = {{The Best of Both Worlds in Network Population Games: Reaching Consensus and Convergence to Equilibrium}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=pXtVyj4R33},
}
Figure