Computing Perfect Bayesian Equilibria, with Application to Empirical Game-Theoretic Analysis

Christine Konicki, Mithun Chakraborty, Michael P. WellmanarXiv 2026 · arXiv · OpenReview

TL;DR

This paper introduces PBE-CFR, a novel algorithm for computing Perfect Bayesian Equilibria (PBE) in complex, imperfect-information games. By adapting the widely-used Counterfactual Regret Minimization (CFR) technique, PBE-CFR can find more refined game solutions than traditional Nash Equilibria, leading to better strategy exploration in empirical game-theoretic analysis.

What Problem Does This Paper Address?

In game theory, especially for games with imperfect information (where players don't know everything that has happened), finding stable outcomes is crucial. Nash Equilibrium (NE) is a fundamental concept, but it can be too broad, allowing for unrealistic strategies. Perfect Bayesian Equilibrium (PBE) is a refinement that adds consistency requirements between a player's strategy and their beliefs about the game's state. However, computing PBE has been computationally challenging, limiting its practical application. This paper addresses this gap by developing a scalable algorithm to compute PBE, making it accessible for analyzing complex games.

Methods

The core contribution is PBE-CFR, an adaptation of the Counterfactual Regret Minimization (CFR) algorithm. While standard CFR aims to minimize regret for finding Nash Equilibria, PBE-CFR is modified to:

  • Minimize "believed regret": Instead of just minimizing expected regret, it considers regret based on a player's beliefs about the game's state.
  • Enforce AGM-consistency: It incorporates a specific consistency criterion (AGM-consistency, based on belief revision theory) to ensure that beliefs are coherent with strategies, even off the equilibrium path.
  • Recursive Belief Updates: The algorithm recursively traverses the game tree, updating both strategies and beliefs at each step.

The authors also provide algorithms for verifying PBE properties (sequential rationality, Bayes' rule, and consistency) and detail the implementation of PBE-CFR.

Datasets

Not discussed in the paper. The authors use parameterized game classes (GENGOOF, PRIVATEGENGOOF, BARGAIN) for experimental evaluation, which are described in detail.

Key Insights and Ideas

  • PBE is more than just NE: PBE's added consistency constraints make it a more refined and potentially more realistic solution concept for imperfect-information games.
  • CFR's adaptability: The success of adapting CFR, a well-established algorithm for NE, to compute PBE highlights the flexibility of regret minimization techniques in game theory.
  • Beliefs matter, especially off-path: The PBE-CFR algorithm's focus on maintaining consistent beliefs even for game states that are unlikely to be reached is key to its refinement capabilities.
  • PBE as a better "solver": Using PBE as a meta-strategy solver (MSS) in empirical game-theoretic analysis (specifically TE-PSRO) leads to higher-quality game models, especially in games with complex information structures.

Key Results

  • Theoretical Guarantees: For two-player zero-sum games, PBE-CFR is proven to converge to a PBE.
  • Scalability: The algorithm's time and space complexity are polynomial in the game size and number of iterations, making it practical for medium-to-large games.
  • Empirical Performance: PBE-CFR demonstrates competent performance in approximating PBE quality and running time on general-sum games.
  • Improved Strategy Exploration: In TE-PSRO, using PBE as the MSS led to better empirical game models compared to using an unrefined NE. The benefit of PBE was more pronounced in games with more complex information structures (e.g., GENGOOF vs. BARGAIN).
  • Runtime: PBE-CFR's runtime is comparable to, though slightly higher than, standard CFR, which is considered a reasonable slowdown given the added complexity of PBE computation.

Limitations and Future Work

  • Computational Cost: While scalable, PBE-CFR is still more computationally intensive than standard CFR due to the additional belief update and consistency checks.
  • Game Class Dependence: The benefit of using PBE as an MSS in TE-PSRO was observed to be dependent on the game's structural properties, suggesting further investigation into which game types benefit most.
  • Future Directions: The authors suggest exploring PBE as an MSS for other game classes (e.g., poker) and investigating further variants of CFR for PBE computation. They also note that their work focuses on two-player games, and extending it to multi-player scenarios would be a natural next step.

Summary updated

Abstract

Perfect Bayesian Equilibrium (PBE) is a refinement of the Nash equilibrium for imperfect-information extensive-form games (EFGs) that enforces consistency between the two components of a solution: agents' strategy profile describing their decisions at information sets and the belief system quantifying their uncertainty over histories within an information set. We present a scalable approach for computing a PBE of an arbitrary two-player EFG. We adopt the definition of PBE enunciated by Bonanno in 2011 using a consistency concept based on the theory of belief revision due to Alchourrón, Gärdenfors, and Makinson. Our algorithm for finding a PBE is an adaptation of Counterfactual Regret Minimization (CFR) that minimizes the expected regret at each information set given a belief system, while maintaining the necessary consistency criteria. We prove that our algorithm is correct for two-player zero-sum games and has a reasonable slowdown in time-complexity relative to classical CFR given the additional computation needed for refinement. We also experimentally demonstrate the competent performance of PBE-CFR in terms of equilibrium quality and running time on medium-to-large non-zero-sum EFGs. Finally, we investigate the effectiveness of using PBE for strategy exploration in empirical game-theoretic analysis. Specifically, we compute PBE as a meta-strategy solver (MSS) in a tree-exploiting variant of Policy Space Response Oracles (TE-PSRO). Our experiments show that PBE as an MSS leads to higher-quality empirical EFG models with complex imperfect information structures compared to MSSs based on an unrefined Nash equilibrium.
BibTeX
@misc{konicki2026computing,
  author = {Christine Konicki and Mithun Chakraborty and Michael P. Wellman},
  title = {{Computing Perfect Bayesian Equilibria, with Application to Empirical Game-Theoretic Analysis}},
  year = {2026},
  eprint = {2602.15233},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.15233},
}
Figure