Distributed convergence to Nash equilibria by adversarial networks

Bahman Gharesifard, Jorge Cortés

Abstract

This paper considers a class of strategic scenarios in which two networks of agents have opposing objectives with regards to the optimization of a common objective function. In the resulting zero-sum game, individual agents collaborate with neighbors in their respective network and have only partial knowledge of the state of the agents in the other network. For the case when the interaction topology of each network is undirected, we synthesize a distributed saddle-point strategy and establish its convergence to the Nash equilibrium for the class of strictly concave-convex and locally Lipschitz objective functions. We also show that this dynamics does not converge in general if the topologies are directed. This justifies the introduction, in the directed case, of a generalization of this distributed dynamics which we show converges to the Nash equilibrium for the class of strictly concave-convex differentiable functions with locally Lipschitz gradients. The technical approach combines tools from algebraic graph theory, nonsmooth analysis, set-valued dynamical systems, and game theory.

Introduction

In classical game theory, players are often modeled as monolithic entities with perfect internal coordination. However, modern applications—ranging from sensor networks and power grids to robotic swarms—frequently involve "players" that are actually distributed networks of individual agents. This paper addresses the challenge of reaching a Nash equilibrium in a two-network zero-sum game where agents must rely on local communication and limited observations of their adversaries.

Problem Formulation

The authors investigate a scenario involving two competing teams: Team A, which seeks to maximize a common objective function, and Team B, which seeks to minimize it. This setup introduces three primary constraints:

  1. Distributed Information: No single agent possesses the complete state of their own team or the opposing team.
  2. Local Interaction: Communication is restricted to immediate neighbors within each network.
  3. Adversarial Uncertainty: Agents only observe a subset of the opposing team's agents, defined by an "engagement graph."
Interaction topology between two adversarial networks $\Sigma_1$ and $\Sigma_2$ through an engagement graph $\Sigma_{\text{eng}}$.

The goal is to design a distributed coordination protocol—a set of differential equations—that allows the entire system to converge to the Nash equilibrium, where neither team can improve its outcome by unilaterally changing its strategy.

Distributed Saddle-Point Dynamics

The proposed methodology centers on a distributed saddle-point strategy that adapts to the underlying communication topology. A core innovation is the "lifting" of the standard game into a higher-dimensional space. In this space, every agent maintains its own local version of the game state, and the authors identify specific conditions (Lemma 3.2) under which solving this distributed game is equivalent to solving the original global game.

Undirected vs. Directed Topologies

For networks with undirected (bidirectional) communication, the authors employ a consensus-based gradient flow. Each agent maintains an estimate of the network state and an auxiliary variable to ensure agreement across the network while simultaneously moving toward the saddle point.

However, the paper demonstrates that this standard strategy can fail on directed graphs (digraphs), potentially leading to oscillations or divergence. This instability arises because the eigenvalues of the network Laplacian in directed graphs can have large imaginary parts, causing the gradient dynamics to "spiral" away from the equilibrium. To address this, the authors introduce a generalized dynamics featuring a design parameter ($\alpha$). This parameter acts as a stabilizer, dampening the system to ensure convergence even when communication is one-way, provided the graph is "weight-balanced."

Key Results

The theoretical findings are supported by rigorous mathematical proofs using nonsmooth analysis and LaSalle’s Invariance Principle:

  • Undirected Convergence: Theorem 4.1 establishes that for strictly concave-convex functions, the proposed dynamics leads agents to a consensus on the Nash equilibrium.
  • Instability Threshold: Lemma 5.1 provides a concrete condition ($\sqrt{3}|\text{Im}(\lambda)| \leq \text{Re}(\lambda)$) identifying when standard dynamics fail on directed graphs.
  • Directed Convergence: Theorem 5.2 provides the first distributed convergence result for zero-sum games on weight-balanced directed graphs using the new $\alpha$-parameterized dynamics.

Beyond theoretical proofs, the authors validated their approach through a numerical simulation of adversarial power allocation. In this case study, one network optimizes signal power to maximize channel capacity while an adversary selects noise power to minimize it across multiple channels.

Conclusion and Future Work

While this work provides a robust framework for distributed adversarial coordination, several avenues for future research remain. The current results for directed graphs rely on the "weight-balance" assumption, which is not always satisfied in real-world hierarchies. Additionally, the proofs require strictly concave-convex objective functions to ensure a unique equilibrium. Future extensions could explore switching topologies where network links are dynamic, as well as relaxing the strictness of the objective function requirements.

Summary updated

Abstract

This paper considers a class of strategic scenarios in which two networks of agents have opposing objectives with regards to the optimization of a common objective function. In the resulting zero-sum game, individual agents collaborate with neighbors in their respective network and have only partial knowledge of the state of the agents in the other network. For the case when the interaction topology of each network is undirected, we synthesize a distributed saddle-point strategy and establish its convergence to the Nash equilibrium for the class of strictly concave-convex and locally Lipschitz objective functions. We also show that this dynamics does not converge in general if the topologies are directed. This justifies the introduction, in the directed case, of a generalization of this distributed dynamics which we show converges to the Nash equilibrium for the class of strictly concave-convex differentiable functions with locally Lipschitz gradients. The technical approach combines tools from algebraic graph theory, nonsmooth analysis, set-valued dynamical systems, and game theory.
BibTeX
@article{gharesifard2013distributed,
  author = {Bahman Gharesifard and Jorge Cortés},
  title = {{Distributed convergence to Nash equilibria by adversarial networks}},
  journal = {Automatica},
  year = {2013},
  doi = {10.1016/j.automatica.2013.02.062},
}
Figure