pith. sign in

arxiv: 1907.07144 · v1 · pith:6IV3NX4Qnew · submitted 2019-07-15 · 🧮 math.OC

Geometric Convergence of Distributed Gradient Play in Games with Unconstrained Action Sets

Tatiana Tatarenko , Angelia Nedich This is my paper

Pith reviewed 2026-05-24 21:22 UTC · model grok-4.3

classification 🧮 math.OC
keywords distributed gradient playNash equilibriumgeometric convergencestrongly monotone mappingunconstrained action setsdistributed algorithmcommunication graph
0
0 comments X

The pith

A distributed gradient play algorithm converges geometrically to Nash equilibrium in strongly monotone games using only one step size.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a distributed algorithm for players to learn a Nash equilibrium in non-cooperative games where each has a smooth local cost and the overall mapping is strongly monotone, with actions unconstrained. Players communicate over an undirected connected graph to run a standard gradient play update. The authors prove that this procedure achieves geometric convergence to the equilibrium when the single step size is chosen properly. This simplifies prior approaches that needed two parameters and an augmented mapping, and the rate is shown to be better than that of the GRANE algorithm.

Core claim

We provide a distributed algorithm to learn a Nash equilibrium in a class of non-cooperative games with strongly monotone mappings and unconstrained action sets. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. We consider a distributed communication-based gradient algorithm. For this procedure, we prove geometric convergence to a Nash equilibrium. In contrast to our previous works, the procedure in this work corresponds to a standard distributed gradient play and, thus, only one constant step size parameter needs to be chosen appropriately to guarantee fast convergence to a game solution. Moreover, we provide a rigir

What carries the argument

Standard distributed gradient play updates, where each player computes its local gradient and exchanges information with neighbors, with strong monotonicity of the game mapping supplying the contraction needed for geometric rate.

If this is right

  • Geometric convergence holds with a single appropriately chosen constant step size.
  • The convergence rate exceeds that of the GRANE algorithm under the same conditions.
  • Implementation requires no augmented mapping and only local gradient evaluations plus neighbor communication.
  • The result applies directly to any game whose pseudogradient is strongly monotone with unconstrained action sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Relaxing strong monotonicity to plain monotonicity would likely replace geometric convergence with slower sublinear rates.
  • The same single-parameter update might be tested on time-varying graphs to see whether connectivity persistence alone preserves the geometric bound.
  • The comparison framework could be reused to benchmark other distributed methods against this baseline on concrete game examples such as network Cournot competition.

Load-bearing premise

The game mapping is strongly monotone and the communication graph is undirected and connected.

What would settle it

A numerical run on a strongly monotone game instance showing that the distance to equilibrium fails to decrease at a constant geometric factor for any fixed step size.

Figures

Figures reproduced from arXiv: 1907.07144 by Angelia Nedich, Tatiana Tatarenko.

