Game-to-Real Gap: Quantifying the Effect of Model Misspecification in Network Games

Technical Summary: Game-to-Real Gap in Network Games

Problem Statement
Game-theoretic models are standard tools for predicting collective behavior in multi-agent systems, such as autonomous driving or smart grid management. However, a critical limitation exists in practical applications: agents often operate with heterogeneous and misspecified models of the environment and other agents. While traditional game theory assumes a shared understanding of the game primitives (preferences, capabilities, and interaction structures), real-world agents may rely on different conjectured models. When these agents independently compute strategies (e.g., Nash equilibria) based on their local, potentially inaccurate models, the resulting joint action may deviate significantly from any single agent's prediction. This misalignment leads to a degradation in realized performance compared to the expected cost. The paper addresses the lack of rigorous metrics to quantify this discrepancy, specifically asking how sensitive an agent's predicted performance is to model misspecifications in the presence of other agents' differing models.

Methodology
The authors formalize the concept of conjectured games, where each agent $i$ possesses a predictive model $G^{(i)}$ consisting of a game structure and a solution concept (specifically, the Nash equilibrium). The agent computes their action $u^{(i)}_i$ based on this local model. The game-to-real gap is defined as the difference between the utility an agent actually obtains in the realized environment ($J_i(u^\circ)$) and the utility they predicted based on their own model ($J_i(u^{(i)})$), where $u^\circ$ is the joint action formed by all agents deploying their locally optimal strategies.

The analysis focuses on quadratic network games, where an agent's cost function comprises:

1. A quadratic term for the magnitude of their local strategy.
2. An interaction term weighted by an interaction matrix $P$.
3. An inner product with an external shock vector $\epsilon$.

The authors investigate two primary sources of misspecification:

1. Heterogeneous Shock Forecasts: Agents have different estimates of the external shock $\epsilon$.
2. Misaligned Interaction Networks: Agents have different conjectures about the interaction matrix $P$.

To analyze the gap, the paper employs linear algebraic techniques involving the Leontief matrix $L = (I - P)^{-1}$ and introduces novel network centrality measures that specifically account for the overlap in network effects between agents with differing models.

Key Contributions

1. Definition of the Game-to-Real Gap: The paper formally introduces the metric $J_i(u^\circ) - J_i(u^{(i)})$ to quantify the performance loss due to model misspecification in multi-agent settings.
2. Arbitrarily Large Gaps: The authors prove that even with arbitrarily small misspecifications in either the external shock parameters or the interaction matrix, the game-to-real gap can be made arbitrarily large. This sensitivity is particularly high when the minimum singular value of $(I - P)$ is small (e.g., in networks with near-unitary edge weights).
3. Novel Centrality Measures:
   • Shock Misspecification Centrality ($B_{i,j}$): A new metric defined as $L^\top_{i,-} P_{i,j} L_{j,-}$, which characterizes the gap arising from heterogeneous shock forecasts.
   • Interaction-Graph Misspecification Centrality ($C_{i,j}$): A metric characterizing the gap arising from misaligned interaction networks.
     These measures allow for the exact closed-form evaluation of the game-to-real gap, revealing that the impact of misspecification depends on the overlap of centrality profiles between agents, rather than just the absolute centrality of the misaligned agent.
4. Counterintuitive Findings on Centrality: The analysis demonstrates that standard centrality measures (like Bonacich centrality) fail to capture the effects of model misspecification. An agent with high Bonacich centrality does not necessarily cause the largest performance degradation if misaligned; rather, the gap is driven by the specific structural overlap between the agents' conjectured models.

Results

• Theoretical Bounds: The paper provides upper bounds for the game-to-real gap. For shock misspecification, the gap is bounded by a term proportional to the square of the inverse of the minimum singular value of $(I - P)$, scaled by the magnitude of the shock differences and the interaction matrix norms. Similar bounds are derived for interaction matrix misspecification.
• Exact Characterization: Theorem 1 and Proposition 3 provide exact formulas for the gap in terms of the new centrality measures. For instance, under heterogeneous shocks, the gap for agent $i$ is the sum over all other agents $j$ of $\epsilon^{(i)\top} B_{i,j} (\epsilon^{(i)} - \epsilon^{(j)})$.
• Numerical Experiments:
  • Misaligned Shocks: In a specific network example, the authors show that an agent (Agent 4) suffers a larger performance loss when misaligned with a low-centrality node (Node 3) compared to a high-centrality node (Node 5). This confirms that the "overlap" in network effects, not just node importance, dictates the gap.
  • Monte Carlo Simulations: Simulations on random networks show that as the bound on misalignment increases, the spread of the relative difference between predicted and realized costs grows. Interestingly, when only network structure is misaligned, the median realized cost difference shows a slight downward trend (agents sometimes perform better than predicted), whereas simultaneous misalignment of both shocks and networks tends to increase the likelihood of worse-than-predicted performance.

Significance
The paper claims that the game-to-real gap is a critical metric for understanding the robustness of game-theoretic planning in multi-agent systems. The findings underscore that standard network centrality measures are insufficient for predicting the impact of model misspecification. By introducing new structural metrics (Shock and Interaction-Graph Misspecification Centrality), the work provides a framework for engineers and autonomous agents to better assess the risks associated with heterogeneous models. The results suggest that in systems where agents must plan ahead with limited opportunity for revision (e.g., autonomous racing, distributed energy management), accounting for the specific structural overlaps between agents' models is essential for ensuring robust performance, as small modeling errors can lead to arbitrarily large deviations from expected outcomes.