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 many real-world scenarios, groups of agents must coordinate to achieve a goal while facing an adversarial group. Examples include sensor networks attempting to maximize coverage against jammers or power grids managing resources against malicious interference. These scenarios can be modeled as two-network zero-sum games.
The fundamental challenge in these games is the lack of a central controller. Each "team" is composed of individual agents who only communicate with their immediate neighbors within their own network. Furthermore, an agent in one network may only have a partial, local view of the actions taken by agents in the opposing network. This paper addresses the gap between centralized game theory and distributed network control, focusing on how the communication topology—whether undirected or directed—influences the ability of the system to reach a stable Nash equilibrium.
Methodology
The authors propose a distributed saddle-point strategy where agents evolve their estimates based on two primary components:
- Consensus Force: Agents adjust their estimates toward the average of their neighbors' estimates within the same network. This ensures that the network eventually acts as a cohesive unit.
- Gradient Force: Agents move in the direction that optimizes (maximizes for Network 1, minimizes for Network 2) their local portion of the global objective function.
Undirected vs. Directed Topologies
For undirected networks, the paper proves convergence for objective functions that are strictly concave-convex and locally Lipschitz. However, the authors demonstrate that standard saddle-point dynamics can fail to converge on directed networks (digraphs). In directed settings, the eigenvalues of the Laplacian matrix can introduce oscillations that destabilize the system.
To overcome this, a generalized dynamics is introduced, incorporating a design parameter $\alpha$. This parameter serves as a mathematical damper, tuning the consensus speed relative to the optimization speed. By choosing $\alpha$ based on the graph's connectivity (eigenvalues) and the function's smoothness (Lipschitz constant), convergence to the Nash equilibrium is guaranteed even in directed settings.
Key Insights and Results
The research yields several critical insights into distributed adversarial optimization:
- The "Directed" Danger Zone: Distributed saddle-point dynamics that work on undirected graphs can become unstable on directed graphs due to the imaginary components of the Laplacian eigenvalues.
- Stability Criteria for Digraphs: A necessary condition for convergence on directed graphs is identified: the ratio of the imaginary part to the real part of the Laplacian eigenvalues must be bounded (specifically, $\sqrt{3}|\text{Im}(\lambda)| \leq \text{Re}(\lambda)$).
- Lifting the Game: The authors demonstrate a method to "lift" local agent-level interactions into a global constrained optimization problem. This ensures that if agents reach a local agreement, it corresponds to the global Nash equilibrium.
- Numerical Validation: The approach was validated through a "Power Allocation in Communication Channels" simulation. In a scenario with 10 agents across 5 channels, the agents successfully converged to the Nash equilibrium despite having only local communication and partial views of the adversary.
Limitations and Future Work
While the proposed framework is robust, it relies on certain assumptions:
- Weight-Balance: For directed graphs, the network must be weight-balanced (incoming edge weights equal outgoing weights), a common but restrictive requirement in distributed control.
- Strict Concavity-Convexity: The current proofs require strict concavity-convexity to ensure a unique solution; relaxing this to standard concavity-convexity is a subject for future research.
- Static Topologies: The work assumes fixed communication links. Future extensions could address "switching" topologies where links are intermittent.
The paper successfully bridges the gap between distributed consensus and zero-sum game theory, providing a scalable method for adversarial coordination in networked systems.
Summary updated