Figure 1
Figure 1. Figure 1: Comparison of the presented algorithm and GRANE base [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
read the original abstract

We provide a distributed algorithm to learn a Nash equilibrium in a class of non-cooperative games with strongly monotone mappings and unconstrained action sets. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. We consider a distributed communication-based gradient algorithm. For this procedure, we prove geometric convergence to a Nash equilibrium. In contrast to our previous works [15], [16], where the proposed algorithms required two parameters to be set up and the analysis was based on a so called augmented game mapping, the procedure in this work corresponds to a standard distributed gradient play and, thus, only one constant step size parameter needs to be chosen appropriately to guarantee fast convergence to a game solution. Moreover, we provide a rigorous comparison between the convergence rate of the proposed distributed gradient play and the rate of the GRANE algorithm presented in [15]. It allows us to demonstrate that the distributed gradient play outperforms the GRANE in terms of convergence speed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a distributed gradient-play algorithm for non-cooperative games whose game mapping is strongly monotone, with unconstrained action sets. Each player updates its action via its local gradient and exchanges information with neighbors on an undirected connected graph. The central claim is a proof of geometric convergence to the unique Nash equilibrium under a single constant step-size parameter; the authors also derive an explicit rate comparison showing that this standard gradient play converges faster than the two-parameter GRANE algorithm of their prior work [15].

Significance. If the contraction argument holds, the result is significant because it removes the need for an augmented mapping and a second tunable parameter while retaining geometric convergence, and supplies a direct, quantitative rate comparison to the authors' earlier GRANE method. The single-parameter simplicity is a practical advantage for distributed implementation, and the explicit comparison supplies a concrete benchmark for choosing between the two approaches under strong monotonicity.

major comments (2)
  1. [§3] §3 (main convergence theorem): the contraction factor for the standard gradient play is stated to be strictly smaller than that of GRANE for the same step-size range, but the derivation of the comparison inequality is not shown to be independent of the choice of the GRANE augmentation parameter; this comparison is load-bearing for the claim that gradient play 'outperforms' GRANE.
  2. [§2.2] §2.2 (step-size selection): the admissible interval for the single step size α is given in terms of the strong-monotonicity constant μ and the Lipschitz constant L, yet the manuscript does not verify that this interval is non-empty for every connected undirected graph; the graph-dependent bound on the largest eigenvalue of the Laplacian appears only implicitly and should be stated explicitly to confirm the interval is always feasible.
minor comments (2)
  1. [§2] Notation for the game mapping F and the stacked gradient vector is introduced in §2 but used interchangeably with the local gradients; a single consistent symbol would improve readability.
  2. [comparison table] The comparison table (or figure) that tabulates the two contraction factors is referenced in the abstract but its caption does not list the precise values of μ and L used for the numerical illustration.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (main convergence theorem): the contraction factor for the standard gradient play is stated to be strictly smaller than that of GRANE for the same step-size range, but the derivation of the comparison inequality is not shown to be independent of the choice of the GRANE augmentation parameter; this comparison is load-bearing for the claim that gradient play 'outperforms' GRANE.

    Authors: The comparison inequality is obtained by taking the supremum of the GRANE contraction factor over its admissible augmentation-parameter range, which renders the resulting bound independent of any particular choice. To make this explicit, we will insert a short additional step in the proof of the rate comparison in the revised manuscript. revision: yes

  2. Referee: [§2.2] §2.2 (step-size selection): the admissible interval for the single step size α is given in terms of the strong-monotonicity constant μ and the Lipschitz constant L, yet the manuscript does not verify that this interval is non-empty for every connected undirected graph; the graph-dependent bound on the largest eigenvalue of the Laplacian appears only implicitly and should be stated explicitly to confirm the interval is always feasible.

    Authors: We agree that an explicit statement is desirable. Because the graph is finite, connected, and undirected, the Laplacian possesses a finite largest eigenvalue λ_max; the admissible interval for α is then (0, 2μ/(L² + λ_max·c)) for a positive constant c depending only on μ and L. This interval is always nonempty. We will add the explicit dependence on λ_max in §2.2 of the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity; central proof is self-contained

full rationale

The paper states a direct proof of geometric convergence for standard distributed gradient play (one constant step-size) to Nash equilibrium under the explicit assumptions of strong monotonicity of the game mapping and connectedness of the undirected communication graph. This contraction argument is derived from those hypotheses via standard analysis and does not reduce to any fitted quantity, self-definition, or prior result. The rate comparison to the authors' earlier GRANE algorithm in [15] is an additional empirical-style contrast, not a load-bearing justification for the main theorem. No self-citation chain, ansatz smuggling, or renaming of known results is present in the derivation chain.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The result depends on standard assumptions in distributed optimization plus the authors' prior analysis framework; no new entities are introduced.

free parameters (1)
  • step size alpha
    Must be chosen sufficiently small depending on the strong monotonicity constant and graph properties; no explicit formula or fitting procedure is given in the abstract.
axioms (2)
  • domain assumption The game mapping is strongly monotone
    Invoked as the key condition that enables the contraction mapping argument for geometric convergence of the distributed updates.
  • domain assumption Communication graph is undirected and connected
    Required for information propagation in the distributed gradient play; standard in the literature but not restated in the abstract.

pith-pipeline@v0.9.0 · 5695 in / 1474 out tokens · 26037 ms · 2026-05-24T21:22:33.417876+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    Alpcan and T

    T. Alpcan and T. Bas ¸ar. Distributed Algorithms for Nash Equilibria of Flow Control Games. In Advances in Dynamic Games , pages 473–

    work page

  2. [2]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson. Matrix Analysis . Cambridge University Press, New Y ork, NY , USA, 2nd edition, 2012

    work page 2012

  3. [3]

    Koshal, A

    J. Koshal, A. Nedi´ c, and U. Shanbhag. A Gossip Algorithm for Aggregative Games on Graphs. In Decision and Control (CDC), 2012 IEEE 51st Annual Conference on , pages 4840–4845. IEEE, 2012

    work page 2012

  4. [4]

    Nesterov and L

    Y u. Nesterov and L. Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete and Continuous Dynamical Systems - A , 31(4):1383–1396

    work page

  5. [5]

    Olshevsky and J

    A. Olshevsky and J. Tsitsiklis. Convergence speed in dis tributed consensus and averaging. SIAM Journal on Control and Optimization , 48(1):33–55, 2009

    work page 2009

  6. [6]

    Paccagnan, M

    D. Paccagnan, M. Kamgarpour, and J. Lygeros. On aggregat ive and mean field games with applications to electricity markets. I n 2016 European Control Conference (ECC) , pages 196–201, June 2016

    work page 2016

  7. [7]

    Qu and N

    G. Qu and N. Li. Accelerated distributed nesterov gradie nt descent. CoRR, (https://arxiv.org/abs/1705.07176), 2018

    work page arXiv 2018

  8. [8]

    J. B. Rosen. Existence and uniqueness of equilibrium poi nts for concave n-person games. Econometrica, 33(3):520–534, 1965

    work page 1965

  9. [9]

    W. Saad, H. Zhu, H. V . Poor, and T. Bas ¸ar. Game-theoretic methods for the smart grid: An overview of microgrid systems, demand -side management, and smart grid communications. IEEE Signal Processing Magazine, 29(5):86–105, 2012

    work page 2012

  10. [10]

    Salehisadaghiani and L

    F. Salehisadaghiani and L. Pavel. Distributed Nash equ ilibrium seeking: A gossip-based algorithm. Automatica, 72:209–216, 2016

    work page 2016

  11. [11]

    Salehisadaghiani, W

    F. Salehisadaghiani, W. Shi, and L. Pavel. An admm appro ach to the problem of distributed nash equilibrium seeking. CoRR, 2017

    work page 2017

  12. [12]

    Scutari, S

    G. Scutari, S. Barbarossa, and D. P . Palomar. Potential games: A framework for vector power control problems with coupled co nstraints. In 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, volume 4, pages 241–244, May 2006

    work page 2006

  13. [13]

    W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An Exact First-O rder Algorithm for Decentralized Consensus Optimization. SIAM Journal on Optimization , 25(2):944–966, 2015

    work page 2015

  14. [14]

    Tatarenko

    T. Tatarenko. Stochastic learning in multi-agent opti mization: Commu- nication and payoff-based approaches. Automatica, 99:1 – 12, 2019

    work page 2019

  15. [15]

    Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking

    T. Tatarenko, W. Shi, and A. Nedi´ c. Geometric convergence of gradient play algorithms for distributed nash equilibrium seeking. CoRR, (https://arxiv.org/abs/1809.07383), 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  16. [16]

    Tatarenko, W

    T. Tatarenko, W. Shi, and A. Nedi´ c. Geometric convergence of gradient play algorithms for distributed nash equilibrium seeking. In 2018 IEEE 57th Annual Conference on Decision and Control (CDC) . IEEE, accepted. Appendix Here we demonstrate that n n+µα + √ n− 1 n+µα 2α3 µ 1+σ2 1− σ2 L4 < 1 (see ( 24)) if 0 < α < √ n2+ 2µ4 (1−σ2 ) (n−1)L4 (1+σ2 ) − n 2µ ...

    work page 2018