Bayes correlated equilibria and no-regret dynamics

Kaito FujiiarXiv 2023 · arXiv · OpenReview

Abstract

This paper explores equilibrium concepts for Bayesian games, which are fundamental models for games with incomplete information. We identify three desirable properties for such equilibria: natural realization via a mediator, efficient distributed computation, and approximately maximized social welfare (measured by the Price of Anarchy). We characterize various non-equivalent extensions of correlated equilibria, collectively known as Bayes correlated equilibria, and identify a specific class that satisfies all three properties. Our main contribution is the introduction of "untruthful swap regret," a new learning objective for Bayesian settings. We provide a polynomial-time algorithm to minimize this regret, proving that decentralized play converges to a communication equilibrium with a bounded Price of Anarchy. Our results provide tight regret bounds and extend the smoothness framework from Bayes-Nash equilibria to this broader, more tractable class of equilibria.

Introduction: The Complexity of Bayesian Games

In games of complete information, the path from individual learning to collective stability is well-mapped: players using no-regret learning algorithms naturally settle into a correlated equilibrium. Furthermore, for "smooth" games, these equilibria are guaranteed to maintain high social welfare relative to the optimum, a concept known as the Price of Anarchy (PoA).

However, Bayesian games—where players possess private information or "types," such as in auctions—present a significantly more complex landscape. In these settings, the concept of a correlated equilibrium does not have a single, obvious extension. Instead, researchers have proposed several non-equivalent versions, including communication equilibria, strategic-form correlated equilibria (CE), and agent-normal-form CE.

The Landscape of Bayesian Equilibria

Understanding the relationship between these concepts is critical for identifying which equilibrium is most suitable for algorithmic implementation and welfare analysis.

Venn diagram illustrating the containment relationships between various Bayesian equilibrium concepts.

As illustrated in the figure above, these concepts form a nested hierarchy. The paper identifies the intersection of communication equilibria and agent-normal-form correlated equilibria as a "sweet spot." This class is narrow enough to allow for robust Price of Anarchy bounds using smoothness arguments, yet broad enough to be reached through decentralized, no-regret learning dynamics. Notably, communication equilibria can be realized by a mediator who collects private types from players and returns correlated action recommendations.

Untruthful Swap Regret and Algorithmic Reduction

To bridge the gap between learning and these equilibrium concepts, the author introduces untruthful swap regret. In a standard complete-information setting, swap regret only considers deviations where a player changes their action. In a Bayesian setting, a strategic player might also lie about their private type.

Untruthful swap regret forces players to consider complex deviations: reporting a false type to the mediator and then potentially swapping the action recommended based on that false report. The paper provides a sophisticated three-step reduction to minimize this regret:

  1. $\Phi$-Regret Interpretation: Minimizing untruthful swap regret is framed as an instance of regret against a set of transformations ($\Phi$-regret).
  2. Fixed-Point Computation: The problem is reduced to finding a strategy that remains stable under these transformations.
  3. Decomposition: The complex problem is broken down into multiple "external regret" sub-problems, which can be solved using standard algorithms like Multiplicative Weights.

Key Results and Theoretical Guarantees

The paper establishes several landmark results for algorithmic game theory in incomplete information settings:

  • Convergence and Efficiency: The proposed algorithm (Algorithm 2) is polynomial in the number of players, types, and actions. If all players minimize untruthful swap regret, their empirical distribution of play converges to a communication equilibrium.
  • Tight Regret Bounds: The author proves an upper bound on regret of $O(\sqrt{T \log |\Theta_i|})$, where $|\Theta_i|$ is the number of types. Using martingale analysis and Doob’s optional stopping theorem, they prove a matching lower bound, demonstrating that the algorithm is optimally efficient.
  • Price of Anarchy Extension: The research extends the "smoothness" framework—originally restricted to Bayes-Nash equilibria—to communication equilibria. For $(\lambda, \mu)$-conditionally smooth games, the social welfare is guaranteed to be at least $\frac{\lambda}{1+\mu}$ of the optimum.

Conclusion and Future Directions

By identifying a computationally tractable equilibrium class and providing the tools to reach it, this work settles a significant question regarding the stability and efficiency of Bayesian games. Future work remains in adapting these algorithms for continuous type and action spaces, which are common in real-world economic mechanisms, and exploring whether similar efficiency can be achieved for the even more restrictive class of strategic-form correlated equilibria.

Summary updated

Abstract

This paper explores equilibrium concepts for Bayesian games, which are fundamental models of games with incomplete information. We aim at three desirable properties of equilibria. First, equilibria can be naturally realized by introducing a mediator into games. Second, an equilibrium can be computed efficiently in a distributed fashion. Third, any equilibrium in that class approximately maximizes social welfare, as measured by the price of anarchy, for a broad class of games. These three properties allow players to compute an equilibrium and realize it via a mediator, thereby settling into a stable state with approximately optimal social welfare. Our main result is the existence of an equilibrium concept that satisfies these three properties. Toward this goal, we characterize various (non-equivalent) extensions of correlated equilibria, collectively known as Bayes correlated equilibria. In particular, we focus on communication equilibria (also known as coordination mechanisms), which can be realized by a mediator who gathers each player's private information and then sends correlated recommendations to the players. We show that if each player minimizes a variant of regret called untruthful swap regret in repeated play of Bayesian games, the empirical distribution of these dynamics converges to a communication equilibrium. We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight up to a multiplicative constant. As a result, by simulating the dynamics with our algorithm, we can efficiently compute an approximate communication equilibrium. Furthermore, we extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes Nash equilibria to equilibria obtained by the proposed dynamics.
BibTeX
@misc{fujii2023bayes,
  author = {Kaito Fujii},
  title = {{Bayes correlated equilibria and no-regret dynamics}},
  year = {2023},
  eprint = {2304.05005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.05005},
}

Loading related content...

Figure