Simultaneous Nash Equilibrium Seeking and Social Cost Minimization in Graphical $N$-coalition Non-cooperative Games

Maojiao Ye, Guoqiang Hu, Frank L. Lewis, Lihua XiearXiv 2017 · arXiv

Abstract

This paper aims to reduce the communication and computation costs of the Nash equilibrium seeking strategy for the $N$-coalition non-cooperative games proposed in [YEAT]. The objective is achieved in two manners: 1). the Nash equilibrium seeking strategy is re-designed and a new Nash equilibrium seeking algorithm that yields less communication and computation costs, is proposed. 2). an interference graph is introduced to describe the interactions among the agents in each coalition. The newly proposed seeking strategy is then adapted for the $N$-coalition non-cooperative games on the interference graph. A sufficient condition on the interference and communication graphs is provided to ensure that the players' actions converge to the Nash equilibrium by utilizing the proposed seeking strategy. Several special cases where there is only one coalition and/or there are coalitions with only one agent are considered. The results for the special cases demonstrate that the proposed seeking strategy achieves the solution seeking for non-cooperative games, social cost minimization problems and single-agent optimization problems in a unified framework. Numerical examples are presented to support the analytical results.

Introduction: Addressing the Curse of Dimensionality

In complex multi-agent systems—such as smart grids, autonomous transport networks, or cloud computing clusters—agents often organize into coalitions. Within these groups, agents cooperate to minimize a collective "social cost," while the coalitions themselves compete against one another in a non-cooperative game. Finding the Nash Equilibrium (NE)—the steady state where no coalition can benefit by unilaterally changing its strategy—is a significant challenge.

Previous methods for NE seeking were often computationally prohibitive for large-scale systems. These approaches typically assumed that every agent's cost function depended on the actions of every other agent within their coalition, forcing agents to track and communicate massive amounts of redundant data. This paper tackles this "curse of dimensionality" by asking: What if agents only communicate with those who actually affect their costs?

The Unified Strategy and Interference Graphs

The authors propose a "Unified Strategy" built on two main pillars: interference graphs and distributed gradient play with consensus.

Interference Graphs ($G_I$)

Instead of assuming a fully connected network of dependencies, the authors introduce an interference graph to describe the specific interactions between agents. If agent A’s action does not influence agent B’s local cost function, they do not need to "interfere" or track each other's variables. This mapping of physical or economic sparsity into the algorithm's design allows the number of auxiliary variables an agent must manage to drop from the total number of agents in the coalition to just the number of its neighbors in the interference graph.

Illustration of a coalition structure and its corresponding interaction graph.

Distributed Gradient Play

The algorithm utilizes a consensus-based protocol where agents maintain auxiliary variables to estimate the gradients of their cost functions. In this approach, agents only generate and communicate these variables for the specific neighbors identified in the interference graph. Furthermore, the authors define specific communication sub-structures ($G_{Ck}^i$) required to ensure that gradient information flows correctly between interfering agents. This framework is "unified" because it simplifies into standard problems depending on the configuration:

  • Social Cost Minimization: When there is only one coalition.
  • Standard Non-cooperative Game: When every coalition consists of only one agent.
  • Single-agent Optimization: When there is one coalition with one agent.

Numerical Validation and Key Results

The theory was validated using numerical examples, including a simulation of a congestion control game in ad hoc wireless networks. In these simulations, agents (users) attempted to send data through network nodes while minimizing costs related to delay and capacity.

Convergence and Robustness

Using Lyapunov stability analysis, the authors proved that the agents' actions converge to a neighborhood of the Nash Equilibrium, controlled by a step-size parameter $\delta$. Simulations demonstrated that even when theoretical assumptions like "strict monotonicity" were intentionally violated, the algorithm successfully found the NE, suggesting high practical robustness.

Convergence of agent actions over time toward the Nash Equilibrium.

Efficiency Gains

The results confirmed that by leveraging sparse interference graphs, agents can ignore a significant portion of the coalition's state. This leads to substantially lower computation and communication overhead compared to traditional methods, making the strategy viable for large-scale decentralized systems.

Conclusion and Future Directions

This research provides a scalable framework for finding Nash Equilibria in multi-coalition games by exploiting the inherent sparsity of agent interactions. While the current proof guarantees convergence to a neighborhood of the NE, future work may explore conditions for exact exponential convergence. Additionally, extending the theory from undirected to directed graphs would better reflect real-world communication constraints in sensor and data networks.

Summary updated

Abstract

This paper aims to reduce the communication and computation costs of the Nash equilibrium seeking strategy for the $N$-coalition non-cooperative games proposed in [YEAT]. The objective is achieved in two manners: 1). the Nash equilibrium seeking strategy is re-designed and a new Nash equilibrium seeking algorithm that yields less communication and computation costs, is proposed. 2). an interference graph is introduced to describe the interactions among the agents in each coalition. The newly proposed seeking strategy is then adapted for the $N$-coalition non-cooperative games on the interference graph. A sufficient condition on the interference and communication graphs is provided to ensure that the players' actions converge to the Nash equilibrium by utilizing the proposed seeking strategy. Several special cases where there is only one coalition and/or there are coalitions with only one agent are considered. The results for the special cases demonstrate that the proposed seeking strategy achieves the solution seeking for non-cooperative games, social cost minimization problems and single-agent optimization problems in a unified framework. Numerical examples are presented to support the analytical results.
BibTeX
@misc{ye2017simultaneous,
  author = {Maojiao Ye and Guoqiang Hu and Frank L. Lewis and Lihua Xie},
  title = {{Simultaneous Nash Equilibrium Seeking and Social Cost Minimization in Graphical $N$-coalition Non-cooperative Games}},
  year = {2017},
  eprint = {1708.02394},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.02394},
}
Figure