Interleaved Information Structures in Dynamic Games: A General Framework with Application to the Linear-Quadratic Case

1. Problem Statement

In noncooperative dynamic game theory, computing Nash equilibria is fundamentally dependent on the information structure—the specific set of information available to each agent at every decision-making timestep.

• Current Limitations: Existing literature primarily focuses on two canonical extremes:
  • Open-Loop: Agents observe only the initial state and plan a fixed sequence of actions.
  • Feedback: Agents observe the full state of all agents at every timestep.
• The Gap: Real-world multi-agent scenarios often exhibit interleaved information structures, where agents observe only a subset of other agents' states at specific timesteps. These structures are neither fully open-loop nor fully feedback.
• The Challenge: There is currently no systematic framework to model or solve dynamic games under arbitrary interleaved information structures. Specifically, for Linear-Quadratic (LQ) games, it is unclear how to derive the Riccati-like equations necessary to characterize Nash equilibria when information is partially and asymmetrically shared.

2. Methodology

The authors propose a novel framework based on Mathematical Program Networks (MPNs) to address this gap.

A. Mathematical Program Networks (MPNs)

An MPN is a directed graph where:

• Nodes represent individual mathematical optimization problems (one for each agent at each timestep).
• Edges encode the interdependencies between these problems based on the information structure.
• Solution Graph: A solution is defined as a vector of decisions that is optimal for every node, given the decisions of its "children" (nodes it depends on).

B. Formulating Interleaved Games as MPNs

The paper maps dynamic games to MPNs by analyzing the dependencies induced by information flow:

1. Temporal Dependencies: An agent's decision at time $t$ depends on its own future decisions (standard in dynamic programming).
2. Informational Dependencies:
   • If Agent $i$ observes Agent $j$ at time $t$, Agent $i$'s optimization problem at time $t+1$ depends on Agent $j$'s decision at time $t$.
   • This creates cross-agent edges in the MPN (e.g., an edge from Node $N_j^t$ to Node $N_i^{t+1}$).
3. Variable Augmentation: To handle these dependencies, the decision variables at a node are augmented to include "reasoning" variables (estimates) of other agents' future actions if those agents are not directly observed but influence the current agent's future state.

C. Deriving Equilibria for LQ Games

For Linear-Quadratic (LQ) games, the authors leverage the convexity of the cost functions and affine constraints to:

1. Construct the solution graph for each node in the MPN.
2. Apply Karush-Kuhn-Tucker (KKT) conditions to each node's optimization problem.
3. Concatenate these KKT conditions across all nodes and time steps.
4. Solve the resulting system of coupled equations, which take the form of Riccati-like equations, to find the Nash equilibrium strategies.

3. Key Contributions

The paper makes two primary contributions:

1. General Modeling Framework:

   • Introduces a systematic method to model dynamic games with arbitrary interleaved information structures as MPNs.
   • Demonstrates that MPNs naturally capture the complex interdependencies arising when agents observe different subsets of the system state at different times. This generalizes previous work that was limited to hierarchical or fully symmetric information.

2. Analytical Solution for LQ Games:

   • Develops a procedure to derive Riccati-like equations for $N$-agent LQ games under arbitrary interleaved information.
   • Unlike standard feedback or open-loop cases, these equations account for the specific topology of the information graph (who observes whom and when).
   • Provides a constructive algorithm: Formulate MPN $\rightarrow$ Construct Solution Graphs $\rightarrow$ Derive KKT conditions $\rightarrow$ Solve coupled Riccati equations.

4. Results and Illustrative Example

The authors validate their framework using a three-agent LQ game with a cyclic information structure:

• Setup:
  • Agent 1 observes Agent 2.
  • Agent 2 observes Agent 3.
  • Agent 3 observes Agent 1.
  • No agent observes themselves directly in the "other" sense (asymmetric observation).
• Execution:
  • They constructed the MPN with nodes representing each agent at each of the 3 timesteps.
  • They defined the decision variables to include estimates of the unobserved agents' future actions.
  • They derived the Lagrangian for each node and established the KKT conditions.
• Outcome:
  • The analysis showed that specific Lagrange multipliers (representing the cost of information constraints) vanish or simplify under the cyclic structure.
  • The resulting system of equations successfully characterized the Nash equilibrium, proving that the MPN approach can handle non-canonical, cyclic information flows where traditional methods fail.

5. Significance

• Bridging Theory and Practice: The framework moves dynamic game theory closer to realistic multi-agent applications (e.g., autonomous vehicle platoons, distributed sensor networks, or economic markets) where full state observability is rare and information is often partial and asymmetric.
• Unified Approach: It unifies the treatment of open-loop, feedback, and mixed information structures under a single mathematical formalism (MPNs).
• Computational Tractability: By reducing the problem to a system of Riccati-like equations for LQ games, the paper provides a computationally feasible path to solving complex equilibrium problems that were previously intractable or required heuristic approximations.
• Foundation for Future Work: The authors identify this as a foundational step, suggesting future research into non-LQ settings and scenarios where the information structure itself evolves dynamically based on agent decisions.