Common Information based Markov Perfect Equilibria for Linear-Gaussian Games with Asymmetric Information

Abhishek Gupta, Ashutosh Nayyar, Cedric Langbort, Tamer BasararXiv 2014 · arXiv

Introduction

In the realm of control theory and game theory, dynamic games provide a powerful framework for modeling interactions between multiple agents over time. However, a significant hurdle arises when players possess different information sets—a condition known as asymmetric information. This paper, published by researchers from the University of Illinois and USC, addresses the computational and conceptual difficulties of finding stable strategies in such environments. By leveraging a "common information" approach, the authors provide a tractable method for identifying Nash equilibria in complex, asymmetric dynamic games.

The Problem of Asymmetric Information

In symmetric dynamic games, where all players share the same observations, established tools like dynamic programming can be used to find Nash equilibria. In contrast, asymmetric games—common in high-frequency trading, power grid management, and cyber-physical security—create a "belief nightmare."

When information is asymmetric, Player A must form a belief about the state of the system, which depends on Player B’s actions. However, Player B’s actions depend on Player B’s own beliefs, which in turn depend on Player B’s estimation of Player A’s beliefs. This infinite regress of "beliefs about beliefs" typically makes finding an equilibrium computationally impossible (often PSPACE-hard).

The Common Information Approach

The authors propose a novel framework to bypass this complexity by transforming the asymmetric game into a more manageable symmetric one. The methodology follows five key steps:

  1. Identification of Common Knowledge: The researchers define "common information" as the subset of data, such as past public observations and actions, that all players are guaranteed to know at any given time.
  2. Virtual Player Transformation: The game is reimagined from the perspective of "virtual players" who only observe this common information. Instead of choosing specific physical actions, these virtual players select "prescriptions"—functions that map a player's private, local information to a specific action.
  3. Symmetric Transformation: By focusing on these prescriptions within the common information space, the asymmetric game is converted into a symmetric game of perfect recall.
  4. Backward Induction: Because the transformed game is symmetric, the authors can apply backward induction (a dynamic programming-like approach) to solve the game sequentially from the final time step to the first.
  5. LQG Specialization: The framework is specifically applied to Linear-Quadratic-Gaussian (LQG) systems. In this setting, the authors demonstrate that the optimization problem simplifies into a sequence of solvable linear equations.

Key Insights and Equilibrium Refinement

A critical component of this framework is the Common Information Based Markov Perfect Equilibrium (CIB-MPE). This is a specific refinement of the Nash equilibrium, designed to be both robust and computationally structured.

One of the paper's core assumptions is that a player’s belief about the system state should be independent of the strategies used by other players. This "no deception" constraint prevents players from taking sub-optimal actions solely to manipulate the beliefs of others. While this limits the scope of the equilibrium to non-signaling strategies, it ensures that the resulting equilibrium is tractable and unique in the LQG case.

Interestingly, the authors observe that more information is not always beneficial for solvability. In their illustrative examples, certain information structures lead to a continuum of Nash equilibria, making it difficult to predict agent behavior. The CIB-MPE approach successfully identifies a unique, structured solution among these possibilities.

Results for LQG Systems

The paper provides several rigorous proofs regarding the application of their method to LQG games:

  • Existence and Uniqueness: Under specific conditions related to the spectral radius of the system matrices, a unique CIB-MPE is guaranteed to exist.
  • Computational Efficiency: Unlike general asymmetric games, the CIB-MPE for LQG systems can be computed inexpensively using standard linear algebra techniques.
  • Subclass Identification: The authors prove that the CIB-MPE is a subset of the broader class of Nash equilibria. They demonstrate that while other Nash equilibria may exist, they cannot be recovered via the common information approach, highlighting the CIB-MPE as a distinct and valuable refinement.

Discussion and Future Work

While the common information framework provides a breakthrough in tractability, it has limitations. The "no deception" requirement means the framework is currently unsuitable for games where "signaling" (conveying private information through actions) is a primary tactic. Additionally, while the theory extends logically to $N$ players, the complexity of defining common versus private information splits increases significantly.

Future research directions include exploring games with non-monotonic information (where players might forget information) and investigating the practical communication overhead required to share "prescriptions" in real-time distributed systems.

Summary updated

BibTeX
@misc{gupta2014common,
  author = {Abhishek Gupta and Ashutosh Nayyar and Cedric Langbort and Tamer Basar},
  title = {{Common Information based Markov Perfect Equilibria for Linear-Gaussian Games with Asymmetric Information}},
  year = {2014},
  eprint = {1401.4786},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.4786},
}

Loading related content...

Figure