Problems with the EFG formalism: a solution attempt using observations

Vojtech Kovarík, Viliam LisýarXiv 2019 · arXiv

Abstract

For decades, the Extensive-Form Game (EFG) has served as the foundational mathematical model for games of imperfect information. However, as modern AI techniques move toward online game solving and sub-game decomposition, the limitations of the EFG formalism have become increasingly apparent. This paper presents a "post-mortem" of an attempt to modernize the EFG by introducing a formal layer of observations. While the authors propose several technical patches, they ultimately conclude that the EFG model is fundamentally ill-equipped for these modern requirements, suggesting a shift toward Partially Observable Stochastic Games (POSGs).

Introduction

In the study of multi-agent systems and competitive games like Poker, the Extensive-Form Game (EFG) has long been the gold standard. It provides a structured way to represent sequences of actions and the private information available to players. However, the EFG has a significant conceptual blind spot: it focuses almost exclusively on what a player knows at the specific moment it is their turn to act. It lacks a native mechanism to describe when information is received or what a player observes while waiting for an opponent to move.

This gap has become a bottleneck for modern AI breakthroughs such as DeepStack and Libratus. these systems rely on "online decomposition"—the ability to break a massive game tree into smaller, manageable sub-games during play. Such techniques require concepts like public states and augmented information sets, which are not natively supported by the classical EFG. This paper attempts to bridge the gap between traditional Game Theory and the Multi-Agent Reinforcement Learning (MARL) community by formalizing an observation-based EFG.

The Observation-Based Framework

The authors propose modernizing the EFG by treating observations as first-class citizens. Their methodology involves several key components:

  1. Observation Functions: The introduction of functions that provide players with "elementary observations" at every state transition in the game, regardless of whose turn it is.
  2. History Tracking: The exploration of how players maintain their internal state, comparing "Set" variants (where observations are unordered) to "Sequence" variants (where the timing of observations is preserved).
  3. Technical Desiderata: The authors identify four essential properties for a robust game model:
  4. Consistency: The new model must match the information structure of the original EFG.
  5. Acting-Player Separation: Players must clearly know when it is their turn to act based solely on their observations.
  6. Stability: The information structure should not collapse or become mathematically inconsistent when new, redundant observations are added.
  7. Perfect Recall: Ensuring players never forget previous observations or actions.

To address instances where the mathematical structure breaks, the authors propose "Stable Modifications," which involve inserting "dummy nodes" (no-op actions) into the game tree to maintain the required properties.

Theoretical Analysis and Toy Domains

The paper utilizes several theoretical domains to highlight the failures of the current EFG standard:

  • Limit Texas Hold’em: The authors demonstrate that standard EFG definitions of "public states" often fail to align with human intuition regarding game rounds (e.g., the transition from Pre-flop to Flop), complicating the process of game decomposition.
  • The Sneaking Game: This custom counter-example shows how "immediate self-observation"—a player observing the result of their own action—can break the consistency of a standard EFG if the player's skill level influences the outcome.
  • Unfair Matching Pennies: A specialized domain used to test the limits of the proposed notation in the presence of asymmetric information.

Key Insights and the "POSG Pivot"

The research reveals a fundamental tension in game modeling. In real-world scenarios, information flow is continuous; players observe an opponent's hesitation, the physical movement of a dealer, or simply the passage of time. Classical EFGs struggle to capture this "continuous" flow without becoming prohibitively complex.

One of the most significant technical findings is an Impossibility Result (Corollary 4.5). The authors prove that it is impossible to simultaneously achieve consistency, acting-player separation, and stability within an EFG without modifying the underlying game tree. While they provide a "canonical recipe" for building a consistent observation-based model, it requires the addition of dummy nodes that can double the size of the game tree in the worst-case scenario.

Ultimately, the authors reach a surprising conclusion: rather than continuing to "patch" the EFG with increasingly complex layers of observations and dummy nodes, it is more productive to migrate to the Partially Observable Stochastic Game (POSG) framework. In POSGs, observations are natively integrated, making them a more natural fit for modern MARL and online solving algorithms.

Conclusion and Future Work

The paper serves as a cautionary tale for researchers attempting to extend aging formalisms beyond their original intent. While the EFG remains useful for static analysis, the authors argue that the future of dynamic, large-scale game solving lies in Factored-Observation Games (a subset of POSGs). Future research should focus on developing robust tools for decomposition and online solving within the POSG framework, rather than attempting to reconcile the inherent rigidities of the Extensive-Form Game.

Summary updated

Abstract

We argue that the extensive-form game (EFG) model isn't powerful enough to express all important aspects of imperfect information games, such as those related to decomposition and online game solving. We present a principled attempt to fix the formalism by considering information partitions that correspond to observations. We show that EFGs cannot be "fixed" without additional knowledge about the original task, and show how to extend the EFG model under this assumption. However, during our investigation, we ultimately concluded that a better solution is to abandon EFGs entirely and instead adopt a model based on partially observable stochastic games. The primary contribution of the text thus lies in exposing the problems with EFGs and presenting a detailed study on introducing imperfect information by adding observations into an underlying perfect-information model.
BibTeX
@misc{kovarik2019problems,
  author = {Vojtech Kovarík and Viliam Lisý},
  title = {{Problems with the EFG formalism: a solution attempt using observations}},
  year = {2019},
  eprint = {1906.06291},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.06291},
}
Figure