Source-linked AI summary
Distributed convergence to Nash equilibria in two-network zero-sum games
Bahman Gharesifard, Jorge Cortes
TL;DR
The paper asks how two partially informed, locally communicating networks with opposing objectives can reach Nash equilibria in a zero-sum game. It constructs distributed saddle-point dynamics and analyzes them under undirected and directed topologies. The original dynamics converges for undirected networks but can fail on directed networks, while a parameterized generalization converges under stronger smoothness conditions.
Problem
The paper studies distributed Nash-equilibrium seeking when two opposing networks share an objective but agents have only local communication and partial information about the other network.
Method
The paper constructs distributed saddle-point dynamics and analyzes them using graph theory, nonsmooth analysis, set-valued dynamical systems, and game theory.
Results
The proposed dynamics converges for undirected networks with strictly concave-convex locally Lipschitz objectives; directed networks require a parameterized generalization that converges under differentiability and globally Lipschitz gradients.
Takeaways & Limitations
Distributed saddle-point coordination can reach Nash equilibria across opposing networks, but directed topologies require a generalized dynamics and appropriate parameter choices.
Abstract
from arXiv · showhide
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.
B. Gharesifard a J. Cort´es b
The paper is framed around adversarial networks, distributed algorithms, zero-sum games, saddle-point dynamics, and Nash equilibria.
- The paper concerns adversarial networks and distributed algorithms.
- Its game-theoretic focus is zero-sum games and Nash equilibria.
- Its dynamical-systems focus is saddle-point dynamics.
1 Introduction
The paper studies two opposing networks whose agents optimize a shared objective using local communication and partial cross-network information. It develops distributed convergence results for undirected and directed interaction topologies.
- Problem setting: Two agent networks have opposing objectives in a zero-sum game while agents collaborate locally and possess partial information about the other network.The objective is decomposed into concave-convex components, with information distributed across agents and networks.
- Problem setting: The paper aims to design a distributed coordination algorithm that drives agents toward a Nash equilibrium.For the considered two-player zero-sum game, a pure Nash equilibrium corresponds to a saddle point.
- Literature review: Prior work addresses distributed optimization, saddle-point dynamics, best-response dynamics, subgradient flows, and distributed Nash-equilibrium computation under varied assumptions.The cited literature spans discrete-time and continuous-time methods and undirected and directed networks.
- Contributions: For strongly connected weight-balanced topologies, the proposed parameterized dynamics converges asymptotically for strictly concave-convex differentiable objectives with globally Lipschitz gradients.The directed-case development extends earlier distributed optimization results to competing networks.
- Contributions: The analysis combines algebraic graph theory, nonsmooth and convex analysis, set-valued dynamical systems, and game theory.
2 Preliminaries
The preliminaries define the mathematical language used throughout the paper: concavity and saddle points, nonsmooth analysis, set-valued dynamics, graph structure, and zero-sum games.
- Definitions: A function is concave-convex when it is concave in its first argument and convex in its second.
- Definitions: A saddle point (x*_1, x*_2) satisfies f(x_1, x*_2) ≤ f(x*_1, x*_2) ≤ f(x*_1, x_2) for all feasible x_1 and x_2.
- Nonsmooth analysis: Locally Lipschitz functions admit generalized gradients that are nonempty, compact, convex, upper semicontinuous, and locally bounded under the stated conditions.The generalized-gradient framework supports analysis of nonsmooth objectives.
- Set-valued dynamical systems: A continuous-time set-valued dynamical system is represented as a differential inclusion, with equilibria satisfying 0 ∈ Ψ(x).Solutions are absolutely continuous curves satisfying the inclusion almost everywhere.
- Set-valued dynamical systems: The set-valued LaSalle principle establishes convergence toward the largest weakly positively invariant subset of the zero Lie-derivative set when trajectories are bounded and the Lyapunov derivative is nonpositive.
- Graph theory: A strongly connected digraph has a directed path between every pair of distinct vertices, while an undirected graph has reciprocal edges.The Laplacian is L = D_out − A; strongly connected weight-balanced graphs have a simple zero eigenvalue of L + L^T.
- Game theory: A zero-sum game has payoffs summing to zero, and a Nash equilibrium prevents any player from improving unilaterally.Under the stated compactness, convexity, continuity, and level-set assumptions, the minmax theorem guarantees a pure Nash equilibrium for the two-player game.
3 Problem statement
The paper models two partially informed agent networks as a zero-sum game and lifts the problem to network-level objectives using local information exchanges and consensus constraints. It characterizes when saddle points of the lifted formulation correspond to Nash equilibria of the original game.
- Networked zero-sum game: Two networks of agents maximize or minimize a common payoff while each agent estimates network states using information from neighbors and an engagement graph.Each network has locally available concave-convex payoff functions, while cross-network information is partial.
- Networked zero-sum game: The network states are constrained to compact convex sets, and the original game seeks a Nash equilibrium through a maxmin formulation.The first network maximizes U and the second minimizes it.
- Lifted formulation: Agent-level payoff extensions produce aggregate network objectives that coincide when all agents agree on common network states.The common lifted payoff then matches the original payoff on consensus states.
- Lifted formulation: The lifted problem is equivalent to the original game when the common aggregate payoff exists and Laplacian constraints enforce consensus within each network.Strong connectivity makes zero Laplacian disagreement equivalent to consensus-form states.
- Scope and assumptions: The extension assumption is not generally guaranteed, so whether suitable extensions always exist remains an open problem.The paper identifies one-to-one interaction topologies as a case where natural extensions satisfy the assumption.
- Saddle characterization: A saddle point of the aggregate functions yields a Nash equilibrium, and every Nash equilibrium admits auxiliary variables completing the saddle property.The saddle characterization also permits additive shifts in the auxiliary variables.
4 Distributed convergence to Nash equilibria for undirected topologies
For connected undirected networks, the paper introduces set-valued distributed saddle-point dynamics whose agent-state projections asymptotically converge to agreement on the game's Nash equilibrium under strict concave-convexity and local Lipschitzness.
- Dynamics: The proposed set-valued dynamics solves the distributed Nash-equilibrium problem when both network topologies are undirected.The construction uses gradient dynamics designed to find saddle points of the prescribed auxiliary functions.
- Dynamics: The dynamics combines saddle-point dynamics for F1 in (x1, z1) and F2 in (x2, z2), with local solutions guaranteed by the stated existence lemmas.The variables xℓ and zℓ belong to R^(nℓdℓ), for ℓ∈{1,2}.
- Convergence result: Under connected undirected graphs, compact convex action sets, and a strictly concave-convex locally Lipschitz objective, the projected first and third components asymptotically converge to agreement on the Nash equilibrium.The invariant-set argument identifies the limiting states with the equilibrium set of the distributed dynamics.
- Equilibrium: Strict concavity-convexity makes the solution unique, with equilibrium states replicated across agents in each network.The proof denotes these replicated states by x∗_1 = 1_n1⊗x∗_1 and x∗_2 = 1_n2⊗x∗_2, and establishes corresponding auxiliary variables z∗_1 and z∗_2.
- Convergence proof: Trajectories are bounded, and the set-valued LaSalle invariance principle reduces their limits to the largest positively invariant subset of the zero-derivative set.The proof constructs a smooth Lyapunov function V and analyzes its set-valued Lie derivative along the dynamics.
5 Distributed convergence to Nash equilibria for directed topologies
For strongly connected, weight-balanced directed networks, the original distributed saddle-point dynamics may fail to converge. Introducing a design parameter yields convergence to the Nash equilibrium under differentiability and globally Lipschitz gradient assumptions.
- The original saddle-point dynamics can fail to converge when applied to directed networks, including strongly connected weight-balanced digraphs.
- Strictly concave-convex examples with no payoff contribution to the linearization show that failing the necessary stability condition prevents convergence.
- The generalized directed-network dynamics introduces a parameter α to address the instability identified for the original dynamics.
- For an appropriate parameter choice, the generalized dynamics converges asymptotically to agreement on the Nash equilibrium.
- The directed-network theorem assumes strongly connected weight-balanced digraphs, compact convex strategy sets, and strictly concave-convex differentiable payoffs with globally Lipschitz gradients.
- The proof establishes a Lyapunov inequality using eigenvalue bounds, selects β below a threshold where h(β)<0, and applies LaSalle's invariance principle.
6 Conclusions and future work
The paper develops distributed saddle-point dynamics for two-network zero-sum games, proving convergence for undirected networks and a parameterized extension for directed networks. It identifies assumptions for the directed result and several directions for relaxing them.
- The paper models two networks with opposing objectives that collaborate internally while having partial information about the other network.
- For undirected networks, the proposed locally implementable saddle-point dynamics converges to Nash equilibria for strictly concave-convex locally Lipschitz objectives.
- For directed networks, the original dynamics can fail even on strongly connected weight-balanced graphs, motivating a parameterized generalization.
- With appropriate parameter choices, the generalized directed dynamics converges for strictly concave-convex differentiable objectives with globally Lipschitz gradients.
- Future work includes relaxing strict concavity-convexity, differentiability, and global gradient-Lipschitz assumptions, and extending the results beyond static zero-sum settings.
A Appendix
The appendix establishes an inequality for concave-convex differentiable functions with globally Lipschitz gradients. It derives the result by applying a concave-function inequality to an auxiliary function and combining the two coordinate-wise bounds.
- The appendix considers a concave-convex differentiable function with globally Lipschitz gradient and Lipschitz constant K.
- It invokes a known inequality for concave functions with globally Lipschitz gradients as the starting point.
- For a fixed comparison point, the proof defines an auxiliary function by subtracting the value and first-order terms of the original function.
- The auxiliary function has zero partial gradients at the comparison point, allowing the concave and convex coordinate restrictions to be treated separately.
- Adding the resulting inequality to its version with the two points interchanged yields the claimed conclusion.