Prices of Anarchy, Information, and Cooperation in Differential Games

Technical Summary: Prices of Anarchy, Information, and Cooperation in Differential Games

Problem Statement
The paper addresses the quantification of efficiency losses and performance variations in non-zero-sum differential games (DGs). While the "price of anarchy" (PoA) is a well-established metric in static games for measuring the inefficiency of Nash equilibria relative to a social optimum, this concept had not been rigorously extended to the dynamic setting of differential games. Furthermore, in dynamic games, the information structure (IS)—specifically whether players act based on open-loop (time-dependent) or closed-loop (state-feedback) information—significantly influences equilibrium outcomes. The authors aim to:

1. Extend the definition of PoA to general differential games.
2. Introduce the "price of information" (PoI) to compare equilibrium performance under different ISs.
3. Introduce the "price of cooperation" (PoC) to measure the benefit or loss to a player adopting altruistic behavior.
4. Derive explicit bounds and closed-form expressions for these indices in a class of scalar linear-quadratic (LQ) differential games, particularly in the large population regime.

Methodology
The authors formulate a general $N$-player differential game framework with state dynamics $\dot{x}(t) = f(x, u_1, \dots, u_N, t)$ and individual cost functions. They define three key indices based on the ratio of costs achieved under different scenarios:

• Price of Anarchy (PoA): The ratio of the worst-case total cost under a Nash equilibrium (NE) to the socially optimal cost (minimized by a central planner).
• Price of Information (PoI): The ratio of the worst-case total cost under one IS (e.g., open-loop) to that under another IS (e.g., closed-loop feedback).
• Price of Cooperation (PoC): The ratio of a player's cost under an altruistic strategy (minimizing a weighted sum of all players' costs) to their cost under the standard non-cooperative NE.

The core analysis focuses on infinite-horizon scalar LQ differential games with quadratic costs and linear dynamics. The authors analyze two specific information structures:

1. Open-Loop (OL): Controls are functions of time only.
2. Closed-Loop (CL) State-Feedback: Controls are functions of the current state and time.

For the CL case, the authors utilize the concept of strongly time-consistent Nash equilibria to avoid informational non-uniqueness. They employ algebraic Riccati equations to characterize the feedback NE. To handle the nonlinearity of the coupled Riccati equations, they transform the problem into an eigenvalue problem involving a specific matrix $M$. For the OL case, they derive explicit solutions using a set of coupled algebraic equations. The analysis is further extended to the "large population regime" ($N \to \infty$) using Taylor series expansions to approximate the solutions.

Key Contributions and Results

1. Extension of PoA to Differential Games:
   The paper successfully defines PoA for DGs. For scalar LQ games with closed-loop feedback, the PoA is characterized by the ratio of the weighted sum of eigenvectors of matrix $M$ to the optimal social cost parameter. The authors derive computable upper bounds for the PoA.

   • In the large population regime, the PoA for feedback games is shown to be bounded and approximated by $\sqrt{N/2}$ (for specific symmetric cases), indicating that efficiency loss grows with the number of players.
   • For open-loop games, a closed-form expression for PoA is obtained.

2. Introduction of Price of Information (PoI):
   The authors define PoI to compare the efficiency of open-loop versus closed-loop feedback structures.

   • A significant theoretical result is the derivation of bounds for the PoI in the large population regime. Specifically, for scalar LQ games, the PoI ($\chi^{OL}_{FB}$) is bounded by:
     $$\frac{\sqrt{2}}{2} \leq \chi^{OL}_{FB} \leq \sqrt{2}$$
   • This implies that in large populations, the open-loop equilibrium can be significantly more efficient (lower cost) than the feedback equilibrium, or vice versa, depending on the specific parameters, but the ratio remains within these constant factors.
   • In the specific application of multiuser rate-based flow control, the authors find that for $N \geq 3$, the open-loop NE yields a lower total cost than the feedback NE, a counter-intuitive result where having less information (open-loop) leads to better system performance.

3. Introduction of Price of Cooperation (PoC):
   The paper defines PoC to quantify the impact of a player placing weight on others' utilities. It establishes that if all players adopt the social weighting vector $\mu$, the resulting Nash equilibrium of the altruistic game coincides with the socially optimal solution (COC).

4. Application to Flow Control:
   The theoretical results are applied to a multiuser rate-based flow control model (bottleneck link congestion).

   • Numerical examples confirm that as $N$ increases, the PoA increases (efficiency loss grows).
   • The PoI analysis reveals that open-loop strategies often outperform feedback strategies in terms of total cost in this specific symmetric setting, with the ratio converging to $\sqrt{2}/2$ as $N \to \infty$.
   • The paper also investigates normalized flow control dynamics where a normalization factor $f(N)$ is introduced. It proves that the PoA and PoI indices are independent of this normalization factor.

Significance and Claims
The paper claims to provide the first systematic extension of the price of anarchy and the introduction of the price of information and cooperation specifically within the framework of differential games. The significance lies in:

• Quantifying Dynamic Inefficiency: Providing a metric to measure how far non-cooperative dynamic equilibria deviate from social optimality.
• Information Structure Impact: Demonstrating that in dynamic games, more information (closed-loop feedback) does not necessarily lead to better outcomes for the system or individual players, contrasting with static team problems where more information is always beneficial.
• Scalability: Offering explicit bounds and approximations for large-scale systems (large $N$), which is relevant for applications in communication networks and economics where the number of agents is large.
• Design Implications: The bounds on PoI suggest that game designers (e.g., in network resource allocation) can use access control or pricing mechanisms to steer the system toward a desired information structure to optimize performance.

The authors conclude that while the results are derived for scalar LQ games, the concepts of PoA, PoI, and PoC are general. They identify future work in extending these results to non-scalar differential games and computing these indices for specific models in communication networks and economics.