Lower Bounds on the Complexity of Solving Two Classes of Non-cooperative Games

Ehsan Nekouei, Girish N. Nair, Tansu Alpcan, Robin J. EvansarXiv 2017 · arXiv

Abstract

This paper establishes the fundamental theoretical limits on how quickly a group of players can find a Nash Equilibrium (NE) in a non-cooperative game when their communication is hindered by noise. By bridging game theory with information theory, the authors prove that the complexity of finding an equilibrium is strictly bounded by the "geometric volume" of the action space and the Shannon capacity of the communication channels. This work provides a "speed limit" for Nash-seeking algorithms, regardless of their design.

Introduction

In many modern engineering systems—such as smart power grids, autonomous traffic management, and wireless networks—multiple independent "players" must coordinate to reach a stable state where no one can benefit by changing their strategy alone (the Nash Equilibrium). In practice, these players do not have perfect information; they must communicate their actions and receive feedback, such as utility gradients, through noisy communication channels.

While researchers have developed numerous "Nash-seeking" algorithms, a critical question remained: What is the absolute minimum number of iterations required to find an equilibrium within a certain accuracy? This paper addresses this by establishing lower bounds on the number of iterations needed to reach an $\epsilon$-accurate Nash Equilibrium under various noise conditions.

System Model and Methodology

The authors treat the process of finding a Nash Equilibrium as a communication problem using a framework called Information-Based Complexity. The game is modeled as a distributed system where agents interact with Utility Service Nodes (USN) and Constraint Service Nodes (CSN) to exchange information.

The communication architecture between agents and service nodes (USN/CSN) over noisy channels.

To derive the fundamental limits, the authors utilize several key techniques:

  • Fano’s Inequality: Used to relate the probability of failing to find the NE to the "mutual information" shared between the game's true state and the players' noisy observations.
  • Kolmogorov $\epsilon$-capacity: Measures the "size" or "complexity" of the action space by counting how many distinct strategies can exist within a given set.
  • Fisher Information: Characterizes how much "useful signal" about the utility function's gradient can be extracted from a noisy message, particularly for non-Gaussian noise.
  • Oracle Models: The study analyzes two types of feedback: a "General" model (arbitrary utility information) and a "Partial-Derivative" model (noisy utility gradients).
Summary of variables and notation used in the information-theoretic analysis of game complexity.

Key Insights

Game Theory as Decoding

The most striking insight is framing an equilibrium search as a decoding task. The "true" Nash Equilibrium is treated like a message being sent over a noisy channel; the iterations of a Nash-seeking algorithm are the "bits" used to decode that message.

Geometry and Scaling

The difficulty of a game is tied to the isoperimetric properties (volume and surface area) of the strategy set. A "larger" strategy space naturally requires more information—and thus more iterations—to navigate. For general continuous games, complexity grows logarithmically with the required precision ($1/\epsilon$). However, for games where utility functions satisfy specific differential constraints (Class $\mathcal{G}_\gamma$), the difficulty jumps significantly to polynomial scaling ($1/\epsilon^2$).

The "Hardness" of Games vs. Optimization

The paper suggests that finding a Nash Equilibrium is fundamentally harder than solving a standard convex optimization problem. While a single optimizer can often find a minimum in $O(1/\epsilon)$ iterations under noise, the competitive nature of games pushes the lower bound to $O(1/\epsilon^2)$.

Key Results

  • General Lower Bound: For a general class of games $\mathcal{G}$, the number of iterations $T$ is bounded by: $$T \geq \frac{(1 - \delta) \log \mathcal{M}_{2\epsilon}(\mathcal{S}) - 1}{C_{down}}$$ Where $\mathcal{M}$ is the capacity of the action space and $C_{down}$ is the communication channel capacity. This proves that better communication channels directly translate to faster equilibrium convergence.
  • The $1/\epsilon^2$ Barrier: For games where the "pseudo-gradient" is well-behaved (Class $\mathcal{G}_\gamma$), the authors prove that no algorithm can reach $\epsilon$-accuracy faster than $\Omega(1/\epsilon^2)$ iterations under Gaussian noise.
  • Non-Gaussian Robustness: This $1/\epsilon^2$ scaling is a fundamental limit that holds even if the noise is non-Gaussian, with the specific difficulty determined by the Fisher information of the noise distribution.

Limitations and Future Work

While this work establishes critical bounds, several areas remain for future exploration:

  • Uniqueness of Equilibrium: The proofs rely on game sub-classes with a unique Nash Equilibrium. The complexity of games with multiple or fluid equilibria remains an open challenge.
  • Static vs. Dynamic Games: The study focuses on static games. Extending these lower bounds to dynamic or stochastic games where the environment evolves is a natural next step.
  • Feedback Structures: The tighter $1/\epsilon^2$ bounds are specific to the partial-derivative feedback model. Future research could explore if other types of "oracles" (like second-order information) can break this barrier.

Summary updated

Abstract

This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with $ε$ accuracy. First, we consider the class $\mathcal{G}$ of all $N$-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving $\mathcal{G}$ that depends on the Kolmogorov $2ε$-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in $\mathcal{G}$ which depends on the volume and surface area of the constraint set. We next consider the class of all $N$-player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Our result in the non-Gaussian case is derived by establishing a connection between the Kullback-Leibler distance and Fisher information.
BibTeX
@misc{nekouei2017lower,
  author = {Ehsan Nekouei and Girish N. Nair and Tansu Alpcan and Robin J. Evans},
  title = {{Lower Bounds on the Complexity of Solving Two Classes of Non-cooperative Games}},
  year = {2017},
  eprint = {1701.06717},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.06717},
}
Figure